Symmetric Shadowcasting

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

       #·     #####              
       #··    #···#        ·#####
···  ###····###···###   ·······  
····················# ······#    
        ····················#    
            #···@···········#    
        ·························
   #················# ······#####
   # ###····######·##   ····#    
       #··        ··       ·#    
       #·          ··            
·#·#·#·  ·····     ·········#····
·###·#·   ····     ········      
   ··                ···       ··
                     ·       ####
········                     ····
············                 ####
·###····                         
·#·                  ·           
·#· ·                ···     ····
·#·#·#·   ········  ·······  ####
·#·#·#·  ··········  ············

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

Why shadowcasting?

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.

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

A B C

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:

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

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 = 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 == self.north:


            return (self.ox + col, self.oy - row)


        if self.cardinal == self.south:


            return (self.ox + col, self.oy + row)


        if self.cardinal == self.east:


            return (self.ox + row, self.oy + col)


        if self.cardinal == self.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())
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.