A tile-based game (TBG) begins life in a simple program called a level editor, where individual tiles from a graphics gallery can be dragged into a grid of squares. Here, the level designer can create the level, designing the various puzzles. The level editor varies in complexity according to the details of the game, but the end result is much the same. Each square is assigned to a particular tile. This grid data is then transferred into memory when the level is loaded, in the form of an array.

Each tile can have several properties. For example, a piece of ground might be able to melt, have a low friction value, be deadly to the touch, or undulate like water. As interesting as the visible presentation might be, such details are not as important as the fact that you can store data about collisions in tiles.

On top of the game world, you create a number of moving characters or enemies. You also create scenery, some of it moving, as with floating platforms. Such objects enhance the game environment. To complement them, you place discrete objects such as obstacles or tokens, and while these do not need to correspond to tiles, they nevertheless add complexity that must be taken into consideration as you work with tiles. You also might create some kind of background image. This is made from tiles and involves work with camera control.

With respect to the general project of developing a tile-based game, all of these elements can be viewed as comprising the game engine. From a summary perspective, then, the game engine has four main ingredients: the tile data, the fixed objects, the moving environment objects, and the characters, including the player. As the game is played, the engine has to composite these images into a single picture on the screen.

Movement in the game world takes place in its own coordinate system, which is usually called game space. The game space houses the game world. Each moving object has a position relative to the origin of the game space. Usually, this origin lies at the top left of the grid. All calculations of collisions take place in this grid, or coordinate system. Your screen can be imagined as a “viewport” into the game world, and an independent or semi-independent camera object follows the player character as it moves about the game world. Whether the camera is independent or not depends on such factors as whether the player directly controls it. In a simple 2-D view, you can consider the camera to be at a particular distance from the main plane of the game. One pixel of the game world might correspond to one pixel on the screen.

The drawWorld() function does what its name implies. Given a particular camera position, it draws a selective portion of the game world in the viewport. The assumption is made that the camera position in the game world is set at the coordinates of the pixel at the middle of the screen:

function drawWorld(tileList, cameraX, cameraY, w, h)
   set x to cameraX-w/2
   set y to cameraY-h/2
   set hoffset to (x mod 16) // assuming 16-pixel tiles
   set voffset to (y mod 16)
   set leftmost to 1+(x-hoffset)/16
   set topmost to 1+(y-voffset)/16
   // add error checks to ensure you aren't out of range
   set largelmage to an empty buffer
   repeat for i=0 to w/16
      repeat for j=0 to h/16
         draw tileList[i+leftmost, j+topmost] to
         square(i*16,j*16,(i+1)*16,(j+1)*16) of largelmage
      end repeat
   end repeat
   copy rectangle(hoffset,voffset,hoffset+w,voffset+h)
                   of largelmage to screen
end function

The drawWorld() function is generalized to the point that it is too inefficient to use as given, but it still provides the basic features of a function that creates a game world. Sixteen-pixel tiles are used, for example, and a 2-D world is spawned. In practice, there are different ways by which such a function might be optimized. For a game that scrolls in only one direction (a side-scroller or a top-scroller), it makes sense to draw the world column by column or row by row, adding a new chunk to the image each time another chunk goes out of range. This saves compositing time but is slow when dealing with an image that scrolls in all directions. It is also inefficient, since the chunks of the image must be repeatedly calculated if the player chooses to go backward. Depending on the size of the level, an alternative is to draw the whole level at the start into a single image held in memory. You then copy portions of this image to the screen as needed.

At the expense of some processing speed, you make the world image more interesting if you add image layers to create parallax scrolling. Parallax scrolling involves using background or foreground images. These images are placed at a distance from the camera that differs from the focal plane. The parallax scenery then scrolls at a different speed. As an example of how to implement parallax scrolling, you might create a background image for which one pixel of the image represents two pixels of world space. With this approach, as perceived the image is twice as far away as the focal plane.

