Pathfinding

This page covers tile pathfinding: the MapPathFindingBehaviour component that walks a character to a target around blocking tiles, how it decides which tiles are walkable, and how to run a path search from your own code.

Concept

The search runs over the map's tiles, not over physics colliders. Each tile is a node, and a character can step to any of its eight neighbours, or four if diagonals are off. The search is A*, and it runs a little at a time across frames, so a long search does not stall your game.

There are three layers of code, all in Scripts/MapPathFinding/:

Type	Namespace	What it does
PathFinding	CreativeSpore.RpgMapEditor.PathFindingLib	The A* search itself. Knows nothing about maps.
MapPathFinding	CreativeSpore.RpgMapEditor	Runs the search on the tiles of AutoTileMap.Instance.
MapPathFindingBehaviour	CreativeSpore.RpgMapEditor	A component that keeps a path to TargetPos up to date and steers the character along it.

Most of the time you only touch the component.

How to use it

1. Add MapPathFindingBehaviour to the character. It needs a MovingBehaviour on the same object and adds one if there is none. MovingBehaviour is what moves the transform.
2. Set Max Speed and Max Force on the MovingBehaviour. Both default to 0.01, which is barely moving. The sample prefabs use values between 0.5 and 1. Max Speed is in units per second.
3. From a script, set TargetPos to the world position the character should go to.

using UnityEngine;
using CreativeSpore.RpgMapEditor;

[RequireComponent(typeof(MapPathFindingBehaviour))]
public class WalkToTile : MonoBehaviour
{
    public int tileX = 10;
    public int tileY = 5;

    MapPathFindingBehaviour m_pathFinding;

    void Start()
    {
        m_pathFinding = GetComponent<MapPathFindingBehaviour>();
        m_pathFinding.OnComputedPath += HandlePathComputed;
        GoTo(tileX, tileY);
    }

    public void GoTo(int x, int y)
    {
        AutoTileMap map = AutoTileMap.Instance;
        // Only send the character to a tile of the map it can stand on.
        if (!map.IsValidAutoTilePos(x, y) || map.GetCellAutotileCollision(x, y) != eTileCollisionType.PASSABLE)
            return;
        m_pathFinding.TargetPos = map.transform.position + RpgMapHelper.GetTileCenterPosition(x, y);
    }

    void HandlePathComputed(MapPathFindingBehaviour source)
    {
        if (source.Path.Count == 0)
            Debug.Log(name + " cannot reach tile " + tileX + "," + tileY);
    }
}

What the component does with that, every physics step (FixedUpdate):

• When TargetPos moves into a different tile, it starts a new search from scratch and drops the one in progress. Moving the target within the same tile does not restart anything.
• While a search runs, the character keeps following the previous path.
• When the search finishes it replaces Path and skips ahead to the path tile after the one nearest the character, so the character does not walk backwards. Then it calls OnComputedPath.
• It steers towards the centre of each tile on the path in turn. It moves on to the next tile once the character is inside the current one and within Min Dist To Move Next Target of its centre.
• It stops at the centre of the target tile, not at TargetPos itself. To stop on an exact point, take over once the character is in the target tile. The sample TouchFollowBehaviour does this: it disables the pathfinding component and calls MovingBehaviour.Arrive directly.

The search itself does not check whether the target tile is walkable, so a target on a blocking tile can produce a path that ends inside it. Test the target first, as GoTo does above.

Disabling the component stops it steering and stops new searches. The AI scripts use that to switch between wandering and chasing. See AI.

Note

MovingBehaviour moves the transform on its own and does not test tile collisions. The sample FollowerAI also requires a PhysicCharBehaviour, the framework's tile collision component. Also note the path follows tile centres in world space as if the map sat at the origin, so keep the map object at (0, 0, 0), as Tiles and Positions recommends for every position helper.

Which tiles are walkable

A tile is walkable or not depending on the collision types set in the tileset (Tile Collisions). For each tile the search looks through the Ground layers, starting from the last one in MapLayers, and the first tile it finds decides:

Collision of that tile	Walkable
PASSABLE	Yes
WALL	Yes, with the restriction below
BLOCK or FENCE	No
OVERLAY or empty	Keep looking in the next ground layer

A tile with nothing on any ground layer is not walkable. Neither is anything outside the map.

Diagonal steps never cut corners. A diagonal move is only allowed when both tiles beside it, the horizontal and the vertical neighbour, are walkable too.

WALL tiles get a special rule for moving between tiles: a step between two neighbouring tiles is allowed when they hold the same tile on a ground layer, and refused when one of them is a WALL tile and the other is something else. So a path can run along a block of the same wall tile, but cannot step onto or off it from other ground.

Warning

The path search and character collision do not agree on WALL tiles. The search treats them as walkable under the rule above, while PhysicCharBehaviour blocks them. A path can therefore lead a character into a wall it then refuses to enter. Where characters must go around something, use BLOCK rather than WALL.

The search also treats the left and right edges of the map as joined: a tile in the first column counts the last column of the row above as a neighbour, and the other way round. Keep the first and last columns blocked in areas where characters use pathfinding.

The walkable test reads the map live, so tiles you change at runtime are taken into account by the next search.

Heuristics and cost

MapPathFinding.eHeuristicType sets how strongly the search heads for its goal:

Value	Behaviour
None	Ignores the direction of the goal and spreads out evenly. It visits the most tiles and is the slowest. With no pull towards the goal it does not commit early to a greedy route, so its paths are usually the shortest of the three.
Manhattan	The default. Pushes hard towards the goal counting only straight steps, so it visits far fewer tiles. The route is not guaranteed to be the shortest.
Diagonal	Like Manhattan, but the distance estimate allows diagonal steps.

