DnD Map Editor - Lighting, Part 2

Part 4 of infinity.

Introduction

As I mentioned in a previous post, I first added lighting to my map editor for a session where the players were wandering in the equivalent of the Kansas of the Negative Energy Plane - an area with no walls, just lots of shambling corpses. As such, the first version of it did not handle obstructed light.

As I mentioned at the time, I was confident I would have to do that as soon as I wanted to have an encounter in an area that had walls and was dark, and it didn’t take too long for that to come up, so as promised I’m back to explain how I did this.

Side Note on Prior Art

I’m sure I’m not the first or the seven hundredth software engineer to have to solve for lighting an area with obstruction, and I realize there are undoubtedly canonical solutions for doing so. However, I did this from scratch without consulting any references, for a few reasons:

  1. I’m not actually rendering a standard environment, like in OpenGL or something - everything in the map editor is drawn “by hand”, so to speak
  2. My evironment is a little specific - idealized 5-foot squares that only have walls in four directions at the exact bounds of them, with wall segments likewise exactly 5 feet long - so some general solutions could actually just be overkill
  3. I’m doing this for fun
  4. This blog would be really boring to read otherwise

HTML Canvas Drawing Primitives

As noted previously I’m drawing the lights with fading-out edges, so I have to draw them with gradients. (As it eventually turned out, this didn’t make a whole lot of difference.)

I was also previously drawing only circles, using the arc method, which takes a center point, radius, start, and end angles (and I would always supply 0 and 2π, except for certain “cone” lights).

Now I need to handle some weirder scenarios. Behold a glimpse into my extremely professional design process:

A scribbled diagram of a circle of light broken up by walls

(That was sarcasm, above. I feel like graph paper probably would have sold my professionalism more.)

Anyway, as the diagram suggests, now I’m going to be drawing a shape that looks like a cirlce, except with chunks taken out of it, and those chunks will themselves have lots of straight lines.

I thought about this for a while and eventually came up with the following. For a given light:

  1. Figure out all of the wall segments that are within its radius
  2. Figure out which angles each wall segment covers
  3. For each range of angles, determine which is the closest wall (if any) and put this in some kind of data structure, in order
  4. Starting at 0 radians, draw the next segment either using the arc method (if there’s no wall obstructing it) or the lineTo method (one line from wherever we were to the wall, another along the wall)
  5. Once we have made it around the circle, fill it with the gradient

Building a Light Data Structure

There are two pieces to this code. One is the logic to construct what I’m currently calling a “LightArc” (although I’ll probably change the name when I inevitably use the same logic for something else, like player-line-of-sight). I’ll just give you the full Typescript definition for this below, but the gist of it is that you declare a LightArc with a center, radius, and start and end angles, and then you “add walls” to it, and every time you “add a wall” it figures out if it blocks off the light more than whatever walls it already knew about, and if so adjusts the segments accordingly. This should in theory mean that you get the exact same LightArc no matter what order you add the walls in, except for maybe some irrelevant edge cases where two walls technically end at the same point (i.e., the corner of a square).

As you can see from the code below - if you don’t just scroll past it, which, let’s be honest, at some point you probably will - it’s mostly made up of edge cases. The biggest one that I ran into the most often was that it’s possible for something to cross the 0 / 2π boundary because I have some lights the originate from the center of a square.

Technically I’m not sure if this is in keeping with the canonical light rules in DnD, where they mostly define areas that are centered at a corner. On the flip side, the DnD light rules are kinda vague and basically backwards (they seem to suggest that whether you can see someone depends on how the area around you is lit, not how the area around them is, or at least they don’t account for people in mixed lighting conditions well), so I felt comfortable making some decisions on my own that deviated slightly from them.

Anyway, getting back to the whole 0 / 2π question, you’ll see below that in this class I address it by, if somebody passes in a wall that crosses the boundary, I just split it into two separate calls, one that covers the portion from 0 to [some low value] and the other that cover from [some high value] to 2π.