Having drawn your tiled planes, you then have to draw all the movable objects on top of them. This is a matter of translating their positions from world coordinates to screen coordinates. Given that their positions are based on the focal plane, you can subtract the position of the top-left of the viewport from their position to work out where they are placed onscreen. In some cases, they might not be placed onscreen.

The final question you face is where to place the camera. One starting rule with respect to this question is that it’s advisable not to have the camera linked directly to the character position. A reason for this is that when the character is at the edges of the game world, images with a lot of blank space at the sides are produced. At the very least, you want to offset the camera whenever the character approaches an edge.

More generally, you want to have a camera that floats behind the character and generally acts like a real camera, following the character around by interpolation. For example, when the character moves in a given direction, the camera can lag slightly behind. You can also choose to focus to one side of the character to take into account the direction in which the character is looking. In a side-scroller, for example, you’re usually much more interested in what’s in front of the character than what’s behind. When the character stops, you don’t want it to be in the center of the screen. On the other hand, if the character is looking right, you want it to be somewhere to the left of center.

After the game world is in place, your next task is to create the functionality that allows you to detect collisions. Apart from the advantages in terms of memory and speed, the biggest advantage of using tiles is that it dramatically simplifies collision detection. How you approach collision detection depends on whether the landscape is defined as solid or permeable. You can choose one or the other or combine the two. If you combine the two, you might make tiles that are solid only from the top. This is a common convention for platform games. With such tiles, when the character is moving, you need to check for collisions only when some part of the character is entering a new tile. This approach is used with the detectCollisionWithWorld() function:

detectCollisionWithWorld(c, w, h, displacement, tiles)
   // w and h are the width and height of the box
   // c is the top-left corner
  
   // determine the colliding edges
   if displacement[1]=0 then set edge1 to "none"
   else if displacement[1]>0	then set edge1 to c[1]+w
   else set edge1 to c[1]
   
   if displacement[2]=0 then set edge2 to "none"
   else if displacement[2]>0	then set edge2 to c[2]+h
   else set edge2 to c[2]
   
   // calculate first collision
   set t1 to 2 // time to collision along vertical edge
   if edge1<>"none" then
      set currTileX to ceil(edge1/16.0)
      set newTileX to ceil((edge1+displacement[1])/16.0)
      if currTileX>newTileX then
         set t1 to ((currTileX-1)*16.0-edge1)/displacement[1]
      otherwise if currTileX<newTileX then
         set t1 to (currTileX*16.0-edge1)/displacement[1]
      end if
   end if
   
   set t2 to 2 // time to collision along horizontal edge
   if edge2<>"none" then
      set currTileY to ceil(edge2/16.0)
      set newTileY to ceil((edge2+displacement[2])/16.0)
      if currTileY>newTileY then
         set t2 to ((currTileY-1)*16.0-edge2)/displacement[2]
      otherwise if currTileY<newTileY then
         set t2 to (currTileY*16.0-edge2)/displacement[2]
      end if
   end if
   
   if min(t1,t2)=2 then return "none" // no change of tile

   if t2<t1 then // first collision is along horizontal
      set newTile to newTileY
      set currTile to currTileY
      set checktile to [ceil(c[1]/16.0), ceil((c[1]+w)/16.0)]
      set mx to the number of columns of tiles
      if displacement[2]>0 then set dir to "bottom"
      otherwise set dir to "top"
   otherwise
      set newTile to newTileX
      set currTile to currTileX
      set checktile to [ceil(c[2]/16.0), ceil((c[2]+h)/16.0)]
      set mx to the number of rows of tiles
      if displacement[1]>0 then set dir to "right"
      otherwise set dir to "left"
   end if
   // at the end of the above process, newtile and currtile give the
   // changed row or column, checktile gives the start and finish
   // of the tiles containing the player
   
   set t to min(t1, t2)
   
   if newTile<1 or newTile>mx then
      // edge of map
      return [c+t*displacement, (0,0),dir]
   end if
   
   // check whether any new tiles entered are solid
   repeat with i=checktile[1] to checktile[2]
      if dir="bottom" or dir="top"
           then set tile to ptiles[newTile][i]
      otherwise set tile to ptiles[i][newTile]
      
      if tile is not empty then
         // potential collision
         if tile.solidity="solid" or
               (tile.solidity="top" and dir="bottom") then
            // tile collision (there could be more options here)
            // move to collision point

            return [c+t*displacement, (0,0),dir]
         end if
      end if
   end repeat
   
   // no collision: recurse
   if t=0 then set t to 0.001
   return detectCollisionWithWorld(
              c+t*displacement, w, h, (1-t)*displacement)

