Tile Maps - Collision, Path Finding

Tile Based Collisions

Introduction


This tutorial is hopefully a quick overview of how to use a simple tile-map for detecting when game entities hit walls and preventing them walking through them. The tutorial and code makes the assumption that the reader understands about Java 2D accelerated rendering and has some basic Java knowledge.

The final game can be see here. The complete source for the tutorial can be found here. Its intended that you read through this tutorial with the source code at your side. The tutorial isn't going to cover every line of code but should give you enough to fully understand how it works.

Context highlighted source is also available here:
Game.java
Entity.java
Map.java

Disclaimer: This tutorial is provided as is. I don't guarantee that the provided source is perfect or that that it provides best practices.

Tile Maps

What are they?

A tilemap is essentially an grid of cells where the value in the cell indicates what should be at that location. So we we might define "1" as grass and "2" as mud and define a map using these values describing an area in the game.

The first nice thing about tilemaps is they're simple. Its very easy to implement a tilemap using a standard two dimensional array. You simply fill it full of values and access them using x/y coordinates.

The second nice thing about tilemaps is that they often save space. You only define the properties of a particular tile type once. You then reuse that set of properties over and over by referencing it form the tilemap.

The last nice thing (that I can think of) about tilemaps is that they're quick to access. Given a particular location on the map it can be very fast to get to the properties associated with that area. Normally its simply a matter of accessing into an array based on the x/y location of an entity.

How do we use them for simple collision?

So, why are they are good for collision. Well, lets look at your standard maze style game. You've got a grid full of cells that are either blocked by a maze wall or free to move through. What are you going to do? Using more advanced techniques you might define a bounding area for each cell and then check your entity against every one! Yuck. Thats a lot of checking! Normally you'd do a broader check first, work out which cells to check first and hence do less bounding shape checks. Tilemaps can be used to perform this broader check - however, in many cases you don't need to perform the more complicated bonunds check at all :)

How does a tilemap help you? Well, instead of checking against every block, you can simply check against the properties for the blocks that are close to your entity. Of course, theres a trade off, its not as accurate as full bounds checking - but normally its more than enough. Lets look at this in more detail:



The diagram above shows a simply tile map with a couple of entities (red blobs). The blue cells represent blocked areas and the white cells clear ones. Around the entity we have a simple box collision bounds. The green points mark locations that we'll check for collision. So, the entity in the top left is in an invalid location (its partly into the wall). The entity is the middle is valid.

Now, how many points you check and where the points are specific to the application - and obviously this isn't perfect collision for everything. However, when entities are simply moving round a map at slow speeds even this 4 point checking can work fine (as we'll see in the tutorial code). Note that with this simple corner checking system the entity bounding box needs to be smaller than the cells of the grid. This is better in some cases because instead of checking resonably complicated bounds checks on bunch of cells, we check explicitly the ones we want to in a very quick tile map based way.

Tutorial Classes

The tutorial code is built up of 3 classes. Lets just go over what they're for.

Game

The game class is our central hub for everything. It handles window creation and the game loop. Its also responsible for creating the map and player.

Map

The map is unsurprisingly our tile map. It contains a data array of values indicating whether each cell is blocked or not. The map is also responsible for rendering itself using simple rectangles.

Entity

The entity class represents things that are wandering the map colliding with the walls. In this example this is simply the player. The entity class is responsible for rendering a sprite representing itself.

Collision Logic

Let's look at how the collision code works, starting in Game we see this:

public void logic(long delta) {
    float dx = 0;
    float dy = 0;
    if (left) {
	dx -= 1;
    }
    if (right) {
	dx += 1;
    }
    if (up) {
	dy -= 1;
    }
    if (down) {
	dy += 1;
    }
		
    if ((dx != 0) || (dy != 0)) {
	player.move(dx * delta * 0.003f,
  		    dy * delta * 0.003f);
    }
}

Elsewhere we've recorded which keys are pressed, we use this to work out which way the player wants their character to move. We then ask the player to move based on the direction and the amount of time thats passed. Player.move() looks like this:

public boolean move(float dx, float dy) {
    float nx = x + dx;
    float ny = y + dy;
		
    if (validLocation(nx, ny)) {
	x = nx;
	y = ny;
			
	return true;
    }
		
    return false;
}

Doesn't do much does it? The actual work is being performed in validLocation(). This method simply works out where the entity will be if the move is performed. It checks if this is a valid location (which performs the collision checks). If it is a valid location it moves the player, if not it doesn't. This way you can't move the player into walls.

Right, so the important bit is in validLocation() which looks like this:

public boolean validLocation(float nx, float ny) {
	if (map.blocked(nx - size, ny - size)) {
		return false;
	}
	if (map.blocked(nx + size, ny - size)) {
		return false;
	}
	if (map.blocked(nx - size, ny + size)) {
		return false;
	}
	if (map.blocked(nx + size, ny + size)) {
		return false;
	}
		
	return true;
}

Again, this is pretty simple right? We go away to the map and check the four points around our player that represent its collision box based on the "size" associated with this entity. If any of the points are blocked then this isn't a valid location - otherwise it is.

Now you can see how this might cause problems in certain cases but for simple situations its fast and most importantly simple. Finally, lets just finish off the picture by seeing what happens in the Map.blocked() method:

public boolean blocked(float x, float y) {
    return data[(int) x][(int) y] == BLOCKED;
}

Really simple and really quick! We take the floating point values passed in (which are in grid cells) - cast them down to ints which instantly gives us the grid cell we need to check. Check the cell and return yes or no.

Thats it for code. The tutorial code does some other bits and pieces to create the window, capture key input and render the scene but this has all been covered in the space invaders tutorial.

Conclusion

Tilemaps make sense for certain situations. In most cases they're based combined with other techniques. For instance, it might make sense to use the tilemap to work out which cells need to be checked and then using bounds checking to work out the actual collision.

Tilemaps don't fit in every game but in many cases they are a powerful tool for both rendering and collision detection.

Suggested Extensions

Implement Sliding - If you've tried the tutorial example you'll find that you don't slide along walls like you do in so many games. This is pretty easy to implement by just apply the x and y axis movement seperately.

Tile based Rendering - Implement a system to rendering a different sprite based on the value in the cells, giving a nice looking map

References

Tutorial written and coded by Kevin Glass
Java is availble from http://www.java.net

Tile Map Path Finding with A Star (A*)

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.

The full package for this tutorial can be downloaded here. The example provided can be tried via Java Web Start here.

The code for the tutorial is here:

Reusable Path Finding Code

PathFinder.java
AStarPathFinder.java
AStarHeuristic.java
Mover.java
Path.java
TileBasedMap.java
ClosestHeuristic.java

Example Game Prototype

PathTest.java
GameMap.java
UnitMover.java

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:

1. At initialization add the starting location to the open list and empty the closed list
2. While there are still more possible next steps in the open list and we haven't found the target:
   1. Select the most likely next step (based on both the heuristic and path costs)
   2. Remove it from the open list and add it to the closed
   3. Consider each neighbor of the step. For each neighbor:
      1. Calculate the path cost of reaching the neighbor
      2. 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)
      3. 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



To demonstrate A* we're going to build the beginnings of a game in which you can move units around on a game map. Different units will be able to move through different terrains and obstacles. The code will show a path from the selected unit to a destination before allowing us to actually move the unit itself.

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