import { Wall, WallType } from "./map";
import { GetDistance, GetAngle } from "./shared";
import { MapPoint, MapDistance } from "./location";

interface LightArcSegment {
    readonly endAngle: number;
    readonly wall: Wall | null;
}

export function GetWallEndpoints(wall: Wall): [MapPoint, MapPoint] {
    // Values should be sorted from low to high
    if (wall.type == WallType.Vertical) {
        return [
            { mapX: wall.x, mapY: wall.y },
            { mapX: wall.x, mapY: wall.y + 1 }
        ];
    } else {
        return [
            { mapX: wall.x, mapY: wall.y },
            { mapX: wall.x + 1, mapY: wall.y }
        ];
    }
}

export class LightArc {
    constructor(
        public center: MapPoint,
        public radius: MapDistance,
        public startAngle: number,
        public endAngle: number,
        public segments: Array<LightArcSegment> = []) {

        if (segments.length == 0) {
            segments.push({ endAngle: this.endAngle, wall: null });
        }
    }

    public addWall(wall: Wall) {
        let endpoints = GetWallEndpoints(wall);

        let angles = endpoints.map(e => GetAngle(this.center, e));

        let start, end;
        if (angles[0] > angles[1]) {
            start = angles[1];
            end = angles[0];
        } else {
            [start, end] = angles;
        }

        if (start == 0 && end > Math.PI) {
            start = end;
            end = 2 * Math.PI;
        }

        if (start > this.endAngle || end < this.startAngle) {
            return;
        }

        if (start < this.startAngle) {
            start = this.startAngle;
        }

        if (end > this.endAngle) {
            end = this.endAngle;
        }

        // I think this should be sufficient to catch wraparound cases
        if (end > Math.PI + start) {
            this.addWallByAngles(wall, 0, start);
            this.addWallByAngles(wall, end, Math.PI * 2);
        } else {
            this.addWallByAngles(wall, start, end);
        }
    }

    private addWallByAngles(wall: Wall, start: number, end: number) {
        let index = 0;
        let lastEnd = 0;

        // Keep going until the segment doesn't end before this wall starts
        while (index < this.segments.length &&
            this.segments[index].endAngle <= start) {
            lastEnd = this.segments[index].endAngle;
            index++;
        }

        // Maybe all the existing segments do, and we should just add this at the end
        if (index >= this.segments.length) {
            this.segments.push({
                endAngle: end,
                wall: wall
            });
            return;
        }

        while (index < this.segments.length && lastEnd < end) {
            if (this.segments[index].wall != null &&
                this.isCloser(this.segments[index].wall!, wall)) {
                lastEnd = this.segments[index].endAngle;
                index++;
                continue;
            }

            // The segment we're comparing to has already started. Add another segment that goes up to the overlap point.
            if (lastEnd < start) {
                this.segments.splice(index, 0, {
                    endAngle: start,
                    wall: this.segments[index].wall
                });

                index++;
            }

            if (this.segments[index].endAngle <= end) {
                this.segments[index] = {
                    wall: wall,
                    endAngle: this.segments[index].endAngle
                };
            } else {
                this.segments.splice(index, 0, {
                    endAngle: end,
                    wall: wall
                });
            }

            lastEnd = this.segments[index].endAngle;
            index++;
        }

        if (index == this.segments.length && lastEnd < end) {
            // This means the existing segments didn't cover this wall entirely
            this.segments.push({
                endAngle: end,
                wall: wall
            });
        }

        // A consequence of the above is we might end up putting the same wall twice in a row
        for (var i = this.segments.length - 1; i > 0; i--) {
            if (this.segments[i].wall == this.segments[i - 1].wall) {
                this.segments.splice(i - 1, 1);
            }
        }
    }

