Support for distinct but overlapping pathfinding?

For example: Villagers who can travel along land and into shallow water, and boats who can travel on water both shallow and deep. They’re completely distinct with no shared geometry to travel on, but the pathfinding overlaps x/y coords; villagers in shallow water will stay stuck to the land while boats will stay stuck to the water level.


There are two options you can use:

  1. Use multiple graphs. Take a look at this tutorial: This is the easiest and most robust solution, but it has a bit higher memory overhead. I wouldn’t worry too much about it unless you have a very big world though. If you are using a recast graph the memory overhead will be smaller.
  2. Use tags. Take a look at this tutorial: This has a lower memory overhead, but it requires a bit more work to set up. It may also be problematic for performance if you have multiple lakes which are disconnected from each other. There would be a path from lake to ground to lake in the graph so if one of the boats try to find a path to the other lake it wouldn’t immediately know it was impossible to get there. This means it has to search all the nodes in the lake before it figures out there is no possible path to the other lake. If you on the other hand use multiple graphs there is a pre-processing step which allows the system to figure out that the two lakes are completely disconnected and the path will just fail immediately instead of spending cpu power to find a path to the other lake. This pitfall can be avoided by ensuring you don’t request paths to disconnected regions of the map. For example if your game just has one single ocean and one single island then this is not a problem.