Dynamic Grid Obstacle is Updating Graphs Outside Bounds

Beginner Questions
1

Hi,

I have about 9 grid maps in my scene and my dynamic obstacle is only inside one of them. None of the grid maps overlap. Nevertheless, all the maps are being updated whenever the dynamic obstacle moves. This is breaking my performance. I was expecting only the one graph containing the obstacle to be updated. Am I missing something or is this how it’s suppose to be?

Thank you,
Celso

2

Hi

The other graphs are likely not being updates as in that they change the node data. However after a graph update is done a flood fill needs to be done to keep pathfinding working, this currently takes linear time with respect to the number of nodes in all graphs (I have an idea for how to optimize this A LOT in the common cases however, hopefully I will get to implementing that soon). Right now there is not much that can be done without changing some of the code in the internals of the system, but I can show you how to do that if you want.

3

Hi Aron,

Thank you for the reply. Yes, I’d be interested in hearing more about optimizing graph updates. As is, the performance quickly becomes untenable whenever there is a single dynamic obstacle.

4

First off is. Can you guarantee that the obstacle will never separate two areas so that there is no valid path between the two areas. If yes, then a nice performance optimization can be applied.

5

Yes, in my case I have a large open space with several grid maps on it. The dynamic obstacle is much smaller than each graph, so there should always be an alternative path.

Also, what would happen if we just turn off the flood fill?

6

Turning off the flood fill would do nothing in most cases, but in the rare case where you request a path where it is not possible to walk from one part of the navmesh to the other the pathfinding system would have to search a every possible node it can reach before being able to say that no valid path could be found.

7

You mention navmeshes in your reply, but what if I only use gridgraphs?

I turned off flood fill and the performance went up as expected. I still haven’t found a case where pathfinding stops working.

Thank you!

8

Right, it is the same for grid graphs.

Pathfinding will never stop working, but some path requests might take a long time to complete.