Using Cellular Automata to Generate Caves

Cellular Automata is a really awesome way to procedurally generate content. And as a game developer, I like procedurally generated content. I've spent much of today exploring the concept of procedurally generating underwater caves for a side scrolling submarine game using cellular automata.

But this goes beyond just CA. I added in some additional sets of rules, both before and after the CA, to really make something cool. Here is a screenshot of the software. You can see a single level generated with it, along with the options on the right side.

Before I go too much into the options, I'll give an overview of the algorithm.

  1. Create a blank grid of the default size. The default size, in this case, is 32x32 px. This is determined by the Grid Size entry for the first set of rules.
  2. Execute the rules shown in the table. Each row represents one set of CA commands. I like to start off with a low resolution and work up. I found that gave really good results for winding, snaking caves. Starting too high led to big empty rooms too often. 
  3. Analyze the output and identify the connected components. Unlike in the screenshot, at this point the cave is more like a collection of unconnected rooms than a usable game level. I find the largest contiguous area and mark that as the main area to work with.
  4. Use the A* algorithm to find the shortest path from the main area to the outer areas. If the path is less than the tunnel distance, blast a tunnel and connect the two up. This helps create the winding cave effect with lots of narrow tunnels. Longer distances and narrow widths lead to some interesting networks.
  5. Execute the CA rules a final few times. This smooths off the tunnels and makes them look more natural.
  6. Delete any chambers that are still not connected to the main chamber.
  7. Analyze the percentage of open space on the map. If that percentage is within the min and max open, the map is accepted. In the screenshot, there is 38.91% open space, nicely within the 30-40% range. I find the best maps for my kind of underwater game have around this range.

Now a look at the options:

  • The table on the top determines the rules for the CA. The CA's main function is a very simple Moore neighborhood analysis. During each cell's processing, the neighborhood is sampled and the number of open cells are counted. If the number of open cells exceeds a given threshold, that cell is opened. Otherwise, it is closed. So the values in the table are Grid Size to determine the size of the grid, the number of times this CA rule should be executed, the Moore neighborhood size (distance from center, so a size of 1 is a 3x3 grid, 2 is a 5x5 grid, etc), the local threshold (the number of cells that must be open to keep this one open) and the initialization percentage. This percentage is the percent of cells that should be opened when this rule set is first started. A high number leads to more caverns. A lower number, coupled with more tunnels, leads to snaking, narrow caves.
  • The tunnel configuration settings determine how to tunnel between caverns after the rules have been processed. Tunnel distance is the maximum length that a tunnel can run between two caverns. The tunnel width is how wide of a tunnel to make and the tunnel initialization is the percent of cells that will be left open when the tunnel is made.
  • The Final section determines one last pass of the CA rules. Grid size is left at the same size as the last ruleset. The Iterations, Local Size and Local Threshold are the same as described for the CA rules.
  • The Minimum Open and Maximum Open values determine what is considered an acceptable amount of open space when all is said and done. I like the 30-40% range, but your rules may want you putting it elsewhere.

This is my first shot at a CA ruleset for level generation and I love it. I've already got some ideas on how to populate the level and I can't wait to explore that.

You can either get the source code on Github or you can download the files here. It's just a single .exe and a .dll with some algorithms that I like to reuse. No installer needed, assuming you have .NET 4.0 installed!