Home Tile Engine Articles Resources Contributors Terms and Conditions

Mazes and Labyrinths: An Introduction to Random Levels

By: Josh "VertexNormal" Tippetts

If you have ever played older classic games such as Rogue, Angband or Nethack, or newer classics along similar lines such as Diablo and Diablo 2, then you are familiar with the idea of randomly generated dungeons. The basic premise is simple: each time you play a certain level of a game, the layout of the level and the locations of various creatures, treasures and objects is randomized. Each play session represents a unique experience within the gameplay parameters set by the game engine. Though the mechanics and rules remain the same, the unpredictability of the world adds an additional dimension to the gameplay. Rather than being able to memorize the tricks and secrets of a dungeon, area or world, the player must instead spend time exploring each time he plays, and must place the fate of his character at least somewhat in the hands of chance, fate, and that otherworld entity known as the Random Number Generator.

The random dungeons of Nethack


This article will focus on various techniques for generating random levels within the context of a 2D, tile-based game world. Included with the article is the source code for a simple test-bed to demonstrate some of the concepts discussed here. For the purposes of this discussion, we will assume a 'typical' dungeon-exploration game from any of the classical 2D genres. No 3D heightmaps, smoothly varying elevation, etc... Just simple tile-based grid-work. The techniques demonstrated here, and the accompanying source code, are founded upon a simple tile-based engine that is scripted using the Lua embedded scripting language for clarity and ease of use.

Fundamentally, randomly generating a level is simple. At the most basic level, pure random (or pseudo-random) noise scattered across a map creates a level that is certainly unpredictable. However, realistic gameplay poses additional constraints. The level must 'make sense' within a given context. This usually means adhering to some overall theme for the level, and means as well ensuring that all areas of the level are accessible by the player given the movement methods available to the character. Areas of the level must be connected together, and the overall appearance of the level must fit some pre-determined theme or idea. If there are disconnected bits of the level that can not be reached, there must be a sensible reason as to why not, and the player should _never_ be left stranded on a level with no way to progress forward, unless it is by his own avoidable foolishness-- and even then, means should be available to overcome such mistakes.

Before getting started, you may want to read up on the Interface and Controls of the Accidental Engine, to familiarize yourself with the way the engine works and how scripts for it are structured.


UPDATE: There have been a few small changes and some pretty major changes in the way the Engine works. It is no longer necessary (as is stated in this article) to shutdown the Engine, edit the MapScript string, and restart the engine in order to change the map script. The Engine now implements a drop-down console that can be used for executing Lua code by the engine. Now, changing the map is as simple as opening the console, entering a string such as dofile("data/scripts/scriptname.lua"), and pressing ENTER. The console can be opened and closed using the ESC key, or by clicking on the UI button labeled CONSOLE. Arbitrary code can be executed from the console, so some caveats apply. It is possible to enter an entire map-generation script piecemeal by way of the console, but the order of operations still applies. The interface isn't 100% idiot proof. Hell, if it's 50% idiot proof I'd be surprised. So be warned. Error text output printed from Lua will still appear in stderr (in the console on Linux, or in the file stderr.txt created after program exit on Windows) and text printed using Lua's print function will still appear in stdout. A helper function, CPrint(), has been included in startup.lua to simplify printing strings of text to the in-game console itself.


Entry-level Tile Engine Scripting

Now that we are somewhat familiar with the Tile Engine scripting interface, let's try a simple test to see how it works. As stated before, the simplest of randomly generated levels consists of random noise scattered across the map, so let's try it. This script will initialize the map, scatter random grass, dirt and water across the map, then scatter some random walls. Very noisy, and it creates levels that don't make much sense, but it's a place to start. The script can be found in the file data/scripts/noisemap.lua:

noisemap.lua

-- noisemap.lua
-- Scatter floor and wall noise across the map

-- Map dimensions
MW = 129
MH = 129


-- Initialize
Builder:ResetMap(MW, MH)

-- Wall in the edges to keep the player from walking off the edge
Builder:WallEdges(1)

-- Now, loop on all tiles inside the outer edges, and add some random noise to the map
for tx=1,MW-2,1 do
for ty=1,MH-2,1 do
  local Random
  Random = RandRange(0,2)

  -- Set floor randomly to grass, dirt or water
  Builder:SetFloor(tx, ty, Random)

  Random = RandRange(1, 100)

  if Random < 20 then

   -- Set wall
   Builder:SetWall(tx, ty, 1)
   -- Flag the wall BLOCKWALK so the player can not walk there
   Builder:SetFlag(tx, ty, TF_BLOCKWALK)
  end

