Path Finding on Tile based Maps
Introduction
Path Finding is something that seems difficult at first thought. How do I work out the best way for one of the guys in my game to get from one location to another taking account of other things on the map. In the general case this is a pretty difficult problem, if you consider free form maps and accounting for other things wandering around the map at the same time it really gets very complicated.
This tutorial hopes to provide somewhere to start, explaining the most common path finding algorithm in the more simple case of tile based maps. It’ll cover how the algorithm works and provide some reusable code to find paths across arbitrary tile based maps.
Reusable Path Finding Code
Disclaimer: This tutorial is provided as is. I don’t guarantee that the provided source is perfect or that that it provides best practices.
The A* Algorithm
The A Star (A*) algorithm is probably one of the most commonly used in games programming. The reason is that, as we will see, it’s extremely configurable to the particular type of game and map. It can be tuned to provide good performance against most data sets.
A* works by maintaining a pair of lists, one containing locations on the tile map which may be a next step in the path (called the ‘open’ list) and one containing locations that have already been searched (called the ‘closed’ list). The algorithm keeps looping while there are still next steps to be considered. It chooses the most likely of the next steps available and considers it’s neighbors. Each neighbor gets added a potential next step and we continue looping. As each location is considered as a step it’s removed from the open list and added to the closed list (i.e. the list of locations that have been searched). In this way we search the map for possible locations but tend towards choosing the “most likely” steps first – this is why the algorithm is reasonably efficient.
However, how do we determine which next step is “most likely”? Thats where the configuration of the algorithm comes in. Each time we need to choose the most likely next step we resolve each possible step against a “heuristic”. This is just a formal name for a function that provides a priority value for anything (more on these later).
There are two primary values used in A*. The first, already mentioned, is the “heuristic cost”. This cost determines which step is most likely. The second value we use to choose the best next step is the cost of getting to the current location, i.e. how many steps is the currently location away from starting point – this is called the “path cost”. By combining these two values the algorithm considers both the most likely route and the shortest.
Let’s look at the algorithm in more detail and in a more implementation oriented manner.
Pseudo Code
The A* algorithm works like this:
- At initialization add the starting location to the open list and empty the closed list
- While there are still more possible next steps in the open list and we haven’t found the target:
- Select the most likely next step (based on both the heuristic and path costs)
- Remove it from the open list and add it to the closed
- Consider each neighbor of the step. For each neighbor:
- Calculate the path cost of reaching the neighbor
- If the cost is less than the cost known for this location then remove it from the open or closed lists (since we’ve now found a better route)
- If the location isn’t in either the open or closed list then record the costs for the location and add it to the open list (this means it’ll be considered in the next search). Record how we got to this location
The loop ends when we either find a route to the destination or we run out of steps. If a route is found we back track up the records of how we reached each location to determine the path.
Heuristics – how to determine what’s a good next step?
As mentioned already, the A* algorithm depends on evaluating the best next step in searching for a path. This is done by evaluating each of the possible next steps against a heuristic to give a value that can be used to sort the list and hence determine the most likely next step. As you can imagine this makes choosing a good heuristic for your map and game really important to getting good path finding performance.
In the example code we’ll make the heuristic “pluggable”, i.e. it’ll be possible to provide a class to implement a new heuristic. Let’s first look at a couple of commonly used heuristics.
Euclidean Distance
The most obvious way to determine the best step is to always pick the step that is the closest to the target. This isn’t always perfect for environments with a lot of obstacles or that are maze like but it does provide a simple heuristic to understand. It would look like:
dx = targetX - currentX;
dy = targetY - currentY;
heuristic = sqrt((dx*dx)+(dy*dy));
Remembering that the heuristic is evaluated frequently during the path finding process we can see that this may not always be a good idea. That sqrt() call is (on most hardware) expensive.
Manhattan Distance
Another common approach is to replace absolute distance with “Manhattan Distance”. This is an approximation of the distance between two points based on adding the horizontal distance and vertical distances rather than computing the exact difference. That would look like this:
dx = abs(targetX - currentX);
dy = abs(targetY - currentY);
heuristic = dx+dy;
This might not always work that well (especially if you allow diagonal movement) but it will work in some limited circumstances and is much cheaper. This is a good example of how the A* algorithm can be customized for specific games and maps.
Tutorial Wars – The Example
Writing a reusable Path Finder
The tutorial code used here is going to get committed into the Slick library as a utility, so ideally it should be nice and reusable. With this in mind we’re going to build the code in such a way that different games can plug into it with the minimal of fuss.
In addition we need to make sure the heuristic can be changed for different games and that it’s not too tricky to write a new heuristic specific to a given game. In the next couple of sections we’ll look at the most important part of developing reusable code, the software contract.
What the Path Finder requires from the Developer?
The path finder code needs to be able to understand the game’s concept of a map. We’re taking the bold assumption that the game is 2D and grid based – though this covers a lot of different games. Looking at the algorithm, what does the path finder need to know about the game map:
- Whether a given tile is blocked or not – potentially based on a given moving entity
- The cost of moving from one location to an adjacent location
To make the map data usable we’re also going to need to know the extent of the map, i.e. it’s width and height. From these requirements we can extract this contract (interface: TileBasedMap.java):
public interface TileBasedMap {
public int getWidthInTiles();
public int getHeightInTiles();
public boolean blocked(Mover mover, int x, int y);
public float getCost(Mover mover, int sx, int sy, int tx, int ty);
public void pathFinderVisited(int x, int y);
}
There’s one extra method in there we haven’t talked about, pathFinderVisited. This is going to allow the path finder to let us know that it’s searched a particular location. We’ll e able to see how much of the map had to be searched before finding a path, this will hopefully help us debug and build efficient heuristics.
There’s also a second concept in the interface, the “Mover”. In most games the thing that’s actually going to move has properties that control where or what it can do – in our example for instance the boat can only move on water. If you look at the Mover.java interface you may be slightly surprised: It contains no methods at all! This type of interface is called a tagging or marker interface and just allows us to give context and typing to otherwise undefined entities. Essentially this means the Mover can be any object that the game knows about. As the object passes out of the game domain and into the reusable code domain it becomes an unknown object – an opaque Mover. When it re-enters the game domain (as it’s passed into the TileBasedMap) the game implementation is safe to cast it back to whatever it passed in and make determinations based on it. There are slightly neater ways to do this using generics but it’s thats out of scope here.
What the Mover interface gives us is the ability to make cost and blockage decisions based on the entity moving. A hero can’t walk through walls – but maybe a ghost can. The Mover interface lets us make this distinction in the middle of our path finding algorithm.
Now we’ve seen what the game must provide, lets consider what path finding code gives us.
How does the Developer use the Path Finder?
First we need to consider how the developer will invoke the path finder. They’ll definitely have to provide a starting and ending point for the path each time. As mentioned above we’ll also have to provide the description of the game entity doing the moving. Finally, the whole point, we’ll want a path back from the invocation that describes the route from start to finish:
public interface PathFinder {
public Path findPath(Mover mover, int sx, int sy, int tx, int ty);
}
There’s one thing missing, how does the path finder know what tile based map to be searching? In this case thats down to the implementation (which we’ll see in a moment). Storing the map being searched in the PathFinder implementation has it’s benefits – information about the map can be cached within the finder. However, this also means that the same path finder instance can’t be reused over and over for different maps.
We’ve seen the Mover interface before, what about the Path object that gets returned. It contains just enough information to describe the route:
public class Path {
public int getLength();
public Step getStep(int index);
public int getX(int index);
public int getY(int index);
public void appendStep(int x, int y);
public void prependStep(int x, int y);
public boolean contains(int x, int y);
}
The path is essentially a list (in fact it’s implemented with an ArrayList) of Step objects, where a “Step” represents a single location on the path. The methods should be self explanatory, we can simply add things to the path and then interrogate the list of steps when using it in the game.
We’ve now completed the contract between the game and the path finding code, yet we still can’t actually do anything. We could write our game against this interface and check everything fits together nicely before implementing the A* algorithm. However, since thats the thing the tutorial is meant to be about we’ll look at it first.
The A* Implementation
The A* algorithm as described above fits nicely into the contract we’ve defined. The PathFinder implementation of A* can be found in AStarPathFinder.java. We’ll look at the algorithm implementation in detail next, but first let’s consider how the algorithm elements have translated into the code.
The open and closed lists as described in the algorithm have become lists in our class:
/** The set of nodes that have been searched through */
private ArrayList closed = new ArrayList ();
/** The set of nodes that we do not yet consider fully searched */
private SortedList open = new SortedList ();
Notice how the open set is “sorted” meaning that our most likely next step can be sorted to the top of the set for selection. Next we have the map of data that is being searched:
/** The map being searched */
private TileBasedMap map;
..which is passed in at construction of the path finder. This allows us to cache this next bit, we need to store information about every cell in the tiled map:
/** The complete set of nodes across the map */
private Node[][] nodes;
So we’ve created a small inner class called “Node” which will hold information about particular locations on the map. This is quite an overhead but makes the code easy to read. It could be more optimal to store the information in primitive arrays, but lets not worry about that here. Finally we have the all important heuristic that drives the A*:
/** The heuristic we're applying to determine which nodes to search first */
private AStarHeuristic heuristic;
This is yet another interface, AStarHeuristic.java which we also (optionally) pass in at construction. This allows us to build custom heuristics for path finding. The heuristic interface has a single method:
public float getCost(TileBasedMap map, Mover mover, int x, int y, int tx, int ty);
Each time we need to determine the priority of a particular location we’ll call this method, supplying the location we’re considering and where we’re trying to get to eventually. This should make writing new heuristics simple and nicely separate.
Now we know whats available to us, lets look at the A* implementation. Most of the work is done in the findPath() method which we’ll cover in detail in the next few sections.
Initialization
The initialization of the algorithm looks like this:
if (map.blocked(mover, tx, ty)) {
return null;
}
// initial state for A*. The closed group is empty. Only the starting
// tile is in the open list and it's cost is zero, i.e. we're already there
nodes[sx][sy].cost = 0;
nodes[sx][sy].depth = 0;
closed.clear();
open.clear();
open.add(nodes[sx][sy]);
// set the parent of the target location to null to mark that
// we haven't found a route yet
nodes[tx][ty].parent = null;
The first check we perform is an simple optimization. If the target we’re attempting to find a route to is blocked then there is no way we can find a route there. Returning null indicates there’s no path that can be found.
Next we initialize the information on the starting location and add it to the open list, ready to start searching. We’re at initial state, the open set has one element and the closed set is empty.
Searching the Map
This is the big bit, following along with the algorithm we need to loop choosing the best available step moving closer to the target and an appropriate path. Let’s look at the code:
int maxDepth = 0;
while ((open.size() != 0)) && (maxDepth < maxSearchDistance)) {
So, were going to loop while there are still available steps and while the best next step isn’t the target – i.e. until we’ve found the path or haven’t got anywhere else to search. The extra piece here is a safe guard that most games will want, the search can’t go on forever – we need to limit it. In this case we only allow the path search to get to certain number of steps in length before we give up.
Next we need to take the best step, mark is as searched and then consider it’s neighbors:
Node current = getFirstInOpen();
if (current == nodes[tx][ty]) {
break;
}
removeFromOpen(current);
addToClosed(current);
for (int x=-1;x<2;x++) {
for (int y=-1;y<2;y++) {
if ((x == 0) && (y == 0)) {
continue;
}
int xp = x + current.x;
int yp = y + current.y;
if (isValidLocation(mover,sx,sy,xp,yp)) {
int nextStepCost = current.cost +
getMovementCost(mover, current.x,
current.y, xp, yp);
Node neighbour = nodes[xp][yp];
map.pathFinderVisited(xp, yp);
We grab the best next step (getFirstInOpen()) and consider this our “current” location. If the current location is the target, then end the search we’ve found our route! Removing the current location from the open list and adding it to the closed list marks it as searched. We then cycle through all of it’s neighbors (excluding the [0,0] current location) considering their cost. Note that the path cost to the neighbor is calculated based on the cost to get the current node added to the movement cost associated with moving from current location to the neighbor.
For each of the neighbors we’ve found we need to consider two things. First, have we found a shorter path to this location than previously, if so we need to re-search it. Second, if we don’t already have this as a step to consider we need to record it so it may get chosen as the next step and hence get us closer to the target:
if (nextStepCost < neighbour.cost) {
if (inOpenList(neighbour)) {
removeFromOpen(neighbour);
}
if (inClosedList(neighbour)) {
removeFromClosed(neighbour);
}
}
if (!inOpenList(neighbour) && !(inClosedList(neighbour))) {
neighbour.cost = nextStepCost;
maxDepth = Math.max(maxDepth, neighbour.setParent(current));
neighbour.heuristic = getHeuristicCost(mover, xp, yp, tx, ty);
open.add(neighbour);
}
This first condition up there is checking that we haven’t found a better route to a node we’d previously considered searched (i.e. it’s in the open or closed lists). If we’ve found a better route to the node (the cost is less than the recorded cost) then remove it from the lists it’s stored in to mark as un-searched.
Finally we consider the neighbor in the context of whether its a good next step. If we haven’t already searched it (or we’ve made it available again because we’ve found a better path) then we need to record the costs associated with it and make it a possible next step (add it to the open list). Note that we call setParent() on the node to record how we got to this new node. This information will be used later when we’re determining the route we used to reached the target node and hence building the Path object to return.
Building the Path
Our final step once we’ve finished looping is to build a path object (if we found a path) and return it to the developer. That looks like this:
// since we've got an empty open list or we've run out of search
// there was no path. Just return null
if (nodes[tx][ty].parent == null) {
return null;
}
// At this point we've definitely found a path so we can uses the parent
// references of the nodes to find out way from the target location back
// to the start recording the nodes on the way.
Path path = new Path();
Node target = nodes[tx][ty];
while (target != nodes[sx][sy]) {
path.prependStep(target.x, target.y);
target = target.parent;
}
path.prependStep(sx,sy);
// thats it, we have our path
return path;
First, if we haven’t found a route to the target we just return null to indicate that there was no path. If we did find a path we cycle through the information we’ve recorded stepping up through the parent’s of the path to build up the route we’ve discovered. Pass it back to the user and we’re done!
Now we’ve seen how to find the paths, let’s quickly cover a simple example of using it.
The Example Game Source
The test case is built up of 3 classes. Most of the code is about rendering and handling mouse input which has been covered in other tutorials, so won’t be covered in depth here. There are 3 classes:
PathTest.java – This is the main renderer, it draws a tile image for each location in the game map. It’s also responsible for translating mouse movement and clicks into path finding operations.
GameMap.java – This is the game’s implementation of TileBasedMap, it provides the description of each location in the game. Each location can hold up to two items of information, the type of terrain and optionally an indicator as to the type of unit. The interesting bit of code in terms of path finding is the blocked() method:
public boolean blocked(Mover mover, int x, int y) {
// if theres a unit at the location, then it's blocked
if (getUnit(x,y) != 0) {
return true;
}
int unit = ((UnitMover) mover).getType();
// planes can move anywhere
if (unit == PLANE) {
return false;
}
// tanks can only move across grass
if (unit == TANK) {
return terrain[x][y] != GRASS;
}
// boats can only move across water
if (unit == BOAT) {
return terrain[x][y] != WATER;
}
// unknown unit so everything blocks
return true;
}
So the implementation changes the valid locations based on the unit that is moving. It knows which unit is moving by looking at the Mover implementation passed in – which we’ll see next. In this case tanks are limited to ground movement, boats are limited to water movement and planes can move anywhere.
UnitMover.java – Our mover implementation, it simply holds an integer indicating which type of unit is moving. In a full game implementation the mover interface may be implemented by the actual objects that represent game entities. However, for our purposes a simple integer is enough.
So, the PathTest class is responsible for rendering the map and accepting clicks. When the mouse moves it calls on a path finder to determine a path to the location the mouse is over. The path finder calls back on the GameMap it’s been given using the UnitMover as the context in which the path is being found. With luck it finds a path, which it describes and passes back to the PathTest class. This path is then recorded and rendered next time the screen is updated.
It’s all a little more complete than that, but it’s left to the reader to fiddle with the example code to understand the details.
Conclusion
A* is a powerful and useful tool in game development. It’s really not that complicated once you get going and it can be customized for optimal performance in different circumstances. It does get more complicated once you start considering other moving entities blocking the movement and the 3rd dimension, however hopefully this tutorial has given you a simple introduction that can be extended.
If you notice something that’s wrong or could be better a different way please let me know at the address below.
Suggested Extensions
Consider some more Heuristics – Search around the web, lots of people have implemented A* with different heuristics. Try some of them out.
Optimize the code – The code presented here is trying to be as simple as possible to aid understanding. Optimization options are plentiful.
Credits and References
Written By: Kevin Glass
Graphics from Advance Wars Net