end function

To augment the detectCollisionWithWorld() function, you can make use of techniques introduced in Chapter 21. For example, you might pre-calculate the heights of a jumping character over time and store them in a table. You can also save on calculations. Consider, for example, a character that is known to be currently walking on the ground. In a profile game (Mario, for instance), this character is necessarily at the junction between two tiles in the vertical direction. When the character is in this position, the first thing to check is whether it is still standing on solid ground, since this is always the immediate collision. Only then do you need to worry about collisions in the horizontal direction.

With respect to how you govern movements and the results of collisions, it is important to recognize that the physics in platform games is seldom realistic. Consider, for example, that it is sometimes possible to change direction in mid-air while jumping, and objects do not as a rule bounce when they hit the ground. As mentioned in Chapter 22, such behavior often makes the game more appealing to the player.

As discussed in the previous section, most TBGs use solid tiles. However, other options are available. Among other things, you might employ a collision map to subdivide a tile into smaller pieces. If you use this approach, as Figure 23.1 illustrates, instead of calculating collisions according to whether a tile is wholly solid or empty, you can employ the collision map so that collisions can be detected on the basis that the tile is solid or empty only in places.

Figure 23.1. A tile with its associated collision map.

To use the collision map as shown in Figure 23.1, you store the normal details along with the collision information. Since this approach makes collision detection more complicated, it’s sensible to limit the number of complex tiles in use. You can also consider using a vector approach instead of a collision map bitmap. If you use the vector approach, the tile illustrated in Figure 23.1 might be thought of as “a wall from top-right to bottom-left.” While less versatile, this approach increases the speed of collision detection.

Another extension of the tile concept involves tiles that change over time. Tiles change in different ways. They can change continuously, as with a conveyor belt, or they can change when triggered by some action, as when a cube of ice melts when stood on. In principle, such changes aren’t complicated, but they are awkward to deal with in the compositing process. To save time, you don’t want to redraw the whole level each time a particular tile changes. Instead, you need only to change the tiles that are currently in view. To accomplish this, you can draw such tiles over the existing level image.

As a further extension, tiles that move from place to place, such as moving platforms, can be dealt with as characters rather than level tiles. Such tiles can be drawn on top of the level image after the fixed world has been copied across. It’s a judgment call regarding other examples. Consider, for example, growing trees, exploding barrels, or whatever else your imagination comes up with. Whether you want to see them as discrete objects drawn on top of the world or tiles in their own right depends on how much work you want to do and how much you feel your game must be optimized. In general, if something can be a tile, to increase performance, it’s better to explore optimization but not necessarily to assume that it is absolutely essential.

The most traditional form of tile-based 3-D game features an isometric world, which you encountered in Chapter 17. Isometric worlds do not differ greatly from 2-D TBG worlds. As illustrated by Figure 23.2, the only significant difference is that the tiles of isometric worlds, representing areas of ground, are drawn as rhombuses instead of squares. However, this is not the whole story. Since isometric worlds are 3-D worlds, the tiles of isometric worlds have height as well as length and width. Generally, the height of a tile is stored along with the tile. When you draw the tile at the appropriate position, it is offset by its stored height.

Figure 23.2. The world of an isometric game.

Many developers today take advantage of 3-D acceleration to display the features of isometric worlds. However, the worlds of the original games of this type were drawn in real time using an approach similar to the one discussed in the previous section for the 2-D TBG.

