For the interested, here’s the code for generating the heightmap and cloud textures:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace ProceduralWorldLib
{
    public class HeightfieldGenerator
    {
        public static float[] GenerateHeightfield(int randomSeed, int sideLength)       //Side length must be POW2
        {
            Random rng = new Random(randomSeed);
            float[] heightField;
            AlgorithmHelper.GeneratePlasma(out heightField, sideLength, rng, 0.5f, 0.75f);

            return heightField;
        }

        public static Texture2D GeneratePlasmaCloud(GraphicsDevice graphics, int randomSeed, int sideLength)
        {
            Random rng = new Random(randomSeed);
            float[] heightField;
            AlgorithmHelper.GeneratePlasma(out heightField, sideLength, rng, 0.5f, 0.75f);

            Texture2D sampleTexture = new Texture2D(graphics, sideLength, sideLength);
            Color[] colorData = new Color[sideLength * sideLength];
            for (int x = 0; x < sideLength; ++x)
            {
                for (int y = 0; y < sideLength; ++y)
                {
                    float genVal = Math.Min(Math.Max(heightField[sideLength * y + x], 0.0f), 1.0f);
                    colorData[y * sideLength + x] = new Color(genVal, genVal, genVal, genVal);
                }
            }
            sampleTexture.SetData<Color>(colorData);

            return sampleTexture;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;

namespace ProceduralWorldLib
{
    public static class AlgorithmHelper
    {
        public static void GeneratePlasma(out float[] plasmaArray, int plasmaSideLength, Random rng, float plasmaSeedValue, float plasmaPerturbation)
        {
            plasmaArray = new float[(plasmaSideLength + 1) * (plasmaSideLength + 1)];

            plasmaArray[plasmaIndex(0, 0, plasmaSideLength)] = plasmaSeedValue;     //0,0
            plasmaArray[plasmaIndex(plasmaSideLength, 0, plasmaSideLength)] = plasmaSeedValue;     //MAX,0
            plasmaArray[plasmaIndex(0, plasmaSideLength, plasmaSideLength)] = plasmaSeedValue;     //0,MAX
            plasmaArray[plasmaIndex(plasmaSideLength, plasmaSideLength, plasmaSideLength)] = plasmaSeedValue;     //MAX,MAX

            float h = plasmaPerturbation;

            int currentSideLength = plasmaSideLength;
            while (currentSideLength >= 2)
            {
                int halfSideLength = currentSideLength / 2;
                for (int x = 0; x < plasmaSideLength; x += currentSideLength)
                {
                    for (int y = 0; y < plasmaSideLength; y += currentSideLength)
                    {
                        float average = plasmaArray[plasmaIndex(x, y, plasmaSideLength)]; //top left
                        average += plasmaArray[plasmaIndex(x + currentSideLength, y, plasmaSideLength)]; //top right
                        average += plasmaArray[plasmaIndex(x, y + currentSideLength, plasmaSideLength)]; //bottom left
                        average += plasmaArray[plasmaIndex(x + currentSideLength, y + currentSideLength, plasmaSideLength)]; //bottom right
                        average *= 0.25f;

                        plasmaArray[plasmaIndex(x + halfSideLength, y + halfSideLength, plasmaSideLength)] = average + (float)(rng.NextDouble() * 2.0) * h - h;
                    }
                }


                for (int x = 0; x < plasmaSideLength; x += halfSideLength)
                {
                    for (int y = (x + halfSideLength) % currentSideLength; y < plasmaSideLength; y += currentSideLength)
                    {
                        float average = plasmaArray[plasmaIndex((x - halfSideLength + (plasmaSideLength)) % (plasmaSideLength), y, plasmaSideLength)]; //left of center
                        average += plasmaArray[plasmaIndex((x + halfSideLength) % (plasmaSideLength), y, plasmaSideLength)]; //right of center
                        average += plasmaArray[plasmaIndex(x, (y + halfSideLength) % (plasmaSideLength), plasmaSideLength)]; //below center
                        average += plasmaArray[plasmaIndex(x, (y - halfSideLength + (plasmaSideLength)) % (plasmaSideLength), plasmaSideLength)]; //above center
                        average *= 0.25f;

                        plasmaArray[plasmaIndex(x, y, plasmaSideLength)] = average + (float)(rng.NextDouble() * 2.0) * h - h;

                        if (x == 0) plasmaArray[plasmaIndex(plasmaSideLength, y, plasmaSideLength)] = average;
                        if (y == 0) plasmaArray[plasmaIndex(x, plasmaSideLength, plasmaSideLength)] = average;
                    }
                }

                currentSideLength *= 0.5f;
                h *= 0.5f;
            }
        }

        static int plasmaIndex(int x, int y, int plasmaSideLength)
        {
            return (plasmaSideLength + 1) * y + x;
        }
    }
}

In this week’s post, I apply this concept by using a fractal generation function to add varying patterns of darkness to my floor tiles. By doing this, I can create an arbitrary number of texture variations for my floor tiles each representing different patterns of random wear-and-tear. With a decent number of variations, it becomes very unlikely for two neighboring floor tiles to look exactly the same which greatly reduces the unrelenting visual regularity you get from seeing the same tile rendered over and over again.

In order to create my floor texture variations, I take my PlanetCute floor texture:

And multiply it in a shader with a plasma fractal like this one:

By programmatically generating random plasma fractals, combining them with the floor tile, and rendering them to a texture, I can create sprite textures that the rest of my engine can use just like any other pre-authored texture.

In XNA, creating a texture at runtime is a simple matter of creating a texture render target and temporarily directing your render commands there instead of to the screen:

for (int i = 0; i < variationCount; ++i)
{
    RenderTarget2D renderTarget = new RenderTarget2D(_graphics, baseTexture.Width, baseTexture.Height);
    
    //_graphics is a reference to Game.GraphicDevice        
    _graphics.Textures[1] = _getMyFractal();

    _graphics.SetRenderTarget(renderTarget);
    _graphics.Clear(Color.Transparent);

    //_renderEffect is an Effect instance that I loaded with a custom shader (.fx) file
    spriteBatch.Begin(0, null, null, null, null, _renderEffect);
    spriteBatch.Draw(baseTexture, Vector2.Zero, Color.White);
    spriteBatch.End();

    textureArray[i] = renderTarget;
}
//Setting RenderTarget to null retargets rendering back to the screen
_graphics.SetRenderTarget(null);

The shader I use to combine the two textures is about as simple as they come, a simple multiplication of the RGB from the second texture onto the first:

sampler TextureSampler : register(s0);
sampler DetailTextureSampler : register(s1);

float4 main(float4 color : COLOR0, float2 texCoord : TEXCOORD0) : COLOR0
{
    // Look up the texture color.
    float4 tex = tex2D(TextureSampler, texCoord);
    float4 detTex = tex2D(DetailTextureSampler, texCoord);
    
    tex.rgb *= detTex.rgb;
	
    return tex;
}

technique Desaturate
{
    pass Pass1
    {
        PixelShader = compile ps_2_0 main();
    }
}

With my texture rendering code in place, it’s just a matter of finding an algorithm for creating my plasma fractal textures. As usual, Wikipedia provides a convenient solution for this with the
Diamond-Square Algorithm. This algorithm generates a height field of values dividing a texture into smaller and smaller squares, generating values for points by averaging the corners of their containing squares (and diamonds). This page at GameProgrammer.com does a good job of describing the algorithm steps:

The diamond step: Taking a square of four points, generate a random value at the square midpoint, where the two diagonals meet. The midpoint value is calculated by averaging the four corner values, plus a random amount. This gives you diamonds when you have multiple squares arranged in a grid.

The square step: Taking each diamond of four points, generate a random value at the center of the diamond. Calculate the midpoint value by averaging the corner values, plus a random amount generated in the same range as used for the diamond step. This gives you squares again.

And the usage of said steps:

While the length of the side of the squares is greater than zero
{
   Pass through the array and perform the diamond step for each square present.
   Pass through the array and perform the square step for each diamond present.
   Reduce the random number range.
}

If you’re like me and sometimes find code easier to understand than pseudo-code, this answer at Stack Overflow provides Java code implementing the algorithm.

Once I have an implementation of the diamond-square algorithm working in C#, I’m able to create a buffer of Color data that I can apply to a Texture2D using SetData(). Then I can use the resulting texture in the rendering code I presented above to create my floor texture variations.

With my floor texture variations ready, I randomly assign them to floor tiles and turn this:

Into this:

To many it’s a subtle difference perhaps, but the increased visual irregularity in the floor goes a long way to reduce the sense of repetition in the dungeon. It’s a nice touch if we expect our players to spend a significant amount of time in our dungeons (which we do!)

For reference, I’ve included my texture and fractal rendering code below:

//************* TextureCreator.cs *********************
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace ProceduralWorldLib
{
    public class TextureCreator
    {
        protected GraphicsDevice _graphics;
        List<Texture2D> _textureSamples;
        protected Effect _renderEffect;

        public TextureCreator(GraphicsDevice graphicDevice, Effect renderEffect)
        {
            _graphics = graphicDevice;
            _textureSamples = new List<Texture2D>();
            _renderEffect = renderEffect;
            Debug.Assert(_renderEffect != null);
        }

        public void AddSampleTexture(Texture2D texture)
        {
            Debug.Assert(texture != null);
            _textureSamples.Add(texture);
        }

        public virtual Texture2D[] GenerateTextureArray()
        {
            Texture2D baseTexture = _textureSamples[0];
            int variationCount = _textureSamples.Count - 1;
            
            SpriteBatch spriteBatch = new SpriteBatch(_graphics);

            Texture2D[] textureArray = new Texture2D[variationCount];

            for (int i = 0; i < variationCount; ++i)
            {
                RenderTarget2D renderTarget = new RenderTarget2D(_graphics, baseTexture.Width, baseTexture.Height);
            
                _graphics.Textures[1] = _textureSamples[i + 1];

                _graphics.SetRenderTarget(renderTarget);
                _graphics.Clear(Color.Transparent);

                spriteBatch.Begin(0, null, null, null, null, _renderEffect);
                spriteBatch.Draw(baseTexture, Vector2.Zero, Color.White);
                spriteBatch.End();

                textureArray[i] = renderTarget;
            }
            _graphics.SetRenderTarget(null);

            return textureArray;
        }
    }
}

//************* PlasmaVariationCreator.cs *********************
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace ProceduralWorldLib
{
    public class PlasmaVariationCreator : TextureCreator
    {
        Texture2D _baseTexture;
        int _variationCount;
        int _rngSeed;

        float[] _plasmaArray;
        const int PLASMA_DIMENSION_SIZE = 64;

        public PlasmaVariationCreator(Game game, int variationCount, int rngSeed) :
            base(game.GraphicsDevice, game.Content.Load<Effect>("Shader/TextureGen"))
        {
            _variationCount = variationCount;
            _rngSeed = rngSeed;
        }

        public void SetBaseTexture(Texture2D baseTexture)
        {
            _baseTexture = baseTexture;
        }

        public Texture2D[] GenerateTextureArrayWithBase(Texture2D baseTexture)
        {
            SetBaseTexture(baseTexture);
            return GenerateTextureArray();
        }

        public override Texture2D[] GenerateTextureArray()
        {
            Debug.Assert(_baseTexture != null);

            Texture2D[] textureArray = new Texture2D[_variationCount];
            
            Random rng = new Random(_rngSeed);
            
            SpriteBatch spriteBatch = new SpriteBatch(_graphics);
            for (int i = 0; i < textureArray.Length; ++i)
            {
                _GeneratePlasmaArray();

                Texture2D sampleTexture = new Texture2D(_graphics, PLASMA_DIMENSION_SIZE, PLASMA_DIMENSION_SIZE);
                Color[] colorData = new Color[PLASMA_DIMENSION_SIZE * PLASMA_DIMENSION_SIZE];
                for (int x = 0; x < PLASMA_DIMENSION_SIZE; ++x)
                {
                    for (int y = 0; y < PLASMA_DIMENSION_SIZE; ++y)
                    {
                        float genVal = Math.Min(Math.Max(_GetPlasmaValue(rng, x, y), 0.0f), 1.0f);
                        colorData[y * PLASMA_DIMENSION_SIZE + x] = new Color(genVal, genVal, genVal, 1.0f);
                    }
                }
                sampleTexture.SetData<Color>(colorData);

                RenderTarget2D renderTarget = new RenderTarget2D(_graphics, _baseTexture.Width, _baseTexture.Height);

                _graphics.Textures[1] = sampleTexture;

                _graphics.SetRenderTarget(renderTarget);
                _graphics.Clear(Color.Transparent);

                spriteBatch.Begin(0, null, null, null, null, _renderEffect);
                spriteBatch.Draw(_baseTexture, Vector2.Zero, Color.White);
                spriteBatch.End();

                textureArray[i] = renderTarget;
            }
            _graphics.SetRenderTarget(null);

            return textureArray;
        }

        float _GetPlasmaValue(Random rng, int x, int y)
        {
            return 1.0f - _plasmaArray[plasmaIndex(x, y)] * 0.5f;
        }

        void _GeneratePlasmaArray()
        {
            const float INITIAL_SEED = 0.5f;

            _plasmaArray = new float[(PLASMA_DIMENSION_SIZE + 1) * (PLASMA_DIMENSION_SIZE + 1)];

            _plasmaArray[plasmaIndex(0,0)] = INITIAL_SEED;     //0,0
            _plasmaArray[plasmaIndex(PLASMA_DIMENSION_SIZE, 0)] = INITIAL_SEED;     //MAX,0
            _plasmaArray[plasmaIndex(0, PLASMA_DIMENSION_SIZE)] = INITIAL_SEED;     //0,MAX
            _plasmaArray[plasmaIndex(PLASMA_DIMENSION_SIZE, PLASMA_DIMENSION_SIZE)] = INITIAL_SEED;     //MAX,MAX
            
            Random rng = new Random();
            float h = 0.25f;

            int currentSideLength = PLASMA_DIMENSION_SIZE;
            while (currentSideLength >= 2)
            {
                int halfSideLength = currentSideLength / 2;
                for (int x = 0; x < PLASMA_DIMENSION_SIZE; x+= currentSideLength)
                {
                    for (int y = 0; y < PLASMA_DIMENSION_SIZE; y += currentSideLength)
                    {
                        float average = _plasmaArray[plasmaIndex(x, y)]; //top left
                        average += _plasmaArray[plasmaIndex(x + currentSideLength, y)]; //top right
                        average += _plasmaArray[plasmaIndex(x, y + currentSideLength)]; //bottom left
                        average += _plasmaArray[plasmaIndex(x + currentSideLength, y + currentSideLength)]; //bottom right
                        average *= 0.25f;

                        _plasmaArray[plasmaIndex(x + halfSideLength, y + halfSideLength)] = average + (float)(rng.NextDouble() * 2.0) * h - h;                        
                    }
                }

                for (int x = 0; x < PLASMA_DIMENSION_SIZE; x += halfSideLength)
                {
                    for (int y = (x + halfSideLength) % currentSideLength; y < PLASMA_DIMENSION_SIZE; y += currentSideLength)
                    {
                        float average = _plasmaArray[plasmaIndex((x - halfSideLength + (PLASMA_DIMENSION_SIZE )) % (PLASMA_DIMENSION_SIZE), y)]; //left of center
                        average += _plasmaArray[plasmaIndex((x + halfSideLength) % (PLASMA_DIMENSION_SIZE), y)]; //right of center
                        average += _plasmaArray[plasmaIndex(x, (y + halfSideLength) % (PLASMA_DIMENSION_SIZE))]; //below center
                        average += _plasmaArray[plasmaIndex(x, (y - halfSideLength + (PLASMA_DIMENSION_SIZE)) % (PLASMA_DIMENSION_SIZE))]; //above center
                        average *= 0.25f;

                        _plasmaArray[plasmaIndex(x, y)] = average + (float)(rng.NextDouble() * 2.0) * h - h;

                        if(x == 0)  _plasmaArray[plasmaIndex(PLASMA_DIMENSION_SIZE, y)] = average;
                        if(y == 0)  _plasmaArray[plasmaIndex(x, PLASMA_DIMENSION_SIZE)] = average;
                    }
                }
                currentSideLength *= 0.5F;
                h *= 0.5f;
            }                                        
        }

        int plasmaIndex(int x, int y)
        {
            return (PLASMA_DIMENSION_SIZE + 1) * y + x;
        }
    }    
}

I’ve spent several posts detailing how to procedurally generate a cave for a player to explore. Now, it’s about time for me to fill that cave with things for the player to do. The most basic goal for any player dropped into the middle of a cave is to find a way out, so the first thing I’ll do is drop a starting point and an exit point into the cave. Just trying to escape a cave by itself is a little too sparse though, so I’ll also add treasure for the player to find and collect while they’re looking for the exit. Now, it’s starting to sound like a real game.

Placing the player starting point and exit is a straight-forward process. The primary case I want to avoid is placing the starting point and exit too close together. After all, I spent all this time generating a cave, I want the player to have to go through it!

In order to accomplish this, I simply place the player starting point and the dungeon exit on opposite ends of the map. For the starting point, I scan each column from the left and randomly pick a floor space from the first column that isn’t all wall onto which to drop the player start point. I then repeat the process from the right side of the map scanning left and drop the exit on a random floor space in the first available column. For maps that are taller than they are wide, I do the same thing only scanning from the top for starting point placement and from the bottom for exit placement.

For treasure placement, I’m still looking for a solution that I like. For now though, I use the Togetherness algorithm I used for floor decoration. This time around, I use just two states for togetherness (0 – no treasure, 1 – treasure) and a significantly lower chance of any given square being non-empty (5% as opposed to the 40% chance for any-given floor space to be something other than gray tile.) After a bit of parameter tweaking, I get a satisfactory dispersal of treasure. (In the picture below, ‘T’ marks the spot.)

Now, with a bit of simple collision code and those nice treasure chest graphics from the PlanetCute tileset I can make my cave a more lucrative place to explore.

You can find my (decidedly unsophisticated) code for placing starting point and exit points below:

void _PlaceStartAndEndPoints(Random rng)
{
    int maxColumn = _mapToPopulate[0].Count;
    int maxRow = _mapToPopulate.Count;
    bool bVerticalMap = maxRow > maxColumn;

    //Add player start to space on furthest left column / top row
    if (!bVerticalMap)
    {
        for (int currColumn = 0; currColumn < maxColumn; ++currColumn)
        {
            List&lt;int&gt; floorsInCol = new List&lt;int&gt;();
            for (int currRow = 0; currRow < maxRow; ++currRow)
            {
                if (_mapToPopulate[currRow][currColumn].SpaceType == CaveSpaceType.Floor)
                {
                    floorsInCol.Add(currRow);
                }
            }

            if (floorsInCol.Count > 0)
            {
                _mapInhabitants.Add(new MapInhabitant(InhabitantType.StartingPoint, currColumn, floorsInCol[rng.Next(floorsInCol.Count)]));
                break;
            }
        }
    }
    else
    {
        for (int currRow = 0; currRow < maxRow; ++currRow)
        {
            List&lt;int&gt; floorsInRow = new List&lt;int&gt;();
            for (int currColumn = 0; currColumn < maxColumn; ++currColumn)
            {
                if (_mapToPopulate[currRow][currColumn].SpaceType == CaveSpaceType.Floor)
                {
                    floorsInRow.Add(currColumn);
                }
            }

            if (floorsInRow.Count > 0)
            {
                _mapInhabitants.Add(new MapInhabitant(InhabitantType.StartingPoint, floorsInRow[rng.Next(floorsInRow.Count)], currRow));
                break;
            }
        }
    }

    //Add end point to space on furthest right column / bottom row
    if (!bVerticalMap)
    {
        for (int currColumn = maxColumn - 1; currColumn >= 0; --currColumn)
        {
            List&lt;int&gt; floorsInCol = new List&lt;int&gt;();
            for (int currRow = 0; currRow < maxRow; ++currRow)
            {
                if (_mapToPopulate[currRow][currColumn].SpaceType == CaveSpaceType.Floor)
                {
                    floorsInCol.Add(currRow);
                }
            }

            if (floorsInCol.Count > 0)
            {
                _mapInhabitants.Add(new MapInhabitant(InhabitantType.EndingPoint, currColumn, floorsInCol[rng.Next(floorsInCol.Count)]));
                break;
            }
        }
    }
    else
    {
        for (int currRow = maxRow - 1; currRow >= 0; --currRow)
        {
            List&lt;int&gt; floorsInRow = new List&lt;int&gt;();
            for (int currColumn = 0; currColumn < maxColumn; ++currColumn)
            {
                if (_mapToPopulate[currRow][currColumn].SpaceType == CaveSpaceType.Floor)
                {
                    floorsInRow.Add(currColumn);
                }
            }

            if (floorsInRow.Count > 0)
            {
                _mapInhabitants.Add(new MapInhabitant(InhabitantType.EndingPoint, floorsInRow[rng.Next(floorsInRow.Count)], currRow));
                break;
            }
        }
    }
}

And the treasure placement code:
(You can find my Togetherness implementation here)

void _PlaceTreasure(Random rng)
{
    //Working but not satisfactory, trying Browninan walk?

    TogethernessAutomoton togetherArray = new TogethernessAutomoton(_randomSeed, _mapToPopulate[0].Count, _mapToPopulate.Count, 1, _treasureDensity, 1000, 6, 12);
    int[] resultArray = new int[togetherArray.DesiredArraySize];
    togetherArray.FillArray(ref resultArray);

    int startPointCol = -1, startPointRow = -1;
    int endPointCol = -1, endPointRow = -1;

    foreach (MapInhabitant inhabitant in _mapInhabitants)
    {
        switch (inhabitant.InhabitantType)
        {
            case InhabitantType.StartingPoint:
                startPointCol = inhabitant.Column;
                startPointRow = inhabitant.Row;
                break;
            case InhabitantType.EndingPoint:
                endPointCol = inhabitant.Column;
                endPointRow = inhabitant.Row;
                break;
        }
    }

    for (int rowIdx = 0; rowIdx < _mapToPopulate.Count; ++rowIdx)
    {
        for (int colIdx = 0; colIdx < _mapToPopulate[rowIdx].Count; ++colIdx)
        {
            if (_mapToPopulate[rowIdx][colIdx].SpaceType == CaveSpaceType.Floor)
            {
                if ( (colIdx == startPointCol && rowIdx == startPointRow) ||
                    (colIdx == endPointCol && rowIdx == endPointRow) )
                {
                    continue;
                }

                if (resultArray[colIdx * _mapToPopulate.Count + rowIdx] == 1)
                {
                    _mapInhabitants.Add(new MapInhabitant(InhabitantType.Treasure, colIdx, rowIdx));
                }
            }
        }
    }
}

In order to lay out the lights, I need to come up with rules for their placement that will produce results that are neither too regular nor too random. Since I’m planning on eventually rendering the lights as wall-mounted torches, I need to make sure the lights are located on cave walls and not lying some place in the middle of the floor. I also need to make sure that the lights I place are on walls neighboring floor tiles, otherwise I might end up with lights buried inside large wall sections.

With that in mind, I come up with the following rules for light placement:

1. Divide the cave into multiple subsections
2. Place a light on a random floor space in each subsection (if there is open floor available in that section)
3. Move the light in an approximation of an Archimedes’ Spiral until it hits a wall

By controlling the number of subsections, I can control the density of lights in my map as well as making sure that lights are relatively evenly distributed around my map. Moving each light around in a spiral allows me to attach the light source to a wall without running the risk of shooting a light down a long hallway which might have happened had I used straight movement.

Dividing my map into subsections is relatively trivial, I simple iterate over a number of spaces equal to column or row count divided by my desired number of subsections. At each subsection, I create a list of floor spaces and randomly assign one of those spaces to contain a light. Using my test map and a subsection count of 8, I end up with the following result.

With all my lights spawned on the floor, I just move spirally them and attach them to the first wall space they hit. To accomplish this, I use the spiral rasterizer described here. Instead of generating a full spiral path, I stop at the first wall space encountered by the spiral algorithm and change my current light’s position to that space. Running the algorithm over the data rearranges the lights like so:

Now that I have the positions of my lights figured out, I just need to render them. The specific rendering technique can vary by game, of course, but this time around I wanted to get a bit of pixel shader experience under my belt. So, for my lights, I picked an arbitrary size and a torch-like orange color for my lights. Then, by feeding the positions of any on-screen lights into my pixel shader, I can tint every pixel with an amount of a light’s color based on the pixel’s distance from that light. Combined with the tile-rendered cave from my previous posts, I get an effect like this:

Atmospheric!

For reference, I’ve included the the most salient code below. Here is the placement code for the lights:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;

namespace ProceduralWorldLib
{
    public enum InhabitantType
    {
        Unknown,
        Light
    }

    public class MapInhabitant
    {
        public InhabitantType InhabitantType;
        public int Column;
        public int Row;

        public MapInhabitant(InhabitantType inhabitantType, int column, int row)
        {
            InhabitantType = inhabitantType;
            Column = column;
            Row = row;
        }
    }

    public class MapPopulator
    {
        private List<MapInhabitant> _mapInhabitants;
        private List<List<CaveSpaceInfo>> _mapToPopulate;
        private int _randomSeed;

        public MapPopulator(int randomSeed)
        {
            _mapInhabitants = new List<MapInhabitant>();
            _randomSeed = randomSeed;
        }

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

        public List<List<CaveSpaceInfo>> MapToPoplulate
        {
            set
            {
                _mapToPopulate = value;
            }
        }

        public List<MapInhabitant> MapInhabitants
        {
            get
            {
                return _mapInhabitants;
            }
        }

        public void PopulateMap()
        {
            Random rng = new Random(_randomSeed);
            int segmentCount = 8;

            _mapInhabitants.Clear();

            int longestDimension = _mapToPopulate.Count;
            if (_mapToPopulate[0].Count > longestDimension)
            {
                longestDimension = _mapToPopulate[0].Count;
            }

            int entriesPerSegment = 0;
            entriesPerSegment = longestDimension / segmentCount;

            for (int segmentRow = 0; segmentRow < segmentCount; ++segmentRow)
            {
                for (int segmentColumn = 0; segmentColumn < segmentCount; ++segmentColumn)
                {
                    int minRow = segmentRow * entriesPerSegment;
                    int maxRow = (segmentRow + 1) * entriesPerSegment;
                    int minCol = segmentColumn * entriesPerSegment;
                    int maxCol = (segmentColumn + 1) * entriesPerSegment;

                    List&lt;Vector2&gt; floorSpacesInSegment = new List&lt;Vector2&gt;();
                    for (int currRow = minRow; currRow < maxRow && currRow < _mapToPopulate.Count; ++currRow)
                    {
                        for (int currCol = minCol; currCol < maxCol && currCol < _mapToPopulate[currRow].Count; ++currCol)
                        {
                            if (_mapToPopulate[currRow][currCol].SpaceType == CaveSpaceType.Floor)
                            {
                                floorSpacesInSegment.Add(new Vector2(currCol, currRow));
                            }
                        }
                    }

                    if (floorSpacesInSegment.Count > 0)
                    {
                        Vector2 selectedFloorSpace = _SpiralIntoWall(
                            floorSpacesInSegment[rng.Next(floorSpacesInSegment.Count)],
                            new Vector2(minCol, minRow),
                            new Vector2(maxCol, maxRow));
                        _mapInhabitants.Add(new MapInhabitant(InhabitantType.Light, (int)selectedFloorSpace.X, (int)selectedFloorSpace.Y));
                    }
                }
            }
        }

        Vector2 _SpiralIntoWall(Vector2 startingPoint, Vector2 upperLeft, Vector2 lowerRight)
        {
            // Distance between spiral loops (1 space)
            float alpha = 1.0f / (float)Math.Sqrt(2.0f);

            // Distance along spiral at each step
            float omega = alpha;

            //Starting theta
            float theta = 0.0f;

            // Find which corner is farthest from the spiral focus
            Vector2[] corners = new Vector2[4];
            corners[0] = upperLeft;
            corners[1] = new Vector2(lowerRight.X, upperLeft.Y);    //Upper Right
            corners[2] = lowerRight;
            corners[3] = new Vector2(upperLeft.X, lowerRight.Y);    //Lower Left
            float currDistance = 0.0f;
            int farthestCornerIndex = -1;
            for (int i = 0; i < corners.Length; ++i)
            {
                float distToCorner = 0.0f;
                Vector2.Distance(ref corners[i], ref startingPoint, out distToCorner);
                if (distToCorner > currDistance)
                {
                    currDistance = distToCorner;
                    farthestCornerIndex = i;
                }
            }
            Vector2 farthestCorner = corners[farthestCornerIndex];

            bool bHitWall = false;
            Vector2 currPoint = startingPoint;
            while (currPoint != farthestCorner)
            {
                //Update the step in angle based on current angle etc.
                float newDelta = _ThetaDelta(alpha, theta, omega);
                theta += newDelta;

                //Calculate the next coordinates
                currPoint = startingPoint + _SpiralCoordinate(theta, alpha);

                //If these coordinates lie within the defined rectangle
                if (currPoint.X >= upperLeft.X && currPoint.Y >= upperLeft.Y &&
                    currPoint.X <= lowerRight.X && currPoint.Y <= lowerRight.Y)
                {
                    //Stop if we hit a wall
                    if (_mapToPopulate[(int)currPoint.Y][(int)currPoint.X].SpaceType == CaveSpaceType.Wall)
                    {
                        bHitWall = true;
                        break;
                    }
                }
            }

            return bHitWall ? currPoint : startingPoint;
        }

        float _ThetaDelta(float alpha, float theta, float omega )
        {
            return (float)((2.0f * Math.PI * omega) / Math.Sqrt( Math.Pow( alpha, 2 ) * (1 + Math.Pow( theta, 2 ) ) ));
        }

        Vector2 _SpiralCoordinate(float theta, float alpha)
        {
            return new Vector2(
                    (int)Math.Round(alpha * theta * Math.Cos(theta) / (2 * Math.PI) ),
                    (int)Math.Round(alpha * theta * Math.Sin(theta) / (2 * Math.PI) )
                );
        } 
    }
}

Also, rendering code:

private void _SetLightParams(Vector2 cameraTransform)
{
	_renderEffect.Parameters["AmbientLightColor"].SetValue(Vector3.One * 0.045f);
        
	int lightIndex = 0;
	foreach(LightInfo light in _lights)
	{	
		Vector2 renderPos = light.Position * _drawScale + cameraTransform;
		float lightSize = light.Size * _drawScale;
		Vector2 sizeVector = Vector2.One * lightSize;
		Vector2 upperLeftExtent = renderPos - sizeVector;
		Vector2 lowerRightExtent = renderPos + sizeVector;

		bool bCull = false;
		bCull = (lowerRightExtent.X < 0.0f || lowerRightExtent.Y < 0.0f);
		bCull |= (upperLeftExtent.X > Game.GraphicsDevice.PresentationParameters.BackBufferWidth || upperLeftExtent.Y > Game.GraphicsDevice.PresentationParameters.BackBufferHeight);

		if( !bCull && lightIndex < MAX_LIGHT_COUNT )	
		{	
			_renderEffect.Parameters["LightPosition"].Elements[lightIndex].SetValue(renderPos);
			_renderEffect.Parameters["LightSizeInverse"].Elements[lightIndex].SetValue(1 / lightSize);
			_renderEffect.Parameters["LightColor"].Elements[lightIndex].SetValue(light.Color);
			lightIndex++;
		}
	}
	_renderEffect.Parameters["LightCount"].SetValue(lightIndex);
}

And finally, the light pixel shader:

// Based on the Sprite Effects sample at http://create.msdn.com/en-US/education/catalog/sample/sprite_effects

sampler TextureSampler : register(s0);
float Saturation;

float3 AmbientLightColor;
int LightCount;
float2 LightPosition[8];
float LightSizeInverse[8];
float3 LightColor[8];

float4x4 MatrixTransform : register(vs, c0);

void SpriteVS(inout float4 color    : COLOR0, 
                        inout float2 texCoord : TEXCOORD0, 
                        inout float4 position : SV_Position) 
{ 
    position = mul(position, MatrixTransform); 
} 

float4 main(float2 screenPos : VPOS, float4 color : COLOR0, float2 texCoord : TEXCOORD0) : COLOR0
{
	// Look up the texture color.
    float4 tex = tex2D(TextureSampler, texCoord);
    
    // Convert it to greyscale. The constants 0.3, 0.59, and 0.11 are because
    // the human eye is more sensitive to green light, and less to blue.
    float greyscale = dot(tex.rgb, float3(0.3, 0.59, 0.11));

	float3 lightPower = AmbientLightColor;
	for(int i=0; i < LightCount; i++)
	{
		float distance = length(screenPos - LightPosition[i]);
		lightPower += clamp(1.0f - (distance * LightSizeInverse[i]), 0.0f, 1.0f) * LightColor[i];
	}
	tex.rgb = lerp(greyscale, tex.rgb, Saturation) * lightPower;

    return tex;
}


technique Desaturate
{
    pass Pass1
    {
		VertexShader = compile vs_3_0 SpriteVS();
        PixelShader = compile ps_3_0 main();
    }
}

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.s² 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 s² "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);
        }
    }
}