The search does up to 10 steps per frame, and one step examines one tile and its neighbours. It gives up after 8000 steps. On a big open map, a target that cannot be reached can therefore keep a character's search busy for up to 800 frames, more than 13 seconds at 60 frames per second, before OnComputedPath reports an empty path. A target inside a small closed area fails quickly, because the search runs out of tiles.

The heuristic and diagonal setting live on the MapPathFinding object inside the component, in the protected field m_mapPathFinding, and they are not shown in the inspector. To change them, derive from the component:

using CreativeSpore.RpgMapEditor;

// Use this component instead of MapPathFindingBehaviour.
public class FourWayPathFinding : MapPathFindingBehaviour
{
    void Awake()
    {
        m_mapPathFinding.AllowDiagonals = false;
        m_mapPathFinding.HeuristicType = MapPathFinding.eHeuristicType.Diagonal;
    }
}

The sample scripts look the component up with GetComponent<MapPathFindingBehaviour>(), which finds a derived class too.

The demo scene

Open Samples/Scenes/demo5 - PathFinding and press Play. Move the player with the keyboard. The DemoPathFinding object, which carries DemoPathFindingBehavior and a MovingBehaviour, searches for a path from its own position to the player every time the player enters a new tile.

• Turn Gizmos on in the Game view to see the path, drawn as red lines. MapPathFindingBehaviour draws it every physics step.
• The drop-down at the top switches the heuristic. Watch the red path change shape as you try each one. The Compute Time(ms) figure in the box under the buttons is the time between the last two finished searches, so it includes the wait for the player to change tile and is not the cost of one search.
• Enable Edit Map opens the in-game map editor so you can paint walls and watch the path change. Enable Debug PathFinding brings the path view back.
• The mouse wheel zooms while the map editor is closed.

DemoPathFindingBehavior derives from MapPathFindingBehaviour and sets TargetPos to the player's position in FixedUpdate, which is the whole pattern for a character that follows another. Since 1.6.1 it is in the CreativeSpore.RpgMapEditor namespace like the rest of the asset. The ZombiePlant and PlayerTouch prefabs in Samples/Prefabs use the same component through FollowerAI and TouchFollowBehaviour, covered in AI.

Searching from your own code

To get a route without moving anything, for a movement range preview or turn based moves, use MapPathFinding directly. GetRouteFromToAsync returns an IEnumerator to run inside a coroutine. The last value it produces is a PathFinding.FindingParams, whose computedPath is the route.

The route comes back starting at the second index and ending at the first. The component relies on this by passing the target first, and the example below does the same, so the list runs from the character to the target.

using System.Collections;
using UnityEngine;
using CreativeSpore.RpgMapEditor;
using CreativeSpore.RpgMapEditor.PathFindingLib;

public class RoutePreview : MonoBehaviour
{
    MapPathFinding m_pathFinding = new MapPathFinding();

    public IEnumerator ShowRoute(Vector3 target)
    {
        int fromIdx = RpgMapHelper.GetTileIdxByPosition(transform.position);
        int toIdx = RpgMapHelper.GetTileIdxByPosition(target);

        IEnumerator search = m_pathFinding.GetRouteFromToAsync(toIdx, fromIdx);
        while (search.MoveNext())
            yield return null;

        PathFinding.FindingParams result = (PathFinding.FindingParams)search.Current;
        foreach (IPathNode node in result.computedPath)
        {
            MapTileNode tile = (MapTileNode)node;
            Debug.Log("Step to tile " + tile.TileX + "," + tile.TileY);
        }
    }
}

Start it with StartCoroutine(ShowRoute(target)). Things to know:

• The route includes the start and the target tiles. It is empty when there is no route, and has one tile when both indices are the same.
• Both indices must be inside the map. Check the positions with IsValidAutoTilePos first (see Tiles and Positions).
• Each MapTileNode has TileX, TileY, TileIdx and Position, the tile centre in world space for a map at the origin.
• Run one search at a time per MapPathFinding object, and let it finish. Give each character its own object, as the component does.
• A MapPathFinding object caches tile nodes, including their positions. Create a new one after loading a different map or changing Cell Size.
• There is also a synchronous GetRouteFromTo(startIdx, endIdx), which finishes the whole search before returning. It can freeze a frame on a large map, which is why the component uses the coroutine.

Reference

MapPathFindingBehaviour member	What it does
TargetPos	World position to walk to. Shown as Target Pos.
MinDistToMoveNextTarget	Shown as Min Dist To Move Next Target. How close to a path tile's centre the character must get before it heads for the next one. Default 0.02 units.
Path	The current route as a LinkedList<IPathNode>, from the character's tile to the target tile.
CurrentPathNode	The path tile the character is heading for, or null when it has none.
IsComputingPath	True while a search is running.
ClearPath()	Forgets the current path and stops steering. The character keeps its current velocity, so also set MovingBehaviour.Veloc to zero if it should stand still. A new path is only computed when TargetPos enters another tile.
OnComputedPath	Delegate called when a search finishes.

MapPathFinding member	What it does
HeuristicType	None, Manhattan (default) or Diagonal.
AllowDiagonals	Allow diagonal steps. Default true.
GetRouteFromToAsync(startIdx, endIdx)	Search as a coroutine. The route runs from endIdx to startIdx.
GetRouteFromTo(startIdx, endIdx)	The same search, finished before it returns.
IsComputing	True while a search is running.

Related

• Tiles and Positions
• AI
• Tile Collisions
• Scripting