"Breathing Life Into Your Arcade Game Sprites"
PC Techniques Vol. 5, No. 2
June/July 1994, page 89

What appears here is the original manuscript, as submitted to Jeff Duntemann. Any changes in the published version are due to Jeff's expert editing. There is a code file that goes with this, see QFSPRIT.ZIP.

Intro

In a previous issue of this magazine, we discussed how to scroll a moving background (PC Techniques, Dec/Jan 1994, p. 28). Obviously there is more to writing an arcade game than simply causing the background to move. The real interest lies in what happens in the foreground: the objects, or "sprites" that move independently and give the game its personality, action and challenge. In this article, we expand upon the Quickfire code by adding sprites and giving them the ability to move independently on a moving background.

The Quickfire demo consists of a continuously scrolling circular background (a cloud-filled sky) and a variable number of foreground sprites (a fighter plane, enemy planes, bullets and explosions). Motion of the objects is governed by both artificial intelligence (self-play demo mode) and optional player interaction (press the arrow keys to move the fighter plane and press CTRL to fire bullets.) The concepts presented by the Quickfire code have general application, and may be expanded upon to create a variety of arcade games. For example, while the Quickfire background scrolls continuously to the right, it could just as easly scroll to the left, up, down, and diagonally. And while our objects are airplanes which fly, spin and shoot, they could as easily be animated characters that run, jump, and throw punches. The data structures and code would be designed in a similar manner, but the artwork and artificial intelligence would be different.

Because of space constraints in this magazine, we will present code that is scaled down to handle a single object, an airplane. The airplane will only perform a few tricks: it will fly forward at variable speeds, and it will spin around a horizontal axis. Performing more tricks is left to the imagination of the game designer, and it is assumed designing new objects and making them perform their magic is the essence of the craft of game design.

Background

In the previous article, a scrolling background was constructed out of 16x16 pixel tiles. A 320x200 Mode X video mode was chosen, and video memory was resized to one large page. Carefully designed bitblits caused the background to be constructed in such a way as to minimize video memory accesses and maximize frame rate. The Fastgraph graphics library was used to illustrate the technique.

Quickfire has two types of video objects, tiles and sprites. Tiles are 16x16 blocks residing in video memory. They have no transparent colors. Applying tiles involves a direct video-to-video transfer using Fastgraph's fg_transfer function. Sprites are bitmaps with a single transparent color (palette 0) which are stored in RAM and applied to video memory using fg_drwimage. Careful application of the tiles and sprites results in the desired affect of fast arcade-style animation.

Speed

Animation speed is critical to an enjoyable arcade game. Animation rates of 12-15 frames per second are adequate, a rate of 20 frames per second is excellent. It is easy to slow down your sprite motion relative to the frame rate, but improving the frame rate is difficult. With this in mind, we will always try to produce the fastest frame rate possible.

In Quickfire, we define the frame rate to mean page flips per second. Even though both 'pages' in Quickfire look almost identical, they are in fact separate, non-intersecting areas in video memory. Swapping from one to the other involves a call to fg_pan. Every page swap is considered a frame of animation.

Ideally, a video game should run at the same speed on every computer. These days it is common to require a 286 or better for a game, and game sales remain brisk when a 386 or better is required. A problem arises when a game is written to run on a 386 and the user has a 486 or better. A game developed on a relatively slow machine will run too fast on a faster machine, and become unplayable. As hardware technology advances, a microprocessors will only become faster. Games that do not take this into account will have obsolescence built into their design -- not a good idea! It is important to normalize the speed of the game to a relatively fast but common processor speed, like my computer, for example. My Quickfire game should run at approximately the same speed on your Pentium as it runs on my '386.

The solution is to the speed problem is to benchmark the microprocessor at the beginning of the game, and add a delay factor to each frame of the animation loop. We call fg_measure once at the beginning loop, and then we define the stall_time to be clockspeed/10, which is negligible on my computer, but will effectively slow down the animation on a faster computer.

Data Structures

The whole trick to maximizing the frame rate is to update only those parts of video memory which have actually changed since the previous frame. Because our background is defined in terms of tiles, this is quite easy. We only replace the background tiles which have changed from one frame to the next. That is, only those tiles under a sprite, or at the edge of a scrolling page, need to be redrawn.

In order to keep track of which tiles have changed, we will flag them with a three dimensional byte array. The array, called the "layout" is defined like this:

char layout[2][22][15];

The first dimension is the number of logical pages (2), the second dimension is the number of columns per page (22), and the third dimension is the number of rows per logical page (15). The entire array is initialized to 0 at load time. Whenever a tile is overwritten by a sprite, the corresponding byte in the layout array is set to 1. See figure 1.

    video memory                        layout array
 +----+----+----+----+                  ------------
 |    |              |
 |    |      \\\     |                   0  1  1   1
 +----+   =========  +           
 |    |      ///     |    -------->      0  1  1  1
 |    |              |           
 +----+----+----+----+                   0  0  0  0
 |    |    |    |    |
 |    |    |    |    |
 +----+----+----+----+   

                        Figure 1