end
end


-- Now, translate the map
Builder:FinalizeMap()

-- And done...

To see this script in action, open the data/scripts/startup.lua file in a text editor such as Notepad, and edit the MapScript string to "data/scripts/noisemap.lua", then execute the program.

A simple map made from random noise.


As you can see, this script is very simple. It simply walls in the edges of the map (you should perform this step for every level, to keep characters from going beyond the boundaries) then fills the interior of the walls with random noise floors and walls. For wall placement, a random number between 1 and 100 is chosen, and if this number is less than 20 then the tile is walled. For the floor, a random number from 0 to 2 is chosen, and this is used as the floor type. Very simple, and the results are pretty much what you would expect.

Simple noise techniques are not always the best to use, but in some situations they can be very useful. Some types of levels, such as forest or woodland, or pretty much any rough outdoor area in general, are usually going to have randomly placed objects such as trees and rocks that don't necessarily hold to any given pattern. Placement of these objects can be simple and straightforward. Here is the noisemap tweaked with some random forest (data/scripts/noiseforest.lua):

noiseforest.lua

-- Initialize
Builder:ResetMap(MW, MH)

-- Wall in the edges to keep the player from walking off the edge
Builder:WallEdges(1)

-- Now, loop on all tiles inside the outer edges, and add some random noise to the map
for tx=1,MW-2,1 do
 for ty=1,MH-2,1 do
  local Random
  Random = RandRange(0,1)

  -- Set floor randomly to grass, dirt or water
  Builder:SetFloor(tx, ty, Random)

  Random = RandRange(1, 100)

  if Random < 20 then

   -- Set wall
   Builder:SetWall(tx, ty, 1)
   -- Flag the wall BLOCKWALK so the player can not walk there
   Builder:SetFlag(tx, ty, TF_BLOCKWALK)
  end

 end
end

for i=1,1000,1 do
 local Random
 Random = RandRange(1,6)

 -- Generate coordinates
 local TX, TY
 TX,TY = RandomNonblockedTile(15)
 if TX == -1 then
  return
 else
  local WhichTree = "Tree"..Random
  PropFunctions[WhichTree](TX,TY)
 end
end

 -- Now, translate map
Builder:FinalizeMap()

Add a few trees with random noise...


So as you can see, pure random noise has it's place in random generation, but for the most part we need to mix it with algorithms that make more 'sense.' Such as mazes.

On To the Mazes

Mazes are a step up from random noise in that there is order and organization to the level. However, they are still fairly pointless (except for the pure fun of 'solving' them). But it's a good trick to learn next, and can be used as a building block for more sophisticated levels, so let's see how to create a maze.

Typically, when people think of mazes they think of twisting passages winding hither and yon. In all good mazes, there is a path from start to finish. In some, there may be multiple paths, in others there may be only one. This first technique will generate a maze that may have multiple paths between any two given points, and guarantees that no part of the maze is unreachable. Let's first take a look at our maze generation functions, which can be found in the file data/scripts/mazefuncs.lua--

Maze generation function interface

The first function is the DrawWall() function:

function DrawWall(sx,sy,dir,len)
  local stepx, stepy
  if dir==0 then stepx=0 stepy=-1 end      -- Up
  if dir==1 then stepx=-1 stepy=0 end      -- Left
  if dir==2 then stepx=1 stepy=0 end       -- Right
  if dir==3 then stepx=0 stepy=1 end       -- Down

  local currx=sx
  local curry=sy
  local i
  for i=1,len,1 do
    if Builder:GetFlag(currx, curry, TF_OFFLIMITS) then return end   -- Hit a wall or other protected location
    Builder:SetWall(currx, curry, 1)
    Builder:SetFloor(currx, curry, 1)
    Builder:SetFlag(currx, curry, TF_BLOCKWALK)
    Builder:SetFlag(currx, curry, TF_OFFLIMITS)
    currx = currx+stepx
    curry = curry+stepy
  end
end

This function accepts a starting tile (sx,sy), a direction (dir) and a length (len), and will attempt to 'draw' a wall on the map in the given direction. The wall is drawn such that it will stop drawing the moment it hits a tile that is blocked (OFFLIMITS), or when the given length is reached. A wall can be drawn in one of 4 directions: up(0), left(1), down(2) and right(3). Drawing a wall simply iterates on len, stepping in the given direction and setting a wall at each location. We then mark the tile OFFLIMITS to prohibit further walls from being placed here, and mark it BLOCKWALK so that it will block the player from walking there.

