Cellular Automata Method for Generating Random Cave-Like Levels

From RogueBasin
(Difference between revisions)
Jump to: navigation, search
m (Removed duplicate title)
(Implementations)
 
(26 intermediate revisions by 17 users not shown)
Line 1: Line 1:
By [[Jim Babcock]]
 
  
It is an old and fairly well documented trick to use [[cellular automata]] to generate cave-like structures. The basic idea is to fill the map randomly, then repeatedly apply the 4-5 rule: a tile is a wall if it is a wall and has 4 neighbors that are walls, or if it is not a wall and has 5 neighbors that are. This rule can be stated more simply: a tile becomes or remains a wall if the 3x3 region centered on it contains at least 5 walls. (''Note: It is important to do this for each tile simultaneously. If you update one, then use its value when you update the next, your results won't look as good, and the tricks described later won't work.'')
+
== Introduction ==
  
If the map initially contains 45% walls, and the process above is repeated 5 times, the output looks like (for example)
+
It is an old and fairly well documented trick to use [http://en.wikipedia.org/wiki/Cellular_automaton cellular automata] to generate cave-like structures. The basic idea is to fill the first map randomly, then repeatedly create new maps using the 4-5 rule: a tile becomes a wall if it was a wall and 4 or more of its eight neighbors were walls, or if it was not a wall and 5 or more neighbors were. Put more succinctly, a tile is a wall if the 3x3 region centered on it contained at least 5 walls. Each iteration makes each tile more like its neighbors, and the amount of overall "noise" is gradually reduced:
 +
 
 +
original:          iteration 1:        2:                  3:                  4:
 +
  #      ### ##    ####  ##########    ####  ##########    ####  ##########    ####  ##########
 +
# ##  ## ## #      # #      ##### #    ###      #######    ###      #######    ###      #######
 +
  # # ##  #### #    # #  #  #### #    ##        ######    ##        ######    ##        ######
 +
  # #  #  # ## #    ###  #    ### #    ##        #####    ##        #####    ##        #####
 +
### # #    # #    #    #    #####    ##        #####    ##        #####    ##        ######
 +
    # # ## #####    ##    ###  ####    #      ## #####    ##      ########    ##      ########
 +
##    ####  #      #      #### ####    ##    ####  ###    ##    #### ####    ##    #########
 +
## ## # ## #  ##    ###    ####    #    ###    ###  ###    ###    ####  ###    ###    #########
 +
# ##  ###  #  #    ##### ###    ###    ####  #####  ###    ####  ##### ####    ####  #########
 +
#  # # #  # ###    # ### ##########    ###### #########    #####  #########    ####  #########
 +
  ## ## #### # #    #####    #######    ####    ########    ####    ########    ####    ########
 +
####    # # # #    # #      #######    ##        ######    ##      #######    ##      #######
 +
        #  ## ##    #          #####    #        ######    #        ######    #        ######
 +
    # #    # ####              #####    #        ######    #        ######    #        ######
 +
# # #  ## ######    #        #######    #        #######    ##      #######    ##      #######
 +
#  #  # ####  #    ################    ################    ################    ################
 +
 
 +
If 45% of the original random map contains walls and the process is repeated 5 times, the output might look like the following:
  
 
  ############################################################
 
  ############################################################
Line 34: Line 53:
 
  #######....#############.......##############.....###..#####
 
  #######....#############.......##############.....###..#####
 
  ##############################################..############
 
  ##############################################..############
  ############################################################  
+
  ############################################################
 +
 
 +
== Advantages ==
 +
Some advantages include:
 +
* Procedurally generated so no two levels are (likely) exactly the same.
 +
* Relatively simple concept, and implementation.
 +
* A natural, cave-like map to add variety, uniqueness or an alternative to room-based dungeons.
 +
 
 +
 
 +
== Disadvantages ==
 +
Some disadvantages include:
 +
* Generation of isolated cave sections, possibly blocking player advancement (see possible solutions below).
 +
* Probably not appropriate for generating towns, so other map generators will probably need to be implemented.
 +
* Very large maps tend to not look as natural, or may require some very fine tuning.
  
The problem is, the results of the algorithm are very inconsistent. Not only is it prone to generating disjoint (not connected) maps, like in this example, with the same parameters:
+
== The isolated cave problem ==
 +
The problem is that the results are inconsistent. The algorithm prone to generating disconnected maps. See example below:
  
 
  ############################################################
 
  ############################################################
Line 69: Line 102:
 
  ############################################################
 
  ############################################################
  
it also sometimes generates maps which consist of basically one huge open space, like this one:
+
It also sometimes generates maps which consist of one huge open space:
  
 
  ############################################################
 
  ############################################################
Line 102: Line 135:
 
  ############################################################
 
  ############################################################
  
We can fix the disjoint segments problem in one of three ways. Either throw away maps that have disjoint segments in them, connect up the segments after the fact, or fill in all but the biggest segment. We can't just retry when we get a disjoint map, because if the map is big then, statistically, that will be almost 100% of the time. Filling in all but the biggest segment will tend to produce a small area in a map that was supposed to be big. Connecting up the regions works, but it tends to look unnatural, as in the example from above, now connected:
+
There are many ways to fix the disjoint segments problem. One approach might be to throw away maps that have disjoint segments in them. Another approach would be to connect the segments after the fact. Another still would be to fill in all but the biggest segment. We can't just retry when we get a disjoint map, because if the map is big then, statistically, that will be almost 100% of the time. Filling in all but the biggest segment will tend to produce a small area in a map that was supposed to be big. Connecting up the regions works, but it tends to look unnatural, as in the example from above, now connected:
  
 
  ############################################################
 
  ############################################################
Line 135: Line 168:
 
  ############################################################
 
  ############################################################
  
 +
=== Rule Tweaking ===
 
The solution to both problems, as it turns out, is to revisit the original cellular automata rules. Recall that the original rule was
 
The solution to both problems, as it turns out, is to revisit the original cellular automata rules. Recall that the original rule was
  
Line 142: Line 176:
 
Or, in more compact notation:
 
Or, in more compact notation:
  
* Winit(p) = rand[0,100) < 45
+
* Winit(p) = rand(0,100) < 45
 
* R(p) = the number of tiles within 1 step of p which are walls
 
* R(p) = the number of tiles within 1 step of p which are walls
* W?(p) = R(p) ? 5
+
* W'(p) = R(p) >= 5
  
 
Now, one of the problems was that we tend to get big, open areas. So why not try filling those areas in? Change the rule to
 
Now, one of the problems was that we tend to get big, open areas. So why not try filling those areas in? Change the rule to
  
* W?(p) = R(p) ? 5 or p is in the middle of an open space
+
* W'(p) = R(p) >= 5 or p is in the middle of an open space
  
 
Or more formally,
 
Or more formally,
  
* Rn(p) = the number of tiles with n steps of p which are walls
+
* Rn(p) = the number of tiles within n steps of p which are walls
* W?(p) = R1(p)?5 || R2(p)=0
+
* W'(p) = R1(p)>=5 || R2(p)=0
  
 
So how does it look?
 
So how does it look?
  
  Winit(p) = rand[0,100) < 45
+
  Winit(p) = rand(0,100) < 45
  Repeat 5: W?(p) = R1(p) ? 5 || R2(p) ? 1
+
  Repeat 5: W'(p) = R1(p) >= 5 || R2(p) <= 1
  
 
  ############################################################
 
  ############################################################
Line 193: Line 227:
 
This is more interesting - it doesn't have any big open areas, it has a decent layout. It's almost fully connected. Still, it has some new problems: there are isolated single-tile walls in places, and in general it's not very smooth. But with a little tweaking:
 
This is more interesting - it doesn't have any big open areas, it has a decent layout. It's almost fully connected. Still, it has some new problems: there are isolated single-tile walls in places, and in general it's not very smooth. But with a little tweaking:
  
  Winit(p) = rand[0,100) < 40
+
  Winit(p) = rand(0,100) < 40
  Repeat 4: W?(p) = R1(p) ? 5 || R2(p) ? 2
+
  Repeat 4: W'(p) = R1(p) >= 5 || R2(p) <= 2
  Repeat 3: W?(p) = R1(p) ? 5
+
  Repeat 3: W'(p) = R1(p) >= 5
  
 
  ############################################################
 
  ############################################################
Line 228: Line 262:
 
  ############################################################
 
  ############################################################
  
Notice that the initial fill percentage is a little lower, the cutoffs are different, and we switch rules after a few generations. This is more like the desired result. So, with these parameters, I give you some more samples, at various sizes.
+
Notice that the initial fill percentage is a little lower, the cutoffs are different, and we switch rules after a few generations. This is more like the desired result. In the Example Output section, you can see some samples with these parameters, at various sizes.
 +
 
 +
=== Flood Fill ===
 +
 
 +
This algorithm creates good looking caves, but the problem is isolated caves. The way I solved this is by picking a random, open point on the map and flood filling. Any open point outside the flood filled portion gets turned back into a wall. I then check to see if the flood filled portion of the map is more than some threshold percent of the map. If the map is ~45% open it usually looks alright. If the percent is below this, I just start over.
 +
 
 +
This turns out to work quite well. On large maps, almost always you will select the largest open connected area, and you won't have to restart the regeneration very often, if at all. On very small maps, this doesn't happen as often, but its also very quick to regenerate because the map is small. It ends up that this method just does the right thing to rectify the non-connected maps naturally!
 +
-[[User:Jlund3|Jlund3]]
 +
 
 +
=== Horizontal Blanking ===
 +
 
 +
Another approach to fixing the problem of disconnected areas involves blanking a horizontal strip of walls, about 3 or 4 block tall, in the middle of of the map after the random fill, but before beginning the automata iterations. Depending on the rules, a horizontal strip of sufficient width will prevent a continuous vertical wall from forming, creating disconnected cave sections.
 +
 +
== Example Output ==
 +
 
 +
Animated GIF of the cellular automata cave process with 12 smoothing iterations (Generated using haskell):
 +
http://filesmelt.com/dl/cavegen.gif
  
 
  ##############################
 
  ##############################
Line 374: Line 424:
 
  ############################################################
 
  ############################################################
  
There's still no guarantee of connectedness, though. However, it's now consistently almost-connected, so that you can reasonably just drop the isolated chunks.
 
  
Finally, here is the C program I used to try out different parameters. Before putting this into an actual game, handling of disconnected regions is needed.
+
== Example Code ==
  
<pre>
+
=== C Code ===
 +
 
 +
Original article by [[Jim Babcock]]
 +
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em">
 +
<syntaxhighlight lang="c">
 
  #include <stdio.h>
 
  #include <stdio.h>
 
  #include <stdlib.h>
 
  #include <stdlib.h>
Line 546: Line 599:
 
  return 0;
 
  return 0;
 
  }
 
  }
