2D Game Algorithms

We have reviewed the constituent elements of traditional 2D games. We will now move on to specific game techniques, reviewing the algorithms behind popular classics such as Zelda and Mario Bros. All the algorithms use the same data structures we discussed previously: tile tables, sprites, and mapping matrices.

Screen-Based Games

The simplest mapped game is the screen-based game, in which the player confronts a series of screens. When he exits one screen through its edge, the graphics are substituted by those in the next screen, and so forth. There is no continuity or transition between screens. The classic Boulder Dash would be a good example of this technique.

In these games, each screen is represented using a different mapping matrix, which represents the screen layout of the different elements. So, for a 320x240 screen using 32x32 tiles, we would store the screen in a 10x8 matrix of bytes. Notice that 240 does not allow for an exact number of tiles to be rendered vertically onscreen (we can fit 7.5 tiles). So, we take the integer excess to ensure the whole screen is mapped.

Then, the rendering routine is very straightforward. Its code would look something like this:

#define tile_wide 32
#define tile_high 32
#define screen_wide 320
#define screen_high 240

int xtiles=screen_wide/tile_wide;
int ytiles=screen_high/tile_high;

for (yi=0;yi<ytiles;yi++)
      {
      for (xi=0;xi<xtiles;xi++)
            {
            int screex=xi*tile_wide;
            int screey=yi*tile_high;
            int tileid=mapping_matrix [yi][xi];
            blit(tile_table[tileid],screenx,screeny);
            }
      }

An interesting variant of the preceding code generalizes the mapping matrix to a 3D matrix indexed by room identifier, x value and y value. This way a single data structure can hold the whole game map. To use this approach, we would need a line such as this in our code:

int tileid=mapping_matrix [roomid][yi][xi];

Two- and Four-Way Scrollers

Screen-based games divide the gameplay into chunks that must be dealt with individually. That makes rendering easier, at the cost of breaking the entertainment each time screens are changed. It would be much better, in terms of gameplay, if the action was a continuum, with no screen swapping at all. This is the goal of scrolling games: to create a larger-than-screen gameworld that we can continually explore from a sliding camera. Classics like 1942 (2-way top-down scrolling), Super Mario Bros (2-way side-scrolling), and Zelda (4-way top-down scrolling) are all part of this large family. Games such as Diablo or the Commodore classic Head over Heels used isometric perspectives, but the approach is virtually the same.

Scrolling games are a bit more complex than screen-based games. The game world is larger than the player's screen, so we need to process only those areas that are visible to the player. Besides, the screen mapping of a scrolling world depends on the player's position, making our code significantly harder.

The initial problem we will be dealing with will be selecting the "window" or portion of the game world that will be visible. For consistency, I will use the same constants we used in the preceding section:

#define tile_wide 32
#define tile_high 32
#define screen_wide 320
#define screen_high 240

Clearly, the number of onscreen tiles is

int xtiles=(screen_wide/tile_wide)+1;
int ytiles=(screen_high/tile_high)+1;

Notice how we added one in each direction to account for the last tile showing, which will probably be cut.

Then, we need to know which cell in the mapping matrix the player is standing on. This way, assuming the player is in the middle of the screen, we can deduct the window coordinates. Specifically, assuming the player is at

Int playerx;
int playery;

his cell position will be

tileplayerx= Playerx/tile_wide
tileplayery= Playery/tile_high

And we must paint the following tile intervals:

X: ( tileplayerx – xtiles/2 .... tileplayerx + xtiles/2)
Y: ( tileplayery – ytiles/2 .... tileplayery + ytiles/2)

Now we know which tiles in the mapping matrix are visible and should be painted. We must now calculate where in screen space those tiles should be painted. Again, this is relatively straightforward. In a screen-based game, we would project at

int screenx=xi*tile_wide;
int screeny=yi*tile_high;

which means we are painting the screen as if it was a checkerboard. Now, the checkerboard is larger than the screen, and it slides according to the player's position. Thus, the new transform will be

int screenx=xi*tile_wide - playerx;
int screeny=yi*tile_high - playery;

There is a caveat to this though. If we implement the previous transform "as is," we are translating by the player's position, which would mean the player is located in the coordinates 0,0 in screen space. This is not usually the case, as players in scrollers are usually placed in the center of the screen. Clearly, the player's coordinates are

