Question about pathfinding in large open worlds (50 km²+)

  • A* version: [5.4.6]
  • Unity version: [6.4]

Question about pathfinding in large open worlds (50 km²+)

Does anyone have experience using the A* Pathfinding Project in large open-world games, especially worlds around 50 km² or larger?

So far, I’ve had good results using around 50 pre-scanned static layered grid graphs for specific areas such as cities and larger POIs. These graphs are not modified at runtime, and performance has been fine so far.

My question is how best to handle AI navigation in the open areas between these locations, where up to 30 randomly spawned AI characters might be active at the same time.

I’m considering two approaches:

Option 1: Small dynamic grid per AI
Each AI gets its own small dynamic grid, for example, 10×10 nodes, created around the AI.

Option 2: One larger dynamic grid per active player
A larger dynamic grid, for example, 200×200 nodes, follows each player. Random AI can spawn within that area.

The game also supports multiplayer with up to 30 players. Players could be spread across different parts of the world, so with Option 1, we could end up with many small dynamic graphs, while Option 2 would require one larger graph for each active player or area.

Which approach would generally be more efficient in terms of performance?

You’ll likely have to implement both and profile them. “Fail fast” and all. There are too many variables to tweak that can affect this. Either option 1 or 2 work well.

For what it’s worth in my game I plan on doing a mix of both. Each enemy spawn gets its own small graph, but only if they’re within a specific distance of the player. No reason to simulate an enemy 30,000km away, right?

Hi

I have definitely seen people use this package on 10x10km worlds (100km2).

I think the best option is typically a single large recast graph.

Grid graphs tend to use too much memory to be useful. But if you only have a few agents, or your agents are only active when near the player, it might work.

I would not recommend having 30 separate grid graphs active at all times. I think it’s likely to be too slow.