Alex Russell's Dos Game Programming in C for Beginners

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

Chapter 5

Collision Detection

Collision detection is figuring out when one object has hit another. For example you want to know when a bullet travelling across the screen has hit one the of sprites that represents an alien craft. We will cover the basics of collision detection in detail, and advanced methods will only be discussed briefly.

Detecting a point in a rectangle.

This is simple, the point is in a rectangle if both its x and y coordinate are within the rectangle.

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;

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 r1 in 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.

Sometimes you cam 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. This site also has articles: Ziron

Colour management

Mode13h supports 256 colours selected from almost 300,000 colours. The BIOS can be used to set the current palette of colours, but as usual that is the slowest method. The palette can be set by directly using the ports on the VGA. To prevent snow and flicker the palette is only changed during the vertical blank.

This is the code to set the whole palette.

unsigned char palette[768];   // 256 colour, 3 bytes each = 768 bytes

void set_palette(unsigned char *p)
{
// wait for vertical re-trace
	while ( inportb(INPUT_STATUS_0) & 8 )
		;
	while ( !(inportb(INPUT_STATUS_0) & 8) )
		;

asm   {
         /* set palette, taking advantage of the auto-increment feature */
         xor   al, al	// set al to zero, the first colour to set
         mov   dx, 03c8h	   // port for the vga palette control
         out   dx, al	  // tell the vga we want to change colours, starting with zero
         mov   cx, 768	  // number of bytes to send
         mov   si, p	  // si points to the colours to copy over
         mov   dx, 03c9h   // port to send the colours to
         rep   outsb     	   //  send the palette values over
         }
}

And to set part of the palette. Start is the first colour to be changed, and num is the number of sequential colours to set.

/* ---------------------- setvga_part_palette() ---------- March 28,1993 */
void setvga_part_palette(char *p, short start, short num)
{

   p+=start*3;
   num*=3;

   	// wait for vertical re-trace
	while ( inportb(INPUT_STATUS_0) & 8 )
		;
	while ( !(inportb(INPUT_STATUS_0) & 8) )
		;

   asm   {
         /* set partial palette */
         mov   ax, start
         mov   dx, 03c8h
         out   dx, al
         mov   cx, num
         mov   si, p
         mov   dx, 03c9h
         rep   outsb
         }
}

Where do you get palettes? You extract them from the drawing files. The VGA palette only uses 6 bits for each RGB value, but most files store them using 8 bits. If you load a palette and all the colours are wrong then you can often correct this by shifting each RGB value to the right by 2 as was done in the PCX file reading code.

Being able to change the palette as you wish allows you to use a wider variety of art and colours making your game more interesting. It is important to plan the use of the 256 colours that are available. One idea is to reserve the first 16 colours for common elements that appear throughout the game, for example the colours used in the user interface. You also might want to reserve colours for special effects like colour cycling.

Colour Cycling

Colour cycling is a technique that gives the illusion of movement by changing the palette rapidly. Usually a set of colours is set to gradually change from a start colour to a middle colour, and back to the start colour. If you then draw a filled rectangle with one of these colours and cycle the colours the rectangle will appear to rotate. Colour cycling can be used for water and fire effects also. To cycle colours means to move all the colours in the set forward by one, and move the last colour back to the beginning. This is repeated at regular intervals.

Code to cycle a set of colours.

/* do colour cycling, starting with color start, num sequential colors */
/* ---------------------- cycle_palette() ---------------- March 28,1993 */
void cycle_palette(short start, short num)
{
   BYTE t[3];
   short x1, x2, len;

   num--;
   len=num*3;


   x1=start*3;
   x2=len + x1;

   /* cycle the palette  */
   memcpy(t, palette+x1, 3);
   memmove(palette+x1, palette+x1+3, len);
   memcpy(palette+x2, t, 3);

   /* set new palette */
   num++;
   setvga_part_palette(palette, start, num);
}

Timing a game, and game design

Time spent planning your game will save you huge amounts time and effort with the programming. Before starting ANY programming plan out your game. Think about what data elements you will need to track, how the user will control the game. What functions and systems will be required to draw the game, and calculate all the game logic. Often you will want to write tools to speed up development of your game, e.g. level editors.

One thing that will greatly simplify game design, and making additions to the game, is to separate the drawing of the screen from the game's logic. By logic I mean any code that moves things, calculates things, times things, or otherwise controls the game.

Testing is an important aspect of any programming project. The best way to test a new function is to plug it into a SMALL test program before adding it to the main program code. Always make test code as simple as possible so that you are testing the new code, not the test stub.

Another concern is to time things so that the game runs at the same speed on computers of different speeds. This is done by using a timer on the PC that runs at the same speed on all PC's. One easy to use timer for DOS games is the BIOS TICK. This is an unsigned long integer that increases by one 18.6 time per second.

// PC bios data area pointer to incrementing unsigned long int
#define TICKS	    (*(volatile unsigned long far *)(0x0040006CL))