    isCloser(newWall: Wall, existingWall: Wall): boolean {
        // We should be able to assume from context that these walls cover
        // some kind of overlapping ranges of angles from the center.
        // I'm not sure we really need to do anything fancy - see if this works:

        let newEndpoints = GetWallEndpoints(newWall);
        let newDistance = GetDistance(this.center, newEndpoints[0]).mapVal + GetDistance(this.center, newEndpoints[1]).mapVal;

        let existingEndpoints = GetWallEndpoints(existingWall);
        let existingDistance = GetDistance(this.center, existingEndpoints[0]).mapVal + GetDistance(this.center, existingEndpoints[1]).mapVal;

        return newDistance < existingDistance;
    }
}

Actually Drawing Stuff

Once this data structure is constructed, I use it to draw the lights on the canvas in the method below.

A couple of notes for things that might not be clear from context:

First, I allow “startAngle” and “endAngle” values other than 0 and 2π because you can have “cones” of light, like from a bullsye lantern, which is apparently a real thing that served as a sort of old-timey flashlight.

Second, the “continuePath” argument - which determines whether the method starts and ends the drawing path inside of it - is a bit of an artifact of the way I chose to draw darkvision, where I added some blue tint to distinguish it from regular light. I need to make sure when I draw two overlapping areas of darkvision, I don’t double up on the blue light. I discussed this at greater length previously, but the rest of the light/darkness is actually drawn by erasing portions of a dark overlay, in effect, and therefore doesn’t have this same stacking concern. But darkvision does, so I had to add a weird exception until I figure out some other, more clever way.

Third, there are some references to “MapPoint” and “ScreenPoint” classes - this is because I kept running into issues where I would just have x- and y-values for things, and I would have to remember to convert them based on the fact that each square is 32 pixels, and the map can be scrolled so the origin isn’t really (0, 0) anymore, etc., so eventually I just made sure the type system always knew which of the two values I was dealing with, and I could prevent myself from mixing them up.

DrawArcWithWalls(ctx: CanvasRenderingContext2D, center: MapPoint, radius: MapDistance, startAngle: number, endAngle: number, continuePath = false) {
    if (startAngle < 0) {
        this.DrawArcWithWalls(ctx, center, radius, 0, endAngle, continuePath);
        this.DrawArcWithWalls(ctx, center, radius, Math.PI * 2 + startAngle, Math.PI * 2, continuePath);
        return;
    }

    let walls = this.GetWallsWithinRadius(center, radius);

    let lightArc = new LightArc(center, radius, startAngle, endAngle);

    for (let wall of walls) {
        lightArc.addWall(wall);
    }

    let { screenX, screenY } = ToScreenPoint(center, this.props.map.origin);

    // The following assumes that the light arc segments will be in order
    if (!continuePath) {
        ctx.beginPath();
    }

    ctx.moveTo(screenX, screenY);

    let currentAngle = startAngle;

    for (let segment of lightArc.segments) {
        if (segment.wall == null) {
            ctx.arc(screenX, screenY, radius.mapVal * SQUARE, currentAngle, segment.endAngle);
        } else {
            let first = ToScreenPoint(this.GetIntersection(center, currentAngle, segment.wall), this.props.map.origin);
            let second = ToScreenPoint(this.GetIntersection(center, segment.endAngle, segment.wall), this.props.map.origin);

            ctx.lineTo(first.screenX, first.screenY);
            ctx.lineTo(second.screenX, second.screenY);
        }

        currentAngle = segment.endAngle;
    }

    if (!continuePath) {
        ctx.fill();
    }
}

You will also note (depending on how quickly you scrolled past) that the 0 / 2π thing rears its head again here. This is partially because of the cone lights I mentioned above - one of the possible directions is “to the right”, i.e. -pi/4 to pi/4. I chose to code it that way originally because it was either that, or, allow cones to specify a list of ranges (although it would always just be one or two). Unfortunately, that means there’s more than one place I have special handling for this scenario, which is probably a bad thing, and probably means I’ll break it in the future. (I did make sure to make some integration tests that covered this, but I’m still concerned.)

