Roguelike, step 3: procedural generation

Previous tutorial – Download files – Next tutorial

Dull, dull, incredibly dull – A recipe for a three-layered dungeon – As the world shifts – Putting the dark in dark, scary dungeon – Turning tables into books and back again

At this stage, our little template for a top-down tile-based game is like a baby RPG.  If you’ve already programmed a 7-day roguelike with the c programming language and libtcod, you’ve probably wrapped your mind around the Gideros Mobile environment and you’re ready to take Step 2 and turn it into the next Sil.  If you’re not so experienced, or you just want to see how I expand the template into a full game, then keep reading.

Dull, dull, incredibly dull

When last we left off, generateTerrain() and placeMonsters() in our WorldMap class simply a returned hand-typed arrays to represent our TileMaps.  Going forward as game designers, we can either

  1. Continue to hand-type our maps.
  2. Load Tiled to create a bunch of maps that we can use in our program (see the Tiled Map Editor programs in your Gideros installation folder for examples of how to do this).
  3. Use an algorithm to create our maps.

Failing to any of the above will result in nobody ever playing our game more than once.  It would always be the same world every time we played.  Dull, dull, incredibly dull.  Choosing option #1 is incredibly boring and surprisingly hard to program; option #2 is how a lot of games do it, especially the AAA studios with dedicated level designers; but option #3 is the Roguelike way to do it.

A recipe for a three-layered dungeon

Enter procedural generation.  Procedural generation in games gets a lot of hype because it promises almost infinite replayability.  Because of its incredible promise, programmers have approached procedural generation from many different angles.  So there’s talk of creating random worlds through BSP algorithms or using Cellular Automata methods.  There’s also Random Walk  generation or Diffuse-Limited Aggregation.  All wonderful things worth reading up on.

When it comes down to the nuts and bolts of programming though, you realize that procedural generation doesn’t mean learning all this theory.  It simply means a function that generate content algorithmically instead of manually.  That being the case, an algorithm can be as simple as we desire.  Here’s one that’ll generate the floor of an old ruin:

for y = 1, LAYER_ROWS do
  for x = 1, LAYER_COLUMNS do
    local i = index(x, y)
    if f then
      local choice = math.random(1, 10)
      if choice ~= 2 then
        choice = 1
      end
    end
    array[i] = choice
  end
end
return array

If we replace the old, hand-typed array in generateTerrain() with the above code, we’ll now have a procedurally generated dungeon floor.  Similarly, add a new tileset

tileset-environment-108px

And a new function addEnvironment()

 --create an array for each layer of size LAYER_ROWS * LAYER_COLUMNS 
 self.mapArrays[LAYER_TERRAIN] = self:generateLevelTerrain()
 self.mapArrays[LAYER_ENVIRONMENT] = self:addEnvironment()
 
 -- assign TileMaps to self.mapLayers
 local group = Sprite.new()
 local layer = self:returnTileMap(self.mapArrays[LAYER_TERRAIN], 
     "images/tileset-terrain-108px.png")
 group:addChild(layer) 
 table.insert(self.mapLayers, layer)
 local layer = self:returnTileMap(self.mapArrays[LAYER_ENVIRONMENT], 
     "images/tileset-environment-108px.png")
 group:addChild(layer) 
 table.insert(self.mapLayers, layer)

And we can now generate a new TileMap layer on top of the dungeon floor.  I added this separate layer so I can add different dungeon features on top of preexisting floors.  WorldMap:addEnvironment() is also very simple.

function WorldMap:addEnvironment()

local array = {}
  local choice = 0
  local p = 0
  for y = 1, LAYER_ROWS do
    for x = 1, LAYER_COLUMNS do
      p = p + 1
      if p > 11 then
        p = 0
      end
      local i = index(x, y)
      --put a wall tile 1 or 2 on the outside of the layer
      if x == 1 or y == 1 or x == LAYER_COLUMNS or y == LAYER_ROWS then
        choice = math.random(1, 2)
      --or every 11th tile put a piller tile 3 or 4      
      elseif p == 0 then  
        choice = math.random(3, 4)
      --irregularly, place a hole (5) or a well (6) on the floor      
      else
        choice = math.random(1, 80)
        if choice ~= 5 and choice ~= 6 then
          choice = 0
         end
      end
      array[i] = choice
    end
  end
  return array
