NOTE:  This is a straight import from word (not pretty).  The To get the Word version of this document,

By: Greg Ratajik

5-5-1998

www.ratajik.net

A. Overall architecture

1. The User Interface Layer

2. The Game Engine Layer

a. Player Sprite

b. Computer Sprite

c. Action Sprites (missiles)

d. Sprite messaging.

3. The Sprite Layer

a. Collision Detection

b. Automove

4. Video Layer.

B. Code Highlights

1. Sprite Linked list.

a. SPRITE_HEADER

b. HIT_INFO

c. SPACE_INFO

b. ACTIVE_BITMAP_LIST

d. BITMAP_INFO

e. User Defined Info

b. Alive, Inactive, and Dead lists.

2. BARCH (Binary Archive)

3. Bitmap Loading

4. "Loose" Synchronization

C. Compiling.

Figure 1 - High Level Logical Diagram

Figure 2 - Game sub-system

Figure 3 - Sprite Layer

Figure 4 - Video Layer

A. Introduction

This document describes a heavily multi-threaded game engine for OS/2. While the engine has been used in the game TunnelWars, this document describes the engine in a generic way, one in which any type of 2D scrolling game may be implement using the engine.

The original reason for writing the engine was to prove whether a action game, with a scrolling background and many sprites, could be totally written using threads. Each sprite is a thread; when the player fires a missile , each is its own thread, interacting with the game environment as a self contained entity. What would game performance be like with so many threads? Would the overhead prove to be to much? And would threading make the game programming easier or more difficult?

Another reason for written the game was to show that OS/2 was able to be a game OS. Could it handle high speed parallax scrolling? Was it possible to blit a large number of sprites using OS/2 API’s, and have acceptable performance?

B. Who this document is for.

I’ve released the source code for the game engine and the sample game in to the public domain. Anyone that wants to use it to write their own game may find this document useful in understanding the architecture of the game engine, and how to go about writing their own game based on the engine.

This document may also be useful for a general introduction to one of the ways a game may be massively multithread, as I’ve have had to address many of the issues that are inherent in this type of code.

C. Information about the code.

The main web page for the engine and Diver can be found at: http://www.ratajik.net/diver

The source code is available from that page. Please read the copyright information found on the main page.

I originally wrote this code in 1994-95. I finished the game engine and was ready to go when my graphics guy (Robert Kauffman) dropped out of the project. As I didn’t have any decent graphics tools (Hey, it was OS/2!) I never actually released the game. The background and Walker were done by Bob (Cool, huh?). The rest I slapped together.

