Evil Science A whole load of stuff

23Feb/146

A C# algorithm to build interesting cave systems for your Roguelike part 1 UPDATED!!!!

I've been playing roguelikes for the last twenty years or so, and one thing that has consistently annoyed me is that dungeons, on the whole, tend to be rectangular rooms connected with long, straight corridors that turn at right angles. I've never came across a roguelike that has complex, chaotic looking cave systems with twisting corridors  and misshapen rooms, and that has annoyed me so much I decided to put together a simple algoritm in C# to generate such a system. Here's an example of a complex cave systems generated by my code, and below that I discuss the code used to generate it.

cavesystem3cavesystem2

!!!Update!!!

I have been blown away by the interest from the users of Reddit's Unity3D  and made an update to the code allowing users to generate a Bitmap of the generated map. See here for more details.

Overview

This algorithm works by using a modified form of Conway's Game of Life where:

  1. Each cell in the map is visited and a randomly probability is used to determine if that cell is closed,
  2. Cells are randomly visited and the number of neighbours that cell has is used to determine whether to close it or open it.

By repeating the second step thousands of times, "blobs" or "caves" start to form which. By adjusting various available properties the characteristics of the caves formed can change considerably, which can lead to some very interesting cave systems being formed.

After caves have been generated, a flood fill based algorithm locates each cave and the data for each cave into a generic list. With this list of caves they can be easily connected together with a dumb corridor building routine is used to try and connect the caves. This works by randomly selecting a cave and growing a corridor in a random direction and seeing if it hits another cave within a time period determined by a series of properties. If sucessful the two connected caves are placed in a list, and a further attempt is made to connect one of those caves to another, and so on.

The Application

You can find a simple C# application which demos the algorithm I've written here, and below is a screenshot of it.

app

The app consists of three areas:

  1. Property grid - the properties which govern the generation of the cave system.
  2. Picturebox - displays the generated cave system.
  3. Buttons:
    1. Build Caves - click to build a cave system.
    2. Connect Caves - click to connect the caves.
    3. Reset Properties - click the reset the property values to their default state.

Simply put, to build a cave system click the Build Caves button, and to change the appearance of a cave system fiddle with the properties.

Properties

This application has a number of properties which can be adjusted to determine the appearance of the generated generated cave system:

  1. Cave Cleaning
    1. Filling - Fills in holes within caves: an open cell with this number closed neighbours is closed.
    2. Lower Limit - the minimum size of caves allowed. If a cave is smaller than this number, it will be removed.
    3. Smoothing - Removes single cells from cave edges: a cell with this number of empty neighbours is removed
    4. Upper Limit - the maximum size of caves allowed. If a cave is larger than this number, it will be removed.
  2. Cave Generation
    1. Close Cell Prob - this value determines the chance of closing a visited cell.
    2. Cells to visit - the number of cells to visit during the generation process.
    3. Map Size - guess what this does.
    4. Neighbours - when this value is equalled or exceeded, change the cell state.
  3. Corridor 
    1. Breakout  - a counter value, that when exceeded stops attempting to generate corridors. Stops the corridor building process from getting stuck.
    2. Corridor Spacing - the number of empty cells the corridor has to have on either side of it for it to be built. This is dependant upon the direction it is travelling. If travelling north, it must have that number of empty cells to the east and west of it.
    3. Minimum Length - the minimum length of a corridor.
    4. Maximum Length - the maximum length of a corridor.
    5. Maximum Turns - the maximum number of direction changes a corridor can make whilst it is being built.
  4. Generated Map
    1. Caves - the number of caves in the generated system.

The Code

The code used to generate a caver system is contained within the class csCaveGenerator.cs, which sits in a standard C# form with a few controls on it which can manipulate that class.

For an overview of the class csCaveGenerator.cs, click here.

For a more detailed look at using the class csCaveGenerator.cs, click here.

To view the class csCaveGenerator.cs in GitHub click here.

Interesting Patterns

Playing around with the properties can produce cave systems with markedly different appearances, here are a few interesting systems that can be produced.

Several Large Caves

Setting the properties to:

  1. MaxSizeToRemove: 1500
  2. MinSizeToRemove: 450
  3. EmptyCells > EmptyCellNeighbours: 3

and clicking build a few times produced these three lovely caves.

cavesystem3

Many small chunky caves

Setting the properties to:

  1. Iterations: 10,000
  2. Smothing>EmptyNeighbours:3
  3. EmptyCells>EmptyNeighbours:4

And clicking build, produces lots of little chunky caves with straight edges, packed closer together.

cavsystem4

One Massive Cave

Setting the properties to:

  1. Caves > MaxSizeToRemove: 10000
  2. Cells > CloseCellProb: 55

And clicking Go a few times will produce a lovely, humongous cave, as shown below.

cavesystem5

 

Links

Github: To view the class csCaveGenerator.cs, which is used to generate the cave system, click here.

To download a C# app which demos the Cave Generator algorithm click  here.

Filed under: C#, Roguelike Leave a comment
Comments (6) Trackbacks (0)
  1. Hello Evil Scientist ;)
    Thought you’d like to know that I’m working this concept into my latest game, and wrote a bit about my own version (and yours) here. I loved the look of your cave shots when you first posted this and even more so the idea that “caves” can be the equivalent of “rooms,” which helps keep multiple dungeon types consistent for the purpose of analysis and object placement. Thanks for sharing!

  2. That’s great! Thanks for your interest!

  3. Thank you for sharing this, i included your approach in my Level-Generator Script for Unity:
    http://forum.unity3d.com/threads/random-level-generator.342587/#post-2215083

  4. That’s great! Keep up the good work, and make sure to send me updates!

  5. I added a new Type of generator to the set, Template-Placer, it is fast and offers some neat features for the later dungeon handling.

    http://forum.unity3d.com/threads/random-level-generator.342587/#post-2348154

    Again, Thank you for sharing your code, i learned from it.

  6. Hi there – thanks for the post and good luck with the project, which looks really neat. Please let me know about any future updates and I’ll happily post them on my site.


Leave a comment


9 − = two

No trackbacks yet.