Virtual Spelunking: Decorating the Floor


With the basic shape generated and tile rendering logic in place, my procedurally-generated cave is ready to be navigated. Unfortunately, it’s still a little bland since all the wall and floor tiles look the same. Worse still, this means that the player would likely have trouble distinguishing between different areas of the map. What we need is a little bit of visual variety to help give each area of the cave a unique visual signature.

To accomplish this, I decided to start by adding more visual detail to the floor. Of course, I could just randomly pepper the ground with detail tiles, but this would a) look random and b) do nothing to help the player distinguish different areas of the floor from each other. So, I needed a way to create distinct regions of like details on my map. I found a method to do this in a rather sentimentally-named cellular automaton called “Togetherness”.

“Togetherness” is an algorithm described on this page. Just as it’s name suggests, given several iterations, it takes randomly placed cells and brings them closer together with cells of the same type. The rules for “Togetherness” are (quoted from here, see “Togetherness”):

(i) Select an integer q in the range 1 through 7. Cells may be in any of the states 1 through q (represented by q distinct colors) and do not change their state as the system evolves.

(ii) Select a grid size s and an integer n such that 1 <= n <= s (this is the "selection range").

(iii) Select a real-valued "concentration" c (range 0 through 1), which is the probability that a location on the grid is occupied by a cell, then set up the initial state of the system by placing c.s2 cells at random locations on the grid and in random states subject to the condition that there are approximately equal numbers of cells in each of the q states.

(iv) Select an integer m in the range 1 through 9999 (the "lossy move chance").

(v) The system evolves as a succession of "steps", each of which consists of a succession of s2 "substeps".

(vi) A "substep" consists of the following process:
   (a) Select at random a cell which is not surrounded by 8 neighbors all in the same state.

   (b) Among those locations on the grid that are within n units of distance from the cell select one at random (which is not the location of the cell itself). (Distance is measured as the length of a minimal path, in horizontal and vertical steps, along the grid.)

   (c) If there is a cell at that location and either it has the same state as the first or it is surrounded by 8 neighbors all in the same state as that (second) cell then continue with the next substep.

   (d) If there is no cell at that location then calculate the "gain" g, that is, the increase or decrease in the number of neighbors of the cell in the same state as that cell, which would result from moving the cell to that location. If g >= 0 then move the cell to the new location. If g = -1 then make the move with a probability of 1 in m.

   (e) If there is a cell at that location then calculate the combined "gain" g, that is, the net increase or decrease in the number of neighbors of the two cells in the same state as those cells which would result from swapping them. If g >= 0 then swap the cells. If g = -1 or g = -2 then perform the swap with a probability of 1 in m.

   (f) This completes a substep.

These rules are a mouthful but they essentially break down into the following:

  1. Populate a board with cells of a random type
  2. For a number of steps per generation:
    1. Pick a random cell and a random target location
    2. If the swapping the cell to the target location would result in an increase in the number of neighbors sharing the same type, perform the swap
    3. Else, perform a “lossy” move (a move that would decrease the total togetherness of the board) with a certain probability

Applying the above algorithm for about 20 generations turns an array of randomly placed numbers like the one below:

Into an array of much more coherently grouped numbers:

Now that I have an array of well-grouped values, I can use it to modify the visualization of my map floor. Here you can see one of my procedurally-generated caves with the floor detail areas created with “Togetherness”.

By using the floor detail numbers as selectors for different graphical tiles I end up with results like this:

It’s not perfect, but it’s definitely more interesting to look at than a single uniform floor. Of course, the floor detail array doesn’t necessarily have to be used to determine which tiles to render. It could also be used to determine what sort of features to blend-in over the floor: patches of moss or discolored wood, for example.

As always, source code for the interested:

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

namespace ProceduralWorldLib
{
    public class TogethernessAutomoton
    {
        int _rngSeed;
        int _columnCount;
        int _rowCount;
        int _stateCount;
        float _concentration;
        int _lossyMoveChance;
        int _generationCount;
        int _selectionRange;

        public TogethernessAutomoton(int seed, int columns, int rows, int stateCount, float concentration, int lossyMoveChance, int generationCount, int selectionRange)
        {
            _rngSeed = seed;
            _columnCount = columns;
            _rowCount = rows;
            _stateCount = stateCount;
            _concentration = concentration;
            _lossyMoveChance = lossyMoveChance;
            _generationCount = generationCount;
            _selectionRange = selectionRange;

            _CheckInvariants();
        }

