Nathaniel Knight

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

Basic Shadow Casting, Part 3

This is the final article in a series about shadow casting. The first article covered a solution that worked for a portion of the field of view. The second article extended the solution to cover the whole field of view.

The solutions in previous articles always checked line-of-sight to the grid's origin (with x,y coordinate 0,0).This article will finish the solution by adding the ability to check line-of-sight for any point in the grid. Our strategy will be to add a transformation to the algorithm that changes its starting point, much like we did to solve the problem of covering different directions.

Some changes to the code are highlighted here; the full code is available here.

To begin, we define a base transformation class so that we can handle transformations generically.

import abc


class BaseTransform(abc.ABC):
    @abc.abstractmethod
    def __call__(self, p: Point) -> Point:
        raise NotImplementedError

    @abc.abstractmethod
    def reverse(self, p: Point) -> Point:
        raise NotImplementedError

Because it already implements this interface, the OctantTransform from the previous article can inherit this base class without other changes.

Next, we define an OffsetTransform class that will let us move points around by specifying x and y offsets as a Point.

class OffsetTransform(BaseTransform):
    def __init__(self, offset: Point) -> None:
        self._offset = offset

    def __call__(self, p: Point) -> Point:
        dx, dy = self._offset
        x, y = p
        return (x + dx, y + dy)

    def reverse(self, p: Point) -> Point:
        dx, dy = self._offset
        x, y = p
        return (x - dx, y - dy)

One final transform: because we want to combine an offset transform and the original octant transform, we'll define a CompoundTransform that takes a list of transformations and applies them together.

import functools


class CompoundTransform(BaseTransform):
    def __init__(self, transforms: ty.Iterable[BaseTransform]) -> None:
        self._transforms = list(transforms)
        self._reversed_transforms = list(reversed(self._transforms))

    def __call__(self, p: Point) -> Point:
        return functools.reduce(lambda p, t: t(p), self._transforms, p)

    def reverse(self, p: Point) -> Point:
        return functools.reduce(
            lambda p, t: t.reverse(p), self._reversed_transforms, p
        )

Putting these together (with some of the code from previous articles) our shadow casting function can now take a Point to calculate field of view from. Each for each octant we combine the offset transformation with the octant transformation.

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

    orig_x, orig_y = frompoint
    origintransform = OffsetTransform((-orig_x, -orig_y))

    mapcoord: BaseTransform

    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 = CompoundTransform(
            [origintransform, OctantTransform(octant)]
        )
        scan(1, 1.0, 0.0)

    return visible

With that final addition, our shadow casting code can now calculate field-of-view relatively efficiently for any point in our map. Hopefully working through this series has helped you get a sense of how the algorithm works.

Depending on your application, you might want to investigate things like tuning the view distance, how it interacts with different geometries, and how it changes if you tune different parameters. Those decisions will depend on your application, so I'll leave them to you.

An index of code listings for this series, as well as a fleshed out example with tests and a demonstration using bearlibterminal is available on GitHub.

Thanks for your attention. 😊