The next function we want to look at is SelectWallStart():

function SelectWallStart(Granularity)
  local SX
  local SY
  local XTarget = MW/Granularity
  local YTarget = MW/Granularity
  SX = Granularity * RandTarget(XTarget)
  SY = Granularity * RandTarget(YTarget)

  return SX, SY
end

This function accepts a parameter called Granularity. Granularity defines the spacing between the walls of the maze, and should be specified as a power of 2 for best results. The smaller Granularity is, the narrower the corridors of the maze will be. Granularity=2 creates a maze where the corridors are 1 tile wide, while a Granularity of 4 creates corridors that are 3 tiles wide. In all such mazes, the walls themselves are only 1 tile wide. SelectWallStart() merely finds a random tile coordinate that lies on the corridor boundaries defined by Granularity.

Next, we have the function AttemptRandomWall() --

function AttemptRandomWall(minlength, maxlength, granularity)
  local WX
  local WY
  WX,WY = SelectWallStart(granularity)
  if Builder:GetFlag(WX, WY, TF_OFFLIMITS) ~= nil then return end      -- Starting location is protected
  local Dir
  Dir = RandTarget(4)
  local Len
  Len = RandRange(minlength, maxlength)
  Len = Len * granularity + 1   -- Length is specified in corridor-widths
  DrawWall(WX, WY, Dir, Len)
end

This function is the workhorse of our maze generator. It accepts 3 parameters (minlength, maxlength, granularity) and attempts to draw a single wall in the maze. Minlength and maxlength determine the average length of the walls to draw. Shorter walls result in mazes with more corners and twists, while longer lengths can result in mazes with longer stretches of corridor. Granularity, of course, determines the spacing of the walls.

The function works by first selecting a random starting location. It checks this location to see if it is blocked, and returns if it is. This prevents walls from starting on other walls, and thus prevents portions of the maze from being closed off and inaccessible. A wall can end on a closed tile but it can not start on one, so all areas of the maze are guaranteed to be reachable. If the location is open, then the function randomly determines a direction for the wall to run and a length to draw. The length is specified in terms of maze units rather than tiles, where a maze unit is determined by Granularity. For instance, if the final length of the wall is 2 and the Granularity is 2, the wall will be drawn of length 5 tiles, thus encompassing 2 adjacent blocks or pieces of the maze. The same wall of length 2 in a Granularity=4 maze would be drawn at length 9 tiles. This ensures that all corridors and passages maintain a consist width defined by Granularity. Finally, the function passes the calculated parameters to DrawWall() to do the work.

The last function we want to look at in mazefuncs.lua (for now) is the GenerateMaze() function--

function GenerateMaze(MinLength, MaxLength, Granularity, NumWalls)
local count
for count=1,NumWalls,1 do
  AttemptRandomWall(MinLength, MaxLength, Granularity)
end
end

This simple function iterates on NumWalls and attempts to generate that many random walls at the given Granularity and length restrictions.

Now, let's take a look at the means to build the maze. In the file data/scripts/maze1.lua you will find this code:

maze1.lua--

Builder:ResetMap(MW, MH)
Builder:WallEdges(1)

local NumWalls = 8000
local Granularity=4
local MinLength=2
local MaxLength=4

GenerateMaze(MinLength, MaxLength, Granularity, NumWalls)

Builder:FinalizeMap()

Our very first maze.


Simply put, this piece of code merely calls GenerateMaze() to draw a certain number of walls, in this case 8000. Fixing a quota of attempts and making AttemptRandomWall() fail gracefully prevents the algorithm from locking itself into an infinite loop if there are no valid locations to start a wall. The walls that are drawn range in length from 2 to 4 maze units, and the granularity is specified as 4. Thus, walls will be 9 to 17 tiles long, though it is possible for walls to be shorter than the specified range, since they will terminate when they hit another wall.

There is a slight problem with this method, in that you are not guaranteed to fill all valid starting locations. That is, when the algorithm completes there may be areas of the maze that are wider than the corridor width because there were not enough walls to fill all available wall space. This can be minimized by choosing a large enough number for count to iterate on. The more walls you attempt to draw, the more likely it is that the loop will fill in all available wall locations and generate a complete maze. And since we are only developing this algorithm as a building block for bigger and better things, this caveat is relatively insignificant.