        public int DesiredArraySize
        {
            get
            {
                return _columnCount * _rowCount;
            }
        }

        public void FillArray(ref int[] targetArray)
        {
            Debug.Assert(targetArray != null);
            Debug.Assert(targetArray.Length == DesiredArraySize);

            Random rng = new Random(_rngSeed);

            //Fill array with random cells
            for (int i = 0; i < DesiredArraySize; ++i)
            {
                if ((float)rng.NextDouble() <= _concentration)
                {
                    targetArray[i] = rng.Next(_stateCount) + 1;
                }
                else
                {
                    targetArray[i] = 0;
                }
            }

            for (int currentGeneration = 0; currentGeneration < _generationCount; ++currentGeneration)
            {
                List&lt;int&gt; notSurroundedIndexList = new List&lt;int&gt;(targetArray.Length);
                for (int y = 0; y < _rowCount; ++y)
                {
                    for( int x = 0; x < _columnCount; ++x )
                    {
                        if (!_IsSurroundedBySame(targetArray, x, y) && targetArray[_ArrayIndex(x, y)] != 0)
                        {
                            notSurroundedIndexList.Add(_ArrayIndex(x, y));
                        }
                    }
                }

                for (int currentSubStep = 0; currentSubStep < _rowCount * _columnCount; ++currentSubStep)
                {
                    //(a) Select at random a cell which is not surrounded by 8 neighbors all in the same state.
                    int targetIndex = notSurroundedIndexList[rng.Next(notSurroundedIndexList.Count)];

                    //(b) Among those locations on the grid that are within n units of distance from the cell select one at random (which is not the location of the cell itself). (Distance is measured as the length of a minimal path, in horizontal and vertical steps, along the grid.)
                    int swapTargetIndex = _RandomIndexWithinSelectionRange(targetArray, _IndexToX(targetIndex), _IndexToY(targetIndex), rng);

                    //(c) If there is a cell at that location and either it has the same state as the first or it is surrounded by 8 neighbors all in the same state as that (second) cell then continue with the next substep.
                    if( targetArray[swapTargetIndex] == targetArray[targetIndex] || 
                        _IsSurroundedBySame(targetArray, _IndexToX(swapTargetIndex), _IndexToY(swapTargetIndex)))
                    {
                        continue;
                    }
                    
                    //(d) If there is no cell at that location then calculate the "gain" g, that is, the increase or decrease in the number of neighbors of the cell in the same state as that cell, which would result from moving the cell to that location. If g >= 0 then move the cell to the new location. If g = -1 then make the move with a probability of 1 in m.
                    if( targetArray[swapTargetIndex] == 0 )
                    {
                        int currentValue = _SameTypeNeighborCount(targetArray, _IndexToX(targetIndex), _IndexToY(targetIndex), targetArray[targetIndex]);
                        int destinationValue = _SameTypeNeighborCount(targetArray, _IndexToX(swapTargetIndex), _IndexToY(swapTargetIndex), targetArray[targetIndex]);
                        int gainFromMove = destinationValue - currentValue;

                        if( gainFromMove >= 0 )
                        {
                            _SwapValues(targetArray, targetIndex, swapTargetIndex);
                        }
                        else if( gainFromMove == -1 )
                        {
                            if( rng.Next(9999) <= _lossyMoveChance )
                            {
                                _SwapValues(targetArray, targetIndex, swapTargetIndex);
                            }
                        }
                    }
                    
                    //(e) If there is a cell at that location then calculate the combined "gain" g, that is, the net increase or decrease in the number of neighbors of the two cells in the same state as those cells which would result from swapping them. If g >= 0 then swap the cells. If g = -1 or g = -2 then perform the swap with a probability of 1 in m.
                    if( targetArray[swapTargetIndex] != 0 )
                    {
                        int currentValue = _SameTypeNeighborCount(targetArray, _IndexToX(targetIndex), _IndexToY(targetIndex), targetArray[targetIndex]);
                        int destinationValue = _SameTypeNeighborCount(targetArray, _IndexToX(swapTargetIndex), _IndexToY(swapTargetIndex), targetArray[targetIndex]);
                        int gainFromMove1 = destinationValue - currentValue;
                        
                        int currentValue2 = _SameTypeNeighborCount(targetArray, _IndexToX(swapTargetIndex), _IndexToY(swapTargetIndex), targetArray[swapTargetIndex]);
                        int destinationValue2 = _SameTypeNeighborCount(targetArray, _IndexToX(targetIndex), _IndexToY(targetIndex), targetArray[swapTargetIndex]);
                        int gainFromMove2 = destinationValue2 - currentValue2;

                        int netGain = gainFromMove1 + gainFromMove2;
                        if (netGain >= 0)
                        {
                            _SwapValues(targetArray, targetIndex, swapTargetIndex);
                        }
                        else if (netGain == -1 || netGain == -2)
                        {
                            if (rng.Next(9999) <= _lossyMoveChance)
                            {
                                _SwapValues(targetArray, targetIndex, swapTargetIndex);
                            }
                        }
                    }
                }
            }
        }

