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