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