Alex Russell's Game Programming Tutorial using DX

Introduction . Chapter 1 . Chapter 2 . Chapter 3 . Chapter 4 . Chapter 5 . Chapter 6 . Chapter 7

Chapter 6

Collision Detection

Often in a game the program needs to detect when one object hits another object, for example ball hits a brick, or a bullet hits a monster. Detecting these situations is called collison detection. The simplest way to do collision detection is to use simple geometric aproximations of the objects colliding. The monster can be represented by a rectangle, and the bullet by a point. Then the math to detect a collsion is very simple. 

typedef struct
	{
	int x, y;
	}
point_t;

typedef struct
	{
	int x0, y0, x1, y1;
	}
rect_t;

point_t p;
rect_t r;

p.x=100;
p.y=100;

r.x0=50;
r.y0=50;
r.x1=150;
r.y1=120;

// check that a point is in a rectangle
if ( p.x >= r.x0 && p.x <= r.x1 && p.y >= r.y0 && p.y1 <= r.y1 )
	{
	// it has hit
	}

// and how to check that the pixel is NOT in the rectangle
if ( p.x < r.x0 || p.x > r.x1 || p.y < r.y0 || p.y > r.y1 )
	{
	// point is not in the rect
	}

rect_t  r1, r2;

// Check for rectangle r1 in rectangle r2
if ( r1.x0 >= r2.x0 && r1.x1 <= r2.x1 && r1.y0 >= r2.y0 && r1.y1 <= r2.y1 )
	{
	// r1 is in r2
	}

//This checks for r1 NOT in r2
if ( r1.x0 > r2.x1 || r1.x1 < r2.x0 || r1.y0 > r2.y1 || r1.y1 < r2.y0 )
	{
	// r1 does not touch r2
	}

Special Cases

If the rectangles to be checked are tiled you do not check each tile one after the other. Instead you directly calculate which tile the point is on. 

int w;    // width of tile
int h;    // height of tile
int tile_x, tile_y;
point_t p;

p points to a pixel. We want to know which tile it is on. Each tile has its own (x, y) coordinate where each tile is counted as 1 coordinate value. 

tile_x=p.x / w;
tile_y=p.y / h;

Pixel-wise Collision Detection

Usually comparing one rectangle to another gives a close enough collision for a game, but when collision must be accurate to the pixel because of irregular shaped sprites you can compare the bitmaps using pixel-wise collision detection.

Only one colour is transparent in a sprite, and if you use zero it simplifies pixel-wise collision detection because you can then test for collisions using the logical `and' operation. If speed is more important than memory used then you can create bitmasks for each object that will collide. Most bitmaps are 16, 24, or 32 bits which means you would have to compare multiple bytes per pixel. If you create a mini-bitmap that only uses one bit per pixel the compares can be done much faster. Of course this uses more memory, and you would want to write a utility to automate making these bitmasks.

Sometimes you can also check for collisions by checking the colour of the pixels on the screen under the moving object. This generally only works for games with simple artwork.

http://www.gamedev.net/ has good articles on collision detection.

Game Timing

Computers all run at different speeds, but we want our games to run at the same speed on any computer. This requires adding code to the game to make sure everything happens at the correct time. In general the game code is split into two parts, the drawing code and the logic code. The drawing code simply draws everything as fast as it can. The logic code is written to make sure all objects, events, etc... all happen only when they should happen. to time events we need a source of time that is independent from the cpu clock rate. As it happens all PC's do have a timer that runs at the same rate. There are a number of win32 timing functions but the simplest one to use is timeGetTime() which returns a DWORD containing the number of milliseconds since windows started. It isn't super accurate (especially under win9x) but is works well enough for simple games.

There are two main situations, the computer is too fast, or the computer is too slow. If the computer is quick you just don't move anything in the logic code until its time comes up. For example we have a pixel moving right, but we want the speed to be constant on any computer (note this code is to demo the timing idea, and has never been compiled): 

typedef struct
	{
	int x, y, dx;
	DWORD speed;
	DWORD next_time;
	}
pixel_t;

pixel_t pix;

pix.x=0;
pix.y=20;
pix.dx=1;
pix.speed=20;
next_time=0;

while ( !done )
	{
	if ( timeGetTime() > pix.next_time )
		{
		pix.x+=pix.dx; // move it
		pix.next_time=timeGetTime() + pix.speed;
		}

	ClearScreen();
	Pixel(pix.x, pix.y, RGB(0,255,0)); // draw the pixel
	}

This code will draw a pixel slowly moving to the right. If a fast computer runs this code the if() statement will not move the pixel until it is the correct time. the call to Pixel() will simply re-draw the pixel at the same place until it is time to move.

If a computer is too slow to draw everything as fast the logic dictates, then we must run the logic for the game in a loop, without drawing, to catch up then re-draw everything. Code for a real game handles both these situations at the same time. 


DWORD master_time, now, catch_up;

master_time=timeGetTime();
while ( !done )
	{
	now=timeGetTime();
	catch_up=now - master_time;
	while ( catch_up-- ) // run the logic once for each 'tick' we missed while drawing
		{
		if ( now > pix.next_time )
			{
			pix.x+=pix.dx; // move it
			pix.next_time=now + pix.speed;
			}
		}

	master_time=timeGetTime();
	ClearScreen();
	Pixel(pix.x, pix.y, RGB(0,255,0)); // draw the pixel
	// in a real game all the drawing could take a while, master_time would
	// allow us to notice that more than one 'tick' has passed
	}

Introduction . Chapter 1 . Chapter 2 . Chapter 3 . Chapter 4 . Chapter 5 . Chapter 6 . Chapter 7

Copyright 2004 (c), Alex Russell, All rights reserved