One of the hardest parts of creating a good isometric game involves control of the character. The principal problem is that movements corresponding to left/right and up/down on the grid don’t correspond to equivalent movements on the screen. Various solutions address this problem. One is to use a point-and-click interface. With a point-and-click interface, you instruct a character to move to a particular spot by clicking on the spot on which the character is to move. Another solution entails using diagonal keys, as in the classic Qbert.

A more fundamental problem arises in situations in which the character can move in dynamic ways. Consider a character that flies over an isometric landscape. If you are working with 3-D, no immediate way exists to distinguish between an object near the camera but high up and an object further away but low down. Because the world is isometric, you can’t even use relative size to help you out. Different solutions to this problem have been presented. An early approach involved using a shadow. The shadow showed the flying character’s position relative to the tile plane.

No rule exists requiring you to use isometric 3-D. Mainly, it is a tradition. The same tile-based technique works just as well for any 3-D world. The original Tomb Raider, for example, clearly shows its origin in tiles. Most of the world is made up of square-based blocks of various sizes and shapes. In fact, there was little essential difference between the original Tomb Raider and Super Mario World. At its heart, each was a simple game in which you had to find your way to a goal in a tile-based environment, dodging or defeating enemies and collecting items along the way.

Many of the issues associated with 3-D isometric games come down to camera control, and camera control is a topic reserved for Chapter 24. Short of camera control, you face the same issues that surfaced in the discussion of TBG games. With respect to these issues, the techniques already discussed still apply. However, the techniques can be enhanced due to the options afforded by the added dimension. Consider, for example, what happens to tiles. Since they no longer have to conform to the isometric grid, with 3-D worlds, tiling can involve more interesting shapes. Among other things, they can have slanted tops. Additionally, you can also apply textures and lights to the surface independently of the tile shape, which gives you much more leeway for design. Collision and visual elements of the tile are separated.

With respect to techniques for collision detection, as with the complex tiles discussed in the previous section, 3-D provides some interesting options. Drawing in part from previous explorations, to consider two such options, you can define tiles with a height map or you can use a vector description such as “sloping down from left to right at an angle of 30° from a height of 50.” If your tiles are reasonably small, using the vector description is almost certainly a better choice. Among other things, this approach leaves you plenty of leeway to create rich surfaces, especially with the addition of textures and bump maps.

To apply some of these observations to code, the box3DTileTopCollision() function makes use of the vector approach to test for collisions between a 3-D AABB and the top of a single tile. To construct this function, you make several assumptions. One is that the tile has a flat top whose normal is known. Two more assumptions are the height of the center point and that the tile has a size of 16. A final assumption is that other faces are all aligned to the coordinate axes. The function is a long one, and Exercise 23.1 challenges you to make it so that the function detects collisions with an increased number of faces.

