Large worlds
How to deal with pathfinding in large worlds.
Contents
Introduction
Large worlds can strain pathfinding, especially if you make the wrong choice of how to set it up. In this tutorial, you will learn about the most common trade-offs when it comes to large worlds, and what solutions there are for dealing with them.
Constraints
It is important to first take a look at what requirements your game has that any solution will have to fulfill. Different solutions suit different games. Take a look at this list of constraints and ask yourself what applies to your game:
Is there more than 1 character?
Are there many agents spread out over the whole world that need pathfinding simultaneously?
Is all pathfinding centered around a single point/character?
Do you need to update the graph while the game is running?
Is the whole world known at build time, or is it procedurally generated?
Does the game need penalties and/or tags?
Graph type
When it comes to large worlds, the primary choice is between a GridGraph or a RecastGraph. Recast graphs are in general better for large worlds, since they typically require many fewer nodes to represent a world with good precision. Grid graphs can scale up to decently sized worlds, but large grid graphs have a large memory and performance overhead since you end up with so many nodes. A grid graph of 500x500 nodes is already large, and I do not recommend trying to go over 1000x1000 nodes since the memory usage becomes prohibitively large. If, however, you don't need pathfinding in the whole world at the same time (e.g. when everything is centered on a single player character) then you can still use a grid or recast graph which moves around the world as the player moves.
Solutions
Here follows a few common setups, together with their pros and cons.
A single recast graph
A single large recast graph can be an excellent choice out of the box. A recast graph can represent both large empty regions and small details very well. You will want to make sure tiling is enabled in the recast graph settings since this will make generating and updating the large graph much faster.
Pros:
It's simple to set up.
It represents both small and large details well.
It has comparatively low memory usage.
Pathfinding on it is fast due to the low node count.
The whole map exists in memory at the same time, so many characters can traverse different parts of the world simultaneously.
Navmesh cutting can be used for pretty fast graph updates.
Cons:
Full graph updates are slower than grid graphs (navmesh cutting is faster).
Recast graphs are bad at representing tags and penalties.
Large undulating empty regions, like a hill without any trees or obstacles, can be hard for the recast graph to represent well. Though, enabling tiling can help break up the large nodes.
Scanning a very large recast graph can take a lot of time. This means it's often not ideal for procedural worlds unless you can generate them piece by piece over time.
A single large grid graph
A single large grid graph can work really well if you stay below the limits where a grid graph doesn't scale well. A grid graph scales decently up to 500x500 nodes, and you can go up to 1000x1000 nodes if you really need to. Larger than that is not recommended.
Pros:
It's simple to set up.
Grid graphs work well with penalties and tags.
Graph updates are fast.
Scanning the graph is comparatively fast (scanning a 1000x1000 graph can still take a bit of time).
The whole map exists in memory at the same time, so many characters can traverse different parts of the world simultaneously.
Cons:
Memory usage is higher than a recast graph.
Pathfinding over long distances can be much slower than on a recast graph.
It doesn't scale to very large worlds.
You can find an example of a grid graph in the example scene called "Example2".
A small moving graph
If your pathfinding is centered around a single point or character (e.g. the player) then you may be able to use a moving grid or recast graph.
A moving grid/recast graph is one that utilizes the ProceduralGraphMover script. The idea is that you have a smallish grid graph (e.g. 100x100) or recast graph that is always centered on a character. As the character moves around, the ProceduralGraphMover will move the graph and scan the new parts that come into view, and discard the old parts.
You can even extend this to several small graphs if you need to. Each small graph is centered on a different point or character. However, past 2-4 such graphs, the overhead of moving and updating all the graphs can become sizable.
Recast graphs can also be used. In that case, the ProceduralGraphMover will work with a tile granularity.
Pros:
You can use a grid graph, which works well with penalties and tags, or a recast graph, which can capture small details well.
Graph updates are fast, as long as the graph is kept reasonably small.
Scanning the graph is comparatively fast.
You can easily support a very large, or even an infinitely large world with this setup.
Memory usage is low.
Cons:
Pathfinding can only happen in the vicinity of a given character/point.
Long distance pathfinding is not possible, which can make it hard to find paths around large obstacles like mountain chains.
There is a constant overhead when the character/point moves, since the graph has to be updated regularly.
Slightly more complicated to set up.
Conclusion
In this tutorial, we have gone through what to think of when you want pathfinding in a large world, and some example setups that you can use in your own game. For more information on different graph types, take a look at Graph Types.