In practice this timer is a bit on the slow side to provide smooth animation. The PC also provides a timer that can generate an int8 at programmable intervals. We can then hook an ISR to this interrupt and use it to time all the game events. Many PC music and sound packages also use this interrupt and provide some sort of timing function. Do not change the int8 timer if using a music package that is also using the int8 service.

NOTE: the int8 timer is used to time many DOS and BIOS functions. The old timer interrupt should be called at approximately its original rate of 18.6 times per second.

Installing an int8 timer, and programming it to run at 60Hz

volatile unsigned long fast_tick, slow_tick;
static void interrupt (far *oldtimer)(void);   /* BIOS timer handler */

void deinit_timer(void);


/*

   You don't have to call the old timer, but if you don't
   you have to write some code to cleanup in de-init that
   fixes DOS's internal clock.

   Its also considered 'good form' to call the old int.
   If everyone does, then everything that other TSR's etc...
   may have installed will also work.

   If you skip the little chunk of ASM code- the out 20-
   you WILL LOCKUP all interrupts, and your computer

   Anyways, this test replacement just increments a couple of
   long ints. 
*/
/* ---------------------- new_timer() ------------------- August 23,1994 */
static void interrupt new_timer(void)
{
   asm cli
   fast_tick++;

   if ( !(fast_tick & 3) ) // call old timer ever 4th new tick
      {
      oldtimer();  // not the best way to chain
      slow_tick++;
      }
   else
      {
      // reset PIC
      asm {
          mov al, 20h
          out 20h, al
          } 
      }

   asm sti
}


/* see that 1st line of inline asm?

   to set whatever clock speed you want load
   bx with 1193180/x where x is the clock speed you want in Hz.

*/
/* ---------------------- init_timer() ------------------ August 23,1994 */
void init_timer(void)
{

   slow_tick=fast_tick=0l;
   oldtimer=getvect(8); // save old timer

   asm cli

   // speed up clock
   asm {
      	mov     bx,  19886     //  set the clock speed to 60Hz (1193180/60)
      	mov     al,  00110110b
    	out     43h, al
      	mov     al,  bl
	out     40h, al
    	mov     al,  bh
      	out     40h, al
      }

   setvect(8, new_timer);

   asm sti
}


/* ---------------------- deinit_timer() ---------------- August 23,1994 */
void deinit_timer(void)
{
   asm cli

   // slow down clock   1193180 / 65536 = 18.2, but we use zero

   asm {
      	xor bx,  bx          // min rate 18.2 Hz when set to zero
    	mov al,  00110110b
      	out 43h, al
	mov al,  bl
    	out 40h, al
      	mov al,  bh
	out 40h, al
      }

   setvect(8, oldtimer);  // restore oldtimer

   asm sti

}

Now that we have a timer how is it used to time things? For each element in the game that must be timed we store a number that indicates the NEXT time it should move. This number is set by getting the current time, and adding to it.

Example of timing the movement of a pixel

int x,y;  // pixel location
int dx, dy;  // speed of pixel
unsigned long next_time;
int done=0;
int loop;

x=100;
y=100;

dx=1;
dy=1;

next_time=fast_tick + 3;  // fast tick is incremented by the int8 ISR

while ( !done )
	{
	// if the computer is quick, we may draw the pixel many times without moving.
	if ( fast_tick >= next_time )
		{
		// if the computer is slow, we may have to move the pixel more than once
		// for it to be were it belongs
		loop=fast_tick - next_time;
		
		while ( loop-- )
			{
			x+=dx;
			y+=dy;
			}

		next_time=fast_tick + 3;
		}
	
	put_pixel(x,y, 5);
	update_buffer();
	}

This timing technique causes slow computers to keep up by `skipping' frames (also referred to as `dropping' frames). The animation will not be smooth, but things will move at the correct speed. Usually you should try to aim at your game running at about 60 frames per second on whatever computer is current without skipping frames. 30 frames per second is the minimum for smooth animation.

Chapter 5 Exercises

1. Write a program that draws a filled rectangle in the centre of the screen, and bounces one pixel. If the pixel hits the centre rectangle it will bounce, and the rectangle will change colour.

2. Write a program that draws a filled rectangle in the centre of the screen, and bounces one pixel. If the pixel hits the centre rectangle it keeps going straight, and the rectangle changes colour until the pixel is no longer touching it.

3. Write a program that bounces 3 small sprites. The spites will bounce off the `walls' and each other.

4. Write a program that fills the screen with rectangles as wide as the screen that alternate with two colours. When the space bar is pressed have the second colour change to the first colour. A second press of the space bar restores the original colour.

5. Write a program to extract the palette from a PCX file, and store it to a second file.

6. You have written a game that has a information screen at the bottom, and the top displays a playing field that changes dramatically with each level including changing all the colours used. What will happen to the bottom score board when you change levels?

7. Write a program that changes the colour of a solid rectangle using colour cycling.

8. Write a program that makes a series of narrow rectangles appear to scroll using colour cycling.

9. Write a program that bounces one sprite on the screen. Pressing Q will speed it up, Pressing A will slow it down. Use a timer to control its speed. How else could you change its speed?

10. What are three (of many) things you should plan before starting programming a game.

Click here for chap5.zip (18 KB)

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

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