I was feeling energised recently so I decided to tackle lighting. Here's what the game look looks like now:

## Lighting Model

As implemented, the lighting model currently supports constant global illumination, a precomputed static lightmap (1:1 mapping with the world tilemap), and point lighting with occlusion (directional lights are not supported but could be added with minimal effort). This feels like a pretty flexible combination and should allow me to do a bunch of cool stuff in the future, including day/night cycles and pre-rendered shadows.

## Basic Implementation

I began by implementing global and static lighting, leaving the more complex point lighting until later. Global illumination is represented as a single 3-element vector, with each component representing a separate lighting channel - one each for red, green and blue. The static lightmap is stored in a 2D array of similar vectors, derived from the world map. Additionally, I defined a scratch area, `frameLightmap`

, to store each frame's lighting computation.

```
const globalIllumination = [0, 0, 0];
const staticLightmap = map.map((row) => {
return row.map(_ => [0.3, 0.3, 0.3]);
});
const frameLightmap = map.map((row) => {
return row.map(_ => [null, null, null]);
});
```

To render a frame we simply compute the overall lighting for each tile by summing its static vector with the global lighting value:

```
for (let y = 0; y < map.height; ++y) {
for (let x = 0; x < map.width; ++x) {
frameLightmap[y][x][0] = staticLightmap[y][x][0] + globalIllumination[0];
frameLightmap[y][x][1] = staticLightmap[y][x][1] + globalIllumination[1];
frameLightmap[y][x][2] = staticLightmap[y][x][2] + globalIllumination[2];
}
}
```

To render the lighting effect we traverse the frame lightmap, drawing a coloured square with a fill matching the tile's lighting value over each previously drawn tile. Using multiplicative blending, the result is an image modulated by the coloured lighting squares, with lower lighting values creating a darkening effect. Fully lit squares (i.e. `r,g,b == 255,255,255`

) pass through unmodified. I read somewhere that performing blending this way is quite expensive but, at least for now, I'm not overly concerned by this - it's a turn based game so there's no need for buttery-smooth 60FPS, plus the end goal is to have a GPU-accelerated renderer anyway.

```
ctx.save();
ctx.globalCompositeOperation = 'multiply';
for (let y = 0; y < map.height; ++y) {
for (let x = 0; x < map.width; ++x) {
const l = frameLightmap[y][x];
const r = clamp(l[0], 0, 1);
const g = clamp(l[1], 0, 1);
const b = clamp(l[2], 0, 1);
ctx.fillStyle = 'rgb(' + Math.floor(r*255) + ',' + Math.floor(g*255) + ',' + Math.floor(b*255) + ')';
ctx.fillRect(x * TILE_SIDE, y * TILE_SIDE, TILE_SIDE, TILE_SIDE);
}
}
ctx.restore();
```

## Adding Point Lighting

At this point I had a decent way of rendering a calculated lightmap, but to create more atmospheric effects like torches, lighting bolts and glowing magical artifacts I needed point lighting.

The algorithm I settled on is pretty naive: for each tile of the light source's bounding square (calculated based on the light's radius/intensity), cast a ray to said tile from the light source, and walk each tile covered by that ray. For each tile thus walked, update the lightmap based by applying a decay function to the light's original colour and distance from the light source. Whenever we hit an impassable tile, abort the current ray's walk.

Bresenham's Algorithm was used for the ray-casting. I had a small concern as I wasn't sure if my perimeter-walking algorithm would result in any unvisited tiles (meaning no lighting would be calculated thereon). Intuitively it seemed it should all work OK but I decided to run a quick test anyway; the numbers below denote the total number of times each cell was hit when casting rays to all cells forming the grid's perimeter. We don't want to see any zeroes in there.

```
3 x 3:
2 1 2
1 12 1
2 1 2
5 x 5:
2 1 1 1 2
1 4 1 3 1
1 1 20 3 1
1 3 3 2 1
2 1 1 1 2
7 x 7:
2 1 1 1 1 1 2
1 2 2 1 2 2 1
1 2 4 3 4 2 1
1 1 3 28 3 1 1
1 2 4 3 4 2 1
1 2 2 1 2 2 1
2 1 1 1 1 1 2
9 x 9:
2 1 1 1 1 1 1 1 2
1 2 2 1 1 1 2 2 1
1 2 4 2 1 2 3 1 1
1 1 2 6 3 5 2 2 1
1 1 1 3 36 5 3 1 1
1 1 2 5 5 4 2 2 1
1 2 3 2 3 2 2 1 1
1 2 1 2 1 2 1 2 1
2 1 1 1 1 1 1 1 2
11 x 11:
2 1 1 1 1 1 1 1 1 1 2
1 2 1 2 1 1 1 2 1 2 1
1 1 2 2 2 1 2 2 2 1 1
1 2 2 4 2 3 2 4 2 2 1
1 1 2 2 6 5 6 2 2 1 1
1 1 1 3 5 44 5 3 1 1 1
1 1 2 2 6 5 6 2 2 1 1
1 2 2 4 2 3 2 4 2 2 1
1 1 2 2 2 1 2 2 2 1 1
1 2 1 2 1 1 1 2 1 2 1
2 1 1 1 1 1 1 1 1 1 2
13 x 13:
2 1 1 1 1 1 1 1 1 1 1 1 2
1 2 1 2 1 1 1 1 1 2 1 2 1
1 1 2 2 1 2 1 2 1 2 2 1 1
1 2 2 4 2 2 1 2 2 3 2 1 1
1 1 1 2 4 3 3 3 4 2 1 2 1
1 1 2 2 3 8 5 7 3 2 2 1 1
1 1 1 1 3 5 52 7 3 3 1 1 1
1 1 2 2 3 7 7 6 3 2 2 1 1
1 1 1 2 4 3 3 3 4 2 1 2 1
1 2 2 3 2 2 3 2 2 2 2 1 1
1 1 2 2 1 2 1 2 1 2 2 1 1
1 2 1 1 2 1 1 1 2 1 1 2 1
2 1 1 1 1 1 1 1 1 1 1 1 2
```

