Best graph on big, dynamic, multiplayer open world?


I’ve been wondering what would be the best graph for our needs. Here are some hard-facts about our project and some answers that i could find by browsing through the forum:

The terrain is going to be quite big (about 5x5km) - Recast Graph (because its fast). Problem: not as detailed/dynamic.
The terrain is procedurally generated - Moving Layered grid graph, like in the example.
The terrain is going to be dynamic (the players can build houses, and the AI will need to be able to navigate through it) - Again, Layered Grid Graph with repositioning (because its dynamic).
Our game is multiplayer (authorotative) - Most of the time, the server will have to do the pathing-work for the AI, but in some occasions the player will need to be able to do pathfinding himself - therefore the graph should be easily syncable over the network.

At first the recast graph sounds great, but then again, we will need to rebuild a whole tile on the server and sync the result to the clients every time a player places some house-parts.
On the other hand, the moving layered grid graph looks like what we need, but then again, the server would have to calculate several of those at the same time (sometimes on top of each other).

At the moment, this seems to me like a pathfinding nightmare, but it must be possible somehow. Any tipps or recommendations would be highly appreciared!
The AI wont need pathfinding when its out of the player’s sight, but when the player encounters an NPC, both - the server and the player need the same, high quality pathfinding of the area they’re interacting.

cheers and thanks for your time!


Well… Yeah, that is a nightmare.
If it is that large then a recast graph is really the only viable way.
Is is possible for you to use navmesh cutting for the buildings instead of recalculating whole tiles? (see
At least with server side pathfinding, occasional lag due to recalculating things is not a big deal.

Recast graphs can definitely be detailed, you just have to reduce the cell size. They will of course take longer to scan however.

If you have very few players (less than 10) then having several moving layered grid graphs might be a viable solution. Any more than a few and your performance will go down drastically.