Agent-Specific Pathfinding

Sometimes you need to customize pathfinding on an agent-by-agent basis.

For example you may want to make some agents avoid water, or perhaps you want to make some agents prefer walking on roads. In some games you may even need unique pathfinding rules for every single agent.

This page will guide you through different options for doing this, as they each have their pros and cons.

• Introduction
• The ITraversalProvider interface
• Case Studies
  • Ships and peasants
  • Turn based games
  • Multiple agent sizes
  • Prefering roads

Introduction

There are a few options you can take:

• Use tags. All nodes can be assigned a single tag from 0 through 31. You can decide for each agent if a particular tag should be walkable or not, and how costly it should be to traverse it. Read more about tags here: Working with tags. This is a very simple way of customizing pathfinding, but it is also very limited in what it can do.

• Use multiple graphs. If different agents require drastically different navmeshes, using different graphs can be a good option. However, this is only reasonable if you only need a small number of different graphs, as it can be quite cumbersome to manage many graphs, not to mention to memory and performance overhead. It is a very robust option though, and it gives you maximum flexibility by trading away some memory and performance. Read more about multiple graphs here: Multiple agent types.

• Use the ITraversalProvider interface to get full control over the walkability and penalty of each node individually for each pathfinding request. This is a very flexible option, but also the most complex one, as it requires you to write some code. Read more about it below.

The ITraversalProvider interface

Any path can be assigned a traversalProvider, which has three methods that you need to override

bool CanTraverse (Path path, GraphNode node);
bool CanTraverse (Path path, GraphNode from, GraphNode to);
uint GetTraversalCost (Path path, GraphNode node);


The CanTraverse(path,node) method should just return true or false depending on if the unit should be able to traverse that node. The CanTraverse(path,from,to) should return true if a unit can traverse the connection between from and to. By default it is forwarded to just return the same value as CanTraverse(path,to). The GetTraversalCost method should return the additional cost for traversing that node. By default if no tags or penalties are used then the traversal cost is zero. A cost of 1000 corresponds roughly to the cost of moving 1 world unit.

As a reference, the default implementation is equivalent to

public class MyCustomTraversalProvider : ITraversalProvider {
public bool CanTraverse (Path path, GraphNode node) {
// Make sure that the node is walkable and that the 'enabledTags' bitmask
// includes the node's tag.
return node.Walkable && (path.enabledTags >> (int)node.Tag & 0x1) != 0;
// alternatively:
// return DefaultITraversalProvider.CanTraverse(path, node);
}

public bool CanTraverse (Path path, GraphNode from, GraphNode to) {
return CanTraverse(path, to);
}
public uint GetTraversalCost (Path path, GraphNode node) {
// The traversal cost is the sum of the penalty of the node's tag and the node's penalty
return path.GetTagPenalty((int)node.Tag) + node.Penalty;
// alternatively:
// return DefaultITraversalProvider.GetTraversalCost(path, node);
}

// This can be omitted in Unity 2021.3 and newer because a default implementation (returning true) can be used there.
public bool filterDiagonalGridConnections {
get {
return true;
}
}
}
By implementing a custom ITraversalProvider you can change the penalties however you want to suit your game's rules. Note that the grid graph for performance reasons removes all connections to unwalkable nodes, so even if you would remove the "node.Walkable &&" part in the traversal provider, a path on grid graphs would still not traverse unwalkable nodes. In other words: you can only make nodes unwalkable, not make unwalkable nodes walkable again.

When you have implemented an ITraversalProvider you can assign it to a path like was done above.

Either by setting it on the Seeker component, so that all paths calculated by that Seeker will use the traversal provider:

seeker.traversalProvider = new MyCustomTraversalProvider();
or by setting it directly on the path: var path = ABPath.Construct(...);
path.traversalProvider = new MyCustomTraversalProvider();


If you use the FollowerEntity component, you can set the traversal provider in its pathfinding settings:

followerEntity.pathfindingSettings.traversalProvider = new MyCustomTraversalProvider();


Case Studies

Here follows a few case studies of common scenarios and how to solve them.

Ships and peasants

Assume you have a nice medieval game with peasants farming the land in an archipelago, and cargo ships sailing the seas. The peasants should be able to walk on land, but not on water. The ships should be able to sail on water, but not on land.

For this case I would recommend using multiple graphs. One for land and one for water. Then you can choose which one the agents use by selecting the appropriate graph in the Seeker inspector.

The reason is that the ships and the peasants cannot move over any common surfaces, so having separate graphs for them makes sense. This will also make it easier to tailor the graphs to suit each agent type. For example, you probably don't want to allow ships to move really close to the shore, but a peasant should without issue be able to walk a fraction of a meter from an obstacle.

If you use a grid graph, you can also solve this instead by using tags to restrict the peasants to the islands, and the ships to the water. This will work, but it will be a bit more cumbersome to set up.

Turn based games

In a turn based game, you often want to prevent units from standing on the same tile. But you also want to allow a unit itself to stand on the tile it is currently on. Turnbased games also often have different movement costs for different units, the rules of which can be quite complex.

This is a clear case for using the ITraversalProvider interface to implement this logic. Fortunately, there are some convenient helpers already implemented for this case. Take a look at Utilities for turn-based games.

Multiple agent sizes

In some games you have agents with a wide range of sizes. This case is common enough that it has its own page! Check it out here: Multiple agent types.

Prefering roads

In some games you want to make units prefer walking on roads, but still allow them to walk on other surfaces if they need to. This can be done by using tags to mark the roads and then using a tag based penalty to make units try to avoid other surfaces.

Note that tag penalties cannot be negative, so you cannot make units prefer roads by using a negative penalty. Instead, we apply a positive penalty to all nodes that are not roads.

This technique works best on grid graphs, since using penalties on grid graphs is predictable, easy to set up and have good granularity. Pathfinding on navmesh/recast graphs is inherently a less precise when using penalties, since the nodes are so much larger.