Basic Shadow Casting, Part 2

2019-10-21

In the last article, we looked at a field-of-view algorithm called shadow casting and implemented it for a special case: one octant of a square grid. In this article, we'll expand this partial solution to cover all directions.

The strategy for extending the solution will be to define a mapping between coordinates in the other octants and the one that we already solved and then, for each octant, apply the mapping, run our original algorithm, and map the solution back.

First, let's take a look at the new shadow-casting algorithm. The logic is the same in the previous post, but:

We've changed the coordinate names from x, y to u, v to reflect the fact that the coordinates in this algorithm are being transformed, and don't correspond to actual points in the grid.
The algorithm runs coordinates through a coordinate mapping before checking for blocking cells or coordinates as visible or invisible; we'll look at the OctantTransform class in more detail below.
The original one octant solution is looped over eight octants.

def get_fov(obstacles: Map) -> Map:
    visible: Map = set()

    mapcoord: OctantTransform

    def scan(u: int, maxslope: float, minslope: float) -> None:
        """Apply shaodwcasting a 'column' `u`.

        Map an octant from the map into the coordinates for the first
        octant and apply shadowcasting. The mapping is applied so that
        the shadowcasting algorithm can be kept simple.
        """

        if u >= MAPSIZE:
            return

        startv = int(u * maxslope)
        endv = max(0, round(u * minslope))

        blocked = mapcoord.reverse((u, startv)) in obstacles
        newmax = maxslope

        for v in range(startv, endv - 1, -1):
            uv = (u, v)
            if mapcoord.reverse(uv) in obstacles:
                if not blocked:
                    blocked = True
                    scan(u + 1, maxslope=newmax, minslope=endslope(u, v))
                else:
                    continue
            else:
                if blocked:
                    blocked = False
                    newmax = startslope(u, v)
                    visible.add(mapcoord.reverse(uv))
                else:
                    visible.add(mapcoord.reverse(uv))
        else:
            if not blocked:
                scan(u + 1, maxslope=newmax, minslope=minslope)

    for octant in range(1, 9):
        mapcoord = OctantTransform(octant)
        scan(1, 1.0, 0.0)

    return visible

Next, let's take a look at the OctantTransform class. The octants are numbered from one to eight, starting at the x-axis and going counter-clockwise (an arbitrary arrangement, but one that's was conventional in my math education). We define three transformations that move points around in this space: reflecting points across the X or Y axes, or reflecting points across the line where X = Y. Next, we assign each octant a list of transformations to map it to the first octant, where we can run our algorithm. These mappings have the lovely property that you can run the backwards to map solutions back to their original location.

def reflect_x(p: Point) -> Point:
    u, v = p
    return -u, v


def reflect_y(p: Point) -> Point:
    u, v = p
    return u, -v


def flip_xy(p: Point) -> Point:
    u, v = p
    return v, u


TRANSFORMS: ty.Dict[int, ty.List[PointFn]] = {
    1: [],
    2: [flip_xy],
    3: [flip_xy, reflect_y],
    4: [reflect_x],
    5: [reflect_y, reflect_x],
    6: [flip_xy, reflect_x, reflect_y],
    7: [flip_xy, reflect_x],
    8: [reflect_y],
}


class OctantTransform:
    def __init__(self, octant: int):
        assert octant in range(1, 9), "Invalid octant: {}".format(octant)
        self.octant = octant
        self.transforms: ty.List[PointFn] = TRANSFORMS[octant]

    @classmethod
    def apply_transforms(cls, p: Point, fns: ty.Iterable[PointFn]) -> Point:
        from functools import reduce

        for f in fns:
            p = f(p)
        return p

    def reverse(self, p: Point) -> Point:
        return self.apply_transforms(p, reversed(self.transforms))

    def __call__(self, p: Point) -> Point:
        return self.apply_transforms(p, self.transforms)

The full code (including tests and an improved map-printing function) can be found here.

In the final article, we'll look at adding another transform to let us calculate field-of-view from points other than the origin.

Nathaniel Knight

Reflections, diversions, and opinions from a progressive ex-physicist programmer dad with a sore back.

Basic Shadow Casting, Part 2