While making a funny little game for the Sega Megadrive, I struggled for a while with colliding with a tilemap. Game engine frameworks that supply collision checking functions for the user have made me soft and weak bellied, clearly.
For my level design, I'm using 16Tile, which exports collision tilemaps as a C array in a text file, and after some experimentation, I noticed the digit in each position corresponded with the index of the tile selected. The sample code and every tutorial I've found only uses solid blocks, but you can use this feature to build slopes and ramps and other shapes into your game levels.
This isn't a SGDK tutorial, the fundamentals and code here can apply to any C or C++ language project.
So, the plan;
- Treat a tileset image as a lookup
- Decorate the map as usual with this tileset
- Use the indexes to figure out which collision is at which location
# Tile format
I'm using this collision tileset for my game, representing all the shapes I need. My tiles are 16x16 and the constants used in this article reflect that.
In your game project, perhaps a "mapCollisions.h" file, paste this Enum (or use #defines or const int's or whatever your poison is).
enum TileType
{
TileBlank = 0, TileSolid = 2, TileSlopeLR = 3, TileSlopeLR2_1 = 4, TileSlopeLR2_2 = 5,
TileSlopeLR3_1 = 6, TileSlopeLR3_2 = 7, TileSlopeLR3_3 = 8, TileSlopeRL = 9, TileSlopeRL2_1 = 10,
TileSlopeRL2_2 = 11, TileSlopeRL3_1 = 12, TileSlopeRL3_2 = 13, TileSlopeRL3_3 = 14,
TileSolidTopHalf = 15, TileSolidBottomHalf = 16, TileSolidLeftHalf = 17, TileSolidRightHalf = 18,
};The indexes in the enum correspond with the entries on the set, if you're making your own or adding to this, you need to ensure the digits line up with the number of each tile. Blank is 0, 2 is Solid, 3 is the first slope, etc. On my tileset here, due to peculiarities of the SGDK/16Tile platform I use, Slot 1 is occupied by a palette and is skipped in the enum. Feel free to ignore/remove this quirk if that doesn't matter to you.
# Storing collision data
Here's a sample scene containing these tiles:
const int16_t E1M1TileWidth = 19;
const int16_t E1M1TileHeight = 16;
const uint16_t E1M1Collisions[304] =
{
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0,
0, 0, 0, 0, 0, 0, 0, 0, 3, 2, 2 ,2 ,9 ,0 ,0 ,0 ,0 ,0 ,0,
0, 0, 0, 0, 0, 0, 4, 5, 2, 2, 2 ,2 ,2 ,10,11,0 ,0 ,0 ,0,
0, 0, 0, 6, 7, 8, 2, 2, 2, 2, 2 ,2 ,2 ,2 ,2 ,12,13,14,0,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 ,2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 ,2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 ,2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 ,2,
};If you squint, you can probably just about make out the mound shape in the center of the map in the numbers.
In my game project, I'm storing a pointer to the map array and the width/height values like this and setting them on map startup;
const uint16_t* LevelCollisionArray; // Pointer to a const uint16_t array, not a const pointer to a uint16_t array.
uint16_t LevelCollisionWidth;
uint16_t LevelCollisionHeight;
void SetMapCollision(const uint16_t* CollisionArray const uint16_t Width, const uint16_t Height)
{
LevelCollisionArray = CollisionArray;
LevelCollisionWidth = Width >> 4; // x >> 4 is equivalent to x / 16
LevelCollisionHeight = Height >> 4;
}
//elsewhere
void E1M1Start()
{
// other stuff
SetMapCollision(E1M1Collisions, E1M1TileWidth, E1M1TileHeight);
// more other stuff
}# Reading the tilemap back
Say you want to read a position from this tile here;
First, you will want to translate the pixel X, Y coordinate from pixel-space into tile-space. Since the tiles we're using are 16px wide, divide the numbers by 16 on each axis and round down to remove the decimal. Our sample pixel is at 161, 155, which translates to [10, 9].
If you are using a 2-Dimensional array in your game, you may directly use these coordinates to read the tilemap data and skip the next step.
const uint16_t tileData = LevelCollisionArray[tx][ty];# 2-Dimensional coordinate in a 1-Dimensional array
If you're using a 1-dimensional array, like myself, you must transform your TX, TY coordinates into an index in the 1-dimensional array. Multiply your Y coordinate by the width of the map and then add the X coordinate to find the position.
// (ty * width) + tx
// (9 * 16) + 10 = 154
const uint16_t tileIndex = (ty * LevelCollisionWidth) + tx;If you ever wish to do the inverse for some reason, modulo by the Width to get the X coordinate and divide (rounding down) to get the Y;
const uint16_t tx = tileIndex % LevelCollisionWidth;
const uint16_t ty = tileIndex / LevelCollisionWidth;Going forwards, I'm wrapping this logic in a helper function;
inline uint16_t CheckMapCollisionTileFast(const int16_t& TX, const int16_t& TY)
{
// this ASSUMES that the TX and TY are within the level bounds. Bad things will happen if they aren't!
return LevelCollisionArray[TX + (TY * LevelCollisionWidth)];
}Here's a complete implementation for reading a slot in the array from any valid pixel postion on the map;
const int TileSize = 16;
const int CollisionShift = 4; // 1 / 16
inline uint16_t CheckMapCollisionTileFast(const int16_t& TX, const int16_t& TY)
{
return LevelCollisionArray[TX + (TY * LevelCollisionWidth)];
}
uint16_t CheckMapCollision(const int16_t& X, const int16_t& Y)
{
const uint16_t tileType = CheckMapCollisionTileFast(X >> CollisionShift, Y >> CollisionShift);
switch(tileType)
{
case TileBlank:
return 0;
case TileSolid:
return 1;
}
return 0;
}This is all you need for collision checking against solid square grid aligned blocks! If you're making a typical 8-bit style platformer game, you can close the page right now!
// in player code maybe!?
const bool FeetSensor = CheckMapCollision(x, y + 1);But if you need slopes, half blocks and more, keep reading, it gets a little trickier...
# And now for shaped tiles
If you recall the tilemap image, many blocks are dedicated to different types of slopes.
We've currently only covered the empty space at the start and the block in the 3rd position.
Working with the other shapes requires a few more steps, as you not only have to figure out what tile your position corresponds to, but also where the pixel relative to that tile lookup lies.
To proceed, you have two main options;
- Read the pixel value from the source image to determine if a pixel is occupied or not
- Mathematically define the collision shape for every single type of tile
I'll leave the implementation of 1. up to the reader as transforming an image into a lookup is a platform dependant operation, and too slow for my needs, but in theory it should be a case of;
- Get the pixel x and y coordinates relative to the tile
- read the value of the source image at that location
- return true if shaded, false if not.
You also have the hidden 3rd option of mixing and matching the two solutions depending on the type of tile if some prove trickier to implement than others.
# Setting the collision handler up to accept shaped tiles
First, lets set up the framework for handling tiles. Modify the collision function to this;
uint16_t CheckMapCollision(const int16_t& X, const int16_t& Y)
{
const uint16_t tx = X >> 4; // This is equivalent to, but faster than X / 16
const uitn16_t ty = Y >> 4;
const uint16_t tileType = CheckMapCollisionTileFast(tx, ty);
// quick return the easy types, same as before
switch(tileType)
{
case TileBlank: // Same as the enums defined above
return 0;
case TileSolid:
return 1;
default:
break;
}
// If the function is still running, calculate the tile pixel
uint16_t px = X % TileSize;
uint16_t py = Y % TileSize;
switch(tileType)
{
// slopes go here
};
};Since we're not dealing with solid blocks anymore, we're calculating the pixel coordinates within the tile we're pointing at and storing it in px and py.
# Basic slopes
Lets tackle the 45" angled 1x1 slopes blocks first.
A decending line in a block can be plotted on a graph like this, with two points of interest marked. The actual digits in game are modulo 16, so would likely be 9,5 and 3,10 or something crazy like that, but it's easier to explain in 0 - 1 scale, the equations remain the same either way.
The surface line on the diagonal splits the box into two segments, one where the X coordinate is always greater than the Y coordinate, and one where the Y coordinate is always greater than the X coordinate.
One dot has the coordinates [0.6, 0.3], the X is larger than the Y, so it's in the top-right half. The other dot has the coordinate [0.2, 0.8], placing it in the bottom-left half.
If this seem backwards to you, remember that in a typical computer coordinate space, Y+ is Negative with 0 starting at the top of the screen/tile, which is the opposite of a normal graph.
Plugging these into the function is a case of translating those concepts to a formula and then placing them in the currently empty switch statement.
switch(tileType)
{
case TileSlopeRL: return py > px; break; // ta da!
}
To calculate the opposite slope, flip the direction of the line. The easiest way to do that is to flip the X input! Any transformation you can apply to a graph, it's often far simpler to transform your input instead. This will be a recurring theme for the rest of this article;
switch(tileType)
{
case TileSlopeLR: return py > (TileSize - px); break;
case TileSlopeRL: return py > px; break; break;
}# Shallow slopes
I'll focus on the decending slopes (x=y) for the rest of the explanations as they're simpler to describe, but for ascending shapes, subtract X from the tile width first to flip the X coordinate as above, the rest of the equation is the same. Full code for both will be at the bottom of the page.
# 2x1 slope
A 2x1 decending slope has the line shape y = x / 2. It's wider, but the basic question is the same. Is our Y coordinate bigger than X?
It can be drawn like this alongside a x = y 1 slope;
Just like y = x / 2 implies, to squeeze the shape into a 1x1 box, divide the X by 2.
To calculate the left tile of the pair, check the input X and Y inside this transformed shape;
case TileSlopeRL2_1: return py > (px / 2); break; // If you're skimming the page, don't do it this way!But in 16-bit land, divide operations are slow, so looking at it from another perspective is wortwhile. x = y * 2 does the same aspect ratio transform, x / 2 and y * 2, creates the same exact magnitude, so we can use that instead;
case TileSlopeRL2_1: return (py * 2) > px; break; // This is better!The right-hand tile requires a little more brain-bending. It's a mostly empty tilewith the slope starting halfway down on the left and concluding at the very bottom-right. Continue the equation as before, adding an entire tile width to the input X to account for the half of the tile we've already covered in the first half.
case TileSlopeRL2_1: return (py * 2) > px; break;
case TileSlopeRL2_2: return (py * 2) > (px + TileSize); And with that you have a half-height slope, ready to go!
# 3x1 slope
This is mostly a repeat of the 2x1 shape, y = x / 3
case TileSlopeRL3_1: return (3 * py) > px; break;
case TileSlopeRL3_2: return (3 * py) > (px + (1 * TileSize)); break;
case TileSlopeRL3_3: return (3 * py) > (px + (2 * TileSize)); break;# Half blocks
If you can mathematically define it, you can check against it. I found it useful to add half-height and half-width blocks to help break up the grid pattern that makes up a tile based game level. For a little half height step up, check that your Y intrudes over the half-way point for a hit. Do the opposite for a block half protruding from the ceiling. For half-width blocks, apply the same logic to the X coordinate.
case TileSolidTopHalf: return py < (TileSize / 2); break;
case TileSolidBottomHalf: return py > (TileSize / 2); break;
case TileSolidLeftHalf: return px > (TileSize / 2); break;
case TileSolidRightHalf: return px < (TileSize / 2); break;I'm not worried about the performance hit of a divide in this case as these numbers are static constants and will be dealt with at compile-time, all the real-time work the CPU has to do is py < 8. Feel free to check the compiler output.
But if your circumstances or peace-of-mind demands it, you can write these in the opposite form. This will likely be a slower approach, as you're introducing a redundant multiply operation.
// wouldn't do it like this personally.
case TileSolidTopHalf: return (py * 2) < TileSize; break;
case TileSolidBottomHalf: return (py * 2) > TileSize; break;
case TileSolidLeftHalf: return (px * 2) > TileSize; break;
case TileSolidRightHalf: return (px * 2) < TileSize; break;# Full code
And as promised, the entire code for this article. Some of the variable names are slightly different, but the logic is the same.
No licence or strings attatched, go nuts, make something cool.
# mapCollision.h
#pragma once
enum TileType
{
TileBlank = 0, TileSolid = 2, TileSlopeLR = 3, TileSlopeLR2_1 = 4, TileSlopeLR2_2 = 5,
TileSlopeLR3_1 = 6, TileSlopeLR3_2 = 7, TileSlopeLR3_3 = 8, TileSlopeRL = 9,
TileSlopeRL2_1 = 10, TileSlopeRL2_2 = 11, TileSlopeRL3_1 = 12, TileSlopeRL3_2 = 13, TileSlopeRL3_3 = 14,
TileSolidTopHalf = 15, TileSolidBottomHalf = 16, TileSolidLeftHalf = 17, TileSolidRightHalf = 18,
};
//
void SetMapCollision(const uint16_t* CollisionArray, const uint16_t Width, const uint16_t Height);
//
uint16_t CheckMapCollisionTileFast(const int16_t& X, const int16_t& Y);
uint16_t CheckMapCollision(const int16_t& X, const int16_t& Y);# mapCollision.c
#include "mapCollision.h"
const int TileSize = 16;
const int CollisionShift = 4; // x >> 4 == x / 16
//
const uint16_t* LevelCollisionArray;
uint16_t LevelCollisionWidth;
uint16_t LevelCollisionHeight;
void SetMapCollision(const uint16_t* CollisionArray, const uint16_t Width, const uint16_t Height)
{
LevelCollisionArray = CollisionArray;
LevelCollisionWidth = Width >> CollisionShift;
LevelCollisionHeight = Height >> CollisionShift;
}
uint16_t CheckMapCollisionTileFast(const int16_t& TX, const int16_t& TY)
{
return LevelCollisionArray[TX + (TY * LevelCollisionWidth)];
}
uint16_t CheckMapCollision(const int16_t& X, const int16_t& Y)
{
uint16_t tileType = CheckMapCollisionTileFast(X >> CollisionShift, Y >> CollisionShift);
uint16_t tx, ty;
// quick return
switch(tileType)
{
case TileBlank:
return 0;
case TileSolid:
return 1;
default:
tx = X % TileSize;
ty = Y % TileSize;
break;
}
// Handle slope tiles
switch(tileType)
{
// Ascending slopes
case TileSlopeLR: return ty > (TileSize - tx); break; // 1:1 slope
case TileSlopeLR2_1: return (2 * ty) > (2 * TileSize - tx); break; // 2:1 slope
case TileSlopeLR2_2: return (2 * ty) > (2 * TileSize - tx - TileSize); break;
case TileSlopeLR3_1: return (3 * ty) > (3 * TileSize - tx); break; // 3:1 slope
case TileSlopeLR3_2: return (3 * ty) > (3 * TileSize - tx - TileSize); break;
case TileSlopeLR3_3: return (3 * ty) > (3 * TileSize - tx - 2 * TileSize); break;
// Descending slopes
case TileSlopeRL: return ty > tx; break; // 1:1 slope
case TileSlopeRL2_1: return (2 * ty) > tx; break; // 2:1 slope
case TileSlopeRL2_2: return (2 * ty) > (tx + TileSize); break;
case TileSlopeRL3_1: return (3 * ty) > tx; break; // 3:1 slope
case TileSlopeRL3_2: return (3 * ty) > (tx + TileSize); break;
case TileSlopeRL3_3: return (3 * ty) > (tx + 2 * TileSize); break;
// Half blocks
case TileSolidTopHalf: return (2 * ty) < TileSize; break;
case TileSolidBottomHalf: return (2 * ty) > TileSize; break;
case TileSolidLeftHalf: return (tx * 2) > TileSize; break;
case TileSolidRightHalf: return (tx * 2) < TileSize; break;
default:
return false;
break;
}
}