Nathaniel Knight

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

Basic Shadow Casting, Part 1

This article is a brief description of a field-of-view algorithm called "shadow casting" with a partial implementation in Python.

Field-of-view calculations are very useful for building grid based, turn based games (things like Brogue, Invisible, Inc, and the XCOM franchise). They can be used to simulate line of sight for the player, as input for non-player characters' AI, for dynamic lighting, etc. While I was learning about shadow casting I was able to find lots of articles describing it and examples of fully realized algorithms, but I wasn't able to find any code that only illustrated the very basics. This article aims to fill that gap, with follow-ups extending the basic code to be more complete.

If you're interested in some of the other approaches to field-of-view in these kinds of games, I found the resources on the Rogue Basin Wiki to be very helpful. This comparison of different field-of-view algorithms was a good overview.

This code was mostly based on the overview of the recursive algorithm I used by Björn Bergström on the Rogue Basin wiki, with reference to Eric Lippert's series series on the topic as well. It implements shadow casting for one eight of a circle; restricting the problem like this lets us focus on the shadow casting algorithm while ignoring some of the trickier details.

import typing as ty

MAPSIZE = 8  # Maximum field-of-view distance


Point = ty.Tuple[int, int]
Map = ty.Set[Point]


def endslope(x: int, y: int) -> float:
    "Top of FoV for the next slope when a scan becomes blocked"
    # When a scan becomes blocked, it should start a scan of the next
    # column that ends with a line through the top left corner of the
    # blocking cell.
    return (y + 0.5) / (x - 0.5)


def startslope(x: int, y: int) -> float:
    "Top of FoV when a scan resumes after being blocked."
    # When a scan becomes unblocked, it resumes scanning from a line
    # that goes through the first open cell's top right corner.
    return (y + 0.5) / (x + 0.5)


def get_fov(obstacles: Map) -> Map:
    "Given a set of obstacles, calculate a field-of-view map."
    visible: Map = set()

    def scan(x: int, maxslope: float, minslope: float) -> None:
        "Scan the portion of a column between minslope and maxslope."
        if x >= MAPSIZE:
            return

        starty = int(x * maxslope)
        endy = max(0, round(x * minslope))

        blocked = (x, starty) in obstacles
        newmax = maxslope

        for y in range(starty, endy - 1, -1):
            if (x, y) in obstacles:
                if not blocked:
                    # When an open section ends,
                    # recursively scan one column deeper
                    blocked = True
                    scan(x + 1, maxslope=newmax, minslope=endslope(x, y))
                else:
                    continue
            else:
                visible.add((x, y))
                if blocked:
                    # When becoming unblocked, remember what slope
                    # we're at for the next scan we start
                    blocked = False
                    newmax = startslope(x, y)
        else:
            if not blocked:
                # If the scan ends blocked, a recursive scan
                # will have been started. If it ends open,
                # we have to resume it in the next column.
                scan(x + 1, maxslope=newmax, minslope=minslope)

    scan(1, 1.0, 0.0)

    return visible


BLACKCHAR = "X"  # out-of-sight
VISCHAR = "."  # visible
WALLCHAR = "#"  # visible, but blocks line-of-sight


def print_maps(maps: ty.Mapping[str, Map]):
    pmap: ty.Dict[Point, str] = dict()
    for x in range(MAPSIZE):
        for y in range(x, -1, -1):
            for c, m in maps.items():
                if (x, y) in m:
                    pmap[(x, y)] = c
    lines: ty.List[str] = list()
    for y in range(MAPSIZE):
        xs = list(range(y, MAPSIZE))
        drawnline = [pmap.get((x, y), BLACKCHAR) for x in xs]
        printedline = " " * y + "".join(drawnline)
        lines.append(printedline)
    print("\n".join(reversed(lines)))


if __name__ == "__main__":
    obstacles = {(4, 1), (4, 2), (5, 1), (5, 2)}
    visible = get_fov(obstacles)
    print_maps({
        "@": {(0, 0)},
        VISCHAR: visible,
        WALLCHAR: obstacles,
    })

The full code is available here.

The next article describes a way to extend this solution to the whole grid using a coordinate transform.