It takes two structures to properly describe the airplane. The "sprite" structure holds information about the physical attributes of the sprite, including a pointer to the bitmap data, the width, height, and vertical offset. The "object" structure holds information about what the airplane is currently doing, including its current position, current frame, current speed, and a pointer to the sprite structure. The object structure will also typically contain a pointer to a function that governs the action of the sprite, for example, if the sprite is shooting, accelerating, or exploding.

The number of sprites is fixed, but the number of objects is variable. For example, when a bullet is fired, a new object must be spawned, and when an enemy explodes, an object disappears. Sprites are properly stored in an array, and objects are stored in a linked list (see figure 2). Each object points to exactly one sprite, which represents the current frame of the object. In our example, the airplane has 8 frames, which represents the airplane rotated in 8 positions around its horizontal axis. Each frame is rotated 45 degrees from the last frame, and displaying all 8 frames in sequence produces the spin effect.

 objects

  +----------+        +----------+        +----------+        +----------+
  |          |        |          |        |          |        |          |
  | object 1 |        | object 2 |        | object 3 |        | object 4 |
  |          | <----> |          | <----> |          | <----> |          |
  | airplane |        |  enemy   |        |  enemy   |        |  bullet  |
  |          |        |          |        |          |        |          |
  |          |        |          |        |          |        |          |
  +----------+        +----------+        +----------+        +----------+
       |                   |                    |                  |
       |                   |                    |                  |
       |                   +--------------+  +--+               +--+
       |                                 |  |                   |
       v                                 v  v                   v
  +--------+--------+--------+--------+--------+--------+---------+--------
  |        |        |        |        |        |        |         |         
  |sprite 0|sprite 1|sprite 2|  ...   |sprite 8|  ...   |sprite 14| ...
  |        |        |        |        |        |        |         |         
  +--------+--------+--------+--------+--------+--------+---------+--------

 sprites
                        Figure 2

It is also possible for several objects to point to the same sprite. All bullets will look the same, for example, and you may have multiple identical enemies on the screen at one time.

Initialization

An important feature to keep in mind when designing games is to do as few disk reads as possible during game play. In Quickfire, all disk accesses occur during "load time". This is the time at the beginning of the game when the title screen is displayed. In multi-level games, data loads are commonly done between levels, and a transition screen is displayed, some kind of score box, story line update, or credit screen. Transition screens should be creative, as they may need to be displayed for several seconds, especially if data is stored on the disk in a compressed format. The player's attention should be drawn to the transition screen so they do not notice the work going on in the background.

In the previous article we discussed how tiles are stored in a PCX file and displayed in off-screen video memory. The tile map array is read from a second file and stored in conventional memory (RAM). In this program we also need to load the bitmaps into RAM. Bitmaps were created with a sprite editor and stored in a file called PLANE.BMP. Eight bitmaps, representing eight views of the same airplane are stored, along with the width and height of each one. These are read into sprite structures. Memory for the structures is allocated at load time. First an array is allocated to hold the bitmap data, then the structure itself is allocated to hold the width, height, and pointers. Finally, an object is allocated to hold the current position, frame, and pointer to the sprite.

Sprites are stored in near RAM. They consist of 256-color images with a single transparent color, assumed to be color 0. For speed reasons, it is most efficient to have only one transparent color, and a compare to 0 is a fast compare, thus we chose color 0 as the transparent color. Sprites are applied to video memory using Fastgraph's fg_drwimage function. They are not clipped. Sprites may go over the edge of the screen and still be wholly within video memory, because we have resized the video memory to be larger than the visible screen. Sprites which will go off the edge of video memory are simply not drawn. Occasionally, it will look as if a sprite has vanished at the edge of the screen. This is a rare circumstance, and worth the tradeoff in terms of speed. We could clip the sprite if we wanted to, but the additional compare would slow every frame of animation, and the benefit would be minimal, so we skip that step.

The vertical offsets are calculated and added to the sprite structure. This is the amount of lift to add to each frame of the airplane above its base y coordinate. When the airplane rotates, we want to give the appearance of revolving around a horizontal axis passing through the nose of the plane. This is accomplished by displaying some frames a little higher than others.

Load time functions also include initializing the variables and benchmarking the microprocessor, as discussed above. A counter is initialized to calculate the frame rate, and then all the load time functions are accomplished. It is time to activate Quickfire.

Action

The main controlling loop in the Quickfire demo occurs in the function activate_level. It performs the following activities on a constant or periodic basis:

1. scroll the background (if necessary)
2. adjust the layout array
3. check for keypresses and adjust object attributes accordingly
4. do any necessary AI
5. rebuild the hidden page
6. traverse the linked list, placing objects on the hidden page and setting the corresponding bytes in the layout array
7. Swap pages
8. Repeat

The background scrolling was covered in the previous article. To understand adjusting the layout array, it is first necessary to understand what the layout array is used for.