For my cave tile rendering implementation, I decided to use some of the best, free graphic resources available on the web: Danc’s Miraculously Flexible Game Prototyping Tiles. In addition to being attractive, this tileset is also very easy to use because each tile is a self-contained piece. With the exception of shadows (which I will cover later), tiles don’t affect each other visually so you don’t need to change which tile you draw based on its neighbors. Because you can treat each tile as a self-contained piece it’s very easy to map a tile to the floor and wall spaces created by the procedural cave generator and end up with something like this:

Adding a vertical offset to the wall tiles to raise them by about 36 pixels makes them actually look like walls:

Not a bad start, but the map still feels flat. This is where the shadow tiles in prototyping tile kit come into play. Danc has lamented that people using his prototyping tiles often don’t take advantage of the shadow tiles he provides. He has a very good reason for feeling this way: they can make a world of difference in the visual quality of a map.

At first glance, implementing the rules for applying the shadow textures can be a bit daunting. Even with the provided diagram and instructions (see “Shadow Tile Placement”), it can take some time to grok the logic needed to place the shadow tiles correctly. For my shadow placement algorithm I broke down the logic as follows:

For a given tile

1. If a taller tile exists to the N, E, S, or W
   Draw the N, E, S, or W shadow on the current tile
2. If a taller tile exists to the SW
   Draw the SW shadow on the current tile only if the tile to the west is the same height or less