end

This layer has a nice solid wall along the perimeter, with pillars spaced regularly throughout and an occasional hole or well for the hero to discover as well.  I ‘tuned’ the algorithm to create the impression of an old temple.  Definitely mess with it to create your own random world for the hero to walk through.

Having successfully procedurally generated our dungeon, we can now procedurally fill it with monsters.  Before doing that though, let’s go back to main.lua and change things around

--the major gaming variables
local hero = {}
--just x, y to represent the hero for now
hero.x, hero.y = 6, 6
local monsters = {}
--create six random monsters
monsters.list = {{}, {}, {}, {}, {}, {}}
for key, m in ipairs(monsters.list) do
  m.x, m.y, m.entry = 0, 0, math.random(2, 4)
end
--create the world and assign locations for the hero and monsters
local world = WorldMap.new(hero, monsters)

The plan is to have WorldMap:placeMonsters find spots for both the hero and the monsters in our dungeon.  Main.lua will call WorldMap.new with our variables and placeMonsters will assign locations after randomly placing them in the dungeon.

function WorldMap:placeMonsters(hero, monsters)

 --this is the array without monsters
 local mArray = {}
 for y = 1, LAYER_ROWS do
   for x = 1, LAYER_COLUMNS do
     mArray[index(x, y)] = 0
   end
 end
 
 local envArray = self.mapArrays[LAYER_ENVIRONMENT]
 local x, y, i = 0, 0, 0
 
 --find an empty spot for each monster 
 for key, m in ipairs(monsters.list) do
   repeat
     x = math.random(2, LAYER_ROWS - 1)
     y = math.random(2, LAYER_COLUMNS - 1)
     i = index(x, y) 
     --returns true only if there are no monsters there and it's a floor tile
     placed = (mArray[i] == 0) and (envArray[i] == 0) 
   until placed 
   --then add to the array
   mArray[i] = m.entry
   --and modify the monster variable
   m.x, m.y = x, y
 end
 
 return mArray
end

For every monster m, the above code defines m.x and m.y.  The only subtlety here is making sure everyone doesn’t end up on top of each other or on top of a pillar.  The same logic then applies to the hero as well.

As the world shifts

At the end of WorldMap:init(), we also need to add the following code

 self:shiftWorld(hero.x - 6, hero.y - 6)

WorldMap:shiftWorld(), of course, is the very same code we use to move the world as the hero walks around.  When we use it in WorldMap:init(), we insure that the world stays centered around the hero from the start.  Which leaves us with

  1. A dungeon because it’s an old ruin.
  2. A scary dungeon because we have a lone hero facing six monsters.
  3. But it’s not quite a dark, scary dungeon, is it?

We address point #3 next.

Putting the dark in dark, scary dungeon 

There are a couple of ways to light a dungeon.  Cardinal Quest 2 uses recursive shadowcasting.  Cogmind uses a brute force Bresenham raycast model.  By the way, have you checked out all the wonderful tutorials and theory at Roguebasin yet?  My approach is to entirely avoid all that theoretical rhetoric – lovely though it is – and keep it simple.

Here’s the plan.  Say we have a world that looks like this:

 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 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 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 0 0 M 0 0 0 0 0 0 
 0 0 0 0 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 M 0 0 0 
 0 0 0 0 0 0 0 0 0 0 0

But we only want to light up a small area around the hero.  Then all we really need to do is overlay a light map where our hero is standing.

 0 0 2 1 2 0 0 
 0 1 1 1 1 1 0 
 2 1 1 1 1 1 2 
 1 1 1 1 1 1 1 
 2 1 1 1 1 1 2 
 0 1 1 1 1 1 0 
 0 0 2 1 2 0 0

And since a light map sounds like a TileMap, let’s use the tools we know and just add another TileMap layer to our dungeon.  WorldMap:init() will now use four LAYER constants to define four arrays to add four TileMaps to the screen

