Ideas for optimizing 3D astar grid generation and pathfinding?

Unity Engine
1

I recently did 3d astar pathfinding based off this astar pathfinding series. I actually got it to work, but I only made it 5 videos in before I got too confused and wasn’t able to implement anymore of the material into 3D, so I never got to making it multithreaded. It’s kind of slow…

  • 10 x 10 x 10: ~1ms Grid, ~1ms Path
  • 20 x 20 x 20: ~11ms Grid, ~8ms Path
  • 50 x 50 x 50: ~131ms Grid, ~40ms Path
  • 100 x 100 x 100: ~1300ms Grid, ~130ms Path

What can I do to speed things up?

2

repo: https://github.com/JazzRhodes/Exploring_3D_Pathfinding_In_Unity

3

if its a 3d system, why not use Unitys built in navmesh?

But anyway, how is your AStar made, are you using anything like a binary heap for your open set and a hashset for your closed set to speed things up. Are you trying to optimize yours nodes first, by representing it with a mesh instead, or using something like a quadtree or octree?

also other note 3d stuff gets big fast, 100x100x100 is already a million nodes

4

Because Navmesh isn’t a 3D pathfinding system?

2 Likes
5

As mentioned, navmesh won’t work in my 3D setting.
The tutorial I followed did throw things into a heap class and the lists were changed to hashsets and this did speed things up by quite a bit.
I’m using a regular grid. I’m looking into octrees now. I even got a udemy course to try and understand it, since it was the only one I saw that used one with pathfinding. Hopefully I can implement it - but after making it halfway in, my hopes aren’t very high if I’m being honest. The making of the grid is confusing. I havent gotten far enough to understand how to do astar over something that isn’t a grid, but I’ve been slightly concerned about it.

6

so noticed in your code, you are using a coroutine and yielding null, this is going to add a lot of time, since its a whole frame of time each time you yield. Might want to either use the job system or do the work in your own thread. Or even just see if without the yielding frames it happens fast enough to just run normally. Keep in mind doing it on the job system or a thread will not make it faster, it will just mean its not longer blocking other things or getting slowed down by yielding frames just so you can maintain framerate

1 Like