A* Pathfinding Project

GridGraph bad, NavMesh top for RTS


#1

I’m very disapointed with your GridGraph due to the very slow grid update. It seems to be the update time equals to the re-scan time. With 2 grid-graphs 1000x1000x2 I had to wait about 30s to update the nodes around an object dynamically. There must be something terrible wrong with grid-update, that should be the advantage of the grid graph, but it isn’t.

Changed the graph to tile based navmesh. It is a kind of grid-graph with navmesh inside grid. Awesome solution, looks very well optimized. The graph update for dynamically moving units is very fast (Grid should be faster, but it isn’t, strange!). Unfortunately I have to replace my old GridGraphs to NavMesh graphs. Not sure what new issues that will cause, maybe it is just a better graph for RTS.


#2

Hi

For such large grid graphs there can actually be an adverse effect caused by the system trying to determine ahead of time which areas of the graph are reachable from other areas.
If a path request would be started such that the end node could not actually be reached from the start node, if the system didn’t know anything else it would have to search through every single node that could possibly be reached from the start node before it could conclude that the end node could not be reached. This would of course be pretty slow, especially if this happened often in the game. So instead this information is precalculated every time the graph is updated (this is called the flood fill internally). However if you have a very large graph this can actually backfire because the time it takes to keep this data up to date is greater than what is saved by avoiding the earlier mentioned performance cliff when the end node could not be reached.
I have been thinking of making this calculation lazy instead so that it is only actually calculated when a path had to search through the whole graph. However I have not yet figured out a good way to do it.
Navmesh graphs have the benefit that they usually have much fewer nodes, so keeping the reachability metadata up to date does not take as much effort.

If you want you can try to disable the flood fill by inserting a return at the start of the GraphUpdateProcessor.FloodFill method (there are several overloads of that method, insert the return at the start of the method that takes no parameters).

This will however cause some parts of the api (most notably the GraphUpdateUtilities.UpdateGraphsNoBlock and PathUtilities.IsPathPossible methods) to stop working.

30 seconds sounds very long though. As a 1000x1000 graph has 1 million nodes (which is a lot) I would expect about 1 or 2 seconds to update them, 30 seconds sounds like a lot unless you are running on a mobile device or something similar (however admittedly I have not tried this recently, it’s just what I would expect). Also keep in mind that in the unity editor the graph visualization used in the scene view needs to be recalculated if you update the graph. This can often take a lot more time than the update of the graph itself. So make sure that you profile when graphs are hidden (uncheck the ‘Show Graphs’ checkbox in the A* inspector).


#3

Hi thank you for your answer,

the NavMesh graph has more advanages. Like, the margin around the collider have a much more better layout (around the unit). So Units are not colliding in the corner of other units. I can optimize now the margin, don’t have to make it to large. It solves a lot of trouble around pathfinding, like hanging in the wall beside the door. Also the pathfinding time is much more faster (0 ms :slight_smile: ). I need 4 NaveMesh graphs for different sized units and it looks like that won’t be a problem.

I will not try to speed up the GridGraph, because I see much more advantages in NavMesh graph. I’m using a xeon E3 1231, kind of I7 47XX, not mobile! And yes, I had for one of the 1000x1000 graphs the grid visible.

However, Recast-Graph is awesome. Nice thing is, that I don’t have to change much to replace the graph. I have just to recreate the graph.