        private int _IndexToX(int i)
        {
            return i / _rowCount;
        }

        private int _IndexToY(int i)
        {
            return i % _rowCount;
        }

        private int _ArrayIndex(int x, int y)
        {
            return x * _rowCount + y;
        }

        private void _SwapValues(int[] targetArray, int index1, int index2)
        {
            int backup = targetArray[index1];
            targetArray[index1] = targetArray[index2];
            targetArray[index2] = backup;
        }

        private int _SameTypeNeighborCount(int[] targetArray, int x, int y, int currentTileValue)
        {
            int neighborCount = 0;
            if (x > 0 && y > 0 && targetArray[_ArrayIndex(x - 1, y - 1)] == currentTileValue) ++neighborCount;
            if (y > 0 && targetArray[_ArrayIndex(x, y - 1)] == currentTileValue) ++neighborCount;
            if (x < _columnCount - 1 && y > 0 && targetArray[_ArrayIndex(x + 1, y - 1)] == currentTileValue) ++neighborCount;

            if (x > 0 && targetArray[_ArrayIndex(x - 1, y)] == currentTileValue) ++neighborCount;
            if (x < _columnCount - 1 && targetArray[_ArrayIndex(x + 1, y)] == currentTileValue) ++neighborCount;

            if (x > 0 && y < _rowCount - 1 && targetArray[_ArrayIndex(x - 1, y + 1)] == currentTileValue) ++neighborCount;
            if (y < _rowCount - 1 && targetArray[_ArrayIndex(x, y + 1)] == currentTileValue) ++neighborCount;
            if (x < _columnCount - 1 && y < _rowCount - 1 && targetArray[_ArrayIndex(x + 1, y + 1)] == currentTileValue) ++neighborCount;

            return neighborCount;
        }

        private bool _IsSurroundedBySame(int[] targetArray, int x, int y)
        {
            if (x == 0 || x == _columnCount - 1 ||
                y == 0 || y == _rowCount - 1)
            {
                return false;
            }

            int currentTileValue = targetArray[_ArrayIndex(x, y)];
            if (currentTileValue == 0)
            {
                return false;
            }

            return _SameTypeNeighborCount(targetArray, x, y, currentTileValue) >= 8;
        }

        private int _DistanceBetween(int x, int y, int x2, int y2)
        {
            return Math.Abs(x - x2) + Math.Abs(y - y2);
        }

        private int _RandomIndexWithinSelectionRange(int[] targetArray, int baseX, int baseY, Random rng)
        {
            List&lt;int&gt; indexesWithinRange = new List&lt;int&gt;(targetArray.Length);
            for (int y = 0; y < _rowCount; ++y)
            {
                for (int x = 0; x < _columnCount; ++x)
                {
                    if (_DistanceBetween(baseX, baseY, x, y) <= _selectionRange)
                    {
                        indexesWithinRange.Add(_ArrayIndex(x, y));
                    }
                }
            }

            return indexesWithinRange[rng.Next(indexesWithinRange.Count)];
        }

        private void _CheckInvariants()
        {
            Debug.Assert(_columnCount >= 1 && _rowCount >= 1);
            Debug.Assert(_stateCount >= 1 && _stateCount < (_columnCount * _rowCount));
            Debug.Assert(_concentration >= 0.0f && _concentration <= 1.0f);
            Debug.Assert(_lossyMoveChance >= 1 && _lossyMoveChance <= 9999);
            Debug.Assert(_generationCount >= 0);
        }
    }
}

Share this Article:
  • Digg
  • StumbleUpon
  • del.icio.us
  • Facebook
  • Yahoo! Buzz
  • Twitter
  • Google Bookmarks
  • Print

One thought on “Virtual Spelunking: Decorating the Floor

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

Comments are closed.