Rebuilding the tiles is a matter of traversing the hidden page layout array, and redrawing tiles every time we encounter a non-zero flag. In this manner, we clear the entire hidden page to a clean background by only replacing those tiles which were overwritten on the previous frame. In the example in Figure 1, the background is cleared by replacing just six tiles, which would be typical when there is only one object on the screen. The corresponding layout array values are set to 0 after the tiles are redrawn (see figure 3).

    video memory                        layout array
 +----+----+----+----+                  ------------
 |    |              |
 |    |      \\\     |                   0  1  1   1
 +----+   =========  +           
 |    |      ///     |    -------->      0  1  1  1
 |    |              |           
 +----+----+----+----+                   0  0  0  0
 |    |    |    |    |
 |    |    |    |    |
 +----+----+----+----+   
                       before redraw_hidden

 +----+----+----+----+
 |    |    |    |    |
 |    |    |    |    |                   0  0  0 & nbsp;0
 +----+----+----+----+           
 |    |    |    |    |    -------->      0  0  0  0
 |    |    |    |    |           
 +----+----+----+----+                   0  0  0  0
 |    |    |    |    |
 |    |    |    |    |
 +----+----+----+----+ 
                       after redraw_hidden

                           Figure 3

This sounds simple, but a problem occurs when the screen is scrolled. Since we do the scroll first, before rebuilding the hidden page, we must adjust the layout array accordingly.

The scroll is accomplished by copying a rectangular area from the visual page to the hidden page, so the layout array is adjusted by copying the visual page layout to the hidden page layout, and shifting left by two columns (see figure 4).

Ideally, we would zero the two rightmost columns of of the layout array. In fact, we skip this step. The rightmost two columns are usually zero anyway, and on those rare occasions when they are not, the time it takes to redraw an unnecessary tile is less than the time it would take to reset those values every frame. This is one of those "trial and error" tradeoffs that gamers are so fond of, and will change according to the character of the game. If a game has a lot of objects on the right side of the screen, then zeroing the rightmost columns of the layout array will pay off in terms of saving unnecessary video transfers.

    video memory                        layout array
 +----+----+----+----+                  ------------
 |              |    |
 |      \\\     |    |                   1  1  1   0
 +   =========  +----+           
 |      ///     |    |   --------->      1  1  1  0
 |              |    |           
 +----+----+----+----+                   0  0  0  0
 |    |    |    |    |
 |    |    |    |    |
 +----+----+----+----+                 
              after the scroll but before redraw_hidden

                         Figure 4

After the background is repaired on the hidden page, it is time to apply the foreground objects. It is assumed the objects have moved since the last frame, and it is also possible that new objects have appeared or old objects have disappeared. These changes are dictated by user interaction and artificial intelligence.

User interaction is determined by polling the keyboard, and adjusting object parameters according to keypresses. In this example, if the right arrow key is pressed, the plane speeds up. If the left arrow is pressed, the plane slows down. The position of the plane is determined by adding the speed to the current position. This occurs in "world map space", which in our map is 3040 pixels wide. So the x coordinate of the fighter plane ranges from 48 to 2983, and is constrained to fit within the visible screen.

The up and down arrows cause the airplane to spin about a horizontal axis, displaying its attractive underbelly. This is accomplished by changing the sprite pointer from sprite[0] (upright position) to one of the other sprites in the array. There are a total of eight possible sprite images in the sprite array, and pressing the up or down arrow key will scroll through them in sequence. The plane->frame variable keeps track of the current frame, and the plane->image variable points to the proper sprite.

Artificial intelligence refers to what the objects do on their own when the player is not controlling the object with keypresses. In our example, the Quickfire airplane has only the most rudimentary artificial intelligence. If you are not pressing a key, the airplane will slow down until it touches the left side of the screen, then it will fly at the same speed as the scroll rate. Also, if the airplane is not currently in an upright position, it will gradually right itself over the span of several frames.

After the new object positions are calculated, the objects are applied to the background using fg_drwimage. As the sprites are drawn, they overwrite the background tiles. The layout array must be updated accordingly. Since sprites can be applied anywhere, not just on byte boundaries, the number of tiles they will cover is variable. The minimum and maximum tiles in the x and y direction are calculated in the function apply_sprite, and the corresponding bytes in the layout array are set to 1.

Finally, the pages are swapped, and the hidden page, which we just updated, becomes visible, and the visible page becomes hidden, and the loop is complete. This sequence is repeated forever, or until the Escape key is pressed.

Conclusion

The ideas in this article are just a bare-bones outline of the techniques used by gamers to create high-speed side-scrolling arcade games. Once these concepts are understood, creating your own games is a straightforward process. Expanding these ideas to include scrolling in multiple directions, improved artificial intelligence, and more objects will result in interesting and playable games. Because of the nature of the object structures, this code is suitable for converting to C++. Future articles will discuss tools for creating tile maps and sprites. Gamers who use these ideas to create their own games are encouraged to send me a copy. Get to work, and let's make 1994 the year of the arcade game!