</pre>
+
</syntaxhighlight>
 +
</div>
 +
 
 +
 
 +
=== C# Code ===
 +
 
 +
Borrowed from [http://www.csharpprogramming.tips/2013/07/Rouge-like-dungeon-generation.html csharpprogramming.tips] with permission from owner Adam Rakaska.
 +
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em">
 +
<syntaxhighlight lang="csharp">
 +
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;
 +
}
 +
if(numWalls<2)
 +
{
 +
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 || y<0 )
 +
{
 +
return true;
 +
}
 +
else if( x>MapWidth-1 || y>MapHeight-1 )
 +
{
 +
return true;
 +
}
 +
return false;
 +
}
 +
 +
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<string>();
 +
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 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;
 +
}
 +
}
 +
</syntaxhighlight>
 +
</div>
 +
 
 +
== Implementations ==
 +
 
 +
* [[C]]: [[Brogue]] source code
 +
* [[C#]]: [http://www.csharpprogramming.tips/2013/07/Rouge-like-dungeon-generation.html csharpprogramming.tips]
 +
* [[Javascript]]: [[rot.js]]
 +
* [[Lua]]: [[RotLove]]
 +
* [[Python]]: [http://pixelenvy.ca/wa/ca_cave.html ca_cave]
 +
 
  
[[Category:Algorithms]]
+
[[Category:Articles]]
 +
[[Category:WorldGeneration]]
 +
[[Category:Maps]]

Latest revision as of 03:23, 19 September 2016

Contents

[edit] Introduction

It is an old and fairly well documented trick to use cellular automata to generate cave-like structures. The basic idea is to fill the first map randomly, then repeatedly create new maps using the 4-5 rule: a tile becomes a wall if it was a wall and 4 or more of its eight neighbors were walls, or if it was not a wall and 5 or more neighbors were. Put more succinctly, a tile is a wall if the 3x3 region centered on it contained at least 5 walls. Each iteration makes each tile more like its neighbors, and the amount of overall "noise" is gradually reduced:

original:           iteration 1:        2:                  3:                  4:
 #       ### ##     ####  ##########    ####  ##########    ####  ##########    ####  ##########
# ##  ## ## #       # #      ##### #    ###      #######    ###      #######    ###      #######
 # # ##   #### #    # #   #   #### #    ##        ######    ##        ######    ##        ######
 # #  #  # ## #     ###  #     ### #    ##         #####    ##         #####    ##         #####
### # #     # #     #    #     #####    ##         #####    ##         #####    ##        ######
    # # ## #####    ##     ###  ####    #       ## #####    ##      ########    ##      ########
##     ####  #      #      #### ####    ##     ####  ###    ##     #### ####    ##     #########
## ## # ## #  ##    ###    ####    #    ###    ###   ###    ###    ####  ###    ###    #########
# ##  ###  #  #     ##### ###    ###    ####  #####  ###    ####  ##### ####    ####   #########
#  # # #  # ###     # ### ##########    ###### #########    #####  #########    ####   #########
  ## ## #### # #    #####    #######    ####    ########    ####    ########    ####    ########
####    # # # #     # #      #######    ##        ######    ##       #######    ##       #######
       #   ## ##    #          #####    #         ######    #         ######    #         ######
   # #    # ####               #####    #         ######    #         ######    #         ######
# # #  ## ######    #        #######    #        #######    ##       #######    ##       #######
#  #  # ####  #     ################    ################    ################    ################

If 45% of the original random map contains walls and the process is repeated 5 times, the output might look like the following:

############################################################
###....####################################.....############
##......######################..#########.........##########
##......#####################....#######...........####.####
##......###################.........................##...###
##......##################..........................###...##
#........##############.............................###...##
#........#############...............................#....##
##.......##############..................................###
##.......###..############..............................####
##.......##....############.............................####
#..............############...###........................###
#...............###########..#####...............##.......##
#................#################...............##.......##
##.....#####..........###########....#..........###.......##
##....#######...........########....###.........####......##
##....#######............######....####........#####......##
##....#######.............####....#####.......#####......###
#......######..............###....####........####......####
#.......######.............###...####.........###.......####
#........#####.............###..####.....................###
##........####..............#...####.....................###
#####......##...................####.....................###
######...........................##.....................####
######..................................................####
######.........###.....................####.............####
######......#########.................######............####
#######....#############.......##############.....###..#####
##############################################..############
############################################################

[edit] Advantages

Some advantages include:

  • Procedurally generated so no two levels are (likely) exactly the same.
  • Relatively simple concept, and implementation.
  • A natural, cave-like map to add variety, uniqueness or an alternative to room-based dungeons.


[edit] Disadvantages

Some disadvantages include:

  • Generation of isolated cave sections, possibly blocking player advancement (see possible solutions below).
  • Probably not appropriate for generating towns, so other map generators will probably need to be implemented.
  • Very large maps tend to not look as natural, or may require some very fine tuning.

[edit] The isolated cave problem

The problem is that the results are inconsistent. The algorithm prone to generating disconnected maps. See example below:

############################################################
#####################################################..#####
#####.....##################...###############............##
#####......###########.####....########.#####..............#
#####.......#########..###.....###############.............#
####.............#####.###....###################.........##
###...............########...####################........###
##.................#######...####################........###
##.......##.........#####.....##################.........###
##......####.........###.......################...........##
##.....########.................#######..######...........##
##...###########................######...#######..........##
#########..######..............######....########........###
########....######..#####......#####.....##########......###
#######......#############.....#####.....###########.....###
#######.......############......###.......###########.....##
#######.......###########.......###.......###########.....##
######.......####..######.......####.......#########......##
#####.......####....#####.......####..........######.....###
####........####......####......####...........#####.....###
####.........###.......###......####...##......######.....##
####...##.....###.......#......###########.....#######.....#
#####.####.....#####...........############....########....#
##########.....######..........############....#########..##
#########.......#####...........##########.....#############
#########.......####...............#####........############
##########......####................###...........##########
###########....#####.....######.....####...........#########
################################...##########.....##########
############################################################

It also sometimes generates maps which consist of one huge open space:

############################################################
############################################################
#################.####.######..######........###############
########...#####...##...####....####..........######...#####
###.####...####....###..####....####..........#####.....####
##...###....##.....###...##.....###............###......####
###.####...........###..........###.....###.........########
########...........###...........#.......#.........#########
#######.............#..............................#########
######.....##..........................................#####
###.......###...........................................####
##.......####...........................................####
##......................................................####
##.....................................................#####
##.....................................................#####
#.....................................##...............#####
#.....................................##................####
#...........................###......###................####
##...........###............###.....#####...............####
###...........#..............##.....######............######
######.......................##......######........#########
##########..................##.........#####......##########
###########................###..........####......##########
############................#...........####......##########
###.....#####.........##...............#####.......####..###
###.....#####.......#####.............#####..............###
###.....####.......#####..............#####.....##.......###
####...#####.......#####.....#####...######....####.....####
#############.##########....################..##############
############################################################

There are many ways to fix the disjoint segments problem. One approach might be to throw away maps that have disjoint segments in them. Another approach would be to connect the segments after the fact. Another still would be to fill in all but the biggest segment. We can't just retry when we get a disjoint map, because if the map is big then, statistically, that will be almost 100% of the time. Filling in all but the biggest segment will tend to produce a small area in a map that was supposed to be big. Connecting up the regions works, but it tends to look unnatural, as in the example from above, now connected:

############################################################
#####################################################..#####
#####.....##################...###############............##
#####......###########.####....########....................#
#####.......#########..###.....###############.............#
####.............####..###....###################.........##
###...............###.####...####################........###
##.................##.####...####################........###
##.......##.........#.###.....##################.........###
##......####..........##.......################...........##
##.....########.................#######..######...........##
##...###########................######...#######..........##
#########..######..............######....########........###
########............#####......#####.....##########......###
#######......#############...............###########.....###
#######.......############......###.......###########.....##
#######.......###########.......###.......###########.....##
######.......####..######.......####.......#########......##
#####.......####....#####.......####.....................###
####........####......####......####...........#####.....###
####.........###.......###......####...##......######.....##
####...##.....###.......#......###########.....#######.....#
#####.####.....#####...........############....########....#
##########.....######..........############....#########..##
#########.......#####...........##########.....#############
#########.......####...............#####........############
##########......####................###...........##########
###########....#####.....######.....####...........#########
################################...##########.....##########
############################################################

[edit] Rule Tweaking

The solution to both problems, as it turns out, is to revisit the original cellular automata rules. Recall that the original rule was

  • There is a wall initially at P with 45% probability
  • In the next generation, there is a wall at spot P if the number of tiles around P which are walls is at least 5

Or, in more compact notation:

  • Winit(p) = rand(0,100) < 45
  • R(p) = the number of tiles within 1 step of p which are walls
  • W'(p) = R(p) >= 5

Now, one of the problems was that we tend to get big, open areas. So why not try filling those areas in? Change the rule to

  • W'(p) = R(p) >= 5 or p is in the middle of an open space

Or more formally,

  • Rn(p) = the number of tiles within n steps of p which are walls
  • W'(p) = R1(p)>=5 || R2(p)=0

So how does it look?

Winit(p) = rand(0,100) < 45
Repeat 5: W'(p) = R1(p) >= 5 || R2(p) <= 1
############################################################
##....######################################################
#.......###..#####..####....###########################..###
#...#.........###.............##########..############....##
##...###...#..###..............########....######..###....##
###...######...#..##...........######.....######....###..###
####..######......##..##........####...#..######....########
####..###.#.......#...##...#.....##...###..######...########
#####.........##...........##........####.....##.....#######
#####.........##...........#.......##.....#.............####
####...###...##................#...##......###...........###
####...###..##...###....##.....##..##..##..###....##.....###
#########..###..####...###.............###..##..####.....###
########...##..#####...##...............#...#...####....####
#######........######......###...##....................#####
#######..##.....######....##########...................#####
######..####.......####...#########...................######
####....####..##....##.....#######...##..............#######
###.....###..#####......#...####....##................######
##..##..###..###........##.........#....#......##......#####
#..####..##...##.................###...##.....####......####
#.....#..###..#..##..........#..###..###.....#####......####
##.......####.....#...##........##..###....#######......####
######....###.......................###...#######....#######
#######......................##.....###...#######...########
########.................#######....####...#####....########
########..............###########..######...........########
#########....####....######################........#########
###################.########################################
############################################################

This is more interesting - it doesn't have any big open areas, it has a decent layout. It's almost fully connected. Still, it has some new problems: there are isolated single-tile walls in places, and in general it's not very smooth. But with a little tweaking:

Winit(p) = rand(0,100) < 40
Repeat 4: W'(p) = R1(p) >= 5 || R2(p) <= 2
Repeat 3: W'(p) = R1(p) >= 5
############################################################
###...###########..#############################.....#######
##..........####....################..#########.........####
##...........##.....####..#########.......####..######...###
##.......#..........###....###.................########..###
##......###........###........................#########..###
##.......##.........#........................##########...##
##.......###...........##.............###....#########.....#
##.......######.......####...........#####....#####........#
###.....#########....#####...........######...#####........#
###########################...........#####...#######.....##
#############...###########.............##....########....##
############.........#######...................#######....##
###########...........########......###............##....###
###..#####.............#########...##########............###
##....###...............######################..........####
###..........................######..#########..........####
####..........................###.....#######...........####
####.................##................##................###
####...###..........####...............#..................##
###...#####.........####..............##......##...........#
##....########......#####............####....####..........#
##....#########.....#####............####....####..........#
##.....######.......#####.............##.....####...##.....#
##......##..........#####....................####..####....#
###.................####.........###........############..##
###............##..######.###...############################
####..........##############################################
######..####################################################
############################################################

Notice that the initial fill percentage is a little lower, the cutoffs are different, and we switch rules after a few generations. This is more like the desired result. In the Example Output section, you can see some samples with these parameters, at various sizes.

[edit] Flood Fill

This algorithm creates good looking caves, but the problem is isolated caves. The way I solved this is by picking a random, open point on the map and flood filling. Any open point outside the flood filled portion gets turned back into a wall. I then check to see if the flood filled portion of the map is more than some threshold percent of the map. If the map is ~45% open it usually looks alright. If the percent is below this, I just start over.

This turns out to work quite well. On large maps, almost always you will select the largest open connected area, and you won't have to restart the regeneration very often, if at all. On very small maps, this doesn't happen as often, but its also very quick to regenerate because the map is small. It ends up that this method just does the right thing to rectify the non-connected maps naturally! -Jlund3

[edit] Horizontal Blanking

Another approach to fixing the problem of disconnected areas involves blanking a horizontal strip of walls, about 3 or 4 block tall, in the middle of of the map after the random fill, but before beginning the automata iterations. Depending on the rules, a horizontal strip of sufficient width will prevent a continuous vertical wall from forming, creating disconnected cave sections.

[edit] Example Output

Animated GIF of the cellular automata cave process with 12 smoothing iterations (Generated using haskell): cavegen.gif

##############################
##..###....###.....###########
#...........................##
#.................##.........#
##..###..........#######.....#
########.........#######.....#
############......####......##
#############...............##
###..########...............##
##....#######...###..#......##
##.....######...#######.....##
##......#####...######......##
##...#...###....#####.......##
##..##.........######.......##
##..........##########......##
###........#####..####.....###
###........####....###.....###
###....##...##.....###.....###
###...####........####......##
###...#####......#####......##
##....#####.....#####.......##
##.....###.....####.........##
##..............##..........##
###.........................##
####........................##
####.......................###
####..........##...........###
#####...###..####.........####
####################.....#####
##############################
############################################################
#########......###...##........####...####.....#############
####............................##.....##............#######
###................###.....##..........................#####
###...............#####...####..........................####
###...............#####....####............#............####
####...###.........####.......##.......................#####
##########..........###........##.....................######
##########...........#..........##...................#######
#########.......................#####..............#########
######.........................#######...#......############
#####..........................############....#############
####...........................###########......######..####
###..........##.................#########................###
##.......#######........#..........######...###.........####
##......########.......##............###...######.....######
###.....#######...............#####........########..#######
###......#####...##...........######........################
###......#####..####...........#####.........###############
#######..#####..####............###...........#######....###
########..###...#####......###.................#####......##
########.......######......####.................###.......##
########.......######.......##....##..................##..##
#######.......######....##.......####................####..#
######.......#######....###......####..........###..#####..#
#####........######.....######....##..........##########...#
######........###........######...............########.....#
##########...............#######.............########.....##
#############...#######..###########...#####################
############################################################
################################################################
#######..#####............####..####...###....###########...####
###......####..................................#########.....###
##.......###.......................................####......###
##......####.............##.........................##......####
##......#####......##...####................##..............####
##......##############..#####...............###.............####
##.....###############...#####...............##........##...####
##.....################..######.........#.............####...###
##.....################...#####........###............####....##
###.....#####..##...##....####.........###.............###....##
####....####..............###..........###...................###
####....####.............####..........##....................###
###.....####...........#####.........................##.....####
##.......##............#####....................##..####...#####
##.....................######................###########...#####
###..##........##......###############.....############....#####
########......####....#################..###############..######
#########...####################################################
################################################################ 
############################################################
#########......###...##........####...####.....#############
####............................##.....##............#######
###................###.....##..........................#####
###...............#####...####..........................####
###...............#####....####............#............####
####...###.........####.......##.......................#####
##########..........###........##.....................######
##########...........#..........##...................#######
#########.......................#####..............#########
######.........................#######...#......############
#####..........................############....#############
####...........................###########......######..####
###..........##.................#########................###
##.......#######........#..........######...###.........####
##......########.......##............###...######.....######
###.....#######...............#####........########..#######
###......#####...##...........######........################
###......#####..####...........#####.........###############
#######..#####..####............###...........#######....###
########..###...#####......###.................#####......##
########.......######......####.................###.......##
########.......######.......##....##..................##..##
#######.......######....##.......####.........##.....####..#
#####........#######....###......####........#####..#####..#
####........#######.....######...#####.......############..#
####.......######..........####..#########..#############..#
###........#####............###..########################.##
##.........####.............###..################.######..##
#....###...####......####....#...######..#######...#####..##
#.....#.....##......######.......#####....#####....#####..##
#...................######........####....###.....#####...##
#....................#####........#####..###......##......##
#....................######........########................#
##......#............########.......#######................#
##......##...........#########......#######...............##
###.....#............####...##.....#######..##...........###
###..........#......####...........######..####..........###
##..........####....####...........#####..######.........###
##...........####..#####............##....######.........###
##............###..######......#...........####..........###
##............###..#######.....##........................###
##.......###...#....#######....#..........................##
###......###.........######.........................##.....#
###.......#..........######........#####...........####....#
###............###...######......########.........#####....#
###...........#####..######.....#########.........####.....#
###...........#####.#######.....########...........###.....#
###...........####..########...#########......##...###....##
###...........####...##################......####..###....##
###...........####......##############.......####..###....##
###...........####..........##########........##...###....##
###............####..........#########.............####..###
###...........#####...........#######..............#########
###.....##########............######.......##......#########
##.....###########.....###.....####.......####......########
##.....############....###......##.......#####........######
###...##############..#####.............#######.......######
################################...##..#####################
############################################################


[edit] Example Code

[edit] C Code

Original article by Jim Babcock

 #include <stdio.h>
 #include <stdlib.h>
 #include <time.h>
 
 #define TILE_FLOOR 0
 #define TILE_WALL 1
 
 typedef struct {
 	int r1_cutoff, r2_cutoff;
 	int reps;
 } generation_params; 
 
 int **grid;
 int **grid2; 
 
 int fillprob = 40;
 int r1_cutoff = 5, r2_cutoff = 2;
 int size_x = 64, size_y = 20;
 generation_params *params;  
 
 generation_params *params_set;
 int generations;
 
 int randpick(void)
 {
 	if(rand()%100 < fillprob)
 		return TILE_WALL;
 	else
 		return TILE_FLOOR;
 }
 
 void initmap(void)
 {
	int xi, yi;
 
	grid  = (int**)malloc(sizeof(int*) * size_y);
	grid2 = (int**)malloc(sizeof(int*) * size_y);
 
	for(yi=0; yi<size_y; yi++)
	{
		grid [yi] = (int*)malloc(sizeof(int) * size_x);
		grid2[yi] = (int*)malloc(sizeof(int) * size_x);
	}
 
	for(yi=1; yi<size_y-1; yi++)
	for(xi=1; xi<size_x-1; xi++)
		grid[yi][xi] = randpick();
 
	for(yi=0; yi<size_y; yi++)
	for(xi=0; xi<size_x; xi++)
		grid2[yi][xi] = TILE_WALL;
 
	for(yi=0; yi<size_y; yi++)
		grid[yi][0] = grid[yi][size_x-1] = TILE_WALL;
	for(xi=0; xi<size_x; xi++)
		grid[0][xi] = grid[size_y-1][xi] = TILE_WALL;
 }
 
 void generation(void)
 {
	int xi, yi, ii, jj;
 
	for(yi=1; yi<size_y-1; yi++)
	for(xi=1; xi<size_x-1; xi++)
 	{
 		int adjcount_r1 = 0,
 		    adjcount_r2 = 0;
 
 		for(ii=-1; ii<=1; ii++)
		for(jj=-1; jj<=1; jj++)
 		{
 			if(grid[yi+ii][xi+jj] != TILE_FLOOR)
 				adjcount_r1++;
 		}
 		for(ii=yi-2; ii<=yi+2; ii++)
 		for(jj=xi-2; jj<=xi+2; jj++)
 		{
 			if(abs(ii-yi)==2 && abs(jj-xi)==2)
 				continue;
 			if(ii<0 || jj<0 || ii>=size_y || jj>=size_x)
 				continue;
 			if(grid[ii][jj] != TILE_FLOOR)
 				adjcount_r2++;
 		}
 		if(adjcount_r1 >= params->r1_cutoff || adjcount_r2 <= params->r2_cutoff)
 			grid2[yi][xi] = TILE_WALL;
 		else
 			grid2[yi][xi] = TILE_FLOOR;
 	}
 	for(yi=1; yi<size_y-1; yi++)
 	for(xi=1; xi<size_x-1; xi++)
 		grid[yi][xi] = grid2[yi][xi];
 } 
 
 void printfunc(void)
 {
 	int ii;
 
 	printf("W[0](p) = rand[0,100) < %i\n", fillprob);
 
 	for(ii=0; ii<generations; ii++)
 	{
 		printf("Repeat %i: W'(p) = R[1](p) >= %i",
 			params_set[ii].reps, params_set[ii].r1_cutoff);
 
 		if(params_set[ii].r2_cutoff >= 0)
 			printf(" || R[2](p) <= %i\n", params_set[ii].r2_cutoff);
 		else
 			putchar('\n');
 	}
 }
 
 void printmap(void)
 {
 	int xi, yi;
 
 	for(yi=0; yi<size_y; yi++)
 	{
 		for(xi=0; xi<size_x; xi++)
 		{
 			switch(grid[yi][xi]) {
 				case TILE_WALL:  putchar('#'); break;
 				case TILE_FLOOR: putchar('.'); break;
 			}
 		}
 		putchar('\n');
 	}
 }
 
 int main(int argc, char **argv)
 {
 	int ii, jj;
 
 	if(argc < 7) {
 		printf("Usage: %s xsize ysize fill (r1 r2 count)+\n", argv[0]);
 		return 1;
 	}
 	size_x     = atoi(argv[1]);
 	size_y     = atoi(argv[2]);
 	fillprob   = atoi(argv[3]);
 
 	generations = (argc-4)/3;
 
 	params = params_set = (generation_params*)malloc( sizeof(generation_params) * generations );
 
 	for(ii=4; ii+2<argc; ii+=3)
 	{
 		params->r1_cutoff  = atoi(argv[ii]);
 		params->r2_cutoff  = atoi(argv[ii+1]);
 		params->reps = atoi(argv[ii+2]);
 		params++;
 	}
 
 	srand(time(NULL));
 
 	initmap();
 
 	for(ii=0; ii<generations; ii++)
 	{
 		params = &params_set[ii];
 		for(jj=0; jj<params->reps; jj++)
 			generation();
 	}
 	printfunc();
 	printmap();
 	return 0;
 }


[edit] C# Code

Borrowed from csharpprogramming.tips with permission from owner Adam Rakaska.

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;
			}
			if(numWalls<2)
			{
				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 || y<0 )
		{
			return true;
		}
		else if( x>MapWidth-1 || y>MapHeight-1 )
		{
			return true;
		}
		return false;
	}
 
	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<string>();
		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 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;
	}
}

[edit] Implementations

Personal tools