Field of view with symmetric shadowcasting

The r/roguelikedev tutorial series runs every summer, and the week on field of view is where the questions start. Everyone gets something on screen. Then someone notices the orc in the corridor is shooting them from a tile they can't see, and the thread fills up.

I went through the same three versions myself, so let's take them one at a time.

Rogue didn't have one

Rogue had no field of view algorithm at all. A room was either lit or dark. Walk into a lit room and the whole room appears, walls and all. In a dark room you see the eight tiles around you, and in a corridor the same. No rays, no slopes, nothing to compute.

It worked because the levels were made of rectangles. The moment you have a cave or a pillar in a room, lit rooms stop making sense, and you need to know which tiles the player can actually see from where they stand.

Rays

The obvious next step is to draw a line from the player to every tile on the edge of the view and mark what the line touches until it hits a wall. Bresenham gives you the line, the loop is ten lines long, and it looks right the first time.

It isn't right. The line from A to B and the line from B to A don't always pass through the same tiles, because Bresenham rounds, and it rounds from the starting end. So A sees B and B doesn't see A. That's the orc in the corridor. If monsters use the same function, and they should, you get fights where one side has the advantage for no reason the player can see.

The other problem is cost. On a wide map you're drawing hundreds of lines a turn, most of which walk over the same tiles. That's fine for one player and too much for forty monsters.

Shadows

Recursive shadowcasting is the classic answer, written up by Björn Bergström on RogueBasin twenty years ago. Split the view into eight octants. In each one, scan outwards row by row, keeping two slopes: where the visible wedge starts and where it ends. When the scan hits a wall, the wall casts a shadow, and the wedge narrows or splits. Each split becomes a recursive call.

It's fast, because every tile is visited once per octant. And the original version still isn't symmetric. It leans towards showing more rather than less, which makes walls look right and lets you peek around corners a bit further than the corner should allow. Again, the monster peeks back.

Symmetric

Albert Ford wrote up a variant called symmetric shadowcasting, and it's the one I use now. The idea is the same, four quadrants instead of eight, and one extra rule: a floor tile is visible only when its centre falls inside the wedge. Walls are visible when any part of them does. The centre rule is what makes floor to floor visibility symmetric, and the wall rule is what keeps walls from looking chewed up.

Ford's reference code is in Python and uses exact fractions for the slopes. Here it is in TypeScript, with the fractions kept as a numerator and a denominator so that floating point can't round a tie the wrong way.

// src/fov/shadowcast.ts
type Slope = { n: number; d: number }; // the fraction n/d, kept exact on purpose

export function computeFov(
  ox: number,
  oy: number,
  radius: number,
  blocks: (x: number, y: number) => boolean,
  reveal: (x: number, y: number) => void,
): void {
  reveal(ox, oy);

  for (let q = 0; q < 4; q++) {
    // A quadrant counts rows away from the origin and columns across it
    const toMap = (depth: number, col: number): [number, number] => {
      if (q === 0) return [ox + col, oy - depth]; // north
      if (q === 1) return [ox + col, oy + depth]; // south
      if (q === 2) return [ox + depth, oy + col]; // east
      return [ox - depth, oy + col]; // west
    };

    const scan = (depth: number, start: Slope, end: Slope): void => {
      if (depth > radius) return;

      // The columns whose centre lies between the two slopes, ties rounded inwards
      const minCol = Math.floor((2 * depth * start.n + start.d) / (2 * start.d));
      const maxCol = Math.ceil((2 * depth * end.n - end.d) / (2 * end.d));
      let prevWall: boolean | null = null;

      for (let col = minCol; col <= maxCol; col++) {
        const [x, y] = toMap(depth, col);
        const wall = blocks(x, y);

        // Walls show when any part is in the wedge, floor only when its centre is. That is the symmetry.
        const centred = col * start.d >= depth * start.n && col * end.d <= depth * end.n;
        if (wall || centred) reveal(x, y);

        // Floor after wall: the wedge starts here. Wall after floor: the wedge ends, scan the next row with it.
        if (prevWall === true && !wall) start = { n: 2 * col - 1, d: 2 * depth };
        if (prevWall === false && wall) scan(depth + 1, start, { n: 2 * col - 1, d: 2 * depth });
        prevWall = wall;
      }

      if (prevWall === false) scan(depth + 1, start, end);
    };

    scan(1, { n: -1, d: 1 }, { n: 1, d: 1 });
  }
}

blocks has to return true outside the map, or the recursion walks off the edge. The radius is the other stop. The quadrant lambda is the only part that's hard to read: a quadrant works in rows away from the origin and columns across, and toMap turns those back into map coordinates for north, south, east and west.

Now if you can see a monster, it can see you, and the fights feel fair because they are. Monsters run the same function. I give them a smaller radius, and most don't need a full scan every turn, a distance check and a line test when they're close is enough.

The bits around it

The function marks tiles visible. Remembering what the player has seen is a second array, set to true whenever a tile is revealed and never cleared, and it's what you draw in grey. Light sources are a third thing: run the same function from the torch and intersect the two results, visible and lit.

Read more here:

• Symmetric Shadowcasting by Albert Ford, with the Python this is ported from and a diagram for every rule
• FOV using recursive shadowcasting by Björn Bergström on RogueBasin