Screenplayerx=screenx/2
Screenplayery=screeny/2

So, the final, correct world-to-screen transform must be

int screenx=xi*tile_wide – playerx-screenplayerx;
int screeny=yi*tile_high – playery-screenplayery;

And the complete rendering loop must be

#define tile_wide 32
#define tile_high 32
#define screen_wide 320
#define screen_high 240

int beginx= tileplayerx – xtiles/2;
int beginy= tileplayery – ytiles/2;
int endx= tileplayerx + xtiles/2;
int endy= tileplayery + ytiles/2;

tileplayerx= Playerx/tile_wide
tileplayery= Playery/tile_high

int xtiles=screen_wide/tile_wide;
int ytiles=screen_high/tile_high;

for (yi=beginy;yi<endy;yi++)
     {
     for (xi=beginx;xi<endx;xi++)
               {
               int screenx=xi*tile_wide – playerx-screenplayerx;
               int screeny=yi*tile_high – playery-screenplayery;
               int tileid=mapping_matrix [yi][xi];
               blit(tile_table[tileid],screenx,screeny);
               }
     }

Notice how I was careful not to impose any restriction on which axis does the scrolling effect. Thus, the preceding code will handle both 2- and 4-way scrollers equally well. If you want to do 2-way only scrolling, you will need to deactivate the superfluous code from the general case explained earlier.

Multilayered Engines

Basic scrollers have been very successful through the years. So successful that a number of variants have been developed for specific scenarios to overcome restrictions imposed by the basic code. We will now see some of them, starting with multilayered engines.

Imagine that we are doing a top-down game that takes place outdoors, in forests and fields. Our art team has created a number of ground tiles to provide variation. The team has also created some great looking trees; so overall, the scenario looks natural and nonrepetitive. Clearly, if all the trees can be painted on all the terrains, we will need a large number of combinatory tiles in order to reach the desired variety. For five terrain types and 10 trees, we will be occupying 50 tiles in our precious, limited memory.

This is one of the use cases for multilayered engines, which allow us to encode the mapping in layers of tiles, so we can combine different tiles (such as terrain and trees from the previous paragraph) at a lesser cost. This is a popular method, which can be used if

• We need to combine tiles.

• We need to move objects over the background.

• We want to give the illusion of depth.

Multilayered engines use several mapping matrices to encode the game map. One matrix represents the background, another matrix the trees, and so on. Then, matrices are painted in a parallel fashion, such as:

