Raytracing Lighting on a 2D Tilemap

Tilemap lighting tutorial

Another great use of Raytracing is lighting. This subject can get pretty complex and is an accomplished discipline in its own right, but we're going to be starting with the basics, so anyone with a limited programming knowledge should be comfortable engaging in this lesson.

View example

We'll be looking at how to add light sources and per-tile lighting on a tilemap. First, let's look at our Light object - we'll create our lights with four initial values: the x, y coordinates of the light on the map, the radius, which is the distance light spreads from this light source, and the lights intensity:

function Light(x, y, radius, intensity)
{
    this.position        = [x,y];
    this.radius        = radius;
    this.intensity        = intensity;
    this.area        = {};
}

Our lighting will be used to determine the opacity at which we draw each tile. A value of 0 is completely invisible (so we'll just show the black background), and 1 is completely visible, at full brightness.

A higher value than 1 is fine, but nothing will be drawn brighter than full opacity (1). A higher value can let the brightness of the light spread further before dimming.

The lights also have a area attribute, which we'll look at next. The Light object has its own method, which we'll call calculate. When this method is executed, we'll begin by resetting the area attribute to an empty object (this object will be used as a HashMap or associative array, depending on which languages you're familiar with).

Light.prototype.calculate = function()
{
    this.area = {};

Now a call is made to Bresenhams circle algorithm to find all of the furthest points from the light source's centre:

    var edges = pointsOnCircumference(this.position[0], this.position[1],
        this.radius);

...and we'll loop through all of the points that are returned and get the points to make a line using Bresenhams line algorithm from the lights position to the current point in the edges list.

    for(var e in edges)
    {
        var line = bresenhamsLine(this.position[0], this.position[1],
            edges[e][0], edges[e][1]);

To find how intense the lighting will be at each step along the line, we'll divide the lights intensity by the number of steps along the line:

        var mult = this.intensity / line.length;

...and then step through the points in the current line. If the current point in the current line falls outside of the maps bounds, we'll break from the loop as there's no point in calculating the rest of the line.

        for(var l in line)
        {
            if(line[0] < 0 || line[0]>=mapW ||
                line[1] < 0 || line[1]>=mapH) { break; }

We'll create a temporary variable, idx, that converts the x, y position of the current point on this line to its coordinate in the mapData array.

            var idx = ((line[l][1]*mapW)+line[l][0]);

The light intensity at this point is equivalent to [total intensity] - ( ([total intensity] / [line length]) x [distance from centre]). As we've already calculated our mult variable, we can get the strength at the current line step like this:

            var strength = mult * (line.length - l);

Now, we check that the current line point is either not currently illuminated by this light, or the light intensity is less than the strength we've currently calculated for this point.

If either of these conditions is true, we set the area entry for this points mapData index (idx) to the value of strength, or 1 if strength is greater than 1.

            if(!(idx in this.area) || this.area[idx]<strength)
            {
                this.area[idx] = (strength > 1 ? 1 : strength);
            }

Additionaly, if the current tile is solid and light cannot pass through it (a value of 0 in our example mapData, we do not continue any further along this line by breaking from the loop. The solid tile is illuminated, but light has not passed through it.

We can also go ahead and close the loops and the method, as we're done for this light!

            if(mapData[idx]==0) { break; }
        }
    }
};

Building the light map

To keep track of lighting throughout the map, we'll create some global variables. First, there will be lightMap, that stores the light levels over ever map tile, and allLights, an array that will contain each light object on our map.

We'll also create a baseLighting variable, which will store the minimum light level for each tile. This is because in our example we want all the map to be visible to some degree - if we wanted unlit areas to be completely invisible (blacked out), we could just set the value of this variable to 0.

var lightMap = null;
var allLights = [];

// The minimum lighting for the map
var baseLighting = 0.1;

Rebuilding the light map

Before we begin drawing our map, or when we update any lights on the map, we need to call our rebuildLightMap function to recreate the lightMap array. This function begins by resetting the lightMap global to an empty array, and then fills it to the same length as our mapData array with the lowest possible light level, baseLighting:

function rebuildLightMap()
{
    lightMap = new Array();
    for(var i = 0; i < (mapW*mapH); i++) { lightMap[i] = baseLighting; }

Now we can loop through all of the lights in the allLights array, and for each light loop through its lit area property to find all the tiles touched by this light.

    for(var l in allLights)
    {
        for(var a in allLights[l].area)
        {

Finally, we check if the illumination provided by the current light source at the destination tile is more than the current illumination value for the tile (provided either by the baseLighting value, or another light). If it is, we set the lightMap value to the value provided by this light:

            if(lightMap[a] < allLights[l].area[a])
            {
                lightMap[a] = allLights[l].area[a];
            }

Now we just need to go ahead and close the open loops and this function with three curly braces:

        }
    }
}

Placing random lights

Just out of curiousity's sake, lets look at how we generate the random lights. In your game, you'd most likely want to place the lights in specific locations, so you can skip over this if you feel with how new light objects are created.

We'll call the function resetLights, and begin by clearing the allLights array.

function resetLights()
{
    // Remove existing lights
    allLights.length = 0;

We'll tell the code to execute until we've created 5 random lights:

    while(allLights.length < 5)
    {

The Javascript Math.random method returns a random floating point number between 0 and 1. We'll use this plus 0.3 for the lights intensity.

        var intensity = 0.3+Math.random();

For our radius, we'll just make it that the brighter the lighter, the further we want it to shine. Our lights radius (in tiles) will be the intensity we randomly generated divided by 0.05, rounded down to the nearest whole number.

        var radius = Math.floor(intensity / 0.05);

The lights position, will just be a random coordinate that falls within the maps bounds (between 0 and mapW or mapH depending on whether we're creating the x or y coordinate).

        var x = Math.floor(Math.random()*mapW);
        var y = Math.floor(Math.random()*mapH);

Now we check if the random x, y coordinate we've chosen falls on a solid tile (a 0 in the mapData array); if it does, we create another random light by jumping back to the start of the loop and try again:

        if(mapData[((y*mapW)+x)]==0) { continue; }

We'll now create a temporary placeHere boolean variable, and loop through and other lights we've already created in the allLights array. If any other lights already occupy the random x, y position we've chosen, we jump back to create a new random light.

        placeHere = true;
        
        for(l in allLights)
        {
            if(allLights[l].position[0]==x &&
                allLights[l].position[1]==y)
            {
                placeHere = false;
                break;
            }
        }
        
        if(!placeHere) { continue; }

If our collision checks are passed, we create a new Light object with the random parameters, calculate the area it illuminates with its method, and add it to the allLights array.

        var l = new Light(x, y, radius, intensity);
        l.calculate();

        allLights.push(l);

We can now close the random light generation loop. When the loop is completed, we'll rebuild our light map (rebuildLightMap), and we're done!

        }

    rebuildLightMap();
}

Example source code

<!DOCTYPE html>
<html>
<head>

<script type="text/javascript">
var ctx = null;
var tileW = 40, tileH = 40;
var mapW = 20, mapH = 10;

var mapData = [
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0,
    0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0,
    0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0,
    0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0,
    0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0,
    0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0,
    0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0,
    0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
];
var lightMap = null;
var allLights = [];

// The minimum lighting for the map
var baseLighting = 0.1;

function Light(x, y, radius, intensity)
{
    this.position        = [x,y];
    this.radius            = radius;
    this.intensity        = intensity;
    this.area            = {};
}
Light.prototype.calculate = function()
{
    this.area = {};
    var edges = pointsOnCircumference(this.position[0], this.position[1],
        this.radius);
    
    for(var e in edges)
    {
        var line = bresenhamsLine(this.position[0], this.position[1],
            edges[e][0], edges[e][1]);
        var mult = this.intensity / line.length;
        
        for(var l in line)
        {
            if(line[0] < 0 || line[0]>=mapW ||
                line[1] < 0 || line[1]>=mapH) { break; }
                
            var idx = ((line[l][1]*mapW)+line[l][0]);
            var strength = mult * (line.length - l);
            
            if(!(idx in this.area) || this.area[idx]<strength)
            {
                this.area[idx] = (strength > 1 ? 1 : strength);
            }
            
            if(mapData[idx]==0) { break; }
        }
    }
};

function rebuildLightMap()
{
    lightMap = new Array();
    for(var i = 0; i < (mapW*mapH); i++) { lightMap[i] = baseLighting; }
    
    for(var l in allLights)
    {
        for(var a in allLights[l].area)
        {
            if(lightMap[a] < allLights[l].area[a])
            {
                lightMap[a] = allLights[l].area[a];
            }
        }
    }
}

function resetLights()
{
    // Remove existing lights
    allLights.length = 0;
    
    // Create 5 random lights
    while(allLights.length < 5)
    {
        // Create random light attributes
        var intensity = 0.3+Math.random();
        var radius = Math.floor(intensity / 0.05);
        var x = Math.floor(Math.random()*mapW);
        var y = Math.floor(Math.random()*mapH);
        
        // Check the destination tile of this light
        // is not solid (or else it will only illuminate
        // the one tile on which it is placed)
        if(mapData[((y*mapW)+x)]==0) { continue; }
        
        // Check another light does not already exist
        // at these coordinates (otherwise it's not really
        // a useful example!)
        placeHere = true;
        
        for(l in allLights)
        {
            if(allLights[l].position[0]==x &&
                allLights[l].position[1]==y)
            {
                placeHere = false;
                break;
            }
        }
        
        if(!placeHere) { continue; }
        
        // Create this light and calculate its
        // illumated area
        var l = new Light(x, y, radius, intensity);
        l.calculate();

        // Add to the allLights array
        allLights.push(l);
    }
    // Rebuild the light map!
    rebuildLightMap();
}

window.onload = function() {
    ctx = document.getElementById('game').getContext('2d');
    ctx.font = "bold 10pt sans-serif";
    
    // Add some random lights
    resetLights();
    
    // If our reset link is clicked, remove existing
    // lights, create new ones, and rebuild the lightMap
    document.getElementById('changeLights').addEventListener('mouseup',
        function() {
        resetLights();
    });
    
    requestAnimationFrame(drawGame);
};

function drawGame()
{
    if(ctx==null) { return; }

    // Clear the Canvas
    ctx.fillStyle = "#000000";
    ctx.fillRect(0, 0, 800, 400);

    for(var y = 0; y < mapH; ++y)
    {
        for(var x = 0; x < mapW; ++x)
        {
            var idx = ((y * mapW) + x);
            
            if(lightMap[idx]==0) { continue; }
            
            ctx.globalAlpha = lightMap[idx];
            
            ctx.fillStyle = (mapData[idx]==0 ? "#0000cc" : "#ffddcc");
            ctx.fillRect(x * tileW, y * tileH, tileW, tileH);
        }
    }

    // Mark light sources
    ctx.globalAlpha = 1;
    ctx.strokeStyle = "#ff0000";
    for(var l in allLights)
    {
        ctx.beginPath();
        ctx.arc(allLights[l].position[0]*tileW + (tileW / 2),
            allLights[l].position[1]*tileH + (tileH / 2),
            5, 0, Math.PI*2);
        ctx.closePath();
        ctx.stroke();
    }
    
    // Ask for the next animation frame
    requestAnimationFrame(drawGame);
}

function bresenhamsLine(x1, y1, x2, y2)
{
    line = new Array();
    
    var dx = Math.abs(x2 - x1);
    var dy = Math.abs(y2 - y1);
    
    var sx = (x1 < x2 ? 1 : -1);
    var sy = (y1 < y2 ? 1 : -1);
    
    var error = dx - dy;
    
    var x = x1, y = y1;
    
    while(1)
    {
        line.push([x, y]);
        
        if(x==x2 && y==y2) { break; }
        
        var e2 = 2 * error;
        
        if(e2 >-dy) { error-= dy; x+= sx; }
        if(e2 < dx) { error+= dx; y+= sy; }
    }
    
    return line;
}

function pointsOnCircumference(cx, cy, cr)
{
    var list = new Array();
    
    var x = cr;
    var y = 0;
    var o2 = Math.floor(1 - x);

    while(y <= x)
    {
        list.push([ x + cx,  y + cy]);
        list.push([ y + cx,  x + cy]);
        list.push([-x + cx,  y + cy]);
        list.push([-y + cx,  x + cy]);
        list.push([-x + cx, -y + cy]);
        list.push([-y + cx, -x + cy]);
        list.push([ x + cx, -y + cy]);
        list.push([ y + cx, -x + cy]);

        y+= 1;

        if(o2 <= 0) { o2+= (2 * y) + 1; }
        else
        {
            x-= 1;
            o2+= (2 * (y - x)) + 1;
        }
    }

    return list;
}    
</script>

</head>
<body>
<p>Random lights with differing intensities are placed on the map below.  <a id="changeLights" style="color:#00a; font-weight:bold; cursor:pointer;">Click here to change the random lights</a>.  If you cannot see the example below, please ensure you have Javascript enabled and that your browser supports the Canvas element.</p>
<canvas id="game" width="800" height="400"></canvas>

</body>
</html>