Squint's Mini 'Fractal Tile Maps' Tutorial
By: Andy 'Squint' Newman
I find one of the problems with computer generated worlds is that they look unnatural. This is certainly true of mazes, and the more traditional rogue-like dungeons, which are far too organised to be natural. It is also true of completely random scattering of features, since lots of little walls randomly placed all over isn't natural either. What we need is a way to come up with a random seeming map which is still locally ordered. For this kind of effect I am a great fan of fractals.
I'm not about to explain what fractals are, or how you can make them. There are a lot of resources about these on the net already. The particular method I have chosen here is multiple layers of linearly interpolated random noise. I've done this not because it's the best approach, but because it's extremely easy to implement and my LUA isn't very strong.
Here is the kind of output you would expect to get from a fractal noise generator:
As it stands it is pretty, but actually not very useful - this is a tile based world, and I want to know if something is wall or not wall, tree or not tree. I want to see the world in black and white, not greyscale. If we specify a cut-off point for the brightness in that fractal, and set everything above it to white and everything below it to black, we get this:
cutoff at 0.5 | cutoff at 0.333 |
 |  |
Now that has quite a few uses - we can use the white area to specify walls, or where the water is, or where the forests are, and everything gets the kind of correlated-random appearance we want. So, to get started then, here is a lua script for generating fractals. As I said before, I'm not explaining how to make them, only how you can use them, but this script should save you half an hours typing:
-- squintfrac.lua
-- This is a set of support functions for generating a fractal noise pattern
-- fractal noise is a wonderful thing if you want more natural looking
-- "random" worlds.
FractalHeight={}
FractalMaxHeight=0
-- This function takes boundaries for the noise, and the number of octaves to generate
-- it is not particularly clever - the size in each direction should be a multiple of
-- 2 to the power of (the number of octaves - 1) + 1
-- (ie, ocataves = 3, width = N*(2^2)+1 = 5, 9, 13, ... etc )
-- It doesn't break if you get this wrong, it just pads the end with low values.
function FractalGenerate(xsize, ysize, octaves)
-- begin by initialising everywhere to 0
for x=1,xsize,1 do
FractalHeight[x]={}
for y = 1, ysize, 1 do
FractalHeight[x][y]=0
end
end
-- add each octave to the fractal
FractalMaxHeight = 0
FractalAddOctave(xsize, ysize, octaves, CutoffHeight)
end
-- recursively adds octaves to the fractal
function FractalAddOctave(xsize, ysize, octave)
-- add this octave
local step = 2^(octave - 1)
local scale = step
FractalMaxHeight = FractalMaxHeight + scale
for x = 1, xsize, step do
for y = 1, ysize, step do
-- Add random value at this point
print(x,y,scale)
FractalHeight[x][y] = FractalHeight[x][y] + RandRange(0,scale)
-- if we aren't on the last octave, interpolate intermediate values
if step > 1 then
if x > 1 then
FractalHeight[x - step / 2][y] = (FractalHeight[x - step][y] + FractalHeight[x][y]) / 2
end
if y > 1 then
FractalHeight[x][y - step / 2] = (FractalHeight[x][y - step] + FractalHeight[x][y]) / 2
end
if x > 1 and y > 1 then
FractalHeight[x - step / 2][y - step / 2] = (FractalHeight[x - step / 2][y - step] + FractalHeight[x - step / 2][y]) / 2
end
end
end
end
-- add the next octave
if octave > 1 then
FractalAddOctave(xsize, ysize, octave - 1)
end
end
We also need a main script which uses this to generate a world, so here we go:
-- squint1.lua
-- Populate the world with fractal noise
dofile("data/scripts/squintfrac.lua")
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)
local xsize = MW-3
local ysize = MH-3
-- floors:
-- Generate a fractal, and use a fairly aggresive cutoff to
-- get just a few areas of water (the rest is grass):
FractalGenerate(xsize,ysize,5)
for x = 1, xsize, 1 do
for y = 1, ysize, 1 do
if FractalHeight[x][y] < (FractalMaxHeight / 3) then
Builder:SetFloor(x, y, 2)
else
Builder:SetFloor(x, y, 0)
end
end
end
-- walls:
-- Generate another fractal, and use a halfway cutoff so
-- that half the terrain is passable, and half wall:
FractalGenerate(xsize,ysize,5)
for x = 1, xsize, 1 do
for y = 1, ysize, 1 do
if FractalHeight[x][y] > (FractalMaxHeight / 2) then
Builder:SetWall(x, y, 1)
Builder:SetFlag(x, y, TF_BLOCKWALK)
end
end
end
-- trees:
-- Generate yet another fractal.
-- This fractal has less octaves, resulting in smaller scale
-- detail - we don't want immense forests sprawling over the map,
-- just clumps of trees in places.
FractalGenerate(xsize,ysize,4)
for x = 1, xsize, 1 do
for y = 1, ysize, 1 do
if FractalHeight[x][y] < (FractalMaxHeight / 3) then
if Builder:GetFlag(x,y,TF_OFFLIMITS) == nil then
local Random
Random = RandRange(1,6)
local WhichTree = "Tree"..Random
PropFunctions[WhichTree](x,y)
end
end
end
end
-- Now, translate map
Builder:FinalizeMap()
The squint1 world type uses a 0.5 cutoff for the walls, and a 0.333 cutoff for water and trees. It is extremely simple, which I generally take as a good sign.
Now when we run it we should get a world a bit like this:
At first glance, it shows that the general principle is right, but it also shows that there are some problems to iron out. The trees are too closely bunched together, and they grow out of lakes and in the middle of rocks. Not good, but hopefully easy to fix. More worryingly, there is no guarantee that any two features I decide to place on this map will be connected - the fractal is quite capable of generating a wall all the way accross the world. Most worrying, and extremely obvious unless you got lucky when you started the engine, is that nothing guarantees that the players spawn point isn't in the middle of a pond, wrapped around a tree, or embedded in solid rock. That is what we need to fix next.
Thinking ahead, we are going to want to place rooms and we are going to want to make sure it is possible to get from each room to each other room. There are a lot of ways of doing this. The simplest is a maze generator, although it needs to be one which generates paths, rather than one which places walls. Ultimately any maze generator would do, we just delete walls where the paths are instead of creating them where the paths aren't. I don't particularly want a labyrinth - I just want some paths with rooms. I have chosen crawlers for this purpose. A crawler simply sets off from some point (the spawn point is good) and carves a path untill it gets bored. Then it may or may not create a room or some other crawlers. That's the principle. The implementation I've gone for is as follows (again, I'm more interested in explaining the principles than the specifics of implementation):
-- squintcrawl.lua
-- This is a set of support functions for generating a connected path
-- network between a set of arbitrary "nodes"
CrawlGrid={}
CrawlStep= { { 1,0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }
CrawlBack= { 2, 1, 4, 3 }
CrawlStepPair= { { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 } }
-- This initialises the grid to be empty, no rooms and no corridors
function GridGenerate(xsize, ysize)
CrawlGrid.xsize = xsize
CrawlGrid.ysize = ysize
for x=1,xsize,1 do
CrawlGrid[x] = {}
for y=1,ysize,1 do
CrawlGrid[x][y] = {}
CrawlGrid[x][y].Room = 0
CrawlGrid[x][y].Connected = 0
CrawlGrid[x][y].Path = {}
for c=1,4,1 do
CrawlGrid[x][y].Path[c] = 0
end
end
end
end
-- launches a crawler from a specified position, with a known
-- number of children:
function GenerateCrawler(sx, sy, num, baddir)
-- Begin the crawler where we asked
print("::", sx, sy)
CrawlGrid[sx][sy].Connected = 1
local terminate = 0
local cx,cy = sx,sy
local steppair = baddir
local attempts = 0
while steppair == baddir and attempts < 6 do
steppair = RandRange(1,4)
attempts = attempts + 1
end
if attempts > 5 then
terminate = 1
end
while terminate == 0 do
-- step in a kind-of-random direction
local dir = RandRange(1,2)
local step = CrawlStepPair[steppair][dir]
local nx = cx + CrawlStep[step][1]
local ny = cy + CrawlStep[step][2]
print("-> ", nx, ny)
-- if we ran off the edge, terminate immediately:
if nx > CrawlGrid.xsize or nx < 1 or ny > CrawlGrid.ysize or ny < 1 then
nx = cx
ny = cy
terminate = 1
elseif CrawlGrid[nx][ny].Connected == 1 then
terminate = 1
else
local stop = RandRange(1,6)
if stop == 1 then
terminate = 1
end
end
-- update the position:
CrawlGrid[cx][cy].Path[step] = 1
CrawlGrid[nx][ny].Path[CrawlBack[step]] = 1
CrawlGrid[nx][ny].Connected = 1
cx = nx
cy = ny
-- if we are terminating normally:
if terminate == 1 and (cx ~= sx or cy ~= sy) then
-- consider generating a room:
if CrawlGrid[cx][cy].Room == 0 then
if RandRange(1,2) == 1 then
CrawlGrid[cx][cy].Room = 1
end
end
-- spawn child crawlers:
local headchild = RandRange(0,num)
local tailchild = num - headchild
if headchild > 0 then
GenerateCrawler(cx, cy, headchild - 1, 5 - steppair)
end
if tailchild > 0 then
GenerateCrawler(sx, sy, tailchild - 1, 5 - steppair)
end
end
end
end
-- Launches the mommy crawler, from which all others spawn:
function PathGenerate(xsize, ysize, startx, starty, mincrawlers, maxcrawlers)
GridGenerate(xsize, ysize)
local numcrawlers = RandRange(mincrawlers, maxcrawlers)
GenerateCrawler(startx, starty, numcrawlers - 1, 0)
end
Nothing there is really as complicated as it seems. Ultimately, we will call PathGenerate with a size, and start position, and a number of crawlers, and it will result in a 2 dimensional array of information for us to use.
Just to check that the principle is sound, here is a new map script which uses it. It is very very similar to squint1, having only a couple of minor changes in addition to the path code.
-- squint2.lua
dofile("data/scripts/squintfrac.lua")
dofile("data/scripts/squintcrawl.lua")
MW = 257
MH = 257
-- Initialize
Builder:ResetMap(MW, MH)
-- Wall in the edges to keep the player from walking off the edge
Builder:WallEdges(1)
local xsize = MW-3
local ysize = MH-3
-- paths and rooms:
-- Run a crawler to make some rooms and paths.
gridsize = 16
gridxsize = 9
gridysize = 9
PathGenerate(gridxsize, gridysize, 3, 3, 10, 10)
-- force every path to be walkable:
-- Note there are some magic numbers here.
-- our little bod would appear to spawn at 63,63 - we need
-- to choose x and y here so that it corresponds to the start point
-- of the crawlers.
x = 31
for px = 1, gridxsize, 1 do
y = 31
for py = 1, gridysize, 1 do
if CrawlGrid[px][py].Connected == 1 then
for dir = 1, 3, 2 do
if CrawlGrid[px][py].Path[dir] == 1 then
local floorx,floory = x,y
local dx = CrawlStep[dir][1]
local dy = CrawlStep[dir][2]
for i = 1,gridsize,1 do
print(floorx, floory)
Builder:SetFloor(floorx , floory , 1)
Builder:SetFloor(floorx , floory+1, 1)
Builder:SetFlag(floorx, floory, TF_OFFLIMITS)
Builder:SetFlag(floorx, floory+1, TF_OFFLIMITS)
floorx = floorx + dx
floory = floory + dy
end
end
end
end
y = y + gridsize
end
x = x + gridsize
end
-- walls:
-- Generate another fractal, and use a halfway cutoff so
-- that half the terrain is passable, and half wall:
FractalGenerate(xsize,ysize,5)
for x = 1, xsize, 1 do
for y = 1, ysize, 1 do
if Builder:GetFlag(x,y,TF_OFFLIMITS) == nil then
if FractalHeight[x][y] > (FractalMaxHeight / 2) then
Builder:SetWall(x, y, 1)
Builder:SetFlag(x, y, TF_BLOCKWALK)
Builder:SetFlag(x, y, TF_OFFLIMITS)
end
end
end
end
-- floors:
-- Generate a fractal, and use a fairly aggresive cutoff to
-- get just a few areas of water (the rest is grass):
FractalGenerate(xsize,ysize,5)
for x = 1, xsize, 1 do
for y = 1, ysize, 1 do
if Builder:GetFlag(x,y,TF_OFFLIMITS) == nil then
if FractalHeight[x][y] > (2 * FractalMaxHeight / 3) then
Builder:SetFloor(x, y, 2)
Builder:SetFlag(x, y, TF_BLOCKWALK)
Builder:SetFlag(x, y, TF_OFFLIMITS)
else
Builder:SetFloor(x, y, 0)
end
end
end
end
-- trees:
-- Generate yet another fractal.
-- This fractal has less octaves, resulting in smaller scale
-- detail - we don't want immense forests sprawling over the map,
-- just clumps of trees in places.
FractalGenerate(xsize,ysize,4)
for x = 1, xsize, 1 do
for y = 1, ysize, 1 do
if Builder:GetFlag(x,y,TF_OFFLIMITS) == nil then
if FractalHeight[x][y] > (2 * FractalMaxHeight / 3) then
local Random
Random = RandRange(1,4)
if Random == 1 then
Random = RandRange(1,6)
local WhichTree = "Tree"..Random
PropFunctions[WhichTree](x,y)
end
end
end
end
end
-- Now, translate map
Builder:FinalizeMap()
One of the other changes made there is to only generate about a quarter of the trees we used to. There is also much stronger use of the TF_OFFLIMITS flag to prevent each stage overwriting the one before. This has been coupled with a re-ordering - the most important stage always comes first.
In the code which handles the paths themselves, note that the grid generated by the crawler is to an arbitrary scale and needs a bit of effort to actually use.
Here are some shots of a world generated with squint2
There are obvious problems here. The first shot takes me back to playing rogue - natural? I don't think so. Sadly, there isn't a great deal we can do about that. Given more resolution there are quite a few tricks we could use to blend the fractal terrain information with the path information and get less straight edges, but we are restrained to the limits of a tile engine, and will have to put up with it for now.
The second shot shows something we could do with the engine, rather than the script - I don't have a problem with the causeway over the water, but it would look nicer if a different floor type was available for it - a bridge, or a shallow-water-marsh-grass image. Sometimes, when you get effects like this, it's easier to turn them into a pretty new feature than to avoid them ;)
The third shot is some of our new sparser trees. Aren't they nice? They show exactly what we set out for in the beginning - a natural kind of clumping which still looks random. We are getting somewhere!
So, let's add some rooms. We already know where they are because the crawler conveniently flags them for us. What we need to do is create them. Please don't restrict yourself to the kind of room I will be making - be imaginative. Our aim here is to build a room which is small enough not to overlap other nearby paths, or other rooms in neighbouring crawler-grid cells. It also needs to have entrances wherever a path hits it, but preferably it shouldn't have entrances which lead nowhere, as those would look a bit odd.
I recommend making the rooms after the paths. The room can overwrite the path where the room feels it is more important, by simply ignoring the TF_OFFLIMITS flag, and it can allow paths to overwrite it's external walls by paying attention to the same flag when it makes them. The rooms I generate are circular, with a random radius, and with the edge surrounded by a neat circle of trees. The code to make this is added here, in squint3.lua
-- squint3.lua
dofile("data/scripts/squintfrac.lua")
dofile("data/scripts/squintcrawl.lua")
MW = 257
MH = 257
-- Initialize
Builder:ResetMap(MW, MH)
-- Wall in the edges to keep the player from walking off the edge
Builder:WallEdges(1)
local xsize = MW
local ysize = MH
-- paths and rooms:
-- Run a crawler to make some rooms and paths.
gridxsize = 13
gridysize = 13
PathGenerate(gridxsize, gridysize, 3, 3, 10, 10)
-- force every path to be walkable:
-- Note there are some magic numbers here.
-- our little bod would appear to spawn at 63,63 - There is no particular
-- correlation between grid points and real world coordinates, so we need
-- to choose x and y here so that 64,64 corresponds to the start point
-- of the crawlers:
gridsize = 16
x = 31
for px = 1, gridxsize, 1 do
y = 31
for py = 1, gridysize, 1 do
if CrawlGrid[px][py].Connected == 1 then
for dir = 1, 3, 2 do
if CrawlGrid[px][py].Path[dir] == 1 then
local floorx,floory = x,y
local dx = CrawlStep[dir][1]
local dy = CrawlStep[dir][2]
for i = 1,gridsize,1 do
print(floorx, floory)
Builder:SetFloor(floorx, floory , 1)
Builder:SetFloor(floorx, floory+1, 1)
Builder:SetFlag(floorx, floory, TF_OFFLIMITS)
Builder:SetFlag(floorx, floory+1, TF_OFFLIMITS)
floorx = floorx + dx
floory = floory + dy
end
end
end
end
y = y + gridsize
end
x = x + gridsize
end
-- generate rooms:
x = 31
for px = 1, gridxsize, 1 do
y = 31
for py = 1, gridysize, 1 do
if CrawlGrid[px][py].Room == 1 then
local radius = RandRange(4, 8)
print("Room",px,py,radius)
radiussqr = radius * radius
local treenum = RandRange(1,6)
local WhichTree = "Tree"..treenum
for dx = -radius, radius, 1 do
for dy = -radius, radius, 1 do
distsqr = dx * dx + dy * dy
if distsqr < radiussqr then
local floorx = x + dx
local floory = y + dy
local delta = radiussqr - ((radius - 1) * (radius - 1))
if radiussqr - distsqr > delta then
Builder:SetFloor(floorx, floory , 1)
Builder:SetFlag(floorx, floory, TF_OFFLIMITS)
else
if Builder:GetFlag(floorx,floory,TF_OFFLIMITS) == nil then
Builder:SetFloor(floorx, floory , 0)
PropFunctions[WhichTree](floorx,floory)
Builder:SetFlag(floorx, floory, TF_OFFLIMITS)
end
end
end
end
end
end
y = y + gridsize
end
x = x + gridsize
end
-- walls:
-- Generate a fractal, and use a halfway cutoff so
-- that half the terrain is passable, and half wall:
FractalGenerate(xsize,ysize,5)
for x = 1, xsize, 1 do
for y = 1, ysize, 1 do
if Builder:GetFlag(x,y,TF_OFFLIMITS) == nil then
if FractalHeight[x][y] > (FractalMaxHeight / 2) then
Builder:SetWall(x, y, 1)
Builder:SetFlag(x, y, TF_BLOCKWALK)
Builder:SetFlag(x, y, TF_OFFLIMITS)
end
end
end
end
-- floors:
-- Generate another fractal, and use a fairly aggresive cutoff to
-- get just a few areas of water (the rest is grass):
FractalGenerate(xsize,ysize,5)
for x = 1, xsize, 1 do
for y = 1, ysize, 1 do
if Builder:GetFlag(x,y,TF_OFFLIMITS) == nil then
if FractalHeight[x][y] > (2 * FractalMaxHeight / 3) then
Builder:SetFloor(x, y, 2)
Builder:SetFlag(x, y, TF_BLOCKWALK)
Builder:SetFlag(x, y, TF_OFFLIMITS)
else
Builder:SetFloor(x, y, 0)
end
end
end
end
-- trees:
-- Generate yet another fractal.
-- This fractal has less octaves, resulting in smaller scale
-- detail - we don't want immense forests sprawling over the map,
-- just clumps of trees in places.
FractalGenerate(xsize,ysize,4)
for x = 1, xsize, 1 do
for y = 1, ysize, 1 do
if Builder:GetFlag(x,y,TF_OFFLIMITS) == nil then
if FractalHeight[x][y] > (2 * FractalMaxHeight / 3) then
local Random
Random = RandRange(1,4)
if Random == 1 then
Random = RandRange(1,6)
local WhichTree = "Tree"..Random
PropFunctions[WhichTree](x,y)
end
end
end
end
end
-- Now, translate map
Builder:FinalizeMap()
And the final result? Here we are, entering the cursed glade by one of its two entrances. All it needs is a big hairy monster and some gold and you could call it a game (OK, slight exageration there).
I am particularly delighted that this image required only about 300 lines of code, and took only a few hours over the weekend. There are a LOT more things which can be done with procedural worlds, and the options only get broader and better as we go from tile engines to height maps to completely three dimensional cave networks. It is very definitely more complicated than writing code to load data created by an artist. It will generally never be quite as good. But it will be different every time. It can be a world a thousand miles wide in minute detail, and it will cost you a minute at start up, rather than 10 man years of artistic talent. And if your artistic talent is anything like mine . . .
Have fun!
Andy 'Squint' Newman
The scripts for this article can be found here.