2D shadowcasting for torchlight, fog of war and line of sight
Torchlight that stops at walls, fog of war and enemy line of sight, all from one roguelike algorithm. With tested Python and Godot code and the pitfalls.
A plain radial light in a top-down game lights everything inside its radius, walls included. Your torch lights up the room next door and the chest in a vault that has no door. Shadowcasting works out which cells the light can reach. It comes from roguelikes, it's cheap enough to run every frame, and the same function gives you fog of war and enemy line of sight.
Same dungeon, same light radius and colors on both. The top lights every pixel inside the radius. The bottom only lights the pixels shadowcasting marks as visible from the torch. The walls are a 16 px SpriteCook tileset on a dual grid, and the hero is a pixel engine sprite with a generated walk cycle.
How it works
Split the area around the light into 8 slices of 45 degrees. Every slice is scanned the same way, so you write the scan once and flip the x and y steps for the other seven.
Inside a slice you go row by row, moving away from the light. Each row only looks at the cells between two slopes, the edges of what the light can still reach. When a row hits a wall, the next row gets the open part up to that wall, and the scan carries on past the wall with a narrower range. Whatever falls behind a wall drops out of every row after it.
The red lines go from the light through the outer corners of each wall. Those are the slopes the scan narrows to, and everything between them is in shadow.
This is Björn Bergström's recursive shadowcasting from RogueBasin. The version below swaps the recursion for a stack, with the same result.
The code
walls is a 2D grid of booleans, true where light can't pass. That can be your tile map, or the pixels of your wall layer. The function returns a grid of the same size with every cell the light can see.
# The 8 slices around the light, as (xx, xy, yx, yy): how a step along a row and a row further out map to x and y.
OCTANTS = [(1, 0, 0, 1), (0, 1, 1, 0), (0, -1, 1, 0), (-1, 0, 0, 1),
(-1, 0, 0, -1), (0, -1, -1, 0), (0, 1, -1, 0), (1, 0, 0, -1)]
def shadowcast(walls, cx, cy, radius):
"""Cells the light at (cx, cy) can see. walls[y][x] is True where light can't pass.
Recursive shadowcasting (Bjorn Bergstrom, 2001), with a stack instead of recursion."""
h, w = len(walls), len(walls[0])
seen = [[False] * w for _ in range(h)]
seen[cy][cx] = True
for xx, xy, yx, yy in OCTANTS:
stack = [(1, 1.0, 0.0)] # (first row, start slope, end slope)
while stack:
row, start, end = stack.pop()
if start < end:
continue
new_start = 0.0
for j in range(row, radius + 1): # rows, moving away from the light
dy = -j
blocked = False
for dx in range(-j, 1): # cells in the row, from the outer edge in
left = (dx - 0.5) / (dy + 0.5)
right = (dx + 0.5) / (dy - 0.5)
if start < right:
continue # not in the open range yet
if end > left:
break # past it
x, y = cx + dx * xx + dy * xy, cy + dx * yx + dy * yy
inside = 0 <= x < w and 0 <= y < h
if inside and dx * dx + dy * dy < radius * radius:
seen[y][x] = True
wall = not inside or walls[y][x]
if blocked:
if wall:
new_start = right # still in the wall
else:
blocked = False # out of it: carry on with the narrower range
start = new_start
elif wall and j < radius:
blocked = True # a wall starts: the next row gets the open part before it
stack.append((j + 1, start, left))
new_start = right
if blocked:
break # the row ended in a wall, nothing further out is lit
return seen
On a 368 x 176 pixel map with a radius of 92, plain Python takes about 4 ms per call. A Numba port of the same loop runs in about 0.04 ms, which is what the video above uses.
In Godot
The same function in GDScript. from_image turns a wall layer drawn into an Image into the byte grid (opaque means wall). For a TileMapLayer, set a byte to 1 for every cell where get_cell_source_id(cell) isn't -1.
# shadowcast.gd: which cells a light (or an enemy's eyes) at `origin` can see.
# Use: var seen := Shadowcast.visible(Shadowcast.from_image(wall_image), size, origin, radius)
class_name Shadowcast
extends RefCounted
# The 8 slices around the light, as [xx, xy, yx, yy].
const OCTANTS := [[1, 0, 0, 1], [0, 1, 1, 0], [0, -1, 1, 0], [-1, 0, 0, 1],
[-1, 0, 0, -1], [0, -1, -1, 0], [0, 1, -1, 0], [1, 0, 0, -1]]
# One byte per pixel, row by row: 1 where the image is opaque (a wall), 0 where it's transparent.
static func from_image(img: Image) -> PackedByteArray:
var walls := PackedByteArray()
walls.resize(img.get_width() * img.get_height())
for y in img.get_height():
for x in img.get_width():
walls[y * img.get_width() + x] = 1 if img.get_pixel(x, y).a > 0.0 else 0
return walls
# Returns the same layout as walls, with 1 for every cell the origin can see.
static func visible(walls: PackedByteArray, size: Vector2i, origin: Vector2i, radius: int) -> PackedByteArray:
var w := size.x
var h := size.y
var seen := PackedByteArray()
seen.resize(w * h)
seen[origin.y * w + origin.x] = 1
for o in OCTANTS:
var stack := [[1, 1.0, 0.0]] # [first row, start slope, end slope]
while not stack.is_empty():
var item: Array = stack.pop_back()
var start: float = item[1]
var end: float = item[2]
if start < end:
continue
var new_start := 0.0
for j in range(item[0], radius + 1): # rows, moving away from the light
var dy := -j
var blocked := false
for dx in range(-j, 1): # cells in the row, from the outer edge in
var left := (dx - 0.5) / (dy + 0.5)
var right := (dx + 0.5) / (dy - 0.5)
if start < right:
continue
if end > left:
break
var x: int = origin.x + dx * o[0] + dy * o[1]
var y: int = origin.y + dx * o[2] + dy * o[3]
var inside := x >= 0 and x < w and y >= 0 and y < h
if inside and dx * dx + dy * dy < radius * radius:
seen[y * w + x] = 1
var wall := not inside or walls[y * w + x] == 1
if blocked:
if wall:
new_start = right
else:
blocked = false # out of the wall: carry on with the narrower range
start = new_start
elif wall and j < radius:
blocked = true # the next row gets the open part before the wall
stack.append([j + 1, start, left])
new_start = right
if blocked:
break
return seen
It runs as is in Godot 4.6, and its results match the Python version cell for cell, on 360 calls per pixel and 360 per tile on this map. Per tile (23 x 11 cells) a call takes about 0.04 ms. Per pixel (368 x 176) it's about 1.6 ms, so in GDScript only run it when the light moves to a new pixel, or port it to C#.
Turn it into light
Multiply your light's falloff by the visible grid. Anything the light can't see gets nothing.
import numpy as np
from scipy import ndimage
walls = np.asarray(walls, bool)
seen = np.array(shadowcast(walls.tolist(), lx, ly, radius))
seen |= walls & ndimage.binary_dilation(seen, iterations=5) # light the wall tops 5 px deep
yy, xx = np.mgrid[0:seen.shape[0], 0:seen.shape[1]]
t = np.clip(1 - np.hypot(xx - lx, yy - ly) / radius, 0, 1) ** 0.8
light = np.ceil(t * 6) / 6 * seen # 6 bands, 0 where the torch can't see
lit = scene * (ambient + light[..., None] * torch_color) # scene: the map as an RGB float array
In an engine, write light into a texture and multiply your scene by it in a shader. Godot's own 2D lights can also cast shadows from LightOccluder2D polygons. Shadowcasting is the grid version, and it hands you the visible cells as data, which the next two sections need.
Fog of war
Keep a second grid of everything the player has seen so far. Every time the light moves, add the visible cells to it. Draw unexplored cells black, explored cells that are out of sight dark and gray, and the rest lit.
explored = np.zeros_like(walls) # once, when the level loads
explored |= seen # every time the light moves
image = lit.copy()
fog = explored & ~seen
image[fog] = scene[fog].mean(-1, keepdims=True) * (0.30, 0.32, 0.40) # seen before: dark, gray-blue
image[~explored] = 0 # never seen: black
Enemy line of sight
Run the same function from the enemy's eyes, with its sight range as the radius. If the player's cell is in the result, the enemy can see them.
sight = shadowcast(walls.tolist(), enemy_x, enemy_y, sight_range)
if sight[player_y][player_x]:
enemy_sees_player = True
Common pitfalls
The light starts inside a wall. Then the cells around it are walls too, every slice stops at the first row, and the light only reaches its 8 neighbors. A torch held out in front in a 3/4 view can end up there when the hero hugs a wall. Move the light to the nearest floor cell before you cast.
Per tile when the art isn't on the tile grid. Per-tile visibility scaled up to pixels gives square light with straight edges that cut through the drawn walls, more so with dual-grid tiles, which sit half a tile off the grid. Per pixel follows the walls you drew.
Dark wall tops. Only the first wall pixel along each line counts as seen, so a wall facing the light gets a 1 px lit edge. Spread the light a few pixels into the walls it touches, like the binary_dilation line in the light code.
One-way sight. This version isn't symmetric. A can see B while B can't see A. On this map's tile grid, 16% of the pairs that see each other only see one way (2.6% per pixel). For lighting nobody notices. For enemy sight, cast from the enemy, as above, or use Albert Ford's symmetric shadowcasting so stealth plays fair both ways.
Where to next
- Dual-grid tilesets, explained, how the dungeon walls are placed
- Make a top-down tileset that actually tiles, for the floor and walls
- Animate a custom sprite, for a walk cycle like the hero's
- 2D water shorelines with a distance field, another trick where one map drives the whole look