Virtual Spelunking: Procedural Cave Generation


It’s easy to understand the lure of algorithmically generating game maps, especially for a programmer. A game using this technique can generate a near-infinite set of unique maps allowing it to be played over-and-over again. Generating random maps is the bread-and-butter of certain game genres, Rogue-likes for example, that thrive on such variety and replay.

There is a wealth of information on the subject of procedurally generated maps on the web. Particularly on sites devoted to the aforementioned Rogue-like genre of game. By using techniques documented on one such site and mixing in some well-known algorithms, I managed to implement a random cave generator that I think I’ll be able to use in a game or two in the future.

For my cave generation algorithm, I decided to implement the cellular automata-based cave generation technique described here. The term “cellular automata” refers to arrays of cells with states that run (usually) simple algorithms that change their state based on the states of their neighbors. Cellular automata-based cave generation creates maps by randomly filling an array of spaces with wall and floor tiles. It then runs an algorithm over the array that changes spaces to walls or floors based on how many walls are in their immediate vicinity. Each run of the algorithm makes a space more like its neighbors and, after 4-5 generations, creates large contiguous regions of walls/floors in the array.

The cave generation algorithm in a nutshell:

  1. Fill each space in the array with either a floor (55% chance) or wall (45% chance)
  2. For each space in the array:
    1. If it is a wall and 4+ neighbors are walls, it stays a wall
    2. If it is a floor and 5+ neighbors are walls, it becomes a wall
    3. Otherwise, it becomes a floor
  3. Repeat step 2 for as many generations as desired (usually 4-5)

Using the algorithm with 4 generations to render a 60×20 map results in a map like this: (‘#’ == walls, ‘.’ == floors)

The overall shape of the cavern is appealing and would make a decent play-area. Unfortunately, not all the caverns are connected which means that some parts of the map would be unreachable. In order to make this cave generation implementation suitable for use in a game, we need a way to guarantee that all floor spaces will be reachable for any map we generate.

To make sure all floor spaces are reachable, I opted to implement logic to carve out tunnels from the smaller caverns to the largest cavern on the map. To do this, I need three things: A) a reliable way to detect all the distinct caverns in the map, B) a way to designate the “central” cavern, and C) a way to find a reasonably short path to dig tunnels between two caverns.

Dusting off the old algorithms textbook, I came up with the following solution:

  1. Use a flood-fill to detect each cavern (defined as a distinct area of contiguous floor) in the map
  2. Pick the largest cavern as the “central” cavern
  3. For each non-central cavern, use A* path-finding to find a path from a random point in the non-central cavern to a random point in the central cavern and turn each space in the path into a floor.

For the A* heuristic function, I value walls as being more expensive than floors, but not impassible. This causes the path-finding to favor paths made of floors while still allowing it to dig through walls as a last resort.

Heuristic cost function:

int _HeuristicCostEstimate(ChamberCoordinate coord1, ChamberCoordinate coord2)
{
    //Manhattan distance with high cost for walls
    int D = 1;
    if (_generatedCave[coord1.i][coord1.j] == CaveSpaceType.Wall)
    {
        D = 10;
    }
    return D * (Math.Abs(coord1.i - coord2.i) + Math.Abs(coord1.j - coord2.j));
}

Applying the tunnel-digging logic to the previous map results in the following:

Now, every floor space in the map is reachable, ready for the player to explore. By varying the number I use to seed my random number generator, I can easily create a large number of navigable maps.