for (yi=beginy;yi<endy;yi++)
        {
        for (xi=beginx;xi<endx;xi++)
                {
                int screenx=xi*tile_wide – playerx-screenplayerx;
                int screeny=yi*tile_high – playery-screenplayery;
                for (layeri=0;layeri<numlayers;layeri++)
                        {
                        int tileid=mapping_matrix [layeri][yi][xi];
                        blit(tile_table[tileid],screenx,screeny);
                }
        }

Notice how I assumed that layers are ordered back-to-front in ascending order: 0 is the background, and larger numbers are closer to the viewer.

Also notice in the preceding code that although the first layer (numbered 0) will usually completely cover the screen, those layers in the foreground will mostly be empty. In other words, there will only be a few trees or clouds. So, front layers will need some optimization to ensure we can handle empty tiles efficiently.

The best way to achieve this is to reserve one tile (usually, the first one) as the "empty space" indicator. So, the preceding code can easily be changed into the following code, which will handle empty space, ensuring that we don't waste time painting empty tiles:

for (yi=beginy;yi<endy;yi++)
      {
      for (xi=beginx;xi<endx;xi++)
               {
               int screenx=xi*tile_wide – playerx-screenplayerx;
               int screeny=yi*tile_high – playery-screenplayery;
               for (layeri=0;layeri<numlayers;layeri++)
                        {
                        int tileid=mapping_matrix [layeri][yi][xi];
                        if (tileid>0) blit(tile_table[tileid],screenx,screeny);
               }
      }

Parallax Scrollers

We have seen how multilayered engines can reduce our memory footprint in some scenarios, but this is only one of their properties. With some extra code, we can convert our plain scroller to a semi-3D approach, which adds a sense of depth and perspective at no extra cost. This is what parallax scrollers are all about.

Parallax is the optical phenomenon described as the apparent displacement of a distant object (with respect to a more distant background) when viewed from two different positions. In other words, if you are driving a car on a highway and you see a fence along the side with mountains on the horizon, the fence seems to move much faster than the mountains. This is due to the fact that perceived object size decreases with the distance to the viewer squared. Thus, apparent movement speeds from distant (but large) objects are smaller than speeds from foreground objects.

Now, imagine that each layer in our tile engine represents one of x possible depth values: Layer 0 will represent the mountains, layer 1 the fence, and layer 2 the foreground. If we move the different layers at decreasing speeds (depending on their depth), we could somehow fool the eye and achieve a sense of depth similar to that found in 3D viewing. This technique is what we usually refer to as parallax scrolling: storing depth-layered tiles and moving them at different speeds to convey a sense of depth.

For easier coding, layer 0 is usually the farthest one, so we can paint back-to-front, increasing the movement speed. Then, we only have to move each layer at a different speed so the parallax effect becomes visible. Because we are really not moving the background but instead are moving the player in front of it, one of the easiest ways to code this is by storing several player positions, depending on the layer. The position from layer 0 (mountains) will advance at a set speed, the position from the next layer (fence) will advance faster, and so on. In practical terms, this will make the layers move at different speeds on the screen, and thus create the illusion of depth. Here is a parallax loop in full:

if (pressed the right cursor)
     for (layeri=0;layeri<numlayers;layeri++) playerx+=1*(layeri+1);

for (layeri=0;layeri<numlayers;layeri++)
      {
      for (yi=beginy;yi<endy;yi++)
           {
           for (xi=beginx;xi<endx;xi++)
                 {
                 int screenx=xi*tile_wide – playerx[layeri]-screenplayerx;
                 int screeny=yi*tile_high – playery[layeri]-screenplayery;
                 int tileid=mapping_matrix [layeri][yi][xi];
                 if (tileid>0) blit(tile_table[tileid],screenx,screeny);
            }
      }

Notice that, as parallax scrollers slide layers on top of others, we choose to make the outer loop cycle through each layer. This way we render the entire first layer before moving on to the next one, making sure order is preserved.

Isometric Engines

Parallax scrollers attempted to convey the illusion of a third dimension by simulating depth. But there is another way to simulate a 3D scenario. It was discovered by architects and industrial designers centuries ago. Using isometric perspective, we can create a convincing 3D effect on a 2D piece of paper, or if we want, in a computer game. The technique was extremely popular in the 1980s, with games such as Knight Lore and Head over Heels leading the way. It is still in use today, and games such as Diablo and many real-time strategy titles are living proof.

Isometric perspective consists of representing an object or game level sideways and from a raised viewpoint, as if it was rotated 45°. It is a parallel perspective, meaning that lines do not converge as in conic perspective projection. Thus, isometric perspective does not suffer from distortion and keeps the object's real proportions and relationships.

Isometric games are coded in a very similar way to regular games. They still use a mapping matrix, a Style Table, and so on. The only changes are that tiles are defined as rhomboids not rectangles, and the screen projection routine is somewhat more complex.

To begin with, tiles for an isometric title are rhomboids, leaving the outer area blank for easy tiling with neighboring tiles. Thus, rendering these tiles requires keeping a transparency mask active at all times. Another characteristic is that these tiles tend to be wider than they are high. The reason for this is that isometric perspective only looks convincing when the viewer is not very high above the ground. Thus, a regular square tile will be converted to a rhomboid with 3x1/6x1 width-height aspect ratio. Several examples using different width-height ratios are shown in Figure 11.2.

Isometric tile rendering must be performed with a different projection routine. We project diagonally on the screen, along the two mapping matrix axes. Here is the source code for the full rendering loop:

int i,j;
for (i=LIM;i>-LIM;i--)
      {
      for (j=-LIM;j<LIM;j++)
            {
            int sx=MAXSCREENX/2+(i*TILEWIDE/2)+(j*TILEWIDE/2)-(TILEWIDE/2);
            int sy=MAXSCREENY/2-(i*TILEHIGH/2)+(j*TILEHIGH/2)-(TILEHIGH/2);
            sx=sx-lx+ly;
            sy=sy+(lx/3)+(ly/3);

            int orgx=0;
            int orgy=TILEHIGH*(world[px+i][py+j]);
            int tx1=orgx;
            int tx2=orgx+TILEWIDE;
            int ty1=orgy;
            int ty2=orgy+TILEHIGH;

            if ((sx<MAXSCREENX) && (sy<MAXSCREENY) &&
                 (sx+TILEWIDE>0) && (sy+TILEHIGH>0))
                        {
            tiles.render(tx1,ty1,tx2,ty2,sx,sy);
                        }

To begin with, we loop from –LIM (a fixed constant) to LIM, so we make sure enough tiles are actually painted to cover the screen. The specific value for LIM will depend on the tile size and screen resolution. In this case, we are working at 640x480, and tiles are 150 pixels wide and 50 pixels high. Thus, we need to loop from –7 to 7 to ensure full screen coverage.

Then, sx and sy are assigned the screen coordinate for the tile being rendered. The equation is simpler than it looks. Let's look at sx first. An increase in the iterator i (used to iterate in X sense of the mapping matrix) causes the next tile to shift TILEWIDE/2 pixels. Tiles are overlapped, and we need to displace by half of the tile width for each X increment. Variations in j (used to loop in Y) produce the same effect. Then, the other two parameters are used to recenter the matrix to the middle of the screen. Now, let's look at sy. A change in X (which is controlled by the iterator i) reduces the Y value by a factor of TILEHIGH/2. Think about it: As the matrix is painted sideways, advancing in positive Y places tiles closer to the top of the screen, thus decreasing their Y value. What happens if we increase the Y (by changing the j iterator)? We will then be placing the tile closer to the bottom of the screen, thus adding TILEHIGH/2 for each iteration in j. For additional clarification, see Figure 11.3.

Page-Swap Scrollers

Another variant of the classic scrolling algorithm can be used in those games where we want to offer a scrolling playing field without being restricted to a closed set of tiles. Imagine a level that offers the gameplay smoothness of a scroller, but where every single piece of art is indeed unique. Games such as Baldur's Gate or the Monkey Island saga come to mind as classic examples of page-swap scrolling.

The starting point is to work on the level map as a single image, and then divide it into sectors, much like checkers on a checkerboard. Then, we use the player's position to determine which sectors should be loaded into main memory. The rest are stored on secondary media (hard drive, CD, etc.), but will be swapped into main memory as needed. It is all a matter of ensuring that our disk bandwidth is good enough so that the player does not notice the loading going on in the background. The smaller the rectangle, the less noticeable it will be. The mapper thus resembles a cache memory: keeping frequently used data within fast reach and swapping it to ensure that we always maintain optimal performance.

There is a specific data structure that can be very helpful when coding this kind of game. It allows us to represent the visible data window and thus pan through a large game map comfortably. The structure is a 2D array, where each node represents one tile of the larger map. The array has a size we will have specified, depending on the preceding parameters, as well as memory constraints. Here is the sample source code:

class tile *tileptr;

class pagescroller
      {
      tileptr **matrix;
      int sizex,sizey;
      int cornerx,cornery;
};

Notice that we store the matrix itself but also need two attributes that help us map the window to the game world. cornerx and cornery tell us where the upper-left corner of the matrix should be placed in the whole map.

Also notice that the double pointer is just used to declare a dynamic-size 2D matrix of pointers to sectors. We use pointers so we can shift the whole matrix just by doing some pointer assigns, not really copying data, which would be too slow. For example, here is the routine used to shift the whole matrix as we advance to higher X values:

for (int iy=0;iy<sizey-1;iy++)
      {
      aux=matrix[iy][0];  // the first element is really thrown away
for (int ix=0;ix<sizex-1;ix++)
      {
            matrix[iy][ix]=matrix[iy][ix+1];
            }
      matrix[iy][sizex-1]=aux;
      Fill matrix[iy][sizex-1] with new data from the sector appearing in high X
      }

It is good to note how we wrap the deleted column around so it appears on the opposite end and is reassigned the newly loaded data. This way we avoid having to call delete and new, which is always costly.

Some techniques that can improve the performance of these scrollers have to do with the format of the graphics also. If your game runs at a very high resolution, the screen updates will need to take place more frequently, because the user will pan through a bigger data set. Similarly, using more colors can reduce performance. Files will become larger and loading times will increase. The last factor we need to keep in mind is the velocity of the player. Clearly, a walking character will traverse the game world at a slower pace than a jet fighter, simplifying the loading routines. Fast players in page-swap scrollers require lots of reloading.