Recently, I been working on a tactical-RPG game in Unity3D and needed a way to find a path from a starting point to an end point. The game is tile-based, so this calls for a pathfinding algorithm, but which one? And how to make it flexible enough to be used on dynamic maps? Read on.

A pathfinding algorithm is a set of logic which starts from a tile and loops through adjacent tiles, calculating costs associated with moving there. It keeps going until it finds the end point. A pathfinding algorithm can work in more cases than just tiles, it can be waypoint based.

From my testing on this site, the best solution was to use the A* algorithm with manhattan heuristic and bi-directional turned on.

The A* algorithm is the most popular pathfinding algorithm, because it is fairly flexible and can be used in a wide range of contexts. The other algorithms will usually just give you trouble when you have to deal with that edge-case pathfind.

The manhattan heuristic counts the number of horizontal and vertical squares remaining to reach the end point without taking into account twists and turns. The bi-directional option speeds up pathfinding – in most cases – by searching both from the starting point and the end point. Once one of the nodes connects with the other, a path can be created.

Pathfinding Requirements

I’m creating a game similar to Final Fantasy Tactics. Which has many rules to movement such as, cannot move through enemy units unless dead and cannot move to tiles too high or low. So the pathfinding interface has to be flexible enough to be used in many cases.

My Implementation

I created a couple of classes but the main two are PathFind and PathFindProps. The PathFind class does the actual search and returns a path to be followed, to reach the end point. The PathFindProps is a simple value object which contains information about the search, like start point, end point and special hook-in methods to custom allowed tiles.

For improved efficiency I chose to use the OrderedBag collection from Power Collections. The OrderedBag supplies a special optimized priority queue. This is used by the algorithm to find the next best tile to search. Remember not every tile is not uniformly searched, only tiles which seem to be closer to the target are first considered. You’ll have to have this library included to use this code.

I didn’t post the source for Map or Tile but it should be easy enough to replicate them by copying the usage in the classes. I know those two classes should be converted into interfaces, Dependency inversion, but in cases like this where there is only one applicable class it’s not needed.

The pathfind algorithm works by searching through each adjacent tile one by one. First the tile will be checked to see if it is valid and if so, a new node will be added to the priority queue for that tile. Priority is based on distance, heuristic and weight. I won’t go into those things but it basically figures out which tiles it thinks will bring it closer to the end point.

As its going through all these tiles it checks if it connected with a node of the other, remember this is bi-directional, so both the start and end points are searching through tiles.

Once the start and end paths connect, the path is then created by stepping backwards through the nodes. A stack object is then returned which contains a list of tile steps needed to reach to wanted end point.

Usage

Start by creating an instance of PathFindProps, this will contain all the configuration options.

PathFindProps props = new PathFindProps();
props.startPos = new Vector3(0, 0, 0);
props.endPos = new Vector3(5, 0, 9);
props.checkWalk = true;

The props instance is then sent into the Search method. Now instead of creating this props class, I could have just created a bigger method parameter list but an object has the added benefit of being reused and just being more extensible.

The checkWalk attribute tells the pathfinder to only consider walkable tiles. Of course the startPos and endPos is used to define the start and end tiles. I chose to use a Vector3 because it will be possible to walk upstairs or in a basement, although the pathfinder currently doesn’t search for that.

Just a note, both the start and end tiles are checked for validity, so make sure they are walkable before attempting to find a path towards them.

PathFind pathFind = new PathFind(map);
Stack<Vector3> path = pathFind.Search(props);

if(path == null){
    Debug.LogWarning("Path was not found");
}

Vector3 firstTile = path.Pop();

This is the most basic usage. A stack instance is returned if a path was successfully found. The stack can the be popped incrementally to show how to reach the end point.

Handling Dynamic Tiles

Cannot walk through tiles occupied by enemies. – Final Fantasy Tactics

The biggest problem I found is how to properly handle dynamic tiles. A tile can be perfectly valid to walk through when unoccupied, but if an enemy is stand their, all of the sudden it is unwalkable. On the picture above, blue tiles are permitted tiles. You can see the enemy units are blocking the tiles they occupy.

The way I dealt with this is by adding a hook-in method OnCheck to the PathFindProps class. This method is used to check if a tile is valid for walking on.

public bool OnCheckTile(Vector3 tile, Vector3 parentTile){
    Entity entity = FindEntityAt(tile);

    return entity == null \|| entity.isAlly \|| entity.isDead;
}

props.OnCheck = OnCheckTile;

So this method is called on every tile. If the tile has an alive enemy it is not walkable. Finally, a OnVisit is available for cases where you want to do something when a tile is successfully added or “visited”. This can be used for debugging and seeing which tiles were added.

public void OnVisit(Vector3 tile){
    showColorAt(tile, Color.green);
}

props.OnVisit = OnVisit;

Handling Jumping

My personal Tactical-RPG game

In my game, as seen above, some tiles are unwalkable if the tile you are on is too low or high compared to the next tile. Thankfully this is easy to implement, first I added two new attributes on the PathFindProps class, maxJump and maxFall. These are both defaulted to reasonable values.

Then in the PathFind code I added an extra check when testing if the tile is valid.

// check tile height difference
if(!parentNode.IsFirstNode()){
    Tile parentTile = _map.FindTile(parentNode.pos);

    if(parentNode.EndNode()){
        Tile temp = parentTile;
        parentTile = tile;
        tile = temp;
    }

    if(tile.GetHeightDiff(parentTile) > _props.maxJump){
        return false;
    }
    if(tile.GetHeightDiff(parentTile) < -_props.maxFall){
        return false;
    }
}

This calculates the height difference between the parent tile and the potential tile. If the difference is too high, then the tile is unreachable from that tile. Remember it could be possible to get on the tile from an other side.

Logic was also put in to handle searches from the end point to the start point. Remember those searches are backwards, and so the tiles get reversed.

Next Time

I didn’t cover how to use the found path, so it will be covered in an other blog post. I will also go into how to display colored tiles around the character as well.

Helpful Links

• Power Collections
• PathFinding.js
• Improving Pathfinding Performance
• Pathfinding for Beginners