Cave Generation Through Fractal Accretion

By: Josh "VertexNormal" Tippetts

This is a little technique that I stumbled across some years ago, and have fiddled with a little bit since then. It is a method for generating a sprawling system of caverns through a process called 'accretion'. An aggregate structure is 'grown' by iteratively accumulating particles, much in the manner that crystals are grown out of solution.

Of course, you will need the Accidental Engine (Windows, Linux ) binaries to execute the script code discussed here. The ideas and concepts, of course, can be utilized anywhere as appropriate.

Overview

The basic algorithm is pretty simple. We are going to accrete a structure composed of various randomly sized circles, where circles represent open areas of the map. We start with a single seed circle placed in the center of the map. Then we iterate some arbitrary number of times, depending on the desired rough dimensions of the cavern complex, and at each iteration we generate another random circle and attach it to the existing complex at some point. We are going to perform this attachment with some restrictions. We want to minimize overlap of circles, to maximize the sprawling, branching nature of the caves, so we need to attach the new particle at a location somewhere on the periphery. To do this, we will spawn the circle somewhere outside the area occupied by the structure, then randomly select a point within the structure to move towards. Then we step through a loop, moving the circle in small steps toward the selected destination until we collide with a circle that is already a part of the structure. We affix the circle at the point of collision, and repeat until we have grown a sufficiently large system.

Some typical fractals generated through accretion

Once we have our system of interconnected circles, we need to convert it to areas of open space and areas of walled space. This is fairly simple to do. At the simplest, we can merely iterate through the list and run an algorithm to iterate through the area of each circle, checking each tile a circle covers to see if it lies within the circle or without. Areas within the circle are set to open, areas without are set to wall. This method works (and is the method I actually use for setting the walls) but we can also derive a little more information from our fractal, information that we can put to better use. The method that I use is stolen from the field of 3D modeling called meta-spheres. Meta-spheres (also called blobby objects) are spheres (or possibly other shapes) that when placed in close proximity to one another have the tendency to merge and flow together in a very liquid, very organic (and very cool) fashion. They operate by modeling each sphere not as a solid object but as a 'field', where each point in space surrounding the center of the sphere out to some radius has a 'field strength' value denoting the strength of the field at that point. The field decreases in strength further from the center. When the spheres are tesselated and rendered, it is done by summing the various fields together and constructing a surface at some threshold field strength. The surface of the object is made to join the points in the field that exist at a certain threshold value. Since fields from adjacent spheres are summed together, this has the effect of causing the individual fields to flow together into one mass.

Metaballs in Blender

We can do the same thing in 2 dimensions with our rickety structure of circles. We can superimpose each circle as a field upon a 2D map, sum the fields, and create open areas at locations where the field strength is greater than some threshold value. The smaller we make the threshold value, the farther out from the center of each circle the walls will be constructed. The following image is a quick mockup of what a set of 2D meta-circles might look like; the blue boundary follows a given threshold value, and could be considered to be the 'surface' of the region; in our cave generator, anything inside the blue region would be open; anything outside would be walled.

2D meta-circles in action

I typically use a threshold of 0 for walls, meaning that walls are traced around a circle at the maximum extent of it's radius. This is functionally equivalent to the simpler method of simply setting any tile that lies within a circle to open, but I am still left with a 2D field representing different levels of strength, with which I can do other things. Some of those things I will describe later, but first lets move on to actually constructing our fractal.

Building the fractal

Of course, before we can get to the meat of things we need to lay a little groundwork. We need to define a few functions (many of which, incidentally, will likely make it into our final library of useful stuff) and we need to set up some tables and variables to help us. The most important of the latter is our list of circles.

CircleList = List:new()

We are using the pylist.lua class, which implements Python-style lists for Lua. This line creates a new list for us to store our circles in.

We also need a way to track the current region that the fractal occupies, since new circles must be spawned outside of this region. We'll track this value as the radius of the circle covering the area and centered at (0,0).

ExtentRadius = 0

Now, we want a way to randomly select a circle from the list. Our accretion technique works by moving a circle inward toward some point within the fractal, so we need to be able to select this point easily.

-- SelectCircle()
-- Randomly choose a circle from the list

function SelectCircle()
  local num = CircleList:len()
  local x,y, radius
  

  local which = RandRange(1, num)
  local circle = CircleList[which]
  return circle
end

Note that SelectCircle() probably shouldn't be called on an empty list. We're not going to do this, since we must seed the area with a starting circle, but I thought it best to warn you. RandRange() won't like you if you call it with (1,0).

We also need to be able to determine if two circles intersect one another.

-- CirclesCollide()
-- Check two circles for intersection

function CirclesCollide(circle1, circle2)
 local dist = (circle1.x-circle2.x)*(circle1.x-circle2.x) + (circle1.y-circle2.y)*(circle1.y-circle2.y)
 local max = ((circle1.radius-1)+(circle2.radius-1))*((circle1.radius-1)+(circle2.radius-2))

 if dist

