Mark is coauthor of Tricks of the Game Programming Gurus (SAMS Publishing, 1994). He can be reached at [email protected].
The center of gravity in computer games is rapidly moving to three-dimensional, first-person games with light-shaded, texture-mapped polygons. However, the basic programming concepts and skills behind most games generally remain the same. To illustrate some of these concepts, I'll present a two-dimensional (2-D) game engine (Figure 1 is a typical game based on this game engine), borrowing ideas from classics such as Space Invaders and Galaxians. With some work, however, it could be made to resemble one of the more-recent games, like Raptor.
The game engine consists of a number of modules, including those that handle VGA and keyboard routines, animation, and file management. Table 1 lists the code modules (available electronically; see "Availability," page 3) that make up the game engine. All code was developed and tested using Borland C++ 3.1, but I made every effort to keep the code compiler neutral. The code should compile under 32-bit Extended DOS (with the Watcom compiler) with some minor changes.
The Keyboard
The system BIOS includes an interrupt handler to manage keyboard input. The BIOS responds to a keyboard interrupt by reading make/break (press/release) codes and storing them in a modest 16-character first-in-first-out (FIFO) buffer. The majority of applications make calls to the BIOS routines via the operating system. The BIOS routines return the keycodes sequentially from this buffer. As an added bonus, most flavors of BIOS include a typematic feature whereby, if a key is held down for more than half a second, the make codes are repeated automatically.
At first glance, this would appear to be a workable method for managing keyboard input. However, consider what happens when a key is held down for several seconds: The BIOS receives a stream of key codes that quickly overflows the 16-character buffer. The BIOS then begins to sound rather annoying beeps on the system speaker. This is hardly a feature you'd like to include in a game.
Your first task, then, is to write a routine that disables the BIOS keyboard interrupt handler. This simply requires a new interrupt handler that avoids key-code buffer overruns. Instead of storing actual key codes in a buffer, I'll use a 128-byte array to store the current status of each key. Each key is either currently pressed or released.
Example 1 shows what the new interrupt handler looks like. Notice that I've declared a function pointer, OldInt9, that saves a pointer to the original BIOS interrupt handler. This way you can restore the interrupt upon exiting the game.
Video Display
The game engine is designed around the standard VGA video mode 13h (a good video mode for games due to its simple memory organization). This mode is supported by all VGA-compatible video adapters. Admittedly, the 320x200 resolution is a bit low given today's Super-VGA hardware, but this drawback is more than offset by the ability to display 256 unique colors.
In mode 13h, a pixel is drawn by writing an 8-bit color value to a 64-KB memory window at physical-memory location A000:0000. Each byte represents a single pixel. Drawing pixels is simple and fast--you merely set a far pointer to this window and dereference the pointer as if it were an array.
The video BIOS provides many useful routines. The engine includes a module, vga.c, that encapsulates the BIOS calls you'll be using. In addition, the module includes routines for tasks such as reading a 256-color palette from disk.
PCX Files
Next, you need routines for reading bitmapped images. These bitmaps will be used as sprites by the game engine. PCX is supported by most paint programs, and source code is readily available for reading images stored in this format. For these reasons, all the sprites used by the engine are stored on disk as 256-color PCX files.
Sprites
At this point, you need to develop data structures for the sprites to keep track of the visual elements of the game. There are two basic classes of sprites in the game engine--actors and missiles. Actors are the bad guys and can have complex behavior such as dive-bombing players or shooting missiles. Missiles are quite simple, marching along a fixed path until either they hit a target or disappear off the screen.
You'll also want to keep track of some additional information for each visual element: current location, current direction, and type. The actor type will need a few additional fields (to be discussed in a moment). Example 2 shows the player, sprite, and missile data structures. Sample sprites (in PCX format) are available electronically.
Linked Lists
You may have noticed the field next in the actor and missile data structures. This field is needed so that you can build linked lists of these data types. The drawback of using linked lists is that they are more difficult to implement than, say, an array of data structures. But for this game, you'll need the ability to create and remove list items, namely actors and missiles, on-the-fly. While this can be accomplished with an array, it is handled much more efficiently with a linked list.
The sprite list-management code is in the module sprite.c (available electronically). This is a relatively straightforward implementation of a linked-list data structure using dummy nodes for the head and tail. All of the basic list operations are supported, including insertion, deletion, and list iteration.
The engine implements list iteration by means of the ForEachActor() and ForEachMissile() functions, which take, as a parameter, a pointer to a user function to apply to each list item. The user function itself takes, as a parameter, a pointer to a list item. Also present are FirstActor() and NextActor(), which allow for more complex processing.
Some Animation Basics
The engine uses several basic animation techniques, the first of which is double buffering the video screen. To implement double-buffering, you allocate memory for a 64-KB buffer during program startup. Next, you design all of the custom video routines to draw to this off-screen buffer. After image composition is complete, the buffer is copied to the screen in one large chunk during vertical retrace.
The main goal of double buffering is to minimize the number of times you access video memory. Because writes to video memory are generally slower than writes to system memory, this usually results in faster animation. An added benefit is that double buffering can be used to minimize image flicker, since all image composition takes place off-screen.
The second animation technique is masked image copying, sometimes known as "AND-XOR animation." This technique makes it possible to draw the sprites with transparent colors. Why do you need transparent colors? Consider a typical sprite bitmap. The bitmap shape is almost certainly not a rectangle, but bitmaps are stored in rectangular blocks of memory. If we simply copied the sprite bitmap to the display, the black edges of our bitmap would overwrite and obscure any image underneath the new sprite.
To implement a masked bitblt, you need both a bitmap image and image mask. When drawing the bitmap, you first copy the image mask to the double buffer performing a bitwise AND to the double-buffer contents and the image mask. The bitmap itself is then drawn to the double buffer using a bitwise XOR operation. The result is that background images can be seen through the transparent regions of the sprite.
Which leads to the obvious question: What is an image mask? An image mask is a copy of the bitmap image in which the transparent color is replaced with its bitwise complement. All other colors are replaced with the transparent color. For sprites, I reserve color 0 as the transparent color. By common convention, color 0 is defined as black and color 255 as white, but this is not required.
An image mask usually looks like a black and white negative of the bitmap. Figure 2 is an example of a bitmap image and its corresponding mask. The engine includes the CreateBitmapMask() routine, which creates a mask image from a bitmap. Also included are PutBitmapAnd() and PutBitmapXor(), which can be used for AND-XOR bitblts to the double buffer.
Using masked images is just one of several ways of handling bitmap transparency. Unfortunately, the technique is not exactly optimal in the sense that you perform additional processing for each pixel drawn. Worse yet, this processing involves no less than six memory accesses per pixel. Nonetheless, for reasonable numbers of relatively small sprites, this may be acceptable.
One alternative method is to encode the bitmap data such that runs of transparent pixels can be skipped over. This allows the bitmap display routines to skip over transparent pixels and draw runs of colored pixels using block-copy routines. The cost of this method is the addition of a conditional branch to the inner loop, but it eliminates the extra memory accesses. The only other disadvantage to this method is the need to store bitmap data in a nonstandard format.
Yet another method of handling transparency is to use compiled bitmaps. By far the greatest benefit of this method is the tremendous performance. In fact, I'll venture to say that there is no faster way to draw a bitmap with transparency. A compiled bitmap is bitblt optimization taken to the extreme--the bitmap data is preprocessed into machine code. This is the minimal code required to draw only the nontransparent pixels which, if you think about it, amounts to a totally unrolled inner loop. The key to performance with compiled bitmaps is the complete elimination of all loops and conditionals.
Example 3 is a typical compiled bitmap. One potential limitation of compiled bitmaps is that significantly greater memory space is required. The data expansion is on the order of six bytes for every nontransparent pixel, plus some overhead. This results directly from the fact that the opcode of each mov instruction takes two bytes plus one byte for the segment override. The operand data includes two bytes for the offset and one byte for the actual pixel data. If you use mov [si+off16], with its implied DS segment override, you can save one byte per pixel at the cost of some additional overhead to setup the DS register upon entry and restore it before returning.
The increased storage requirements of compiled bitmaps is significant enough so that, for large sprites, memory space may be a problem. Then again, low memory is a common and well understood problem in games, and there are a number of workable solutions. These solutions include bitmap caching, virtual memory, and EMS/XMS.
Another drawback of compiled bitmaps is that clipping to the viewport becomes very difficult, if not impossible. You can accept that limitation in the engine since sprites are not allowed outside the viewport. I designed the game logic so that sprites change direction when they reach the borders of the screen. Another approach might be to reduce the viewport size and only copy a portion of the double buffer to the display. This would give the appearance of sprite clipping without having to test each sprite.
To illustrate the level of performance improvements possible through the use of compiled bitmaps, I have included a bitmap compiler routine with the engine. To use the compiler, pass a bitmap pointer to CreateCompiledBitmap() and the routine returns a far pointer to the compiled bitmap. Listing One presents the source for the bitmap compiler.
Calling the compiled bitmap is as easy as making a far function call through the pointer. You must make a far call because the game engine uses the compact memory model and the return value is really a far pointer to data, rather than a near code pointer, as you might expect. Note that this violates some of the rules of protected-mode programming, where attempting to execute data will generate a fault. If necessary, this can be handled by creating an alias selector for the data. In flat-model, protected-mode environments, such as the Tenberry DOS-Extender, this is usually not a problem because the code and data selectors overlap and point to the same physical memory.
The compiled bitmap function is designed to be passed a far pointer to the double buffer, and the x- and y-coordinates for the upper-left corner of the sprite. You must be careful to pass only valid pointers to the compiled bitmap function. Passing an invalid pointer to the compiled bitmap will almost certainly crash the system.
Setup and Cleanup
Before getting to the heart of the engine, you need to attend to some housekeeping details. The game engine requires some initialization routines to set up the environment. Likewise, you'll need some routines to free memory allocations and properly restore the environment.
When the game engine starts, it makes a call to StartUp(), which in turn calls routines to set up the video mode, load bitmap sprites, install the new interrupt handlers, and so on. All game variables and data structures, including sprite lists, are initialized at this point. Upon a successful return from StartUp(), the engine calls the event loop. When the current game is over, ShutDown() is called to restore the environment before exiting.
The Event Loop
The core of nearly every game is an event loop--and this is where the game spends the majority of its time. The event loop is, in essence, nothing more than a while loop. This loop manages the various game tasks, in order, calling helper routines as needed.
The helper routines handle tasks such as processing user input, drawing sprites, and updating the screen. Many of these tasks require the application of a helper routine to an entire list of items. An example of this is sprite movement; each sprite chooses a course of action independently. In these cases, you use the list-iteration routines, as in ForEachActor(MoveActor), to apply a user function to each sprite.
The engine includes a function, EventLoop(), that is called after the start-up routines and returns only when the game is over or the player hits Escape. Figure 3 describes the event loop; Listing Two presents the complete source code for it.
If you look closely at the outline in Figure 2, you may wonder why the aliens are not drawn at the same time that they are moved. As you will see in a moment, it is often convenient in games to subdivide tasks in this way.
Timer Functions
At this point, you have bitmap animation routines, sprite-list management, and an event loop. What comes next? Well, you could place all of the action routines inside the event loop and call it a day. The problem with this approach is that the speed of the game animation is directly tied to hardware speed. When run on a Pentium/133, it may well be that game play is unacceptably fast relative to a 486/25.
Therefore, you must find some way to regulate the timing of the various game activities. In the game engine, this is handled using the system timer. The game engine manages the system timer in two ways. First, the 8254 timer IC is reprogrammed to generate interrupts at a rate of 144 Hz. This allows for a timer accuracy of about 7 milliseconds.
Second, the engine installs its own timer hardware-interrupt handler. This interrupt handler manages several one-shot count-down timers. When the interrupt handler receives control it decrements a global variable until it reaches zero. Meanwhile, at each pass through the event loop, you check to see if one of these counters has reached zero. If so, you call a helper routine and reset the timer.
The game engine sets up unique timers for the game events:
- Missile movement.
- Alien decision making.
- Alien movement.
- Alien animation.
- Palette animation.
Each of these events is scheduled to happen at a different rate. For example, the actor-movement timer is setup to update the location of each actor about every 13ms, while the actor bitmap changes once every quarter second. By subdividing the various event-loop tasks, you can fine tune the rates of these tasks by assigning them to different timers.
Palette Animation
One technique used frequently in games is palette animation. This is a really clever way to produce simple animation. In designing the sprites for the game, I reserved the last 16 colors for palette animation. During the game, the RGB values of these colors are periodically cycled to all black and then back to the original values. This is done by writing new values to the DAC palette registers.
This is not the same thing as changing the individual pixel colors. You don't need to calculate the memory addresses of the changing pixels (this alone is reason enough to use palette animation). Moreover, by changing the RGB value of a palette register, you instantly change the color of each and every pixel on the screen.
The engine has a routine, AnimatePalette(), which makes calls to AnimatePaletteUp() and AnimatePaletteDown() as required. These two routines write directly to the VGA palette registers (rather than through the video BIOS) for performance reasons. The routine AnimatePalette(), in turn, is called from EventLoop(). Like many of the other game functions, AnimatePalette() is controlled by a count-down timer.
Enemy AI
To this point, the actors do not have very interesting behavior. In fact, without additional code, they do not have any behavior at all. It would certainly be nice to give the actors some actions that challenge the player and make the game interesting.
The technique I used for giving the actors some savvy is a simple finite-state machine. A finite-state machine is an abstraction or model of behavioral patterns: the premise being that an actor's current behavior depends upon its previous behavior and upon the status of one or more external variables.
To implement the finite-state machine in the game engine, each actor is given a variable that holds its current state. You then create a state table that lists the new states an actor can attain, given its current state and another variable. The engine chooses the new state randomly from one of five possible choices. At each state change, you have the option of calling some action routines. This is handled by the call ForEachActor(UpdateActorState) inside the event loop.
Example 4 shows the state table used by the engine. The rows of the table represent the chances or probability levels, while the columns represent the current state. As you can see, if an actor is currently in the shooting state, it has no choice but to return to the hover state. However, while in the hover state, the actor may continue to hover (60 percent chance), shoot a missile (20 percent chance), or dive at the player (20 percent).
Using the finite-state machine, you can build up quite complex behavior patterns. If necessary, you could expand the state table defining new states and/ or adding additional probability levels. You could even develop more complex behaviors by layering or nesting state tables.
Game Play
Playing a game is simple. You are the hero racing through space in your interceptor. Your ship can move in any direction, with movement controlled by the arrow keys. The alien attack is unpredictable and sometimes confusing as they attempt to destroy you. You have three lives, but you may eject from your spaceship at any time by pressing the Escape key.
Conclusion
There are certainly a number of ways that the game engine could be extended and improved. For instance, the star background could be replaced with tiled scenery. Also, the state table could be expanded, or you could add additional state tables defining entirely new classes of actors.
The count-down timer settings currently used by the engine provide a reasonable balance between action and playability, but feel free to change these values as you experiment with your own ideas.
I encourage you to use the code presented here as a basis for building your own games. If you do develop a game using some of the techniques presented in this article, I would love to hear about it.
Figure 1: Screen from a typical game.
Figure 2: A Sprite and its mask.
Figure 3: The event loop.
1. React to player inputs--move player, fire missiles 2. Draw the background 3. Move any missiles 4. Move the aliens 5. Draw the aliens 5. Draw our player 6. Update the video display 7. Palette Animation 8. Alien AI 9. Loop to 1 until game over
Table 1: Game-engine code modules.
Module Description VGA.C Low-level VGA routines. KEYBOARD.C Low-level keyboard routines. PCX.C PCX file management. DRAW.C Sprite animation. PALANIM.C Palette animation. DATA.C All global data. INIT.C Program setup/shutdown. VIDEO.C Low-level video routines. SPRITE.C Sprite list management. TIMER.C 8254 Timer IC routines. COMPILE.C Bitmap sprite compiler. MAIN.C Where it all begins, event loop.
Example 1: New keyboard interrupt handler.
unsigned char kbKeyboard[128];
// This is the new Int 09h handler
void static _interrupt NewInt9(void)
{
register unsigned char acode;
// read key code from keyboard
kbScanCode=inp(0x60);
acode=inp(0x61);
outp(0x61,(acode | 0x80));
outp(0x61,acode);
// send End-Of-Interrupt to 8259 PIC
outp(0x20,0x20);
// record a keypress
kbKeyboard[kbScanCode & 127]=1;
if(kbScanCode & 128)
// clear a keypress
kbKeyboard[kbScanCode & 127]=0;
}
Example 2: Sprite data structures.
typedef struct tagPlayer
{
int x,y;
unsigned Score,Level,Lives;
} Player;
typedef struct tagActor
{
int type;
int x,y;
int dx,dy;
int State,LastState,Momentum;
unsigned MissileDelay;
struct tagActor *next;
} Actor;
typedef struct tagMissile
{
int type;
int x,y;
int dx,dy;
struct tagMissile *next;
} Missile;
Example 3: (a) Portion of a compiled bitmap; (b) a more-efficient alternative.
(a) mov byte ptr [es:di+10],FF mov byte ptr [es:di+11],F0 mov byte ptr [es:di+12],F0 mov byte ptr [es:di+13],FF retf (b) push ds ... mov byte ptr [si+10],FF mov byte ptr [si+11],F0 mov byte ptr [si+12],F0 mov byte ptr [si+13],FF pop ds retf
Example 4: Finite-state table.
uchar StateTable[CHANCES][LAST_STATE]=
{
// col = current state, row = chance
// HOVER SHOOT DIVE
{HOVER_STATE, HOVER_STATE, DIVE_STATE},
{HOVER_STATE, HOVER_STATE, DIVE_STATE},
{HOVER_STATE, HOVER_STATE, DIVE_STATE},
{SHOOT_STATE, HOVER_STATE, DIVE_STATE},
{DIVE_STATE , HOVER_STATE, SHOOT_STATE}
};
Listing One
// compiled.c - This module implements a bitmap compiler.
// Copyright (c) 1996 by Mark Seminatore, all rights reserved.
#include <stdio.h>
#include <stdlib.h>
#include "compat32.h"
#include "vga.h"
#include "pcx.h"
#include "sprite.h"
#include "globals.h"
// #define UNIT_TEST
//
// []------------------------------------------------------------[]
// | |
// | |
// []------------------------------------------------------------[]
//
CompiledSprite CompileBitmap(uchar *pBitmap, int width, int height)
{
uchar *pCompiled, *pTemp;
unsigned column, row, TotalBytes=0;
// calc bytes required
pTemp=pBitmap;
for(row=0; row < height; row++)
for(column=0; column < width ; column++)
if(*pTemp++)
TotalBytes++;
// far function-call overhead
TotalBytes *= 5;
TotalBytes += 25;
pTemp = pCompiled = malloc(TotalBytes);
if(!pTemp) return (CompiledSprite)pTemp;
*pTemp++ = 0x55; // push bp
*pTemp++ = 0x8b; // mov bp,
*pTemp++ = 0xec; // ...sp
*pTemp++ = 0x56; // push si
*pTemp++ = 0x1e; // push ds
*pTemp++ = 0xc5; // lds si,[bp+06] (pBitmap parm)
*pTemp++ = 0x76;
*pTemp++ = 0x06;
*pTemp++ = 0x8b; // mov ax,[bp+12] (y parm)
*pTemp++ = 0x46;
*pTemp++ = 0x0c;
*pTemp++ = 0xbb; // mov bx,320 (screen width)
*pTemp++ = 0x40;
*pTemp++ = 0x01;
*pTemp++ = 0xf7; // mul bx (calc offset)
*pTemp++ = 0xe3;
*pTemp++ = 0x03; // add ax,[bp+10] (x parm)
*pTemp++ = 0x46;
*pTemp++ = 0x0a;
*pTemp++ = 0x03; // add si,ax
*pTemp++ = 0xf0;
for(row=0; row < height; row++)
for(column=0; column < width ; column++)
{
if(*pBitmap)
{
*pTemp++ = 0xc6; // mov [si+off16],xx
*pTemp++ = 0x84;
// 16-bit offset
*(((unsigned*)pTemp)++) = row * 320 + column;
// pixel data
*pTemp++ = *pBitmap;
}
pBitmap++;
}
*pTemp++ = 0x1f; // pop ds
*pTemp++ = 0x5e; // pop si
*pTemp++ = 0x5d; // pop bp
*pTemp = 0xcb; // retf
return (CompiledSprite)pCompiled;
}
#ifdef UNIT_TEST
#include <conio.h>
uchar *VideoMem;
void main(void)
{
PcxImage pcx;
CompiledSprite pfnSprite;
int result,i;
result=PcxLoadImage("alien1.pcx",&pcx);
pfnSprite=(CompiledSprite)CompileBitmap(pcx.pBitmap, pcx.Width, pcx.Height);
getch();
VgaSetMode(0x13);
for(i=0;i < 199-16; i+=16)
pfnSprite(VideoMem,i,i);
getch();
VgaSetMode(3);
}
#endif
Listing Two
// Main.c: This module contains the event loop code
// Copyright (c) 1996 by Mark Seminatore, all rights reserved.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dos.h>
#include "compat32.h"
#include "keys.h"
#include "init.h"
#include "vga.h"
#include "pcx.h"
#include "sprite.h"
#include "draw.h"
#include "palanim.h"
#include "globals.h"
// []------------------------------------------------------------[]
// | This is the main even-loop |
// []------------------------------------------------------------[]
void EventLoop(void)
{
// ESC quits the game
while(!kbKeyboard[ESC_KEY])
{
// fire a player missile
if(kbKeyboard[SPACE_BAR])
{
// check if re-loading
if(!PlayerMissileDelay)
{
AddMissile(PLAYER_MISSILE, player.x, player.y-MISSILE_H, NONE, UP);
// delay for missile re-load
PlayerMissileDelay=HALF_SECOND;
}
}
// move player up
if(kbKeyboard[UP_ARROW])
{
player.y--;
if(player.y < 0)
player.y=0;
}
// move player to the left
if(kbKeyboard[LEFT_ARROW])
{
player.x--;
if(player.x < 0)
player.x=0;
}
// move player to the right
if(kbKeyboard[RIGHT_ARROW])
{
player.x++;
if(player.x + PLAYER_W > (SCREEN_WIDTH-1))
player.x=(SCREEN_WIDTH-1) - PLAYER_W;
}
// move player down
if(kbKeyboard[DOWN_ARROW])
{
player.y++;
if(player.y + PLAYER_H > VIEW_HEIGHT)
player.y= VIEW_HEIGHT - PLAYER_H;
}
// draw the starfield
DrawBackground();
// allow missile movement
ForEachMissile(MoveMissile);
// time to move?
if(!AlienMovementDelay)
{
// allow actor movement
ForEachActor(MoveActor);
AlienMovementDelay=TWO_TICKS;
}
// draw the aliens
ForEachActor(DrawActor);
// show our hero
DrawPlayer();
// update double-buffer
UpdateScreen();
// check if time to animate palette
if(PaletteToggle)
{
AnimatePalette();
PaletteToggle=0;
}
// aliens don't think too quickly!
if(!AlienStateDelay)
{
ForEachActor(UpdateActorState);
AlienStateDelay=TWO_SECONDS;
}
// animate aliens
if(!AlienAnimationDelay)
{
AlienBitmap=(AlienBitmap == Alien1Bitmap) ? Alien2Bitmap : Alien1Bitmap;
#ifdef PUTBM
AlienMask=(AlienMask == Alien1Mask) ? Alien2Mask : Alien1Mask;
#endif
AlienAnimationDelay=QTR_SECOND;
}
// you won...this round
if(nActors ==0)
{
player.Level++;
UpdateScore();
InitAliens();
}
} // end while()
} // end EventLoop()
// []------------------------------------------------------------[]
// | This is the main program entry-point |
// []------------------------------------------------------------[]
#pragma argsused
void main(int argc,char *argv[])
{
// Call the various initialization routines
StartUp();
// Display player info
UpdateScore();
// Jump into the main program loop
EventLoop();
// Call the various cleanup routines
ShutDown();
}
End Listings
