Tile Map Collision Detection, Part 1

This two part series will go over the details of handling tile map collisions. For some reason, there really aren't any good, generic guides on the web that detail tile map collisions despite all the games out there that utilize tile maps. Today that changes.

If you found this post chances are you have come across what I think is the best tile map guide (besides this one of course): The guide to implementing 2D platformers. It provides a nice overview but it doesn't really get into the details. Note that a full example in C# is available in Nez via the TiledMapMover.

Physics Engines are the Devil

Lets just get this out of the way now: don't use a physics engine if you are making a platformer. Lots of newbies go with a physics engine because it's just stupidly simple to get started: apply a force and let the physics engine do the rest. Physics engines should be used only when you are emulating reality or your gameplay revolves around physics. Most games do not emulate reality so there is no point in using a physics engine. You'll never be able to own your games feel unless you take control of it. Don't hand off the feel of your game to a squirrely physics engine.

Basic Collision Detection (no slopes)

The algorithm for collision in the absence of slopes is quite simple once you see how its done. We aren't going to get into parsing or rendering a tile map here so it is assumed that you have that part covered. We'll be using an axis aligned bounding box (AABB) for our player as is often the case. Our AABB has a little trick up it's sleeve though and this is key to keeping the collision detection so simple.

The AABB Trick Defined

We are going to break our AABB up into 4 AABBs. This simple trick makes collision detection way easier and at the same time gives us some neat side effects for free. We will use a different AABB based on the direction of movement (up, down, left, right). When moving right we slice the AABB in half and use the right half of the AABB. And now for the trick: we shrink the collider a few pixels vertically. This is best explained with an image:

Take notice of how we shrink the collider a bit in the opposite plane of movement. You may be wondering how exactly this is going to help us. There are 2 main problems this solves:

  1. when we gather the interesting tiles to look at in more detail we use the shrunk AABB. Because it is inset a bit we don't have to worry about snags when the AABB is directly adjacent to a tile.
  2. free polish! Because we inset the AABB if the player misses a jump by just a small bit they will automatically get pushed up onto the platform. There is no need to specifically code this behavior into your algorithm!

Here is an image showing the "almost made it" behavior in action. When collisions are resolved the player will end up getting bumped up onto the black platform even though they missed the jump by a few pixels:

Resolving Collisions

Now that we have the background covered lets see how we actually handle collision detection.

  • break up movement into x and y components. We will step the x direction first (this is important later when we implement slopes).
  • fetch the AABB for the direction of movement that we will be using. Expand the AABB by the amount of movement in the direction of movement.
  • use the AABB to get all the intersecting tiles. The order that we get the intersecting tiles will be important when we handle slopes but isn't important if slopes aren't in the picture.
  • loop through the tiles. If we find a solid tile we have a collision. Move the AABB just enough to not be intersecting.
  • repeat these steps for the y direction

Let's take a look at an image depicting the collision to solidify the principles with a visual.

Our AABB consists of the red, blue and green boxes. Remember it is the normal AABB for this side (red box) expanded by delta movement (blue and green boxes). The green box depicts the overlap and the blue box shows how much we will actually move.

The numbered tiles show all of the tiles our AABB intersects in the order that makes sense for horizontal movement (closest to our forward edge first, top down). When we loop through the tiles we will have no collision for 1 and 2 since they are empty then 3 will trigger a collision and break the loop. We use the tile left edge to get our collision point.

The algorithm in pseudocode:

def move( motion ):  
  # get bounds in x direction
  AABB = collisionRectForSide( direction, motion.x )
  # check for a collision
  if testMapCollision( AABB, direction, out collisionResponse ):
    # respond to the collision
    motion.x = collisionResponse - bounds.side( direction )

  # get bounds in y direction
  AABB = collisionRectForSide( direction, motion.y )
  # check for a collision
  if testMapCollision( AABB, direction, out collisionResponse ):
    # respond to the collision
    motion.y = collisionResponse - bounds.side( direction )

def testMapCollision( AABB, direction, out collisionResponse ):  
  get all relevant tiles (populateCollidingTiles)
  # check all tiles for a collision
  for each tile:
    if tile is not null and testTileCollision( tile, direction.opposite, leadingPosition, out collisionResponse ):
      return true

def testTileCollision( tile, edgeToTest, leadingPosition, out collisionResponse ):  
  # without slopes this is pretty basic. Just set collisionResponse to the side of the tile opposite movement
  collisionResponse = tile.position( edgeToTest )
  return true

def collisionRectForSide( side, motion ):  
  return bounds for side expanded by motion

def populateCollidingTiles( AABB, direction ):  
  return tiles intersecting AABB ordered with nearest tiles first