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 suite different games better. For each method I have listed some advantages and disadvantages.

• Method 1: Random point inside a circle
• Method 2: Random node 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 node 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.

GraphNode randomNode;

// For grid graphs
var grid = AstarPath.active.data.gridGraph;

randomNode = grid.nodes[Random.Range(0, grid.nodes.Length)];

// For point graphs
var pointGraph = AstarPath.active.data.pointGraph;
randomNode = pointGraph.nodes[Random.Range(0, pointGraph.nodes.Length)];

// Works for ANY graph type, however this is much slower
var graph = AstarPath.active.data.graphs[0];
// Add all nodes in the graph to a list
List<GraphNode> nodes = new List<GraphNode>();
graph.GetNodes((System.Action<GraphNode>)nodes.Add);
randomNode = nodes[Random.Range(0, nodes.Count)];

// Use the center of the node as the destination for example
var destination1 = (Vector3)randomNode.position;
// Or use a random point on the surface of the node as the destination.
// This is useful for navmesh-based graphs where the nodes are large.
var destination2 = randomNode.RandomPointOnSurface();
Depending on what you want to use this for, you may want to do some checks after you have picked a node to for example:

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

• Check if the node can be reached from the AI (see Pathfinding.PathUtilities.IsPathPossible)

• Some other check that might be relevant for your game. If one of these checks fail you can pick a new random node and run the checks again. Unless valid nodes are very rare you will likely find a valid node quickly.

Advantages

• Very fast (unless you use the generic approach above)

• 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 chosing 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 chosing 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 loose the ability to easily offload it from the main Unity thead.

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