Roguelike #3: FOV with recursive shadowcasting

The previous roguelike used a simple raycasting FOV — cast N rays from the player, mark tiles hit. Fast to implement, wrong output. You get arc-shaped FOV edges instead of true shadow boundaries, and thin walls cast no shadow.

Recursive shadowcasting (Björn Bergström’s algorithm) fixes both. It operates per octant — eight sectors around the player — and recurses through columns of tiles, tracking the slope of the current shadow. Any tile that falls in shadow gets skipped.

The GDScript implementation is ~120 lines. The hard part isn’t the algorithm, it’s the coordinate system.

func compute_fov(origin: Vector2i, radius: int) -> void:
    visible_tiles.clear()
    visible_tiles.add(origin)
    
    for octant in range(8):
        _cast_light(origin, radius, 1, 1.0, 0.0, octant)

func _cast_light(origin: Vector2i, radius: int, row: int,
                 start_slope: float, end_slope: float, octant: int) -> void:
    if start_slope < end_slope:
        return
    
    var next_start = start_slope
    for col in range(row, radius + 1):
        var blocked = false
        for dx in range(-col, 1):
            var dy = -col
            var l_slope = (dx - 0.5) / (dy + 0.5)
            var r_slope = (dx + 0.5) / (dy - 0.5)
            if start_slope < r_slope:
                continue
            if end_slope > l_slope:
                break
            
            var pos = _transform_octant(origin, dx, dy, octant)
            if _in_bounds(pos):
                if origin.distance_to(pos) <= radius:
                    visible_tiles.add(pos)
                
                if blocked:
                    if _is_wall(pos):
                        next_start = r_slope
                    else:
                        blocked = false
                        start_slope = next_start
                else:
                    if _is_wall(pos) and col < radius:
                        blocked = true
                        _cast_light(origin, radius, col + 1, start_slope, l_slope, octant)
                        next_start = r_slope
        
        if blocked:
            break

The three attempts:

1. Got the octant transforms wrong — FOV was mirrored in two quadrants.
2. Off-by-one in the slope comparison — thin corridors were sometimes fully dark.
3. This version. Correct.

The octant transform is where most implementations trip up. There are eight transforms (reflections and rotations) and they’re easy to get subtly wrong. I wrote a test that generates FOV from the center of a 15×15 room with no walls and verified all visible tiles are symmetric.

Memory-wise: the visible set is rebuilt every turn, which is fast enough (map is 80×80 max, tile count is bounded). If performance became an issue, a dirty-region approach would be the next step.