This post is about procedural content generation of cave-like dungeons/maps for rogue-like games using what is known as the Cellular Automata method.
To understand what I mean by cellular automata method, imagine Conway's Game of Life. Many algorithms use what is called the '4-5 method', which means a tile will become a wall if it is a wall and 4 or more of its nine neighbors are walls, or if it is not a wall and 5 or more neighbors are walls. I start by filling the map randomly with walls or space, then visit each x/y position iteratively and apply the 4-5 rule. Usually this is preceded with 'seeding' the map by randomly filling each cell of the map with a wall or space, based on some weight (say, 40% of the time it chooses to place a wall). Then the automata step is applied multiple times over the entire map, precipitating walls and subsequently smoothing them. About 3 rounds is all that is required, with about 4-5 rounds being pretty typical amongst most implementations. Perhaps a picture of the the output will help you understand what I mean.
Using the automata-based method for procedural generation of levels will produce something similar to this:
Sure the dungeon generation by linking rooms approach has its place, but I really like the 'natural' look to the automata inspired method. I first originally discovered this technique on the website called Roguebasin. It is a great resource for information concerning the different problems involved with programming a rogue-like game, such as Nethack or Angband.
One of the major problems developers run into while employing this technique is the formation of isolated caves. Instead of one big cave-like room, you may get section of the map that is inaccessible without digging through walls. Isolated caves can trap key items or (worse) stairs leading to the next level, preventing further progress in the game. I have seen many different approaches proposed to solve this problem. Some suggestions I've seen include: 1) Discarding maps that have isolated caves, filling in the isolated sections, or finely tweaking the variables/rules to reduce occurrences of such maps. None of these are ideal (in my mind), and most require a way to detect isolated sections, which is another non-trivial problem in itself.
Despite this, I consider the problem solved because I have discovered a solution that is dead simple and almost** never fail because of the rules of the automata generation itself dictate such. I call my method 'Horizontal Blanking' because you can probably guess how it works now just from hearing the name. This step comes after the random filling of the map (initialization), but before the cellular automata iterations. After the map is 'seeded' with a random fill of walls, a horizontal strip in the middle of of the map is cleared of all walls. The horizontal strip is about 3 or 4 block tall (depending on rules). Clearing a horizontal strip of sufficient width will prevent a continuous vertical wall from being created and forming isolated caves in your maps. After horizontal blanking, you can begin applying the cellular automata method to your map.
** I say 'almost' because although it it not possible to get whole rooms that are disconnected from each other, it is possible to get tiny squares of blank space in the northern or southern walls that consist of about 4-5 blocks in total area. Often, these little holes will resolve themselves during the rounds of automata rules, but there still exists the possibility that one may persist. My answer to this edge case would be to use some rules around the placement of stairwells (and other must-find items) dictating that such objects must have a 2-3 block radius clear of walls to be placed.
See below for the code that produced the above screenshot, or click here to download the entire project with source code that you can compile yourself.
public class MapHandler
{
Random rand = new Random();
public int[,] Map;
public int MapWidth { get; set; }
public int MapHeight { get; set; }
public int PercentAreWalls { get; set; }
public MapHandler()
{
MapWidth = 40;
MapHeight = 21;
PercentAreWalls = 40;
RandomFillMap();
}
public void MakeCaverns()
{
// By initilizing column in the outter loop, its only created ONCE
for(int column=0, row=0; row <= MapHeight-1; row++)
{
for(column = 0; column <= MapWidth-1; column++)
{
Map[column,row] = PlaceWallLogic(column,row);
}
}
}
public int PlaceWallLogic(int x,int y)
{
int numWalls = GetAdjacentWalls(x,y,1,1);
if(Map[x,y]==1)
{
if( numWalls >= 4 )
{
return 1;
}
return 0;
}
else
{
if(numWalls>=5)
{
return 1;
}
}
return 0;
}
public int GetAdjacentWalls(int x,int y,int scopeX,int scopeY)
{
int startX = x - scopeX;
int startY = y - scopeY;
int endX = x + scopeX;
int endY = y + scopeY;
int iX = startX;
int iY = startY;
int wallCounter = 0;
for(iY = startY; iY <= endY; iY++) {
for(iX = startX; iX <= endX; iX++)
{
if(!(iX==x && iY==y))
{
if(IsWall(iX,iY))
{
wallCounter += 1;
}
}
}
}
return wallCounter;
}
bool IsWall(int x,int y)
{
// Consider out-of-bound a wall
if( IsOutOfBounds(x,y) )
{
return true;
}
if( Map[x,y]==1 )
{
return true;
}
if( Map[x,y]==0 )
{
return false;
}
return false;
}
bool IsOutOfBounds(int x, int y)
{
if( x<0 data-blogger-escaped-else="" data-blogger-escaped-if="" data-blogger-escaped-return="" data-blogger-escaped-true="" data-blogger-escaped-x="" data-blogger-escaped-y="">MapWidth-1 || y>MapHeight-1 )
{
return true;
}
return false;
}
Here is the rest of the program, such as filling, printing and blanking:
public void PrintMap()
{
Console.Clear();
Console.Write(MapToString());
}
string MapToString()
{
string returnString = string.Join(" ", // Seperator between each element
"Width:",
MapWidth.ToString(),
"\tHeight:",
MapHeight.ToString(),
"\t% Walls:",
PercentAreWalls.ToString(),
Environment.NewLine
);
List<string> mapSymbols = new List();
mapSymbols.Add(".");
mapSymbols.Add("#");
mapSymbols.Add("+");
for(int column=0,row=0; row < MapHeight; row++ ) {
for( column = 0; column < MapWidth; column++ )
{
returnString += mapSymbols[Map[column,row]];
}
returnString += Environment.NewLine;
}
return returnString;
}
public void BlankMap()
{
for(int column=0,row=0; row < MapHeight; row++) {
for(column = 0; column < MapWidth; column++) {
Map[column,row] = 0;
}
}
}
public void RandomFillMap()
{
// New, empty map
Map = new int[MapWidth,MapHeight];
int mapMiddle = 0; // Temp variable
for(int column=0,row=0; row < MapHeight; row++) {
for(column = 0; column < MapWidth; column++)
{
// If coordinants lie on the edge of the map
// (creates a border)
if(column == 0)
{
Map[column,row] = 1;
}
else if (row == 0)
{
Map[column,row] = 1;
}
else if (column == MapWidth-1)
{
Map[column,row] = 1;
}
else if (row == MapHeight-1)
{
Map[column,row] = 1;
}
// Else, fill with a wall a random percent of the time
else
{
mapMiddle = (MapHeight / 2);
if(row == mapMiddle)
{
Map[column,row] = 0;
}
else
{
Map[column,row] = RandomPercent(PercentAreWalls);
}
}
}
}
}
int RandomPercent(int percent)
{
if(percent>=rand.Next(1,101))
{
return 1;
}
return 0;
}
public MapHandler(int mapWidth, int mapHeight, int[,] map, int percentWalls=40)
{
this.MapWidth = mapWidth;
this.MapHeight = mapHeight;
this.PercentAreWalls = percentWalls;
this.Map = new int[this.MapWidth,this.MapHeight];
this.Map = map;
}
}
And of course, the main function:
public static void Main(string[] args)
{
char key = new Char();
MapHandler Map = new MapHandler();
string instructions =
"[Q]uit [N]ew [+][-]Percent walls [R]andom [B]lank" + Environment.NewLine +
"Press any other key to smooth/step";
Map.MakeCaverns();
Map.PrintMap();
Console.WriteLine(instructions);
key = Char.ToUpper(Console.ReadKey(true).KeyChar);
while(!key.Equals('Q'))
{
if(key.Equals('+')) {
Map.PercentAreWalls+=1;
Map.RandomFillMap();
Map.MakeCaverns();
Map.PrintMap();
} else if(key.Equals('-')) {
Map.PercentAreWalls-=1;
Map.RandomFillMap();
Map.MakeCaverns();
Map.PrintMap();
} else if(key.Equals('R')) {
Map.RandomFillMap();
Map.PrintMap();
} else if(key.Equals('N')) {
Map.RandomFillMap();
Map.MakeCaverns();
Map.PrintMap();
} else if(key.Equals('B')) {
Map.BlankMap();
Map.PrintMap();
} else if(key.Equals('D')) {
// I set a breakpoint here...
} else {
Map.MakeCaverns();
Map.PrintMap();
}
Console.WriteLine(instructions);
key = Char.ToUpper(Console.ReadKey(true).KeyChar);
}
Console.Clear();
Console.Write(" Thank you for playing!");
Console.ReadKey(true);
}
See also: Roguebasin - Cellular Automata Method for Generating Random Cave-Like Levels