function WorldMap:init(hero, monsters)

  self.mapArrays = {}
  self.mapLayers = {}

  self.mapArrays[LAYER_TERRAIN] = self:generateLevelTerrain()
  self.mapArrays[LAYER_ENVIRONMENT] = self:addEnvironment()
  self.mapArrays[LAYER_MONSTERS] = self:placeMonsters(hero, monsters)
  self.mapArrays[LAYER_LIGHT] = self:addLight(hero)
 
  local group = Sprite.new()
  local layer = self:returnTileMap(self.mapArrays[LAYER_TERRAIN], 
               "images/tileset-terrain-108px.png")
  group:addChild(layer) 
  table.insert(self.mapLayers, layer)
  layer = self:returnTileMap(self.mapArrays[LAYER_ENVIRONMENT], 
               "images/tileset-environment-108px.png")
  group:addChild(layer) 
  table.insert(self.mapLayers, layer) 
  layer = self:returnTileMap(self.mapArrays[LAYER_MONSTERS], 
               "images/tileset-monsters-108px.png")
  group:addChild(layer) 
  table.insert(self.mapLayers, layer)
  layer = self:returnTileMap(self.mapArrays[LAYER_LIGHT], 
               "images/tileset-light-108px.png")
  group:addChild(layer) 
  table.insert(self.mapLayers, layer)

  self:addChild(group)
  self:shiftWorld(hero.x - 6, hero.y - 6)
end

The light tileset will look like so

tileset-light-short.png

It will be tiles with various levels of transparency, from completely transparent to completely dark.  Tile #1 will be a fully bright tile (can you even see it?), while #4 will function as the completely dark, unexplored areas on the map.

Our fourth layer array is created by calling WorldMap:addLight(hero).

function WorldMap:addLight(hero)
  
  --fill the light array with dark tiles
  local lArray = {}
  for y = 1, LAYER_ROWS do
    for x = 1, LAYER_COLUMNS do
      lArray[index(x, y)] = 4
    end
  end
  
  local torch = {
    0, 0, 2, 1, 2, 0, 0, 
    0, 1, 1, 1, 1, 1, 0, 
    2, 1, 1, 1, 1, 1, 2, 
    1, 1, 1, 1, 1, 1, 1, 
    2, 1, 1, 1, 1, 1, 2, 
    0, 1, 1, 1, 1, 1, 0, 
    0, 0, 2, 1, 2, 0, 0}

  --overlay the hero with a torch array
  local torchIndex = 0
  for y = hero.y - 3, hero.y + 3 do
    for x = hero.x - 3, hero.x + 3 do
      torchIndex = torchIndex + 1
      local i = index(x, y)
      --only change the light array if on the screen
      if i > 0 and i < #lArray and torch[torchIndex] ~= 0 then
        lArray[i] = torch[torchIndex]
      end
    end
  end
  return lArray
end

WorldMap:addLight is slightly misnamed.  addLight() for the most part makes everything dark.  At the end of the day, it does in fact light up the area directly around the hero so we’ll keep the name.

tut3

So there you have it.  A dark and scary dungeon except for a small patch of light where the hero is standing.  And since shiftWorld already moves all the layers when the hero moves, our small patch of light moves around when the hero moves too.  Sometimes it’s wonderful how programs come together.

Turning tables into books and back again

Before we finish up this tutorial, let’s talk about our cyclopedia variable in Constants.lua.  At the end of step 2, it was a simple Lua table that we pull information out of to identify tiles in our map arrays.

cyclopedia = {
 ["monsters"] = {
   [1] = {name = "hero"},
   [2] = {name = "goblin"},
   [3] = {name = "bugbear"},
   [4] = {name = "orc"},},
 ["background"] = {
   [1] = {name = "floor", blocked = false},
   [2] = {name = "floor", blocked = false},
   [3] = {name = "wall", blocked = true},
   [4] = {name = "wall", blocked = true},}}

In CheckMove, for instance, we use WorldMap:getTileKey to pull up the entry and layer we were interested in and then pull that information out of cyclopedia.

 local entry, layer = world:getTileKey(hero.x + dx, hero.y + dy) 
 if layer == LAYER_MONSTERS then 
   local tile = cyclopedia.monsters[entry]