function box3DTileTopCollision(center, width, length,
                                height, displacement,
                                tileCenter, tileHeight, tileNormal)
   // width, length and height are the
   //half-lengths of the sides of the box
   // calculate tile top edges
   set edge1 to crossProduct(tileNormal,
                               (1,0,0)) // edge vector parallel to z-axis
   set edge2 to crossProduct(tileNormal,
                               (0,0,1)) // edge vector parallel to x-axis
   multiply edge1 by 16/edge1[3]
   multiply edge2 by 16/edge2[1]
   // find vertices
   set c to tileCenter+(0,tileHeight,0)
   set v1 to c-edge1/2-edge2/2
   set v2 to v1+edge1
   set v3 to v2+edge2
   set v4 to v1+edge2

   set t to 2

   // find collision time with base of box
   if displacement[2]<0 then // box is going down
      set planec to center+(0,-height,0) // start height of base
      set vtop to the one of v1, v2,
                              v3, v4 with the highest y-coordinate
      set t1 to (vtop[2]-planec[2])/displacement[2]
      // possible collision during time period
      if t1<1 and t1>=0 then
         // check for intersection within box base
         set p to vtop[2]-t1*displacement-planec
         // vector from box center to intersection point
         if abs(p[1])<width and abs(p[3])<length then
            set t to t1 // top vertex collides
         end if
     end if
     // NB: if there is a collision with this vertex,
     //it has to be the first collision
   end if

   if t=2 then // try other collisions with base
      if dotProduct(displacement, tileNormal)<0 then
         // find the vertex of the box that
         //would collide with the tile face
         set basevertex to planec
         if tileNormal[1]<0 then add (width,0,0) to basevertex
         otherwise add (-width,0,0) to basevertex
         if tileNormal[3]<0 then add (0,0,length) to basevertex
         otherwise add (0,0,-length) to basevertex
         // basevertex is the leading vertex
         // on the box with respect to the tile top

         set t2 to dotProduct(basevertex-c, tileNormal) /
                                dotProduct(displacement, tileNormal)
         // leading vertex intersects tile plane
         if t2<1 and t2>=0 then
            // check for intersection within tile
            set p to basevertex +t2*displacement-c
            if abs(p[1])<8 and abs(p[3])<8 then
               set t to t2 // leading vertex collides

            end if
         end if
      end if
      // NB: again, this collision will always
      // come before any other potential collision
   end if

   if t=2 then // try edge-to-edge collision
      set n1 to crossProduct((1,0,0), norm(displacement))
      // n1 is the normal of the plane swept
      // out by x-aligned edge of box
      set s1 to dotProduct(basevertex-vtop,n1)
      if s1>0 then
         set s1 to -s1
         set n1 to -n1
      end if
      // check for intersection with z-aligned axis of tile
      divide s1 by dotProduct(edge1,n1)
      if dotProduct(c-vtop,edge1)<0 then set s to -s1
      otherwise set s to s1

      if s>=0 and s<1 then
         set p1 to vtop+s1*edge1 // intersection point with edge
         set t3 to magnitude(p1-basevertex)/ magnitude(displacement)
         if t3<1 and t3>=0 then set t to t3
      end if
      || repeat for other edge pair
   end if
   if t<1 and t>=0 then return t
end function

This function takes advantage of several optimizations that result from the alignment of the boxes. For example, since the edges of both boxes are aligned with the axes, as shown in Figure 23.3, only two possible edge-edge collisions can occur. In this respect, note that the vertices marked vt and bv correspond to the variables vtop and basevertex in the code for the box3DTileTopCollision() function.

Figure 23.3. Possible edge-edge collisions with a 3-D tile.

A final example of a TBG is a game set on one or more curving paths. Since this is a complex scenario, it is not possible discuss it at great depth. However, a few central points can be made. For one, although nominally constructed in 3-D environments, this game is limited to a single path that curves through the game world, with a small range of movement in either the x or y directions.

As it is, you can’t be sure how particular games are programmed, but it’s interesting to speculate how a game using spline-based tiles might be created. One way involves describing the main path in terms of a 3-D spline, which is then mapped to a simple 2-D tiled map. To review the context of this notion, see Figure 21.2.

When a game using spline-based tiles is loaded, you translate the 2-D map into 3-D, just as you do with a normal platform game, but you also curve the map to fit onto the spline. Such methods can be used to create racing games. You transform a straight line into a curved track, either on a plane or curving through space as in more space-age racing games.

The most useful aspect of using spline-based tiles is that you can perform all your collision detection routines in the simple tile space, using actual 3-D space for display purposes only. However, working this way requires more than a little fiddling to achieve effects that are robust and feel natural. This is especially so when you deal with speeds along different curves of the track. In the end, however, the approach offers many payoffs.

Complete the box3DTileTopCollision() function and extend it to take into account collisions with the other faces of the tile. The version given in the chapter leaves some of the work unfinished. See if you can complete it. Then finish it off by doing some of the easier work of detecting collisions with the other faces. Note that there are only two other possible face-face collisions. Attending to them should be reasonably straightforward, but don’t forget that the top edge is not parallel to the ground.