This function simply calculates the distance between the centers of the circles, and compares it to the sum of the radii of the circles. We are actually using distance*distance and radii*radii, to avoid sqrt() operations for a little better efficiency. Also, in this function I subtract 1 from both radii, in order to allow for a small bit of penetration between circles. This helps to ensure continuity when the fields are summed and the threshold taken, since it is possible to generate isolated circles that do not connect with the main structure if care is not taken.

We also need to be able to tell if a circle intersects with any circle already in the list, so we'll build a brute-force search for this. We could likely improve the efficiency of this operation by using different data structures and methods, but my typical cave doesn't usually go much over 400 or 500 individual circles, and this isn't too bad for that many. There is a slight delay during level generation, but not unbearable.

-- CircleCollidesWithList()
-- Check a circle against all circles currently in the list

function CircleCollidesWithList(circle)
 local num = CircleList:len()
 local i

 for i=1,num,1 do
   circle2 = CircleList[i]
   if CirclesCollide(circle, circle2) then return 1 end
 end

 return nil
end

This following function comes in handy for generating a random unit-length 2D vector. I do not know the distribution characteristics of this function, but it works 'well enough' for our purposes.

-- RandomVector()
-- Generate a unit-length vector pointing in a random direction

function RandomVector()
  local x,y

  x = Rand01()
  y = Rand01()

  x = -1 + (x*2)
  y = -1 + (y*2)

  local len = sqrt((x*x)+(y*y))
  x = x/len
  y = y/len

  return x,y
end

Next, we'll write a quick helper function to spawn new random circles for us.

-- SpawnRandomCircle()
-- Generate a circle outside of the current extents
function SpawnRandomCircle()
  local radius = RandRange(MinRadius, MaxRadius)
  local vx, vy = RandomVector()

  vx = vx * (ExtentRadius + radius + 2)
  vy = vy * (ExtentRadius + radius +2)

  local c={}
  c.x = vx
  c.y = vy
  c.radius = radius

  return c
end

This function generates a new circle, then uses RandomVector() to calculate a new location outside of the circle defined by ExtentRadius.

The next function is used to insert a circle into the list once a collision with the fractal is detected. In this step, it is necessary to update ExtentRadius to reflect the new area.

-- InsertCircle()
-- Insert a circle into fractal, and update extent radius if necessary
function InsertCircle(circle)
  CircleList:append(circle)

  local i,j
  for i=circle.x-circle.radius, circle.x+circle.radius,1 do
    for j=circle.y-circle.radius, circle.y+circle.radius, 1 do
      local dist = sqrt( (i*i)+(j*j) )
      if dist > ExtentRadius then ExtentRadius = dist end
    end
  end
end

This is another inelegant, hackish function that is good enough for our purposes. It iterates through the area covered by the circle, and calculates the distance to each tile from (0,0), and compares that distance to the current ExtentRadius, updating if necessary. I am certain other means could be applied here to make things more efficient.

Now, we need a function to seed the map with a starting circle.

-- SeedFractal()
-- Seed the fractal with an initial circle (at 0,0) and calculate ExtentRadius
function SeedFractal()
  local radius = RandRange(MinRadius, MaxRadius)
  local c = {}

  c.x = 0
  c.y = 0
  c.radius = radius

  ExtentRadius = radius
  CircleList:append(c)
end

All this does is simply spawn a new circle at (0,0), and initialize the ExtentRadius.

Finally, we have our groundwork laid and we can get to the workhorse of the algorithm: the function that performs the accretion.

-- AccreteCircle()
-- Spawn a random circle, pick a random circle already in the list, and
-- propagate the circle in 1-unit increments until
-- it hits the fractal
function AccreteCircle()
  local c1 = SpawnRandomCircle()
  local c2 = SelectCircle()

  local vx, vy = (c2.x-c1.x), (c2.y-c1.y)
  local len = sqrt( (vx*vx)+(vy*vy) )
  vx = vx/len
  vy = vy/len

  local collide = CircleCollidesWithList(c1)
  while collide==nil do
    c1.x = c1.x + vx
    c1.y = c1.y + vy
    collide = CircleCollidesWithList(c1)
  end

  c1.x = c1.x + vx
  c1.y = c1.y + vy

  InsertCircle(c1)
end

This function simply spawns a new circle, selects a point within the existing structure, and computes a vector from the new circle to the destination point. Then it loops, moving the circle along the vector in 1-unit steps until a collision is detected with any circle within the fractal, at which point the circle is inserted into the list. Simple as that.

Constructing the field

Now, we need to move on to translating our fractal into an aggregated field. Consider that each circle represents a field of decreasing strength. We can simply iterate through the list of circles, compute the field strength for every tile that a given circle overlaps, and add that calculated field strength to the total field strength of the given tile. First, we are going to need to define another variable and some more functions.

FieldMap={}

FieldMap is just a table to hold our 2D field for the entire map.

Now, we need to define a function to initialize our field and clear all tile strengths to 0.

