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.

Contents

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

Note

Make sure that you do not have any other components attached that also try to set the destination of the AI (e.g the AIDestinationSetter component).

See also

Pathfinding.IAstarAI

Random.insideUnitSphere

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 you will have to pass it to the seeker manually.

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

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

See also

Searching for paths

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.

See also

Pathfinding.RandomPath

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.

See also

Pathfinding.ConstantPath

Pathfinding.PathUtilities.GetPointsOnNodes

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.Default).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.

See also

Pathfinding.PathUtilities.BFS

Pathfinding.PathUtilities.GetPointsOnNodes

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.