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.

• Alternatives
• The ITraversalProvider interface
  • Using the ITraversalProvider with a movement script
• Case Studies
  • Ships and peasants
  • Turn-based games
  • Multiple agent sizes
  • Preferring roads

Alternatives

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 the 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

The ITraversalProvider interface is something you can implement to be able to control exactly which nodes are traversable, how costly it is to traverse them, and how costly it is to traverse connections between nodes. This enables a lot of flexibility in how you can control pathfinding, significantly more than using the built-in tag system.

Any path can be assigned a traversal provider, which has four methods that you can override

As a reference, here's one implementation:

public class MyCustomTraversalProvider : ITraversalProvider {
public bool CanTraverse (ref TraversalConstraint traversalConstraint, GraphNode node) {
// If, for example, your agents are afraid of heights, prevent your agents from going above 50 world units
return ((Vector3)node.position).y < 50;
}
public bool CanTraverse (ref TraversalConstraint traversalConstraint, GraphNode from, GraphNode to) {
// Connections between nodes can be filtered too.
// If you don't have any special rules for this, just forward the call to checking if the 'to' node is traversable.
// (or just skip this method, as the default implementation will do the same)

// We can, for example, prevent the agent from going directly from a node with tag 2 to a node with tag 3
if (from.Tag == 2 && to.Tag == 3) return false;

return CanTraverse(ref traversalConstraint, to);
}
public float GetTraversalCostMultiplier (ref TraversalCosts traversalCosts, GraphNode node) {
// For example, if your agent is afraid of heights, you can make nodes high up be 10 times more expensive to traverse
if (((Vector3)node.position).y > 30) return 10.0f;

return DefaultITraversalProvider.GetTraversalCostMultiplier(ref traversalCosts, node);
}
public uint GetConnectionCost (ref TraversalCosts traversalCosts, GraphNode from, GraphNode to) {
// The traversal cost is, by default, the sum of the penalty of the node's tag and the node's penalty
return traversalCosts.GetTagEntryCost(to.Tag) + to.Penalty;
// alternatively:
// return DefaultITraversalProvider.GetConnectionCost(ref traversalCosts, from, to);
}
}
By implementing a custom ITraversalProvider you can change the penalties however you want to suit your game's rules.

Using the ITraversalProvider with a movement script

When you have implemented an ITraversalProvider, you can use it with any built-in movement script, or in your own path requests.

Seeker

If you use the Seeker component, assigning a traversal provider to it will make all requests made through it use that provider.

seeker.traversalProvider = new MyCustomTraversalProvider();
FollowerEntity

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

followerEntity.pathfindingSettings.traversalProvider = new MyCustomTraversalProvider();
Custom path request

Or if you create your own path requests, you can set it directly on the path:

var path = ABPath.Construct(Vector3.zero, Vector3.one);
var traversalProvider = new MyCustomTraversalProvider();

// Use the same provider for both traversability and costs
path.traversalConstraint.traversalProvider = traversalProvider;
path.traversalCosts.traversalProvider = traversalProvider;


Case Studies

Here follow 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 be able to walk a fraction of a meter from an obstacle without issue.

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. Turn-based 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.

Preferring 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.

You can find an example of this in the Recast graph on a terrain example scene.