-- ClearFieldMap()
-- Construct the field table and clear
function ClearFieldMap(w,h)
 FieldMap["width"]=w
 FieldMap["height"]=h
 local i, j

 for i=1,w,1 do
  FieldMap[i]={}

  for j=1, h, 1 do
   FieldMap[i][j]=0
  end

 end
end

Pretty simple. We merely set up a 2D array sized by the given dimensions. We pass this function MapWidth and MapHeight so that we have 1 field sample for each tile in the map.

Next, we need a function to take a circle and apply it is a field to the field map.

-- MetaCircle()
-- Apply a circle as a meta-circle to the FieldMap

function MetaCircle(cx, cy, radius)
 local left, right, top, bottom
 left = cx-radius
 right = cx+radius
 top = cy-radius
 bottom = cy+radius

 local i,j

 for i=left, right, 1 do
  for j=top, bottom, 1 do
   local distance_squared = (cx-i)*(cx-i)+(cy-j)*(cy-j)
   local distance = sqrt(distance_squared)
   local inten = (radius - distance) / radius
   if inten<0 then inten=0 end
   if inten>1 then inten=1 end
   if i>=1 and i<=FieldMap["width"] and j>=1 and j<=FieldMap["height"] then
    FieldMap[i][j] = FieldMap[i][j] + inten
   end
  end
 end

end

The field strength at each tile is calculated as a linear fall-off in intensity from the center (1) to the radius (0), and added in to the map.

This final function will iterate the entire list of circles and apply each to the field. Note that since we seeded the map with a circle at (0,0), we need to shift everything to center it in the middle of our map. To do so, we simply add one half the map dimensions to the circle centers before applying them to the field.

function BuildField()
  local num = CircleList:len()
  ClearFieldMap(MW, MH)
  
  for i=1,num,1 do
    local c = CircleList[i]
    MetaCircle(Int(c.x+(MW/2)), Int(c.y+(MH/2)), c.radius) 
  end
end

The end result is a map that, if we could visualize it, would look vaguely similar to the image seen earlier, of the 2D meta-circles. Now, all we have to do is iterate through this field map and set walls based on some threshold. If the field strength for a given tile is less than or equal to the threshold, we set a wall there; if it is greater than the threshold, we clear the wall there.

So, let's whip up a quick test script to try it out. The previously listed functions and data can all be found in the script metacircle.lua, and the following test map script can be found in the file meta_map.lua. Copy these files into the data/scripts directory of your Accidental Engine folder (be sure to rename them using the extension .lua; copying these files may not be necessary if you have downloaded the latest version as of this writing, as these scripts are included), and execute the map file from the Accidental console. Press ESC to open the console and enter the line dofile(“data/scripts/meta_map.lua”). It may be helpful to also enter the line Builder:PlacePlayerAt(Int(MW/2), Int(MH/2)) in order to center the player in the map; since the fractal is centered as well, this location is guaranteed to not be a wall.

-- meta_map.lua
-- Test map for accretion fractal dungeon building

-- Import our fractal stuff
dofile("data/scripts/metacircle.lua")


-- Build the field
local n

SeedFractal()
for n=1, 400, 1 do
  AccreteCircle()
end

BuildField()


Builder:ResetMap()

-- Load the lava lands, 'cuz it looks more like a cave environment
LoadAshlandsTileset()

-- Now, translate the field into open and walled areas
local i,j
for i=0, MW-1, 1 do
  for j=0, MH-1, 1 do
    local inten = FieldMap[i+1][j+1]
    if inten == 0.0 then 
      Builder:SetFloor(i,j,DirtType)
      Builder:SetWall(i,j,1)
      Builder:SetFlag(i,j,TF_BLOCKWALK)
    else 
      Builder:SetFloor(i,j,GrassType)
    end
  end
end

Builder:WallEdges(1) -- Close off any open edges

Builder:FinalizeMap()

The script will take a few seconds to execute, then you should get something like this:

Wandering the Fractal Caverns

Now, you will notice that I simply use a threshold of 0 for setting walls, so it seems as if it might be overkill to go through the process of generating a variegated field. However, this field can come in handy in other regards. It can come in handy, for instance, in placement of props and objects. You can ensure that props do not block paths of travel by only placing them on tiles that are at least a certain threshold level; this keeps the props more toward the center of rooms and passageways, instead of placing them at the edges where they can clog exits. The field strengths can also be useful for placement of rivers and lava flows, to emulate the fluid flowing along the passageway; restrict flows to certain threshold levels, and add a little random noise in the final placement if desired. The following screenshot shows lava placed at a threshold of >=0.5. The script to generate this map can be found in the file meta_lava.lua.

Using the field to place lava flows

There are many ways in which this algorithm can be tweaked to vary the results. The collision routines can be modified to allow more inter-penetration of circles; the range of radii for circles can be tweaked to allow larger-sized circles in the map; the number of circles can be varied; other field shapes such as ellipses can be used in conjunction with circles; and so on. Good luck, and have fun.