You can play with the values for MinLength, MaxLength, NumWalls and Granularity to see the various effects they can have on the final maze.

A maze with Granularity=2


The mazes generated using this method are straightforward, regular, and usually have multiple paths to get between points. They tend to not be very difficult to solve, and finding your way through them usually is pretty straightforward. Dead-end paths are usually not very long. By combining mazes of different Granularity levels, however, we can increase the variety and difficulty of the maze.

If you generate a maze with a large Granularity, say 16, and long walls, then you get a maze with very wide corridors and very long stretches of unbroken passageways. This in effect segregates the level into large areas and sections. These larger sections can then be filled in with shorter pieces of walls at lower Granularity levels. By playing with the number of walls to draw as well, you can greatly modify the appearance of the maze. The maze thus generated can have very long dead-end paths that must be explored at length before their nature is discovered, making the level more difficult to solve. The following code creates a maze using 4 levels of Granularity. You can tweak the various parameters for each stage to see how each contributes to the whole. This code can be found in data/scripts/maze2.lua--

maze2.lua--

Builder:ResetMap(MW, MH)
Builder:WallEdges(1)

GenerateMaze(2,4,16,200)
GenerateMaze(2,4,8,400)
GenerateMaze(2,4,4,1000)
GenerateMaze(1,2,2,200)

Builder:FinalizeMap()

A maze with 4 levels of Granularity(16,8,4 and 2)


We rough out a maze at larger sizes, then iteratively fill in details at lower levels. By playing with the number of walls to draw as well, we can modify the density of the maze in random places, and generate some interesting variety.

This technique, of using progressively denser maze iterations, can be used to generate levels that might be useful in a standard castle-like environment. Lower level granularity maze walls will frequently wall off larger pieces of higher granularity corridor, creating 'rooms' to be explored. All of the various parameters can be adjusted to tweak the final output.

Rooms, Features, and other Interesting Stuff

Now, this technique on it's own can create some pretty interesting mazes, but good levels usually have more than just mazes to explore. We can run some random item and prop generation algorithms to scatter good stuff through the mazes, such as rocks and trees and healing potions and ghouls and zombies, but frequently we will want a little greater control over what is placed where, and over the layout of certain sections of the maze. This is where the idea of Features comes in.

The maze generator can create rooms or room-like enclosures quite by accident, but we can also generate rooms explicitly, according to pre-determined patterns or layouts. To do this, we first need to add a new function definition to our data/scripts/mazefuncs.lua file, LayoutFeature()--

function LayoutFeature(sx, sy, FeatureDef)
 local w=FeatureDef.Width
 local h=FeatureDef.Height
 local Floors=FeatureDef.Floors
 local Walls=FeatureDef.Walls
 local x,y

 for x = sx,sx+w,1 do
  for y = sy,sy+h,1 do
   if Builder:GetFlag(x,y,TF_OFFLIMITS) then return 0 end  -- Can not place it; something already there
  end
 end

 -- Iterate and set features
 for x=1,w,1 do
  for y=1,h,1 do
   Builder:SetFloor(x+sx-1,y+sy-1,Floors[y][x])
   Builder:SetWall(x+sx-1,y+sy-1,Walls[y][x])
   if Walls[y][x]==1 then Builder:SetFlag(x+sx-1,y+sy-1,TF_BLOCKWALK) end
   if Floors[y][x]==2 then Builder:SetFlag(x+sx-1,y+sy-1,TF_BLOCKWALK) end
  end
 end

 return 1
end

LayoutFeature() accepts a tile coordinate location and a definition table for the room. Our simple room constructor expects a room definition table to have a certain structure. It must have Width and Height members to define the width and height, in tiles, of the room; it must also have two 2-dimensional arrays sized Height x Width, indexed as Table[y][x], one array called Floors and the other called Walls. The LayoutFeature() function performs a couple of actions. First, it iterates the area of the room and checks each tile for OFFLIMITS, which would indicate that a room or other feature has already been placed that intrudes on the prospective area. At this point we return 0, since we can't stack one room on top of another. If the area checks out, then we iterate the area again and set the tile floor from Floors and the wall from Walls. If a floor is water or if there is a wall, we also set BLOCKWALK to prevent the player from walking there. When we are finished setting walls and floors, we return 1 to indicate success.

We also want to implement a quick function to set a rectangle off limits. It'll come in handy in lots of situations--