3. If a taller tile exists to the SE
   Draw the SE shadow on the current tile only if the tile to the east is the same height or less
4. If a taller tile exists to the NW
   Draw the NW shadow on the current tile only if the tiles to the west and to the north are the same height or less
5. If a taller tile exists to the NE
   Draw the NE shadow on the current tile only if the tiles to the east and to the north are the same height or less

Or in code:

private void _DrawShadow(int i, int j, Vector2 drawPos, float widthIncrement, float heightIncrement)
{
    int currTileHeight = _GetTileHeight(_CaveTileToRenderTile(i, j));

    int iMinus = i > 0 ? i - 1 : i;
    int iPlus = i < _arrayToRender.Count - 1 ? i + 1 : i;
    int jMinus = j > 0 ? j - 1 : j;
    int jPlus = j < _arrayToRender[i].Count - 1 ? j + 1 : j;

    if (_GetTileHeight(_CaveTileToRenderTile(iMinus, jMinus)) > currTileHeight)
    {
        if (_GetTileHeight(_CaveTileToRenderTile(iMinus, j)) <= currTileHeight && _GetTileHeight(_CaveTileToRenderTile(i, jMinus)) <= currTileHeight)
        {
            _DrawShadowTile(TileShadowType.NorthWest, drawPos, widthIncrement, heightIncrement);
        }
    }
    if (_GetTileHeight(_CaveTileToRenderTile(iMinus, j)) > currTileHeight)
    {
        _DrawShadowTile(TileShadowType.North, drawPos, widthIncrement, heightIncrement);
    }
    if (_GetTileHeight(_CaveTileToRenderTile(iMinus, jPlus)) > currTileHeight)
    {
        if (_GetTileHeight(_CaveTileToRenderTile(iMinus, j)) <= currTileHeight && _GetTileHeight(_CaveTileToRenderTile(i, jPlus)) <= currTileHeight)
        {
            _DrawShadowTile(TileShadowType.NorthEast, drawPos, widthIncrement, heightIncrement);
        }
    }
    if (_GetTileHeight(_CaveTileToRenderTile(i, jMinus)) > currTileHeight)
    {
        _DrawShadowTile(TileShadowType.West, drawPos, widthIncrement, heightIncrement);
    }
    if (_GetTileHeight(_CaveTileToRenderTile(i, jPlus)) > currTileHeight)
    {
        _DrawShadowTile(TileShadowType.East, drawPos, widthIncrement, heightIncrement);
    }
    if (_GetTileHeight(_CaveTileToRenderTile(iPlus, jMinus)) > currTileHeight)
    {
        if (_GetTileHeight(_CaveTileToRenderTile(i, jMinus)) <= currTileHeight)
        {
            _DrawShadowTile(TileShadowType.SouthWest, drawPos, widthIncrement, heightIncrement);
        }
    }
    if (_GetTileHeight(_CaveTileToRenderTile(iPlus, j)) > currTileHeight)
    {
        _DrawShadowTile(TileShadowType.South, drawPos, widthIncrement, heightIncrement);
    }
    if (_GetTileHeight(_CaveTileToRenderTile(iPlus, jPlus)) > currTileHeight)
    {
        if (_GetTileHeight(_CaveTileToRenderTile(i, jPlus)) <= currTileHeight)
        {
            _DrawShadowTile(TileShadowType.SouthEast, drawPos, widthIncrement, heightIncrement);
        }
    }
}

