Virtual Spelunking: Turning on the Lights

Continuing my adventure in interior decoration for imaginary places, it’s about time for me to start populating my procedural cave with objects. This time around, I’ll focus on adding light sources to my cave. There are two major reasons for this: 1) light sources, like torches, won’t have to be collidable so I can lay them out without worrying about breaking the navigability of my cave; 2) rendering the lights gives me an excuse play around with pixel shaders.

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:


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

    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
                _randomSeed = value;

        public List<List<CaveSpaceInfo>> MapToPoplulate
                _mapToPopulate = value;

        public List<MapInhabitant> MapInhabitants
                return _mapInhabitants;

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


            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(
                            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;

            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["LightSizeInverse"].Elements[lightIndex].SetValue(1 / lightSize);

And finally, the light pixel shader:

// Based on the Sprite Effects sample at

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();
Share this Article:
  • Digg
  • StumbleUpon
  • Facebook
  • Yahoo! Buzz
  • Twitter
  • Google Bookmarks
  • Print