function RectOffLimits(sx, sy, w, h)
 for x=sx,sx+w-1,1 do
  for y=sy,sy+h-1,1 do
   Builder:SetFlag(x, y, TF_OFFLIMITS)
  end
 end
end

In the file data/scripts/maze3.lua, we see the familiar maze2.lua script with a new addition-- a Lua table called Features, which holds functions to generate various rooms or features. For now, we only have one Feature defined, the CavesOfHellEntrance (which is obviously the entrance to the Caves of Hell, probably a very unsavory place; it's a good thing we can't actually enter the cave--yet). Each entry in a Feature table is a function which is called with a set of tile coordinates for the upper left corner of the area covered by the feature. Calling an element of the Features table will either place the feature in the given location, or return 0 to indicate failure. Our sample CavesOfHellEntrance feature definition looks like this--

FeatureTable["CavesOfHellEntrance"] = function(sx, sy)
 local FeatureDef=
 {
 Width = 17,
 Height = 17,

 Floors = {
  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
  {0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0 },
  {0,0,0,0,2,2,2,2,2,2,2,0,0,0,0,0,0 },
  {0,0,0,1,2,2,2,2,2,2,2,2,2,2,1,0,0 },
  {0,0,2,2,2,2,2,2,2,2,2,2,2,2,1,1,0 },
  {0,0,2,2,2,2,0,0,0,0,0,2,2,2,1,1,0 },
  {0,1,2,2,2,2,0,0,1,0,0,2,2,2,0,1,0 },
  {0,1,2,2,2,2,0,1,1,1,0,2,2,2,0,1,0 },
  {0,0,0,2,2,2,0,0,1,1,0,2,2,2,0,1,0 },
  {0,0,0,2,2,2,0,0,1,0,0,2,2,2,1,1,0 },
  {0,0,0,2,2,2,2,0,1,0,2,2,2,2,0,0,0 },
  {0,0,0,2,2,2,2,2,1,2,2,2,2,0,0,0,0 },
  {0,0,0,0,0,0,2,2,1,2,2,0,1,1,0,0,0 },
  {0,0,0,0,0,1,1,2,1,2,1,1,1,1,0,0,0 },
  {0,0,1,1,1,1,1,1,1,0,1,1,1,0,0,0,0 },
  {0,0,0,1,0,1,1,1,1,1,1,1,1,0,0,0,0 },
  {0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0 }
 },

 Walls = {
  {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 },
  {1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1 }
 }
 }

 LayoutRoom(sx, sy, FeatureDef)

 -- Place cave
 PropFunctions["CaveEntrance"](sx+8, sy+8)
 PropFunctions["Tree3"](sx+8, sy+5)
 PropFunctions["Tree5"](sx+6, sy+9)
 PropFunctions["Tree6"](sx+10, sy+9)

 -- Now, fixate with OFFLIMITS
 RectOffLimits(sx, sy, FeatureDef.Width, FeatureDef.Height)
end

The first thing we see is a local table called FeatureDef, which is structured in the format expected by LayoutFeature(). It includes the dimensions of the rectangle the feature will occupy, and the arrays for Floors and Walls which LayoutFeature() will use to set tiles. After defining the layout, the creation function calls LayoutFeature() to set the tiles. After that, we place a few test props including the actual cave entrance (doesn't really go anywhere; it's just another prop) and maybe a few trees. Once the feature is constructed, we run a pass of RectOffLimits() over the top of everything to freeze it in place, and keep the maze generator from trampling our nice new feature.

To correctly work with our maze generator we should construct rooms that are dimensioned as odd numbers. This ensures that any outside walls encircling the room will lie on even numbered rows and columns, where maze walls at Granulariy=power-of-2 can be created. To do otherwise may result in maze walls being generated directly adjacent to room walls, creating a double-width wall. While the map translator has no problem with this sort of wall, it mars the neat, tidy appearance of our maze. Likewise, rooms should be placed at even-numbered coordinate locations, to facilitate this matching up of room walls with maze walls. If the room is walled on the outer perimeter, doorways should be placed to line up with where maze corridors may adjoin the wall. For instance, single-width openings may be placed at odd-numbered coordinate locations, and so forth. Placing openings on even-numbered locations runs the risk of a maze wall running up to the perimeter of the room and creating an odd juncture of tiles where the player must sort of squeeze through a gap in order to get in or out; this sort of thing should be avoided.

