Symmetric Shadowcasting

Shadowcasting is a common technique for calculating field of view. With the right implementation, it is fast, consistent, and symmetric.

Show outlines
#· #####
#·· #···# ·#####
··· ###····###···### ·······
····················# ······#
····················#
#···@···········#
·························
#················# ······#####
# ###····######·## ····#
#·· ·· ·#
#· ··

·#·#·#· ····· ·········#····

·###·#· ···· ········
·· ··· ··
· ####
········ ····
············ ####
·###····
·#· ·
·#· · ··· ····
·#·#·#· ········ ······· ####
·#·#·#· ·········· ············

Click and drag to edit the grid.

How it works
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 [Link]():

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 = [Link]()

next_row.end_slope = slope(tile)

scan(next_row)

prev_tile = tile

if is_floor(prev_tile):

scan([Link]())

return

···
·#···
·······
######·##
······#·#··
·······#·#···
········#·#····

< >
In the grid above, the pink dashed lines show the current start and end slopes. The white box outlines the current row. The black square tracks the current tile.

Why shadowcasting?
In his excellent Roguelike Vision Algorithms post, Adam Milazzo lists six desirable properties for field of view algorithms:

Symmetry
Expansive walls
Expanding pillar shadows
No blind corners
No artifacts
Efficiency

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.

Symmetry
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 [Link]). 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.

A B
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:

Make slopes originate from the edges of the tile instead of the center.
Change the comparisons in is_symmetric to strict inequalities.

Field of view from a wall tile

Field of view from a floor tile

Expansive walls
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.
#######
#·····#
#@····#
#######

Expansive walls
######
#·····#
#@····#
####

###

Non-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.

Expanding pillar shadows

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.
@······
·#·····
·· ···
·· ·
···

··
····
····

Expanding shadows
@······
·#·····
·· ····
··· ···
···· ··

·
·
·

Constant-width shadows

No blind corners
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.
···@···
####···
#···
# ··

···
··· ·

Safe corner
···@···
####···
# ··
# ·

··· ·
··· ··

Blind corner

This example of a blind corner comes from shadowcasting without beveled walls.

No artifacts
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.

Efficiency
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.

Prior art and other resources

Roguelike Vision Algorithms, as mentioned earlier
Adam Milazzo’s list of desirable properties may have originated with PaulBlay’s similar list
Roguebasin’s Discussion:Field of Vision is a great resource for comparing different possible algorithms. This variant of shadowcasting follows the diamond walls, point visibility model
with additional floor-wall symmetry rules to create expansive walls.
Björn Bergström wrote a great article explaining how recursive shadowcasting works.
/r/roguelikedev has a couple FAQ Fridays on the subject of field of view: one, two.

Full implementation
import math

from fractions import Fraction

def compute_fov(origin, is_blocking, mark_visible):

mark_visible(*origin)

for i in range(4):

quadrant = Quadrant(i, origin)

def reveal(tile):

x, y = [Link](tile)

mark_visible(x, y)

def is_wall(tile):

if tile is None:

return False

x, y = [Link](tile)

return is_blocking(x, y)

def is_floor(tile):

if tile is None:

return False

x, y = [Link](tile)

return not is_blocking(x, y)

def scan(row):

prev_tile = None

for tile in [Link]():

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 = [Link]()

next_row.end_slope = slope(tile)

scan(next_row)

prev_tile = tile

if is_floor(prev_tile):

scan([Link]())

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):

[Link] = cardinal

[Link], [Link] = origin

def transform(self, tile):

row, col = tile

if [Link] == [Link]:

return ([Link] + col, [Link] - row)

if [Link] == [Link]:

return ([Link] + col, [Link] + row)

if [Link] == [Link]:

return ([Link] + row, [Link] + col)

if [Link] == [Link]:

return ([Link] - row, [Link] + col)

class Row:

def __init__(self, depth, start_slope, end_slope):

[Link] = depth

self.start_slope = start_slope

self.end_slope = end_slope

def tiles(self):

min_col = round_ties_up([Link] * self.start_slope)

max_col = round_ties_down([Link] * self.end_slope)

for col in range(min_col, max_col + 1):

yield ([Link], col)

def next(self):

return Row(

[Link] + 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 >= [Link] * row.start_slope

and col <= [Link] * row.end_slope)

def round_ties_up(n):

return [Link](n + 0.5)

def round_ties_down(n):

return [Link](n - 0.5)

def scan_iterative(row):

rows = [row]

while rows:

row = [Link]()

prev_tile = None

for tile in [Link]():

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 = [Link]()

next_row.end_slope = slope(tile)

[Link](next_row)

prev_tile = tile

if is_floor(prev_tile):

[Link]([Link]())

The entrypoint to the program. Call this function to compute the field of view from an origin tile.

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.

Within 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.
Scan a row and recursively scan all of its children. If you think of each quadrant as a tree of rows, this essentially is a depth-first tree traversal.
A 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.
Convert a (row, col) tuple representing a position relative to the current quadrant into an (x, y) tuple representing an absolute position in the grid.
A 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.

[1]

[2]

[2], if prev_tile was a floor tile and tile is a wall tile, then the slope represents an end slope and should be tangent to the left edge of the wall tile.

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.
Non-recursive version of the algorithm.

The full implementation is licensed under CC0.