Shadowcasting is a common technique for calculating field of view. With the right implementation, it is fast, consistent, and symmetric.
#· #####
#·· #···# ·#####
··· ###····###···### ·······
····················# ······#
····················#
#···@···········#
·························
#················# ······#####
# ###····######·## ····#
#·· ·· ·#
#· ·· ·#·#·#· ····· ·········#····
·###·#· ···· ········
·· ··· ··
· ####
········ ····
············ ####
·###····
·#· ·
·#· · ··· ····
·#·#·#· ········ ······· ####
·#·#·#· ·········· ············ The best way to explain shadowcasting is to show it in action. So here’s the core function of the algorithm. You can step through the code line by line with the slider and buttons below. You can also use the arrow keys to navigate once the slider has focus.
A complete implementation is at the bottom of the page. Click on any function to jump to its definition.
def scan(row):
prev_tile = None
for tile in row.tiles():
if is_wall(tile) or is_symmetric(row, tile):
reveal(tile)
if is_wall(prev_tile) and is_floor(tile):
row.start_slope = slope(tile)
if is_floor(prev_tile) and is_wall(tile):
next_row = row.next()
next_row.end_slope = slope(tile)
scan(next_row)
prev_tile = tile
if is_floor(prev_tile):
scan(row.next())
return @
···
·#···
·······
######·##
······#·#··
·······#·#···
········#·#···· In his excellent Roguelike Vision Algorithms post, Adam Milazzo lists six desirable properties for field of view algorithms:
Symmetric shadowcasting satisfies all six of these properties.
Also: Adam’s post is also where I first saw the idea to use beveled corners. Our final algorithms are very similar, and if you want something more permissive, you should check his article out.
Symmetric shadowcasting has perfect symmetry between floor tiles. If any floor tile A is in the field of view of a floor tile B, then B will always be in the field of view of A. This guarantee is enforced by the is_symmetric function.
As is, the same guarantee doesn't hold for wall tiles. For simplicity, the algorithm assumes the origin tile does not block vision. But if you need to cast field of view from a wall tile (perhaps for a wall-mounted torch), you can get universal symmetry with some simple modifications to the algorithm.
When casting field of view from a floor tile, we model the origin as a point centered in that tile. And when scanning floor tiles, we model them as points centered in the tile (see is_symmetric). But when scanning wall tiles, we model those as diamonds inscribed in the tile (see Row.tiles). So to maintain symmetry, if the origin is a wall tile, we must model it as a diamond.
Now that our origin (A) can be a diamond, it can cast two types of shadows: umbra (B) and penumbra (C). In the penumbra, the origin is partially visible, whereas in the umbra, it cannot be seen at all.
Tiles completely in the umbra obviously should not be in the field of view. But tiles in the penumbra should be in the field of view, for if we don’t include them, then they can see the origin, but not vice versa, thus breaking symmetry.
So here are the modifications for casting field of view from a wall tile:
is_symmetric to strict inequalities.A field of view algorithm has expansive walls if, when standing in a convex room, you can see all the wall tiles of the room. Symmetric shadowcasting has expansive walls.
####### #·····# #@····# #######
###### #·····# #@····# ####
#
### This particular non-expansive walls example comes from a shadowcasting variant that checks is_symmetric for floor and wall tiles alike. That’s a quick and easy way to get symmetry between floor and wall tiles, but it leads to odd-looking room corners, as shown.
Symmetric shadowcasting normally produces expanding pillar shadows. The only exception comes with field of view originating from a wall tile. Then, to maintain expansive walls, pillar shadows must be constant-width.
In many roguelikes, the player can cut diagonally across a corner. If doing so lands them next to a tile they couldn’t see, the corner is a blind corner. Symmetric shadowcasting does not have blind corners.
···@··· ####··· #··· # ··
··· ··· ·
···@··· ####··· # ·· # ·
··· · ··· ··
This example of a blind corner comes from shadowcasting without beveled walls.
This implementation minimizes artifacts by avoiding approximation. It uses rational numbers instead of floating point, and it carefully controls rounding behavior.
Some approximation is inevitable. After all, shadowcasting operates on a grid, not a full Euclidean plane. For the most part, the grid provides intuitive-looking results. The only exception arises around small gaps between walls; sometimes the resulting field of view is discontinuous.
@··# ··# ··· ··· ····· ····· ····· ······ ·
·············
· ··········
····· ····
·······
·········· This particular model comes with a big benefit: it maps exactly to line of sight with Bresenham’s algorithm. So if you can draw an unobstructed line between two floor tiles, they are guaranteed be in each other’s field of view. And if you can’t, they won’t be.
This means applications of line of sight like ranged combat will match field of view. If you can target a tile symmetrically, you can see it, and vice versa.
Shadowcasting tends to perform well compared to other field of view algorithms. If recursion poses a problem, a non-recursive replacement for the scan function is at the end of the page.
import math
from fractions import Fractiondef compute_fov(origin, is_blocking, mark_visible):
mark_visible(*origin)
for i in range(4):
quadrant = Quadrant(i, origin) def reveal(tile):
x, y = quadrant.transform(tile)
mark_visible(x, y)
def is_wall(tile):
if tile is None:
return false
x, y = quadrant.transform(tile)
return is_blocking(x, y)
def is_floor(tile):
if tile is None:
return false
x, y = quadrant.transform(tile)
return not is_blocking(x, y) def scan(row):
prev_tile = None
for tile in row.tiles():
if is_wall(tile) or is_symmetric(row, tile):
reveal(tile)
if is_wall(prev_tile) and is_floor(tile):
row.start_slope = slope(tile)
if is_floor(prev_tile) and is_wall(tile):
next_row = row.next()
next_row.end_slope = slope(tile)
scan(next_row)
prev_tile = tile
if is_floor(prev_tile):
scan(row.next())
first_row = Row(1, Fraction(-1), Fraction(1))
scan(first_row)class Quadrant:
north = 0
east = 1
south = 2
west = 3
def __init__(self, cardinal, origin):
self.cardinal = cardinal
self.ox, self.oy = origin def transform(self, tile):
row, col = tile
if self.cardinal == north:
return (self.ox + col, self.oy - row)
if self.cardinal == south:
return (self.ox + col, self.oy + row)
if self.cardinal == east:
return (self.ox + row, self.oy + col)
if self.cardinal == west:
return (self.ox - row, self.oy + col)class Row:
def __init__(self, depth, start_slope, end_slope):
self.depth = depth
self.start_slope = start_slope
self.end_slope = end_slope def tiles(self):
min_col = round_ties_up(self.depth * self.start_slope)
max_col = round_ties_down(self.depth * self.end_slope)
for col in range(min_col, max_col + 1):
yield (self.depth, col)
def next(self):
return Row(
self.depth + 1,
self.start_slope,
self.end_slope)def slope(tile):
row_depth, col = tile
return Fraction(2 * col - 1, 2 * row_depth)def is_symmetric(row, tile):
row_depth, col = tile
return (col >= row.depth * row.start_slope
and col <= row.depth * row.end_slope)def round_ties_up(n):
return math.floor(n + 0.5)
def round_ties_down(n):
return math.ceil(n - 0.5)def scan_iterative(row):
rows = [row]
while rows:
row = rows.pop()
prev_tile = None
for tile in row.tiles():
if is_wall(tile) or is_symmetric(row, tile):
reveal(tile)
if is_wall(prev_tile) and is_floor(tile):
row.start_slope = slope(tile)
if is_floor(prev_tile) and is_wall(tile):
next_row = row.next()
next_row.end_slope = slope(tile)
rows.append(next_row)
prev_tile = tile
if is_floor(prev_tile):
rows.append(row.next())
origin: an (x, y) tuple. is_blocking(x, y): returns true if the tile at (x, y) blocks vision and false otherwise. mark_visible(x, y): adds the tile at (x, y) to the field of view.
compute_fov, we define some local functions that abstract away the details of quadrants from the scan function. The inputs to reveal, is_wall, and is_floor are (row, col) tuples representing positions relative to the current quadrant. In contrast, the inputs to is_blocking and mark_visible are (x, y) tuples representing absolute coordinates in the grid. Quadrant represents a 90 degree sector pointing north, south, east, or west. Quadrants are traversed row by row. For the east and west quadrants, these “rows” are vertical, not horizontal. (row, col) tuple representing a position relative to the current quadrant into an (x, y) tuple representing an absolute position in the grid. Row represents a segment of tiles bound between a start and end slope. depth represents the distance between the row and the quadrant’s origin. tiles returns an iterator over the tiles in the row. This function considers a tile to be in the row if the sector swept out by the row’s start and end slopes overlaps with a diamond inscribed in the tile. If the diamond is only tangent to the sector, it does not become part of the row. slope calculates new start and end slopes. It’s used in two situations: [1], if prev_tile (on the left) was a wall tile and tile (on the right) is a floor tile, then the slope represents a start slope and should be tangent to the right edge of the wall tile. prev_tile was a floor tile and In both situations, the line is tangent to the left edge of the current tile, so we can use a single slope function for both start and end slopes.
is_symmetric checks if a given floor tile can be seen symmetrically from the origin. It returns true if the central point of the tile is in the sector swept out by the row’s start and end slopes. Otherwise, it returns false. round_ties_up and round_ties_down round n to the nearest integer. If n ends in .5, round_ties_up rounds up and round_ties_down rounds down. Note: round_ties_up is not the same as Python’s round. Python’s round will round away from 0, resulting in unwanted behavior for negative numbers. The full implementation is licensed under CC0.