Wandering AI Tutorial

Tutorial on how to make a wandering AI.

There are several methods for making a wandering AI. They differ in both quality and performance. There is no obvious best solution; different methods will suit different games better. For each method, I have listed some advantages and disadvantages.

• Method 1: Random point inside a circle
• Method 2: Random point in the whole graph
• Method 3: The RandomPath type
• Method 4: The ConstantPath type
• Method 5: Breadth-first search

Method 1: Random point inside a circle

The easiest method for picking a point to move to is simply to pick a random point within a specific distance around the character.

Vector3 PickRandomPoint () {
var point = Random.insideUnitSphere * radius;

point.y = 0;
point += transform.position;
return point;
}
If you are using one of the included movement scripts, you can, for example, change the destination of the AI whenever it has reached the end of its current path:

using UnityEngine;
using System.Collections;
using Pathfinding;

public class WanderingDestinationSetter : MonoBehaviour {
public float radius = 20;

IAstarAI ai;

void Start () {
ai = GetComponent<IAstarAI>();
}

Vector3 PickRandomPoint () {
var point = Random.insideUnitSphere * radius;

point.y = 0;
point += ai.position;
return point;
}

void Update () {
// Update the destination of the AI if
// the AI is not already calculating a path and
// the ai has reached the end of the path or it has no path at all
if (!ai.pathPending && (ai.reachedEndOfPath || !ai.hasPath)) {
ai.destination = PickRandomPoint();
ai.SearchPath();
}
}
}


You can attach the script above to any GameObject with one of the built-in movement scripts (e.g., AIPath/RichAI/AILerp).

Advantages

• Very fast.

• Simple code.

• Works reasonably well for all graph types.

Disadvantages

• Ignores the actual distance to the point, which means it can produce very long paths if the world is not very open (see the video above).

• Has a slight bias towards points close to walls/obstacles as any points that were generated inside the obstacles would have to be snapped to the closest point on the graph.

Misc

• Ignores penalties when picking points (penalties will be taken into account when searching for a path to the point though).

Method 2: Random point in the whole graph

Sometimes you just want something very simple. Instead of picking a node around the current position, you can just pick a random node in the graph and try to walk towards the position of that node.

// Pick a random walkable point on the graph, sampled uniformly over the graph's surface
var sample = AstarPath.active.graphs[0].RandomPointOnSurface(NNConstraint.Walkable);

// Use a random point on the surface of the node as the destination.
var destination1 = sample.position;
// Or use the center of the node as the destination
var destination2 = (Vector3)sample.node.position;


Depending on what you want to use this for, you may want to pass in an NNConstraint to restrict which nodes can be returned:

• Check if the node is walkable (see NNConstraint.Walkable)

• Check if the node can be reached from the AI (see NNConstraint.constrainArea)

Advantages

• Fast in most cases (sampling points on navmesh/recast graphs is slower, and it can also be slow to find a valid point if the NNConstraint is very restrictive).

• Simple code

Disadvantages

• Very little control over the length of the path.

Misc

• Ignores penalties when picking points (penalties will be taken into account when searching for a path to the point though).

Method 3: The RandomPath type

The RandomPath type is a path type that, in contrast to the normal paths which calculate a path from a specific point to another specific point, calculates a random path away from a starting point.

If you are using one of the built-in movement scripts (see Movement scripts) you can do something like this:

// Disable the agent's internal automatic path recalculation
ai.canSearch = false;
RandomPath path = RandomPath.Construct(transform.position, searchLength);
path.spread = spread;
// Give the agent a path to calculate and follow
ai.SetPath(path);
If you are using a custom movement script, you will have to pass it to the seeker manually.

RandomPath path = RandomPath.Construct(transform.position, searchLength);

path.spread = spread;
seeker.StartPath(path);


Advantages

• Picks a point and calculates a path in one go.

• Every node that is considered has the same probability of being chosen; no bias towards being near obstacles like in Method 1: Random point inside a circle.

• A minimum path cost can be set (searchLength).

Disadvantages

• Can be slow for long paths.

• Does not work that well for navmesh/recast graphs as every node has the same probability of being chosen, which will cause a bias towards regions with a lot of detail (and thus more and smaller nodes).

Misc

• Takes penalties into account.

Method 4: The ConstantPath type

The ConstantPath type is a path type which will find all nodes which can be reached from the start point with a cost at most equal to a particular value. After all those nodes have been found, we can pick one or more random points on the surface of those nodes.

ConstantPath path = ConstantPath.Construct(transform.position, searchLength);

AstarPath.StartPath(path);
path.BlockUntilCalculated();
var singleRandomPoint = PathUtilities.GetPointsOnNodes(path.allNodes, 1)[0];
var multipleRandomPoints = PathUtilities.GetPointsOnNodes(path.allNodes, 100);
If you want to feed this to a built-in movement script, you can use the same approach as in Method 1: Random point inside a circle.

Advantages

• Can pick multiple random points with just a single path request.

• The probability of choosing a node is proportional to its surface area (so if all nodes have the same size, e.g., when using a grid graph, then every node that is considered has the same probability of being chosen). There is no bias towards being near obstacles like in Method 1: Random point inside a circle.

• Possible to do custom filtering of the nodes afterwards if that should be necessary.

• Usually slightly faster than Method 3: The RandomPath type.

• Works reasonably well for navmesh/recast graphs.

Disadvantages

• Can be slow when having to search a lot of nodes.

Misc

• Takes penalties into account.

Method 5: Breadth-first search

A breadth-first search is a simple search that searches outwards from the starting node a single node at a time. It doesn't take penalties or any other types of costs into account. This means, for example, that moving diagonally on a grid graph has the same cost as moving along one of the 4 non-diagonal connections.

The way you use it is very similar to what is done in Method 4: The ConstantPath type.

// Find closest walkable node
var startNode = AstarPath.active.GetNearest(transform.position, NNConstraint.Walkable).node;
var nodes = PathUtilities.BFS(startNode, nodeDistance);
var singleRandomPoint = PathUtilities.GetPointsOnNodes(nodes, 1)[0];
var multipleRandomPoints = PathUtilities.GetPointsOnNodes(nodes, 100);

If you want to feed this to a built-in movement script, you can use the same approach as in Method 1: Random point inside a circle.

Advantages

• Can pick multiple random points, not just one.

• The probability of choosing a node is proportional to its surface area (so if all nodes have the same size, e.g., when using a grid graph, then every node that is considered has the same probability of being chosen). There is no bias towards being near obstacles like in Method 1: Random point inside a circle.

• Possible to do custom filtering of the nodes afterwards if that should be necessary.

• No round trip to the pathfinding system necessary, which can save some overhead.

• Usually slightly faster than Method 4: The ConstantPath type and Method 3: The RandomPath type.

Disadvantages

• Can be slow when having to search a lot of nodes.

• Does not use the pathfinding threads, so you lose the ability to easily offload it from the main Unity thread.

• Does not work particularly well for navmesh/recast graphs as the paths will have a large variation in length depending on the detail of the navmesh (more and smaller nodes means the BFS will not reach as far).

Misc

• Does not take penalties or any other costs into account; only the number of nodes traversed is relevant.