Of course, this is only a general guideline, as a Feature can really be anything you want, including non-rectangular. A Feature is just a function that we call before filling the rest of the level with maze corridors, and it can be as simple as placing a rock, or it can be as complicated as constructing an entire castle to fill the entire map. That is the beauty of a simple, dynamically typed scripting language such as Lua; code and data become intertwined, and constructing elaborate structures of code and data can be done with ease.

The room technique is used to seed a level with 'interesting' things-- throne rooms, locked vaults, prison cells full of bones hanging from shackles, and so on. Whatever you desire. After the level is seeded with Rooms, the maze generator is called to fill in the spaces in between.

Let's take a look at our room. This code can be found in data/scripts/maze3.lua--
Builder:ResetMap(MW, MH)

Builder:WallEdges(1)

-- Randomize grass/dirt
local x,y
for x=1,MW-2,1 do
 for y=1,MH-1,1 do
  local Type
  Type = RandRange(0,1)
  Builder:SetFloor(x,y,Type)
 end
end

FeatureTable["CavesOfHellEntrance"](56, 54)

GenerateMaze(2,4,16,500)
GenerateMaze(2,4,8,1000)
GenerateMaze(2,4,4,400)
GenerateMaze(2,3,2,800)

Builder:FinalizeMap()

The Entrance to the Caves of Hell. Terrifying.


A Brief Introduction to Props and Objects

Now, in some of our examples, we have seen the use of props without really delving into the specifics. We'll briefly discuss props now, for future reference.

Props are the various non-floor, non-wall objects that are used to make things interesting. Rocks, trees, campfires, tents, jars, and so forth. In the Tile Engine, props are simply static images, drawn at a certain location. The tile BLOCKWALK flag can be leveraged to emulate props blocking tiles, but in a real game it is likely you will want to expand the functionality and game 'presence' of props. Perhaps, some props may be interactive, allowing the player to push them around, knock them over, etc... As well, the Tile Engine will use static props where a real game would instead use other dynamic objects, such as items, treasure chests, and so on. The purpose of the Tile Engine is not to provide a complete game or game framework (though as I work on it it seems to be evolving that way). The purpose is to demonstrate level generation techniques, so for now it can get away with using static props for everything.

Props are stored and loaded as .TGA (Targa) format images stored in the data/props/ directory. In the generation script, they are constructed using the Builder:InstanceProp(name, width, height, offsetx, offsety) function, which takes a few parameters. The name parameter gives the name (minus the .tga extension and the data/props/ path) of the prop image file. The parameters width and height specify the size of the image, and can be different from the actual dimensions of the .TGA image in order to allow for scaling. Finally, offsetx and offsety define the coordinates in the image that correspond to the 'center' of the prop. The center of the prop is the specified world coordinate location at which the prop sits; for a tree, for example, the center or offset indicates the bottom end of the trunk where the tree enters the ground. Actually, InstanceProp() must specify this as a negative offset into the image, since that is the way the animation engine expects it. To find the offset of your own props, open the image in the Gimp, find the image coordinate of the location you wish to be the center, and negate these coordinate values when instancing the prop. Prop images are stored with an alpha channel for transparency, since the Tile Engine uses OpenGL as the underlying renderer and alpha blending to implement sprite transparency.

Once a prop is instanced, it can then be placed using the Builder:PlaceProp() function. This function takes a coordinate (x,y) in world units and a prop, and attempts to place the prop in the map. Note that by default, no specific checks for blocking terrain etc. are performed; if the world coordinate location resolves to a valid tile coordinate, the object should be successfully placed, regardless of whether or not that space is already occupied by something.

In the file data/scripts/propfuncs.lua, I define a table full of functions that can be called to instance any particular prop. Ideally, I would use several of these tables, with prop tables customized per level and area, but for illustrative purposes one large table works well enough. Each prop constructor accepts a pair of tile coordinates, and the prop is placed at the center of that tile. It is up to this function to query the MapBuilder interface for pertinent blocking data (I usually use OFFLIMITS, NOITEM, etc... to check if I can place a prop somewhere) and return 0 if the prop could not be placed. Otherwise, the function will instance the prop and put it in the map. It is also the responsibility of the prop function to set any blocking flags. Some props may be large, and may cover several tiles; special care should be taken with these to correctly block portions of the map that the prop should occlude.

And that's it for this (long) installment. Included with the sample code for this tutorial is a map script called ????? which demonstrates these techniques in generating a complicated level. In the next tutorial, I will try to delve more deeply into the structuring of Features, as well as introduce some other filler-type algorithms than the maze generator. Until next time....

All content on page copyright 2004 Joshua Tippetts