Pixelate:Issue 13/jnrdev

From Allegro Wiki
Jump to: navigation, search
tilebased collision detection and response
Original author: Florian Hufsky (aka no_skill)
zip: jnrdev example

1. Introduction

this is my first online tutorial, so please give me feedback.

this is planned as a series on jump and run development, so more articles will follow, until we have build a complete jump and run with scrolling, tilebased maps, enemy ai and some items.
I have no strict timeline yet, but I want to release my articles monthly on jnrdev and in pixelate.

in this article we will build a simple tile-engine with a player and player-to-map collision detection.

But enough for now, let's get started.

2. Theory

For player-map collision detection I'll use a technique x-tender from halflife 2d and eiswuxe from poke53280 showed me:

separate axis testing (just made up that name)

it's quite simple: first you check for collisions on the x and then on the y axis.

here's an example:

Jnr Theory1.gif
the player before and after collision detection.
the blue box are the players boundaries, we'll use for collisoin checking.
velx and vely are the speed of the player on the x and y axis. note that they won't get that big in game, this would cause errors, but more on that [#problems later].

1. x-axis testing: test on the right side of the new position of the player (because we're moving right)

Jnr Theory2.gif note: only the x velocity is used for calculating the new position

2. y-axis testing: we test on the ground of the new position

Jnr Theory3.gif
for y-axis checking the new position from x-axis checking and the y velocity are used.

3. we're done

Jnr Theory4.gif

this technique is quite accurate and also quite fast, the only problem is speeds higher than the tilesize, because you might miss tiles:

Jnr Theory5.gif
note: in the above example i also used velocities higher than the tilesize, but it made the picture clearer.

you can avoid this problem by either checking the whole path the player traveled through, or limiting the players speed to the tilesize.

I will limit the players speed, because we don't need such high moving speeds in a jump and run, it doesn't look good and who is able to control that game?
but games like PuffBOMB by Mike Kasprzak where such high speeds may occure need to check the whole path (or maybe hamster uses another technique).

3. Implementation

3.1 Data Structures

3.1.1 the map:

struct CTile{
	bool		solid;	//is the tile solid
	_gfxSprite	*spr;	//sprite to draw

class CMap{
		void loadMap(const char *file);		//loads the map from a file
		void draw();

		bool colmapxy(int x, int y){		//test for a collision, note: map coordinates, not pixels!
			return tiles[x][y].solid;


CTile represents a single tile.
all tiles have the same height and width: 20 pixels.

the map currently consists of a 2d array of tiles (32x24), but in a later article we'll use a better structure for bigger maps.
when checking for collisions with the map we'll use colmapxy(), note that the parameters are map coordinates, not pixels.

3.1.2 the player:

class CPlayer{
		void think();		//handle input, collision detection, ...
		void draw();


		bool collision_ver(int x, int y, int &tilecoordx);	//tests for collision with a tile on the
									//vertikal line from [x,y] to [x,y+height]
		bool collision_hor(int x, int y, int &tilecoordy);	//horizontal line from [x,y] to [x+width, y]

		int x, y;		//x, y coordinate (top left of the player rectangle)
		int h, w;		//height, width
		int velx, vely;		//velocity on x, y axis

		bool faceright;		//player facing right? -> graphics
		bool lockjump;		//may the player jump

Jnr CPlayer.gif
x and y are the coordinats of the player, h and w are height and width, which form the blue box: the boundaries used for collision detection.
velx and vely are the velocities (movement speed) on the x and y axis.

the players height and width are currently defined as height=37 and width=11, but we'll read them from a object definition file later on.

3.2 Collision Detection and response

now let's take a closer look at CPlayer::think(), the function that handles everything concerning the player:

void CPlayer::think(){
	velx=0;		//don't move left / right by default

		velx = VELMOVING;		//move right
		faceright = true;		//player graphic is facing right
		velx = -VELMOVING;		//move left
		faceright = false;		//player graphic is facing left
	if(keystates[SDLK_RSHIFT] && !lockjump){	//if the player isn't jumping already
		vely = -VELJUMP;		//jump!
		lockjump = true;		//player is not allowed to jump anymore

first of all we react to the players input.

now the interesting stuff:

	//check for collisions with the map
	int tilecoord;

	//x axis first (--)
	if(velx > 0){		//moving right
		if(collision_ver(x+velx+w, y, tilecoord))	//collision on the right side.
			x = tilecoord*20 -w-1;			//move to the edge of the tile
								//(tile on the right -> mind the player width)
		else			//no collision
			x += velx;
	else if(velx < 0){	//moving left
		if(collision_ver(x+velx, y, tilecoord))		//collision on the left side
			x = (tilecoord+1)*20 +1;		//move to the edge of the tile
			x += velx;

first we check for collisions on the x axis.

if the player is moving right we check against the right side of the player (->collision_ver will be explained later).
and if we find a solid tile on the right side, the player is moved to the side of this tile.

note: i use else if, instead of else so that we don't check on the x-axis if the player isn't moving.

now we check on the y axis:

	//then y axis (|)
	if(vely < 0){	//moving up
		//printf("test: up, vely:%d\n", vely);
		if(collision_hor(x, y+vely, tilecoord)){
			y	= (tilecoord+1)*20 +1;
			vely	= 0;
			y	+= vely;
			vely	+=GRAVITATION;
	else{		//moving down / on ground
		//printf("test: down, vely:%d\n", vely);
		if(collision_hor(x, y+vely+h, tilecoord)){	//on ground
			y	= tilecoord*20 -h-1;
			vely	= 1;				//1 -> we test against the ground again int the next frame
								//(0 would test against the ground in the next+1 frame)

			if(!keystates[SDLK_RSHIFT])		//player only may jump again if the jump key is
				lockjump = false;		//released while on ground

		else{	//falling / in air
			y	+= vely;
			vely	+=GRAVITATION;

			if(vely >= TILESIZE)		//if the speed is higher than this we might fall through a tile
				vely = TILESIZE;

			lockjump = true;		//don't allow jumping after falling of an edge / while in air

this is basically the same as checking on the x-axis, the only difference is that when yvel is 0 the player is falling, this is important when jumping: yvel is 0 at the highest point of the jump.

when we hit the ground and RSHIFT (the jump key) isn't pressed the player may jump again. and if we are in air the player mustn't jump.

and: the movement speed while falling is limited to the tilesize, i [#problems already] explained what happens if the speed isn't limited.

i use collision_hor and collision_ver to check for solid tiles on the horizontal / vertical sides of the player.
this is how it works:

bool CPlayer::collision_hor(int x, int y, int &tilecoordy){
	int tilexpixels = x-(x%20);	//calculate the x position (pixels!) of the tiles we check against
	int testend = x + w;		//calculate the end of testing (just to save the x+w calculation each for loop)

	tilecoordy = y/20;		//calculate the y position (map coordinates!) of the tiles we want to test

	int tilecoordx = tilexpixels/20;	//calculate map x coordinate for first tile

	//loop while the start point (pixels!) of the test tile is inside the players bounding box
	while(tilexpixels <= testend){
		if(map.colmapxy(tilecoordx, tilecoordy))	//is a solid tile is found at tilecoordx, tilecoordy?
			return true;

		tilecoordx++;		//increase tile x map coordinate
		tilexpixels+=20;	//increase tile x pixel coordinate

	return false;

Jnr Code1.gif
this is an illustration to see how collision_hor works.
in this case we would return true after the first tile, because a solid tile was found, but i wanted to show you why we have to differ between map and pixel coordinates.

4. the example

the source example is here: jnrdev1example.zip.

for running the game you will also need SDL.dll, which you can get here: SDL-1.2.6-win32.zip.

for compiling you need the SDL headers, which can be found here: SDL-1.2.6.zip.
note: you have to add some include / library directories if you use VC++, take a look at VisualC.html, which comes with SDL how to do that.

if the direct links to the sdl stuff don't work here's the official sdl site: www.libsdl.org.

you can download the whole article including the example game here: jnrdev.weed-crew.net/downloads/jnrdev1full.zip (100kb).

5. That's it

I hope you enjoyed this article as much as i did writing it and i hope to see you again in the next issue of jnrdev.

Issue 13: The Diet Issue
Exception Handling
jnrdev #1 - tilebased collision detection and response
Interview - Dave Astle