Tile Based Game Tutorials

Collision Detection And Response

This example presents some simple collision detection and response in a tile based environment. It uses a lookup table of routing functions to connect the red square with the appropriate collision methods to resolve collision with the specific tiles he is touching. I realize that's not a very straight forward way to explain how things work, so I'll go into greater detail below. First check out the example, though. Click or double tap to jump and notice how the red square gets caught on adjacent solid tiles:

I'll address the seeming glitch later on, but before I can do that, let me explain in more detail how the system works. Any tile based world is made up of rows and columns and ultimately individual tile spaces. You may not have realized it, but this is actually a naturally occurring spatial partitioning system that we can use to speed up collision detection a great deal by ruling out intensive broad phase collision detection methods. We don't need to check if the red square is colliding with ALL the tiles on screen because we can figure out exactly which one's he is colliding with just by calculating his row and column in the map to see which tiles are right under him.

Because tile maps are essentially a spatial partitioning system, it's super easy to look up which tiles the red square is interacting with at any time. To get the tile value under a specific point you can use this code:

var column = Math.floor( object.x / tile_width );
var row = Math.floor( object.y / tile_height );

var value = tile_map[ row * map.number_of_columns + column ];

The value variable will give you the tile value of the tile at the row and column occupied by the object and you can use row and column to calculate the tile's physical position in the map. But how do we use this data to detect collision? Well, in effect, this is the broad phase collision method. All we know from the code above is that the object is colliding with a tile space that has a certain value. But that tile could be a slope tile, or a half tile or some other shape with empty space in it and although the object may be in the tile's personal space, it might not be touching the collision shape inside. All we have here is a super simple broad phase collision detection method with no resolution. But for 3 lines of code, that's some pretty sweet broad phase, right?

Now that you know the location and value of the tile space the object is occupying, you can move onto the next step, which I'm going to call routing. The routing part of this technique simply utilizes a lookup table stocked with a unique function for each type of collision shape. So, say the red square is on a tile with a value of 2. You just hand 2 to the lookup table and it gets the appropriate function to use. You could actually just put your collision code right into the functions in the lookup table, but I took it a step further. And here's why:

Each tile has four sides, right? To be more specific, each tile space has four sides. For instance, a platform tile might have one actual collision surface on the shape itself, but an object can still approach it from the top, left, right or bottom or some combinations of those. I wanted a collision engine that could reuse collision functions between tiles instead of having one beastly chunk of code for a complex tile. For example, look at this code which depicts the routing function and the final collision functions for a solid tile:

2: function( object_, row_, column_ ){
	doTopCollision( object_, row_, column_ );
	doBottomCollision( object_, row_, column_ );
	doLeftCollision( object_, row_, column_ );
	doRightCollision( object_, row_, column_ );
}

The wrapper function is the routing function. In the scenario I gave before, the red square was in a tile space that had a value of 2, so the lookup table goes to function 2 with the object, row, and column parameters and then calls the specific collision functions needed to resolve collision between the red square and collision tile 2. A solid tile has four physical sides so we call four collision functions that handle narrow phase collision detection and response for each side.

The benefit of this approach is that the collision engine itself is EXTREMELY modular. You can add completely new shapes just by adding a new function to the lookup table and use a combination of existing narrow phase collision functions to do the final resolution. And those functions can look like anything you want: slopes, curves, flat surfaces... Well, there's not a ton of options, but you could add other functions as well, like levers, spiky floor tiles, water, whatever. It's as easy as putting a new function inside the routing function. I guess you could put all the collision code right into the routing function, but then you'd be redefining functions like doTopCollision for every tile that has a flat surface on top. And that's fine if you want to tweak the code a little. You can pretty much do whatever you want because collision code for one tile isn't dependent at all on other tiles.

Now I can finally address those solid tiles and why they make the red square stick to them. If you looked at that routing function code, you'll notice that collision starts on the top side, goes to the bottom side, then left and right. This is because we want to separate our axes. If you've researched the topic elsewhere you might have seen the phrase "y-first check" or "y-first collision detection". You want to do collision on the y axis first if your objects mostly move over the tops of tiles, and they usually do. You jump up and fall down in most games. Collisions with the left and right sides of tiles aren't nearly as common as top and bottom collisions. With that in mind, consider what happens when your object is sitting on top of two adjacent tiles. The first tile will push him up out of the collision, resolving collision on the y axis. The second tile will now no longer have the option to push him up because the other tile pushed him out of y range. This leaves only two options: resolve collision on the x axis or do nothing if no collision exists. This functionality causes the object to get stuck between adjacent square tiles.

The behavior is even more prevalent when falling down the side of a wall of solid tiles because the first collision check happens on the y axis. The tiles don't know they're part of a wall, they just know how to resolve collision as if they were a solitary tile. If an object passes through the top side of one of the tiles, collision will be checked on the y axis first and likely return a valid collision if the object is moving up or down through the top or bottom of the tile. This causes the object to get stuck on the tile's top or bottom edge rather than sliding along the left or right side smoothly.

But never fear! There's an easy way to overcome this annoying behavior. All you have to do is not place tiles with conflicting edges next to one another. You can achieve all the tile shapes you need by mixing and matching edges and the result is super smooth collision. Of course you would never want to use this method for a level comprised of only solid, four sided tiles because you need 15 different combinations to simulate one solid tile this way. But the benefits of this approach for adding in slope tiles and other odd shaped tiles are well worth the tedium of coding the extra 14 tile types.

There's one last thing to cover and that's the collision code itself. This is ridiculously simple when you do it one side at a time. So, imagine that your object is falling down and you want to keep him from falling off the bottom of the screen. How do you stop him from disappearing into the unknown? Simple:

/* Assuming 256 is the bottom boundary of the screen. */
if ( object.y + object.height > 256 ) {
	object.y = 256 - object.height;
	object.velocity.y = 0;
}

Well, that's pretty much as simple as it gets, but how does it translate to tiles? Pretty much like this:

function collideWithTopOfTile( object_, top_ ){
	if ( object_.velocity.y > 0 && object_.y + object_.height > top_ ){
		object_.y = top_ - object_.height;
		object_.velocity.y = 0;
	}
}

The value of top_ will have to be calculated in the routing function of course, but it's that simple. The other sides are basically just variations of that extremely straight forward function. And that's it for this tutorial! Be sure to take a look at the source code and the next example, which covers slope tiles.

Game Loop Source Slopes

Index