For the code-hungry, here is my cave generation implementation:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace ProceduralWorldLib
{
    public enum CaveSpaceType
    {
        Floor,
        Wall
    }

    public class RandomCaveGenerator
    {
        struct ChamberCoordinate
        {
            public int i;
            public int j;

            public ChamberCoordinate(int inI, int inJ)
            {
                i = inI;
                j = inJ;
            }

            public void Empty()
            {
                i = -1;
                j = -1;
            }

            public bool IsSet()
            {
                return i >= 0 && j >= 0;
            }

            public bool Equals(ChamberCoordinate c)
            {
                return c.i == this.i &&
                    c.j == this.j;
            }

            public override bool Equals(object obj)
            {
                if (obj is ChamberCoordinate)
                    return Equals((ChamberCoordinate)obj);
                return false;
            }
        };

        int _columnCount;
        int _rowCount;
        int _rngSeed;
        List<List<CaveSpaceType>> _generatedCave;

        Random _rng;
        List<List<ChamberCoordinate>> _chambers;
        int _centralChamberIndex;
        bool _bDigToCentralCavern;

        const int INITIAL_WALL_CHANCE_PERCENT = 45;
        const int WALLS_FOR_WALL_CONVERSION = 4;
        const int WALLS_FOR_NON_WALL_CONVERSION = 5;
        const int WALL_CONVERSION_GENERATION_COUNT = 4;

        public RandomCaveGenerator(int seed, int columnCount, int rowCount)
        {
            _columnCount = columnCount;
            _rowCount = rowCount;
            _rngSeed = seed;

            _bDigToCentralCavern = true;
        }

        public int ColumnCount
        {
            set
            {
                _columnCount = value;
            }
        }

        public int RowCount
        {
            set
            {
                _rowCount = value;
            }
        }

        public int RandomSeed
        {
            set
            {
                _rngSeed = value;
            }
        }

        public bool DigToCenter
        {
            set
            {
                _bDigToCentralCavern = value;
            }
        }

        public void GenerateMap()
        {
            _rng = new Random(_rngSeed);
            //Fill initial seeds
            _generatedCave = new List<List<CaveSpaceType>>(_rowCount);
            for (int i = 0; i < _rowCount; ++i)
            {
                List&lt;CaveSpaceType&gt; rowArray = new List&lt;CaveSpaceType&gt;(_columnCount);
                for (int j = 0; j < _columnCount; ++j)
                {
                    if (i == 0 || j == 0 || i == _rowCount - 1 || j == _columnCount - 1)
                    {
                        rowArray.Add(CaveSpaceType.Wall);
                    }
                    else
                    {
                        rowArray.Add(_rng.Next(100) < INITIAL_WALL_CHANCE_PERCENT ? CaveSpaceType.Wall : CaveSpaceType.Floor);
                    }
                }
                _generatedCave.Add(rowArray);
            }

            //Convert spaces to walls or floors based on neighbors
            for (int genCount = 0; genCount < WALL_CONVERSION_GENERATION_COUNT; ++genCount)
            {
                CaveSpaceType[][] scratchArray = new CaveSpaceType[_generatedCave.Count][];
                for (int i = 0; i < _generatedCave.Count; ++i)
                {
                    scratchArray[i] = new CaveSpaceType[_generatedCave[i].Count];
                    for (int j = 0; j < _generatedCave[i].Count; ++j)
                    {
                        scratchArray[i][j] = _generatedCave[i][j];
                    }
                }


                for (int i = 0; i < _generatedCave.Count; ++i)
                {
                    for (int j = 0; j < _generatedCave[i].Count; ++j)
                    {
                        _generatedCave[i][j] = _NewSpaceValue(genCount, scratchArray, i, j);
                    }
                }
            }

            //Paint fill to figure out where our caverns are
            _FillPaintCavernDetection();

            //Pick "central" chamber based on size (or proximity to center of map?)
            int lastChamberSize = 0;
            for (int chamberIndex = 0; chamberIndex < _chambers.Count; ++chamberIndex)
            {
                if (_chambers[chamberIndex].Count > lastChamberSize)
                {
                    _centralChamberIndex = chamberIndex;
                    lastChamberSize = _chambers[chamberIndex].Count;
                }
            }

            //A* pathfinding to go from each cavern to central cavern.  Walls have high cost, but are not impassable
            if (_bDigToCentralCavern)
            {
                _DigToCentralCavern();
            }
        }

        public void CopyGeneratedMap(ref List&lt;List&lt;CaveSpaceType&gt;&gt; arrayTarget)
        {
            //Temp: make it actually copy
            arrayTarget = _generatedCave;
        }

        private CaveSpaceType _NewSpaceValue(int genCount, CaveSpaceType[][] scratchArray, int i, int j)
        {
            if( i == 0 || i == _generatedCave.Count - 1 || j == 0 || j == _generatedCave[i].Count - 1 )
                return scratchArray[i][j];

            int wallCount = 0;
            if (_IsWall(scratchArray[i - 1][j - 1])) wallCount++;
            if ( _IsWall(scratchArray[i][j - 1]) ) wallCount++;
            if ( _IsWall(scratchArray[i + 1][j - 1]) ) wallCount++;

            if ( _IsWall(scratchArray[i - 1][j]) ) wallCount++;
            if ( _IsWall(scratchArray[i + 1][j]) ) wallCount++;

            if ( _IsWall(scratchArray[i - 1][j + 1]) ) wallCount++;
            if ( _IsWall(scratchArray[i][j + 1]) ) wallCount++;
            if ( _IsWall(scratchArray[i + 1][j + 1]) ) wallCount++;

            if (scratchArray[i][j] == CaveSpaceType.Wall && wallCount >= WALLS_FOR_WALL_CONVERSION)
            {
                return CaveSpaceType.Wall;
            }

            if (scratchArray[i][j] == CaveSpaceType.Floor && wallCount >= WALLS_FOR_NON_WALL_CONVERSION)
            {
                return CaveSpaceType.Wall;
            }

            return CaveSpaceType.Floor;
        }

        private bool _IsWall(CaveSpaceType spaceType)
        {
            return spaceType == CaveSpaceType.Wall;
        }

        private void _FillPaintCavernDetection()
        {
            _chambers = new List&lt;List&lt;ChamberCoordinate&gt;&gt;();

            char[][] scratchArray = new char[_generatedCave.Count][];
            for (int i = 0; i < _generatedCave.Count; ++i)
            {
                scratchArray[i] = new char[_generatedCave[i].Count];
                for (int j = 0; j < _generatedCave[i].Count; ++j)
                {
                    if (_generatedCave[i][j] == CaveSpaceType.Floor)
                    {
                        scratchArray[i][j] = '.';
                    }
                    else
                    {
                        scratchArray[i][j] = '#';
                    }
                }
            }

            int fillNumber = 0;
            for (int i = 0; i < _generatedCave.Count; ++i)
            {
                for (int j = 0; j < _generatedCave[i].Count; ++j)
                {
                    if (scratchArray[i][j] == '.')
                    {
                        _chambers.Add(new List&lt;ChamberCoordinate&lt;());
                        _FillPaintCavern(scratchArray, i, j, Convert.ToChar(fillNumber.ToString()));
                        fillNumber++;
                    }
                }
            }

            //For visualization test
            /*for (int i = 0; i < _generatedCave.Count; ++i)
            {
                for (int j = 0; j < _generatedCave[i].Count; ++j)
                {
                    _generatedCave[i][j] = scratchArray[i][j];
                }
            }*/
        }

        private void _FillPaintCavern(char[][] scratchArray, int i, int j, char fillNumber)
        {
            /*1. If the color of node is not equal to target-color, return.
            2. Set the color of node to replacement-color.
            3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
                Perform Flood-fill (one step to the east of node, target-color, replacement-color).
                Perform Flood-fill (one step to the north of node, target-color, replacement-color).
                Perform Flood-fill (one step to the south of node, target-color, replacement-color).
            4. Return.*/

            if (scratchArray[i][j] != '.')
                return;

            scratchArray[i][j] = fillNumber;
            _chambers[_chambers.Count - 1].Add(new ChamberCoordinate(i, j));

            if (i > 0)
                _FillPaintCavern(scratchArray, i - 1, j, fillNumber);
            if (i < _generatedCave.Count - 1)
                _FillPaintCavern(scratchArray, i + 1, j, fillNumber);

            if (j > 0)
                _FillPaintCavern(scratchArray, i, j - 1, fillNumber);
            if (i < _generatedCave[i].Count - 1)
                _FillPaintCavern(scratchArray, i, j + 1, fillNumber);
        }

        private void _DigToCentralCavern()
        {
            for (int chamberIndex = 0; chamberIndex < _chambers.Count; ++chamberIndex)
            {
                if (chamberIndex != _centralChamberIndex)
                {
                    ChamberCoordinate originCoordinate = _chambers[chamberIndex][_rng.Next(_chambers[chamberIndex].Count)];
                    ChamberCoordinate targetCoordinate = _chambers[_centralChamberIndex][_rng.Next(_chambers[_centralChamberIndex].Count)];

                    _DigBetweenPoints(originCoordinate, targetCoordinate);
                }
            }
        }

        void _DigBetweenPoints(ChamberCoordinate originCoordinate, ChamberCoordinate targetCoordinate)
        {
            List&lt;ChamberCoordinate&gt; closed_set = new List&lt;ChamberCoordinate&gt;();
            List&lt;ChamberCoordinate&gt; open_set = new List&lt;ChamberCoordinate&gt;();
            ChamberCoordinate[] came_from = new ChamberCoordinate[_rowCount * _columnCount];
            open_set.Add(originCoordinate);

            int cameFromSize = _rowCount * _columnCount;
            for (int i = 0; i < cameFromSize; ++i)
            {
                came_from[i].Empty();
            }

            int[] g_score = new int[_rowCount * _columnCount];
            int[] h_score = new int[_rowCount * _columnCount];
            int[] f_score = new int[_rowCount * _columnCount];
            g_score[_ChamberToIndex(originCoordinate)] = 0;
            h_score[_ChamberToIndex(originCoordinate)] = _HeuristicCostEstimate(originCoordinate, targetCoordinate);
            f_score[_ChamberToIndex(originCoordinate)] = g_score[_ChamberToIndex(originCoordinate)] + h_score[_ChamberToIndex(originCoordinate)];

            while (open_set.Count > 0)
            {
                int openSetIndex = 0;
                ChamberCoordinate x = open_set[openSetIndex];
                int currentFScore = f_score[_ChamberToIndex(x)];
                for (int idx = 0; idx < open_set.Count; ++idx)
                {
                    ChamberCoordinate check_x = open_set[idx];
                    int check_currentFScore = f_score[_ChamberToIndex(check_x)];

                    if (check_currentFScore < currentFScore)
                    {
                        openSetIndex = idx;
                        currentFScore = check_currentFScore;
                        x = check_x;
                    }
                }

                /*  
                    if x = goal
                        return reconstruct_path(came_from, came_from[goal])*/
                if (x.Equals(targetCoordinate))
                {
                    List&lt;ChamberCoordinate&gt; FinalPath = new List&lt;ChamberCoordinate&gt;();
                    _ReconstructPath(ref FinalPath, ref came_from, came_from[_ChamberToIndex(targetCoordinate)]);

                    for (int i = 0; i < FinalPath.Count; ++i)
                    {

                        _generatedCave[FinalPath[i].i][FinalPath[i].j] = CaveSpaceType.Floor;
                    }
                    return;
                }

                open_set.RemoveAt(openSetIndex);
                closed_set.Add(x);

                //Neighbor calculation purposely excludes outermost edge of spaces from being potential dig targets
                // i.e. [2,rowCount-2), [2,columbCount-2) instead of [1,rowCount-1), [1,columbCount-1)
                List&lt;ChamberCoordinate&gt; xNeighbors = new List&lt;ChamberCoordinate&gt;();
                if (x.i > 1) xNeighbors.Add(new ChamberCoordinate(x.i - 1, x.j));
                if (x.j > 1) xNeighbors.Add(new ChamberCoordinate(x.i, x.j - 1));
                if (x.i < _rowCount - 2) xNeighbors.Add(new ChamberCoordinate(x.i + 1, x.j));
                if (x.j < _columnCount - 2) xNeighbors.Add(new ChamberCoordinate(x.i, x.j + 1));

                for (int neighborIdx = 0; neighborIdx < xNeighbors.Count; ++neighborIdx)
                {
                    ChamberCoordinate y = xNeighbors[neighborIdx];
                    if( closed_set.Contains(y) )
                        continue;

                    int tentative_g_score = g_score[_ChamberToIndex(x)] + _DistanceBetween(x, y);
                    bool tentative_is_better = false;

                    if (!open_set.Contains(y))
                    {
                        open_set.Add(y);
                        tentative_is_better = true;
                    }
                    else if (tentative_g_score < g_score[_ChamberToIndex(y)])
                    {
                        tentative_is_better = true;
                    }
                    else
                    {
                        tentative_is_better = false;
                    }

                    if (tentative_is_better)
                    {
                        //_generatedCave[x.i][x.j] = CaveSpaceType.Floor;
                        came_from[_ChamberToIndex(y)] = x;
                        g_score[_ChamberToIndex(y)] = tentative_g_score;
                        h_score[_ChamberToIndex(y)] = _HeuristicCostEstimate(y, targetCoordinate);
                        f_score[_ChamberToIndex(y)] = g_score[_ChamberToIndex(y)] + h_score[_ChamberToIndex(y)];
                    }
                }
            }
        }

        void _ReconstructPath(ref List&lt;ChamberCoordinate&gt; finalPath, ref ChamberCoordinate[] cameFrom, ChamberCoordinate currentNode)
        {
            if (cameFrom[_ChamberToIndex(currentNode)].IsSet())
            {
                _ReconstructPath(ref finalPath, ref cameFrom, cameFrom[_ChamberToIndex(currentNode)]);
                finalPath.Add(cameFrom[_ChamberToIndex(currentNode)]);
            }
            finalPath.Add(currentNode);
        }

        int _ChamberToIndex(ChamberCoordinate chamberCoord)
        {
            return chamberCoord.j * _rowCount + chamberCoord.i;
        }

        int _HeuristicCostEstimate(ChamberCoordinate coord1, ChamberCoordinate coord2)
        {
            //Manhattan distance with high cost for walls
            int D = 1;
            if (_generatedCave[coord1.i][coord1.j] == CaveSpaceType.Wall)
            {
                D = 10;
            }

            return D * (Math.Abs(coord1.i - coord2.i) + Math.Abs(coord1.j - coord2.j));
        }

        int _DistanceBetween(ChamberCoordinate coord1, ChamberCoordinate coord2)
        {
            int D = 5;
            return D * (Math.Abs(coord1.i - coord2.i) + Math.Abs(coord1.j - coord2.j));
        }
    }
}
Share this Article:
  • Digg
  • StumbleUpon
  • del.icio.us
  • Facebook
  • Yahoo! Buzz
  • Twitter
  • Google Bookmarks
  • Print

2 thoughts on “Virtual Spelunking: Procedural Cave Generation

  1. Pingback: Virtual Spelunking: Tiles and Shadows | Game Dev Without a Cause

  2. Pingback: Virtual Spelunking: Exits and Treasure | Game Dev Without a Cause

Comments are closed.