Tile based collision techniques

Having only ever written 3D games before, I thought it would be fun to use SDL2, Tiled and TMX to clone some classic arcade games - and it is! I started with Sokoban, then Pacman and I’m currently working on Gradius.

Collision detection in Sokoban and Pacman was easy: a tile was either solid or it empty. However for Gradius this wasn’t good enough as there are many angled surfaces like the mountains on Stage 1. The tiles used for these surfaces are “semi-solid” i.e. there are empty parts of the tile and solid parts. The naive intersection test just detected a collision between the ship and the ground if the tile was non-empty (gid != 0)

I ripped the tilemap and tileset from Gradius using the graphics mode (F4) in MAME to view the tile map as I scrolled through the level. I stuck them together end to end, then used ImageToMap.py and MapWriter.py to convert to .tmx files. Great little scripts!

From this I noticed that not all of the tiles in a tilemap (layer) should be collidable. The grass should be pass through. So in the Tiled tileset I added a property to tiles I didn’t want to be solid: Solid = “false”. This allowed the ship to fly through the grass, but it was still colliding with the part-solid tiles.

I found a great post “The Guide To Implementing 2D Platformers” by Rodrigo Monteiro which describes how 2d platform games such as Megaman store a left and right height per tile to allow movement over smooth slopes. I thought this technique would be applicable here, so I used the Tiled Collision Editor to add a line per part-collidable tile. This is the top left mountain tile:

This allows a plane to be calculated at runtime for each semi-solid tile (normal, distance) which can be easily intersected against the ship hitbox (2D AABB) for accurate ship-ground collision detection, using a SignedDistance(AABB, Plane) function (like Real Time Collision Detection p164)

This all works well, but I’m not sure if it’s the standard approach for 2D games. I just wondered how other users are doing collision detection in their tile-based games? Something inside me says it might be easier to use a collision mask bitmap or something more “2D”, which might allow pixel-perfect collision detection.


Well, your own link to Rodrigo Monteiro’s guide (very nice read, btw) already showed you there is no standard, just a lot of different approaches. For your use-case, I would definitely also consider using a collision mask since your tiles seem to be usable as such already. This means it would come at no memory overhead and no need for setting up all those lines.

Personally, I’ve implemented both solid-tile collision systems and a collision system where you could indicate for each tile from which of its 4 sides it was blocked. For the latter I used a special tileset which featured the 16 variations:

(this was used for example in Blues Brothers RPG - GitHub)

For anything more complex I’d probably opt for using a physics engine like Box2D.

How is this normally implemented? Would I take a copy of the tileset.png in photoshop and manually convert to a “black and white” mask (removing non-collidable trees etc), or are you implying I use the tileset.png as is and use the Solid tile property to mark totally-non-solid tiles?

I’ll have a look at the Blues Brothers RPG for the latter. Could you please explain what you mean by the former - is itjust the Sokoban/Pacman case in which a tile is completely solid or completely empty?


I think with your graphics you do not need to create a separate black & white image. You’d just need to iterate the overlapping pixels of two objects and when any pair of pixels are both opaque you got a collision. Before this, you’d use rectangle intersection to determine if it makes sense to start checking pixels at all of course. Now, if you’re using hardware accelerated rendering then accessing pixels is going to be slow, so in that case you could put a copy of the relevant data in plain memory.

Exactly. And here, even the latter system was still pretty simple because I only allowed movement from one tile to the next, rather than free movement. It’s implemented in Object::walk.

I later also wrote a free movement system with full blocking tiles, where the player rectangle can be smaller than a tile. You can find this code in the CollisionHelper of the Tales client.

I’m not particular proud of this code though. Especially the latter has so many similar blocks, just to deal with x, y and negative and positive cases. But it’s much more efficient than using a physics library, at least.