Danc’s instructions also include two special case instructions for shadow placement, but I didn’t need them for my map so I didn’t implement them.

Finally, in order to have the walls look taller, I implemented a bit of logic to render some of the walls with the 2-unit tall wall tile instead of the 1-unit tall version. In order to not obscure floor tiles located north of walls, I only drew tall walls in cases where the given wall tile had no floor tiles above it in the same column. Walls with floors to their north are rendered as 1-unit tall walls so the player will never find themselves completely obscured by the wall to their south.

Now that’s starting to look like a cave worth exploring!

Here’s the tile and shadow rendering code:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;


namespace ProceduralWorldLib
{
    public enum RenderTileType
    {
        Floor,
        Wall,
        TallWall
    }

    public enum TileShadowType
    {
        SouthEast,
        South,
        SouthWest,
        East,
        West,
        NorthEast,
        North,
        NorthWest
    }

    public class MapRendererTilesComponent : MapRendererBaseComponent
    {
        class TileTexture
        {
            public string TexturePath;
            public Texture2D Texture;
            public Vector2 PositionOffset;
            public bool DrawFloor;              //Should we draw floor under this tile or not? (Will be drawn sans positionoffset)

            public TileTexture(string _texturePath, Vector2 _positionOffset, bool _drawFloor)
            {
                TexturePath = _texturePath;
                Texture = null;
                PositionOffset = _positionOffset;
                DrawFloor = _drawFloor;
            }
        }

