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.