cyclopedia.monsters[2] pulls up {name = “goblin”}.  As such, when we use our cyclopedia, it more like using an index then looking things up in a encyclopedia.  Going forward,

cyclopedia:getEntry("monsters", entry)

will do the exact same thing, but now cyclopedia will be a local instance of a class Cyclopedia and getEntry will be a function in that class.  If we program this class just so, it’ll allow

cyclopedia:getEntry("monsters", "goblin")

which is the main reason we should do it.  With this, we can just look stuff up directly instead of having to always remember which entry corresponds to which number in each list.

To do so, we simply transfer everything into a class.  Here, let’s rename cyclopedia as manual and then put it in a Cyclopedia:init() function.  What our Cyclopedia class is going to do is go through the manual variable and assign each value to a self.lists key.

Cyclopedia = Core.class()

function Cyclopedia:init()
  self.lists = {} 
  local manual = {
  ["terrain"] = {
    [1] = {name = "stone floor"},
    [2] = {name = "stone floor"},
    [3] = {name = "stone floor"},
    [4] = {name = "stone floor"},},
  ["environment"] = {
    [1] = {name = "wall", blocked = true},
    [2] = {name = "wall", blocked = true},
    [3] = {name = "pillar", blocked = true},
    [4] = {name = "pillar", blocked = true},
    [5] = {name = "dirt hole", blocked = false},
    [6] = {name = "well", blocked = false},},
  ["light"] = {
     [1] = {name = "bright"},
     [2] = {name = "dim"},
     [3] = {name = "dark/remembered"},
     [4] = {name = "unexplored"},
     [5] = {name = "white"},
     [6] = {name = "black"},},
  ["monsters"] = {
     [1] = {name = "hero"},
     [2] = {name = "goblin"},
     [3] = {name = "orc"},
     [4] = {name = "bugbear"},},
  }
  for key, val in pairs(manual) do
    self.lists[key] = val
  end
end

At this point, all we’ve done is complicate our cyclopedia variable by putting it in a class and then assigning it to self.lists.  We took our table and put it in a book variable and then assigned it to a table instance.  But there’s a method to our madness.  The point is now to write a custom getEntry function to extract the information directly.

function Cyclopedia:getEntry(list, entry)
  local cyclopedia = self.lists[list]
  local isNumber = tonumber(entry)
  if isNumber then
    return cyclopedia[entry]
  else
    for key, val in pairs(cyclopedia) do
      if val.name == entry then
        return val
      end
    end
  end
end

If we call Cyclopedia:getEntry() with an entry that’s a number, it functions exactly as it did before.  That is, it returns the value associated with that number.  But if we call it with an entry that’s a name, we get the same value.  If we need to refer the tile in the light tileset that’s the dim one, we can use

manual:getEntry("light", "dim")

We can now add pretty much all our useful game information to manual and look it up directly.  Defining different light sources could be done like so

  ["light-source"] = {
    [1] = {name = "torch", radius = 3, array = {
      0, 0, 2, 1, 2, 0, 0, 
      0, 1, 1, 1, 1, 1, 0, 
      2, 1, 1, 1, 1, 1, 2, 
      1, 1, 1, 1, 1, 1, 1, 
      2, 1, 1, 1, 1, 1, 2, 
      0, 1, 1, 1, 1, 1, 0, 
      0, 0, 2, 1, 2, 0, 0}},},

At which point, giving the hero a torch in Main.lua becomes

manual = Cyclopedia.new()
hero.light = manual:getEntry("light-source", "torch")

Summary

At the end of Step 2, we had a nice little game template, but it hardly fit the definition of a Roguelike game template.  By adding random dungeon generation and monster placement, we’re really close to having a functional Roguelike game.  We even equipped our hero with a torch which allows them to wander around in a dark, scary dungeon and look at things.  But look at things?  Heroes don’t enter dungeons to look at things.  This needs to be addressed.  While it was fun to hand them a torch, a real hero needs a sword.

Next up:  Attack!