        private SpriteBatch _spriteBatch;

        private int _tileWidth;
        private int _tileHeight;
        private Dictionary<RenderTileType, TileTexture> _tileTextures;
        private Dictionary<TileShadowType, TileTexture> _shadowTextures;
        private float _drawScale;

        private bool _drawShadows;
        private Vector2 _cameraPosition;

        public MapRendererTilesComponent(Game game, List<List<CaveSpaceType>> arrayToRender, int tileWidth, int tileHeight, float drawScale)
            : base(game, arrayToRender)
        {
            _tileWidth = tileWidth;
            _tileHeight = tileHeight;
            _tileTextures = new Dictionary<RenderTileType, TileTexture>(2);
            _shadowTextures = new Dictionary<TileShadowType, TileTexture>(8);
            _drawScale = drawScale;

            _drawShadows = true;
        }

        public Vector2 CameraPosition
        {
            get
            {
                return _cameraPosition;
            }
            set
            {
                _cameraPosition = value;
            }
        }

        public float DrawScale
        {
            set
            {
                _drawScale = value;
            }
        }

        public bool DrawShadows
        {
            set
            {
                _drawShadows = value;
            }
        }

        public void AddTile(RenderTileType spaceType, string texturePath, Vector2 posOffset)
        {
            _tileTextures.Add(spaceType, new TileTexture(texturePath, posOffset, false));
        }