I recently decided to re-release all of my OS/2 shareware software (http://www.ratajik.net/OS2), and most of the source code. This release of Diver is from that effort. While I’ve touched up the code a bit (fixed a couple of bugs, general clean up, etc.), it still is very much a pre-released game. I may port the code to Windows (the code is VERY portable, as it’s layered nicely). If so, I will continue to make improvements to it. I also am now mostly a Windows/C++ programmer, so I’ll probably be moving it to C++.

While I am not promising support on this, you can email me at diver@ratajik.net and I’ll try to help out. If you make mods or fixes to the source, please mail me at this address so I can integrate it in.

 

II. High level design

A. Overall architecture

1. The User Interface Layer

This layer primarily feeds UI information down to the game engine, along with high-level management of the game’s windows, menu’s and dialogs. It also kicks off the game engine.

 

2. The Game Engine Layer

a. Player Sprite

The Game Engine layer process input from the UI layer (keyboard input, mouse or joystick if it is enabled.) It translates this input into movement or action of the player sprite. The player sprite is a thread, and handles input by using sprite messaging (see Messaging for more information.). The player thread handles movement, collision, and action for the player sprite.

b. Computer Sprite

At the appropriate time (currently based on time and then a random number), the Game Layer will spawn a Walker (Computer Sprite). When creating the sprite, it sets the Walkers destination, starting point, and velocity. The Game Layer will spawn the Computer Sprite by creating a new thread. The Computer Sprite runs in this thread, and handles movement, collision, and actions (firing at the player, primarily).

c. Action Sprites (missiles)

The player sprite or the computer sprite can both spawn various types of missiles. They create a thread for the missile sprite, setting its destination, start point, and velocity. The thread handles movement and collisions, using sprite messaging.

d. Sprite messaging.

Each sprite has a value, "usMessage". When the Sprite Layer has detected that something has happened to the sprite (collision, boundary hit, destination reached), it will set this value to the appropriate message. Each sprite uses this message to determine what to do next. For example, by using the message, a sprite can determine that it was hit by an ACTIVE COMPUTER_SPRITE, and die.

 

3. The Sprite Layer

a. Collision Detection

As each sprite is processing (a request made by the Video layer), it detects if it has collided with another sprite. It does this by simple overlapping rectangle calculations. If it detects a collision, it uses sprite messaging to notify the controlling sprite thread.

b. Automove

Each sprite can be put into "Auto Move" mode. If this happens, a function is called in the Sprite Layer to move the sprite. When an AutoMove has finished, sprite messaging is used to notify the controlling sprite thread that it has arrived.

4. Video Layer.

B. Code Highlights

I am not going to attempt to fully document the code at this time. If I port it to C++, I will do some modeling and OOD, and will inherently have more documentation for it For now I will cover some of the most important parts of the code.

1. Sprite Linked list.

The most important linked list is the sprite linked list. It holds everything together. The list is a standard forward-backward pointing linked list, composed of pointers to the structure SPRITE_OBJECT. Each of these sprite nodes contains all of the information needed to manipulate and process a sprite. Some of the highlights to this structure are:

a. SPRITE_HEADER

This structure contains general sprite information, such as the name of the sprite, semaphore information, the sprites type, the state of the sprite, the PID of the sprite, and a pointer to the function that controls the sprite.

b. HIT_INFO

The HIT_INFO structure contains information about whether to detect collisions for the sprite, the hit state the sprite is in (hit, not hit, et al), and, if hit, a pointer to the sprite that hit it. This can be used to determine what happens on a hit (e.g., if a computer missile hits the player, the player can look at the sprite that hit it and figure out that it needs to blow up).

c. SPACE_INFO

This structure contains the information about where the sprite is, where the sprite is going, and how fast it is going there (both velocity and frame rate).

b. ACTIVE_BITMAP_LIST

The active bitmap list contains a pointer to the BITMAP_INFO, and the offset the bitmap should be draw from the origin.

 

d. BITMAP_INFO

This struct is tells the graphics layer which bitmap list to process (Alive, Dead, idle), and how to process them (forward, backwards).

e. User Defined Info

b. Alive, Inactive, and Dead lists.

As each sprite processes, it will change the bitmap list in this structure to point to one of the three possible states (Alive, dead, or idle).

2. BARCH (Binary Archive)

Think "PAK" or "WAD" file. This is a separate utility that I wrote that will place files in a archive, and provides an API set to manipulate those files. Currently, all of the BMP’s for the sprites are kept in the .BAR archive (good thing, to, as there are a lot of them!) NOTE on the code: BARCH is as-is from ’95. I made no attempt to clean the code up or improve on it in any way. I plan on using an off the shelf version next time around, so didn’t want to put any extra effort in to BARCH.

3. Bitmap Loading

A pointer to each bitmap is stored on a linked list. When a request for a bitmap is made, the loader function first checks to see if the bitmap is on the list. If it is, it just returns a pointer to it. Otherwise it creates a new node and loads the bitmap. This ensures maximum performance on bitmap loads.

IMPORTANT: Never delete the pointer to a bitmap, except when cleaning up this list.

4. "Loose" Synchronization

When a program makes use of threads, it normally uses semaphores to synchronize access to memory and some types of resources. For example, when adding a node to a linked list, a semaphore would be used to ensure that no other thread accesses the list’s memory while it manipulates it.. In order to achieve the maximum performance, I’ve written the code in such a way that this is not, for most case, needed. (You’re cringing, right? Well, it works, and it’s fast! <VBG>)

The only time a semaphore is used is inside of the node creation for the SPRITE_OBJECT linked list. This ensures that if a node is reused or created, pointer collisions won’t happen (e.g, two threads end up using the same sprite node. Amusing to see, but not to fun in a game engine). The only part of the system that looks at the semaphore is the node creation function; everyone else just processes as needed.

In order to do this "lose" threading, there’s one big rule that needs to be followed: NEVER DELETE ANYTHING! An example of this is when a sprite has finished processing, the thread "deletes" the sprite, which only results in a state change for the sprite node (STATE_INACTIVE). The next time a sprite is created that is the same type as the newly inactive sprite, the node is reused. This ensures that we don’t start gobbling up memory by re-using it, and will prevent memory collisions/walks/et al.

The only big downside to this is sprite message walks. It is possible that three sprite threads might "post" messages to a single sprite before that sprite can process the messages. This will result in messages being lost. A simple fix for this would be to create some kind of FIFO array or list to hold each message. I have not yet done this, primary for times sake, and I haven’t actually seen this happen (it might have, it’s just not noticeable.)

 

C. Compiling.

II. Other Information.

As I stated earlier, I don’t really consider this code complete. I’ve done some clean-up in the last couple of days, made it compile with the current version of Visual Age and work with Merlin (Hey IBM, what happened to the gamesvr.dll!?!?! In Warp, I would go into full-screen mode, getting about 30% better frame rates. Perhaps OS/2 was never meant to be a game OS, eh? Or an OS at all? <VBG>)

A. Known issues.

Sprite Message Collision (see above).

The access times on linked lists are not very good, at least not for a game. As more sprites are added, the game starts getting slower (80+ sprites). A lot of this can be attributed to the SPRITE_OBJECT list. I would like to turn this in to something a bit faster (hash table, binary tree, etc.).

The collision detection only works on rectangles. What should be done is a rectangle detection, and then, if it passes that, a bit (every other bit?) comparison for better detection.

Many of the sprite handler functions do very much the same thing. Functionallizing this would be a good idea, and make adding new stuff much easier.

 

A. Performance characteristics

I original wrote this game under OS/2 Warp, on a 66 DX/2. I don’t recall what the performance was on it (other that "OK"), but I’ve put together some info running on my Pentium 166:

Max threads: 113 (Just haven’t tried to go higher, as the performance goes down. See "Known Issues").

Frames per second: 640x480, max out around 30 or so. If IBM hadn’t taken the gamesvr.dll out of OS/2 it could do full-screen Dive and get much better numbers.

RAM usage:

Stability: Ok, could be improved. I’ve had the game run for a long time, and then had it crash after 20 minutes. I think I’ve got a small memory walk somewhere, I just haven’t had time to track it down (and the debugger frags when I debug the problem, so I end up re-booting OS/2 EVERY time. Fun.)

 

III. Conclusions