What type of graph should be used for a semi-procedural world?

I have a procedurally generated world (sort of), it is made of 9 400x400 terrain chunks arranged in a 3x3 grid formation for a total of 1200x1200 as the map size.

Around every 15 minutes (so the map doesn’t update that frequently) one or more of the terrain chunks gets all prefabs wiped off and is repopulated with new ones at runtime, terrain chunks on the opposite end of the map are also unloaded if the player is on the other side.

Many AI agents spawn in the terrain chunks either at start or the 15min cycle but they player doesn’t pathfind.

So here is a list of what I need in a graph:

  1. Can cover a 1200x1200 area with low performance impact.

  2. Can detect if new terrain/prefabs are created and adjust accordingly at runtime (preferably through a script or manually)

  3. Many AI can pathfind at once.

  4. Multiple layers for things like bridges and walkways.

What I have tried: (I have only scratched the surface but wanted some input before committing to a graph)

  1. I looked at the Procedural graph example but I can’t have every AI moving their own graph.

  2. I looked at recast graphs but the seeker could not seem to path around walls of instantiated objects very well but did If the prefab was spawned in editor and I scanned the scene first.

  3. I looked into grid graphs but they were a bit lagy even on just one 400x400 terrain chunk.

What do others recommend for something like this?

That is a very long list of requirements…

So (4) essentially implies using a recast or layered grid graph.

(1) makes using a layered grid graph a bit suboptimal because of the memory requirements of large grids. So that leaves recast graphs.

3). Just so you know, make sure that Show Graphs is disabled when you test the performance of graphs. Drawing gizmos for large graphs is pretty expensive.

2). Recast graphs can be updated during runtime, either using full tile updates (which can happen asynchronously, but they are still pretty slow) or using navmesh cutting (which is faster). You can read more about it here: http://arongranberg.com/astar/docs/graph-updates.php

Since the world is procedurally generated, you can unfortunately not precalculate chunks of the world.
So you would have to use full tile updates. Well… that can work, but your world is pretty big and recalculating it is going to take some time. On the plus side I have recently optimized recast scanning for large worlds which can lead to improvements as large as 20x faster scanning. It might still be too slow though.

Well the whole 1200x1200 graph is only calculated once when the level is first loaded so I can just have a loading screen or something similar. Navmesh cutting wont work for my purposes. Is there a way I can update just a part of a recast graph or use multiple recast graphs for the areas that regenerate every 15 minutes, also if I have multiple recast graphs will AI transition into a new graph well if they walk from one into another?


You would use a tiled recast graph. You can recalculate individual tiles separately.
Take a look at the documentation page I linked above.