        public void AddShadowTile(TileShadowType spaceType, string texturePath)
        {
            _shadowTextures.Add(spaceType, new TileTexture(texturePath, Vector2.Zero, false));
        }

        public override void Initialize()
        {
            base.Initialize();
        }

        protected override void LoadContent()
        {
            _spriteBatch = new SpriteBatch(Game.GraphicsDevice);

            foreach (KeyValuePair<RenderTileType, TileTexture> entry in _tileTextures)
            {
                entry.Value.Texture = Game.Content.Load<Texture2D>(entry.Value.TexturePath);
                Debug.Assert(entry.Value.Texture != null);
            }

            foreach (KeyValuePair<TileShadowType, TileTexture> entry in _shadowTextures)
            {
                entry.Value.Texture = Game.Content.Load<Texture2D>(entry.Value.TexturePath);
                Debug.Assert(entry.Value.Texture != null);
            }

            base.LoadContent();
        }

        public override void Update(GameTime gameTime)
        {
            base.Update(gameTime);
        }

        public override void Draw(GameTime gameTime)
        {
            _spriteBatch.Begin();

            Vector2 cameraTransform = _GetCameraTransform();
            Vector2 drawPos = Vector2.Zero;
            float widthIncrement = _tileWidth * _drawScale;
            float heightIncrement = _tileHeight * _drawScale;

            for (int i = 0; i < _arrayToRender.Count; ++i)
            {
                for (int j = 0; j < _arrayToRender[i].Count; ++j)
                {
                    RenderTileType renderTileType = _CaveTileToRenderTile(i, j);

                    Color drawColor = Color.White;
                    Vector2 tilePos = drawPos + cameraTransform + _tileTextures[renderTileType].PositionOffset * _drawScale;
                    
                    if (_tileTextures[renderTileType].DrawFloor)
                    {
                        //Draw floor underneath tiles with negative Y offset since you'll be able to see below them
                        _spriteBatch.Draw(_tileTextures[RenderTileType.Floor].Texture, drawPos + cameraTransform, null, drawColor, 0.0f, Vector2.Zero, _drawScale, SpriteEffects.None, 0.0f);
                    }
                    _spriteBatch.Draw(_tileTextures[renderTileType].Texture, tilePos, null, drawColor, 0.0f, Vector2.Zero, _drawScale, SpriteEffects.None, 0.0f);
                    if (_drawShadows)
                    {
                        _DrawShadow(i, j, tilePos, widthIncrement, heightIncrement);
                    }
                    drawPos.X += widthIncrement;
                }

                drawPos.X = 0.0f;
                drawPos.Y += heightIncrement;
            }

            _spriteBatch.End();
            base.Draw(gameTime);
        }