One other decision I had to make was how to decide when NPCs were “visible” based on being in a lit area. (I couldn’t just paint over them - I also show a list of them to the players next to the map, and I change the font color of entries in the list from black to red as they take damage, which has prompted a lot of session time dedicated to debates amongst the players over whether a particular name is still straight black or has a hint of burgandy. I have some regrets, but it’s too late to go back now. Anyway, the point is “visible” is a binary characteristic at this point.)

Once again, I don’t find the canonical rules to be very helpful here - do you consider somebody to be in “bright light” if there’s a tiny sliver of it crossing their square? For the moment I have chosen to go with the extremely conservative answer that, yes, you do, and therefore I treat an NPC as visible if their square has essentially any light in it whatsoever.

Here’s an example:

A dark map with two light sources that are blocked by various walls

This is the DM’s view, so NPCs hidden in darkness have mostly-white letters, and visible ones have solid black letters with white outlines. The players would see this:

A dark map with two light sources that are blocked by various walls

What I Learned From This

I wouldn’t necessarily say any of these things are brand-new lessons, but they’re things worth having reinforced:

  1. When dealing with numerical data, it’s a good idea to make sure your type system is giving you indications of what a given number (or pair of numbers, etc.) means. You see the final version above, which still isn’t perfect, but some of the intermediate versions caused a lot of confusion before I got strict about this.
  2. When dealing with angles, you will inevitably need to define an acceptable range of values and stick to it (and it should probably only contain 2π worth of radians). Actually, this is probably a good note for any scenario dealing with ranges of numbers - are negatives allowed? Does it go to infinity? Etc.
  3. If you’re not testing it, it’s probably broken. (As soon as I started running the session I realized the logic for lights-that-players-had-on-them got rendered on every floor, regardless of which floor the given player was on.) This is just as true for drawing logic, even though it’s a serious pain to test. (My integration tests actually have reference .pngs that get compared pixel-by-pixel to screenshots from a live Chrome window. They’re a bit flaky as a result, but they still cover a lot of stuff.)

I will readily admit this list of lessons is less impressive than some past entries - I have a lot of the basics down for this project, unless I decide to make some serious changes in how I do things, so I’m more in “exploit” mode than “explore” mode regarding my knowledge. On the plus side this does also mean that I get to dig in on more algorithmic challenges, rather than spending days reading about the basic functions I need to pursue an idea.

Remaining Issues

As I mentioned repeatedly above, arcs that cross the 0 / 2π boundary are still an obvious issue. The code has special handling for this in more than one place, and I should find a way to simplify this.

One thing that has been true since I first started rendering lighting was that there’s some slight discrepancies between the spaces that look lit and the spaces that are actually lit, at the edges of the circles. This is because DnD rules simplify everything into 5-foot distances and use a rule-of-thumb that treats a diagonal move as ~7.5 feet when it’s actually 5√2, or ~7.07 feet, so if you draw a circle of a given radius, it won’t perfectly align with the squares that the rules say are within that radius. See these area templates for a comparison.

Also, before working out this light logic, I controlled visibility by having a sort of “fog of war” that obscured player sight, and I used this to manually paint, e.g., the inside of buildings that the players were outside of. Now that I have mostly worked out line-of-sight drawing logic, I should instead just use that to determine what the party can see, but this raises some additional questions, like, if they go into a building, should I take away the exterior map? Even if they can’t see the people outside, they might reasonably assume the buildings are still there, so maybe I have to keep track of which parts of the structure the players have seen (which is a lot more complicated than anything I’m doing right now). Also, if I want to have one set of overlays for light and another for “stuff outside your line of sight”, I probably need to figure out how to differentiate them visually.

Honestly I could continue on like this for a while - the number of useful features for running a DnD game even just to do with visibility is basically endless - so I’ll stop for now and I guess you can look forward to future blog posts where I explain my decisions, assuming the code for it is interesting.


Timothy Bond

2858 Words

2020-10-22 13:00 -0700