Suggested graph for game capabilities

In my 3D game I have

  1. A relatively large map, 1000x1000 meters
  2. Cities with multiple walkable levels. For example, you can open a door to walk inside a building, and up stairs to the roof of the building
  3. Pathfinding objects that move. A wall may fall over, blocking a path. The wall is later destroyed, making that path available.
  4. Multiple types of units with different sizes
  5. Randomly generated terrain (meaning I generate the graph at runtime)
  6. Large armies of units (100 vs. 100)

I would like to verify that Layered Grid Graph with Dynamic Grid Obstacle is still the best option given how large my map is.

Hi

If you have such a large map and you need precision enough to represent an open/closed door, then a layered grid graph will not work I think. You would need to use a graph larger than 1000x1000 and that really uses a lot of memory and will probably not give you very good performance. I would recommend a recast graph. It will increase load times a bit, but it should at least be able to represent everything well.
I also have some updates in the pipeline which may improve the scanning times of recast graphs with up to 30%.

Can you clarify the cost/benefit of NavmeshCut vs. Dynamic Grid Obstacle? The big reason I went with Layered Grid Graph is it’s fast for objects that move. For example, if a tower falls over which is the primary use case. From my understanding I would have to switch in order to use Recast graph.

This depends a lot on how complex and large the graph is. The cost of an update to a layered grid graph is roughly proportional to a large factor times the number of nodes the update overlaps plus a much smaller factor times the number of nodes in the graph. The time it takes to update a graph with a navmesh cut is roughly proportional to the number of nodes in the tiles that the navmesh cut touches plus a much smaller factor times the number of nodes in the whole graph.

There are cases where a layered grid graph will be faster and cases where a recast graph with navmesh cuts will be faster. It’s hard to say what it will be in your specific case without testing it. In your case with a 1000x1000 layered grid graph, I would expect navmesh cutting to be faster though.

Generally recast graphs are nice because they can represent a much more detailed world with a much lower memory footprint and pathfinding on them is usually faster (because they have fewer nodes). However recast graphs do take longer to scan (sometimes significantly so).