        private RenderTileType _CaveTileToRenderTile(int i, int j)
        {
            RenderTileType renderTileType = RenderTileType.Floor;
            if (_arrayToRender[i][j] == CaveSpaceType.Wall)
            {
                bool bFloorToNorth = false;
                for( int tempI = i; tempI > 0; --tempI)
                {
                    if (_arrayToRender[tempI][j] == CaveSpaceType.Floor)
                    {
                        bFloorToNorth = true;
                        break;
                    }
                }
                renderTileType = bFloorToNorth ? RenderTileType.Wall : RenderTileType.TallWall;
            }
            return renderTileType;
        }

        private Vector2 _GetCameraTransform()
        {
            return -_cameraPosition;
        }

        private int _GetTileHeight(RenderTileType renderTileType)
        {
            switch (renderTileType)
            {
                case RenderTileType.Floor:
                    return 0;
                case RenderTileType.Wall:
                    return 1;
                case RenderTileType.TallWall:
                    return 2;
            }
            return 0;
        }

        private void _DrawShadow(int i, int j, Vector2 drawPos, float widthIncrement, float heightIncrement)
        {
            int currTileHeight = _GetTileHeight(_CaveTileToRenderTile(i, j));

            int iMinus = i > 0 ? i - 1 : i;
            int iPlus = i < _arrayToRender.Count - 1 ? i + 1 : i;
            int jMinus = j > 0 ? j - 1 : j;
            int jPlus = j < _arrayToRender[i].Count - 1 ? j + 1 : j;

            if (_GetTileHeight(_CaveTileToRenderTile(iMinus, jMinus)) > currTileHeight)
            {
                if (_GetTileHeight(_CaveTileToRenderTile(iMinus, j)) <= currTileHeight && _GetTileHeight(_CaveTileToRenderTile(i, jMinus)) <= currTileHeight)
                {
                    _DrawShadowTile(TileShadowType.NorthWest, drawPos, widthIncrement, heightIncrement);
                }
            }
            if (_GetTileHeight(_CaveTileToRenderTile(iMinus, j)) > currTileHeight)
            {
                _DrawShadowTile(TileShadowType.North, drawPos, widthIncrement, heightIncrement);
            }
            if (_GetTileHeight(_CaveTileToRenderTile(iMinus, jPlus)) > currTileHeight)
            {
                if (_GetTileHeight(_CaveTileToRenderTile(iMinus, j)) <= currTileHeight && _GetTileHeight(_CaveTileToRenderTile(i, jPlus)) <= currTileHeight)
                {
                    _DrawShadowTile(TileShadowType.NorthEast, drawPos, widthIncrement, heightIncrement);
                }
            }
            if (_GetTileHeight(_CaveTileToRenderTile(i, jMinus)) > currTileHeight)
            {
                _DrawShadowTile(TileShadowType.West, drawPos, widthIncrement, heightIncrement);
            }
            if (_GetTileHeight(_CaveTileToRenderTile(i, jPlus)) > currTileHeight)
            {
                _DrawShadowTile(TileShadowType.East, drawPos, widthIncrement, heightIncrement);
            }
            if (_GetTileHeight(_CaveTileToRenderTile(iPlus, jMinus)) > currTileHeight)
            {
                if (_GetTileHeight(_CaveTileToRenderTile(i, jMinus)) <= currTileHeight)
                {
                    _DrawShadowTile(TileShadowType.SouthWest, drawPos, widthIncrement, heightIncrement);
                }
            }
            if (_GetTileHeight(_CaveTileToRenderTile(iPlus, j)) > currTileHeight)
            {
                _DrawShadowTile(TileShadowType.South, drawPos, widthIncrement, heightIncrement);
            }
            if (_GetTileHeight(_CaveTileToRenderTile(iPlus, jPlus)) > currTileHeight)
            {
                if (_GetTileHeight(_CaveTileToRenderTile(i, jPlus)) <= currTileHeight)
                {
                    _DrawShadowTile(TileShadowType.SouthEast, drawPos, widthIncrement, heightIncrement);
                }
            }
        }

        private void _DrawShadowTile(TileShadowType shadowType, Vector2 drawPos, float widthIncrement, float heightIncrement)
        {
            Vector2 shadowDrawPos = drawPos + _shadowTextures[shadowType].PositionOffset;
            _spriteBatch.Draw(_shadowTextures[shadowType].Texture, shadowDrawPos, null, Color.White, 0.0f, Vector2.Zero, _drawScale, SpriteEffects.None, 0.0f);
        }
    }
}

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));
        }
    }
}