That all looks good. Next I wrote a function that performed a walk of Bresenham's algorithm on a cartesian grid, invoking a callback for each visited tile. This turned out to be slightly tricky as most implementations of the algorithm work by swapping the start and end co-ordinates under certain conditions to ensure that the line's slope always matches the necessary invariants, but such swap causes the walk to become outside-in rather than inside-out. For the purposes of lighting it's critical that the algorithm always walks from (x0,y0) to (x1,y1), as going in the opposite direction means that iteration potentially starts from beyond an impassable object, leaving a ray of light *behind* the wall and none between the wall and the light source.

The standard definition of Bresenham's algorithm only behaves correctly in octant zero of the diagram depicted below:

```
\2|1/
3\|/0
---+---
4/|\7
/5|6\
```

To handle all octants, the walk function was modified to accept the current octant as an explicit argument and to perform juggling on the input/output values that allow the algorithm to always operate on co-ordinate pairs in octant zero. The trade-off is that it's now necessary to manually co-ordinate eight separate calls to `bresenhamWalk()`

, but it's simple enough to extract a helper function to do this transparently.

```
function bresenhamWalk(octant, x0,y0, x1,y1, cb) {
let tmp;
tmp = oi(x0, y0);
x0 = tmp[0];
y0 = tmp[1];
tmp = oi(x1, y1);
x1 = tmp[0];
y1 = tmp[1];
const dx = x1 - x0;
const dy = y1 - y0;
let D = 2*dy - dx;
let y = y0;
for (let x = x0; x <= x1; ++x) {
if (oo(x, y) === false) {
return;
}
if (D > 0) {
y++;
D = D - 2*dx;
}
D += 2*dy;
}
function oi(x, y) {
switch (octant) {
case 0: return [x, y];
case 1: return [y, x];
case 2: return [y, -x];
case 3: return [-x, y];
case 4: return [-x, -y];
case 5: return [-y, -x];
case 6: return [-y, x];
case 7: return [x, -y];
}
}
function oo(x, y) {
switch(octant) {
case 0: return cb(x, y);
case 1: return cb(y, x);
case 2: return cb(-y, x);
case 3: return cb(-x, y);
case 4: return cb(-x, -y);
case 5: return cb(-y, -x);
case 6: return cb(y, -x);
case 7: return cb(x, -y);
}
}
}
```

The penultimate step is to perform the ray-casting and record which tiles are lit. Technically this could be combined with the lighting calculation performed in the next step but I found a two-step approach simpler conceptually.

```
const marked = {};
function mark(x, y) {
if (!isPassable(state.map, x, y)) {
return false;
}
marked[x + ',' + y] = true;
}
for (let i = 0; i <= lightRadius; ++i) {
bresenhamWalk(0, e.x, e.y, e.x + lightRadius, e.y + i, mark);
bresenhamWalk(7, e.x, e.y, e.x + lightRadius, e.y - i, mark);
bresenhamWalk(3, e.x, e.y, e.x - lightRadius, e.y + i, mark);
bresenhamWalk(4, e.x, e.y, e.x - lightRadius, e.y - i, mark);
bresenhamWalk(1, e.x, e.y, e.x + i, e.y + lightRadius, mark);
bresenhamWalk(2, e.x, e.y, e.x - i, e.y + lightRadius, mark);
bresenhamWalk(6, e.x, e.y, e.x + i, e.y - lightRadius, mark);
bresenhamWalk(5, e.x, e.y, e.x - i, e.y - lightRadius, mark);
}
```

(I wimped out and used an object and stringy keys for tracking visited squares; in the future I'll optimise this to use an array).

Finally we iterate over each tile within the light source's bounding box and, if the tile is lit, update the frame lightmap based on the light's colour and the tile's distance from the light source. I'm just using a simple linear decay function for now and it works well enough for now.

```
const lightX = e.x + 0.5;
const lightY = e.y + 0.5;
const x1 = lightX - lightRadius;
const x2 = lightX + lightRadius + 1;
const y1 = lightY - lightRadius;
const y2 = lightY + lightRadius + 1;
for (let y = y1; y < y2; ++y) {
for (let x = x1; x < x2; ++x) {
const dx = x - lightX;
const dy = y - lightY;
const d = Math.sqrt(dx*dx + dy*dy);
const tx = Math.floor(x);
const ty = Math.floor(y);
if (tx < 0 || tx >= map.width || ty < 0 || ty >= map.height) continue;
if (!marked[tx + ',' + ty]) continue;
const i = clamp(lightRadius - d, 0, lightRadius) / lightRadius;
frameLightmap[ty][tx][0] += e.lightColor[0] * i;
frameLightmap[ty][tx][1] += e.lightColor[1] * i;
frameLightmap[ty][tx][2] += e.lightColor[2] * i;
}
}
```

## Demo

Demo for this installment. Press `L` to toggle the hero's light.

## Future Improvements

- Investigate using HSL rather than RGB
- Directional lights
- Make static lightmap indirect so it can be modulated with a function?

## Next Steps

- Support maps larger than a single screen
- Add animation/tweening for entity/camera movement
- Proper graphics; I'm becoming bored of looking at coloured squares. I've found a few good free/cheap tilesets - will pick one and drop it in.