A* Pathfinding Project

Is it possible to improve scanning time of grid graphs?


#1

I have a 1k by 1k graph that takes about 30 seconds to scan. This process is only done once in a loading screen, but I’d like to reduce that to under 5 seconds.

I was thinking to just simply create the graph and initialize every node to be set to walkable without doing any checks as I already have the infrastructure in place that whenever a new object is instantiated, the pathing graph around it is updated. So I tried scanning with ‘Collision testing’ off and seemed to improve the time by a bit, but the the biggest time consumer is ‘height testing’ and the ‘calculating connections’ step. However if that’s disabled, then the graph will just be a flat mess.

Doing it the async way only makes the process even longer, which is not an option. I’m still on 4.2.2.


#2

Hi

Are you using a grid graph?
If so, do check out the 4.3.x beta (https://www.arongranberg.com/astar/download). It uses burst which should make the scanning time a lot faster. And if you can use the ‘Ray’ collision detection mode (Grid Graph Settings -> Collision Testing) then it will be even faster. This may not be possible in your world though.


#3

Hi, yes I’m using a grid graph.

I did check out the beta, I’ve tried it out already and made a little prototype in ECS and it worked fine for the most part. But this project I’m on is relatively old and large. It’s still using Unity 2018.1 and from what my experiences in the ECS world, you need to be up to date with the editor, lest you run into all kinds of issues. Upgrading the editor is also out of the question. Already tried and just broke so many things it would take forever to fix everything.

I’m assuming your 4.3 beta would require the latest Burst package? Burst is up to 1.1.2 now, while 2018.1 only works with 0.2.4 preview. I’d rather not put that into a final production.


#4

Okay.

In that case I’d suggest using as little erosion as possible. I’d suggest a value of 0 or 1.
I’d also suggest checking if you have any GraphUpdateScene components in your game, and make them cover as little ground as possible.
Lastly, can you cache the graph or does it have to be scanned during the loading screen. See https://arongranberg.com/astar/docs/saveloadgraphs.html for more info.
Other than that there are not really any good tips I have for optimizing grid graphs. They kinda have the speed they have and all the optimization effort after your current version has gone into the burst translation.


#5

Sadly, starting position of the graph is always different so no caching possible either. Thanks for the tips though, it looks like I’ll just have to deal with it. That or slightly modify the game design.