What is the fastest way to compute field of view on a grid?

Recursive shadowcasting is the fastest correct way to compute field of view on a grid: 4.5 µs per call at radius 16 on a 256x256 map with 10% walls. That is about 3x faster than casting a Bresenham line to every cell, and it missed 0 of the 6,759 truly visible cells where the lines missed 959. Perimeter rays were within about 15% of its speed either way, depending on the run, and missed 551. The surprise was in the shadowcaster itself. The version most people copy has an inverted-wedge bug that showed 260 cells through solid walls in that test. A one-line guard cut that to 36 and made the function faster.

Hardware: Apple M3, 16 GB, macOS 26.4.1. Node v23.5.0, no packages. Other benchmarks were running on the same machine (load average 10 to 13), so every timing is a median and the ratios matter more than the microseconds. Every method was timed in its own Node process, in five rounds with the order rotated.

The short answer

• Shadowcasting was the only fast method with zero misses. Across all 24 combinations of grid size, wall density and radius, it failed to show a truly visible cell 0 times. Bresenham-to-every-cell missed up to 22.5% of visible cells. Perimeter rays missed up to 10.6%.
• Its speed advantage grows as walls get denser. At radius 32 on 256x256 with 40% walls, it was 37x faster than a line to every cell and 4.5x faster than perimeter rays. On an empty map it was only 1.3x faster than perimeter rays.
• Perimeter rays are not "good enough" at radius 32. With 10% walls they missed 10.6% of visible cells and showed another 23.4% through walls.
• The copied RogueBasin shadowcaster leaks. At radius 32 with 10% walls it showed 1,083 cells that no line of sight can reach, even with walls shrunk by 2%. Adding if (start < end) return after the wedge is reopened cut that to 98 and made each call faster: 1.16x in the full benchmark, 1.65x in the check script below.
• Symmetry is not a proxy for correctness. The method that misses the most cells, a line to every cell, was the most symmetric. The ground-truth definition itself was the least.

How was it measured?

Four methods, all written by hand:

1. Bresenham to every cell. Walk a line from the origin to each cell in the radius. The cell is visible if no wall sits between them.
2. Perimeter rays. Walk a Bresenham line to each cell on the edge of the view square. Light every cell on the way and stop at the first wall or at the radius.
3. Recursive shadowcasting, 8 octants. A line-for-line port of the RogueBasin Python version that most tutorials copy, plus the same code with the guard.
4. A reference, used only as ground truth. A cell counts as visible if any straight segment from the centre of the origin cell to any point on the target square avoids the inside of every wall. The script tests 32 points per side facing the origin, then 512 per side for anything still hidden, with an exact grid walk for each segment. It is thousands of times too slow for a game and is never timed.

Grids were 64x64 and 256x256 with 0%, 10%, 25% and 40% random walls from a seeded generator. The view radius was 8, 16 and 32, with circular distance measured between cell centres. Each setting used 20 seeded origins on floor cells. Walls that are visible count as visible, as in most roguelikes.

A "false positive" against the reference can mean two different things. Some cells are seen only through the exact point where two diagonal walls touch. That is a convention, and many games want it. Others are seen straight through a wall. To separate them, every false positive was re-tested against a reference with every wall shrunk by 2% of a cell. The table below calls the ones that stay hidden through solid walls.

Which method is fastest?

Median microseconds per call on 256x256, five rounds. The 64x64 grids gave the same ordering.

The cost curves explain the table. A line to every cell does work proportional to the radius cubed: on the empty map it read 58,269 cells at radius 32. Perimeter rays do work proportional to the radius squared, and read 7,071. Shadowcasting only reads cells that are lit, plus the walls at their edges, so it read 4,480. Add walls and shadowcasting's work falls off a cliff: 91.5 cells at radius 32 with 40% walls, against 676 for perimeter rays.

At low wall density and a small radius, perimeter rays were as fast or slightly faster: 0.95x of the guarded shadowcaster at radius 8 with 10% walls. That is inside the noise on a loaded machine. If speed were the only question, a small radius would make the choice a coin toss.

Does shadowcasting's advantage survive at 40% walls?

We expected dense walls to narrow the gap, since every method gets cheaper when the view is blocked early. It went the other way. Perimeter rays still cast every ray, and each one stops at its first wall. Shadowcasting stops scanning whole wedges, so it barely does any work at all. Going from 10% to 40% walls at radius 32, the guarded shadowcaster's time fell from 9.93 µs to 0.84 µs. Perimeter rays only fell from 10.88 µs to 3.79 µs.

Which method shows cells it should not?

Correctness at radius 32 on 256x256, summed over 20 origins. Percentages are of truly visible cells.

Both shadowcasters missed 0 visible cells in every row. With no walls, every method matched the reference exactly.

The ray methods fail in opposite ways. A line to every cell is too strict: Bresenham picks one staircase of cells, and if a wall sits on that staircase the target is hidden, even when a slightly different line would reach it. Perimeter rays are too loose. A long ray takes diagonal steps between two walls that touch at a corner and lights whatever lies beyond. That leak grew with density, up to 40.6% of visible cells at 25% walls.

What is wrong with the shadowcaster everyone copies?

We did not expect a bug here, and at first we assumed our reference was wrong. Dumping one false positive showed otherwise. The origin had a wall right beside it. That wall leaves a lit wedge of zero width along the diagonal. Further out, a diagonal wall is followed by a floor cell, and the code resets start to the wall's far-corner slope, 0.778. But end was 1.0. The wedge is now inside out. The function only checks start < end on entry, so it carries on into the next row and lights cells behind a solid wall.

The fix is one line, right after the reset:

blocked = false; start = newStart
if (start < end) return   // the wedge closed; nothing further out is lit

It also saves work. At radius 32 with 10% walls, the guarded version read 784 cells instead of 860, and ran in 9.93 µs instead of 11.53.

About 14.5% of visible cells were still shown with no true line of sight at radius 16 with 10% walls. Almost all of those are seen through a zero-width corner gap. If your game should not let players peek between diagonal walls, that is a rule to add on top, not a bug in the algorithm.

How symmetric is each method?

Symmetry matters for stealth and tactics: if the guard can see the player, the player expects to see the guard. We tested 500 seeded pairs of floor cells per setting. For each method we counted the pairs where one direction sees and the other does not, as a share of pairs where at least one direction sees.

At radius 16 on 256x256 with 10% walls: line to every cell 9.9%, perimeter rays 19.7%, guarded shadowcasting 28.6%, and the reference itself 31.5%. The reference is asymmetric by definition: it looks from a point to an area, and the reverse looks from a different point to a different area. So the line method's symmetry is a side effect of how it works, not a sign that it is accurate. If you need guaranteed symmetry, choose an algorithm designed for it. Do not assume it comes with the fastest one. These counts are small, 232 to 318 pairs where at least one side sees at 10% walls and as few as 26 at 40%, so read them as rough.

What does it cost for 50 units per turn?

Calculated from the measured medians, not measured directly. At radius 16 on 256x256 with 10% walls, 50 guarded shadowcasts take 50 x 4.52 µs = 0.23 ms. The line to every cell takes 0.67 ms. The worst setting in the table, radius 32 with no walls, costs 1.17 ms for shadowcasting and 7.4 ms for a line to every cell. That is 44% of a 16.67 ms frame, spent before anything is drawn. A turn-based game will never notice. A real-time stealth game that recomputes every unit every frame will.

The spike pattern is the same one we measured in pathfinding when there is no path: cost follows the map's open space, so a player knocking down walls makes vision more expensive. The walls-as-bytes layout used here is the flat array from how to store a big tilemap. For deciding which units need a vision check at all, see the collision broadphase measurements.

Check it yourself

Save as fov-check.cjs and run node fov-check.cjs. It takes about 3 seconds. The correctness counts reproduce exactly from the seeds. The timings run each method in its own child process and will vary with your machine and its load.

// fov-check.cjs — node fov-check.cjs   (no packages; ~3 s)
// 256x256 grid, 10% random walls (seeded), view radius 16, 20 seeded origins.
// Correctness counts are exact and reproduce. Timings run each method in its own child process.
const { execFileSync } = require('child_process')
const W = 256, DENS = 0.10, R = 16, NORIG = 20, SEED = 256017

function rng(a){return()=>{a|=0;a=a+0x6D2B79F5|0;let t=Math.imul(a^a>>>15,1|a);t=t+Math.imul(t^t>>>7,61|t)^t;return((t^t>>>14)>>>0)/4294967296}}
const G = new Uint8Array(W*W), MARK = new Uint32Array(W*W); let STAMP = 0
{ const r = rng(SEED); for (let i = 0; i < W*W; i++) G[i] = r() < DENS ? 1 : 0 }
const O = []; { const r = rng(SEED+1); while (O.length < NORIG*2) { const x = (r()*W)|0, y = (r()*W)|0; if (!G[y*W+x]) O.push(x, y) } }

function bresenhamAll(ox, oy, r) {           // (a) a line to every cell in the radius
  STAMP++; MARK[oy*W+ox] = STAMP
  for (let ty = Math.max(0, oy-r); ty <= Math.min(W-1, oy+r); ty++)
    for (let tx = Math.max(0, ox-r); tx <= Math.min(W-1, ox+r); tx++) {
      const dx = tx-ox, dy = ty-oy
      if (dx*dx+dy*dy > r*r || (!dx && !dy)) continue
      const ax = Math.abs(dx), ay = Math.abs(dy), sx = Math.sign(dx), sy = Math.sign(dy)
      let x = ox, y = oy, err = ax-ay, open = true
      for (;;) { const e2 = 2*err
        if (e2 > -ay) { err -= ay; x += sx } if (e2 < ax) { err += ax; y += sy }
        if (x === tx && y === ty) break
        if (G[y*W+x]) { open = false; break } }
      if (open) MARK[ty*W+tx] = STAMP
    }
}
function perimeterRays(ox, oy, r) {          // (b) lines to the square's edge only
  STAMP++; MARK[oy*W+ox] = STAMP
  const ray = (tx, ty) => {
    const dx = tx-ox, dy = ty-oy, ax = Math.abs(dx), ay = Math.abs(dy), sx = Math.sign(dx), sy = Math.sign(dy)
    let x = ox, y = oy, err = ax-ay
    for (;;) { const e2 = 2*err
      if (e2 > -ay) { err -= ay; x += sx } if (e2 < ax) { err += ax; y += sy }
      if (x < 0 || y < 0 || x >= W || y >= W || (x-ox)**2+(y-oy)**2 > r*r) return
      MARK[y*W+x] = STAMP
      if (G[y*W+x] || (x === tx && y === ty)) return }
  }
  for (let i = -r; i <= r; i++) { ray(ox+i, oy-r); ray(ox+i, oy+r) }
  for (let j = -r+1; j < r; j++) { ray(ox-r, oy+j); ray(ox+r, oy+j) }
}
const M = [[1,0,0,-1,-1,0,0,1],[0,1,-1,0,0,-1,1,0],[0,1,1,0,0,-1,-1,0],[1,0,0,1,-1,0,0,-1]]
function makeShadowcast(guard) {             // (c) recursive shadowcasting, RogueBasin form
  function cast(cx, cy, row, start, end, r, xx, xy, yx, yy) {
    if (start < end) return
    let newStart = 0
    for (let j = row; j <= r; j++) {
      let dx = -j-1, blocked = false; const dy = -j
      while (dx <= 0) {
        dx++
        const X = cx + dx*xx + dy*xy, Y = cy + dx*yx + dy*yy
        const l = (dx-0.5)/(dy+0.5), rs = (dx+0.5)/(dy-0.5)
        if (start < rs) continue; else if (end > l) break
        const inb = X >= 0 && Y >= 0 && X < W && Y < W
        if (inb && dx*dx+dy*dy <= r*r) MARK[Y*W+X] = STAMP
        const wall = !inb || G[Y*W+X] === 1
        if (blocked) {
          if (wall) { newStart = rs; continue }
          blocked = false; start = newStart
          if (guard && start < end) return      // <- the one-line fix: the wedge just inverted
        } else if (wall && j < r) { blocked = true; cast(cx, cy, j+1, start, l, r, xx, xy, yx, yy); newStart = rs }
      }
      if (blocked) break
    }
  }
  return (ox, oy, r) => { STAMP++; MARK[oy*W+ox] = STAMP
    for (let o = 0; o < 8; o++) cast(ox, oy, 1, 1, 0, r, M[0][o], M[1][o], M[2][o], M[3][o]) }
}
const METHODS = { 'bresenham to every cell': bresenhamAll, 'perimeter rays': perimeterRays,
  'shadowcasting as copied': makeShadowcast(false), 'shadowcasting + guard': makeShadowcast(true) }

// (d) Ground truth only, far too slow for a game: visible if ANY segment from the origin cell's centre
// to a point on the target square misses every wall interior. Sampled at 32, then 512 points per side.
let SHRINK = 0
function hitsBox(x0, y0, dx, dy, a0, b0, a1, b1) {
  let t0 = 0, t1 = 1
  for (const [p, d, lo, hi] of [[x0, dx, a0, a1], [y0, dy, b0, b1]]) {
    if (d === 0) { if (p <= lo || p >= hi) return false; continue }
    let a = (lo-p)/d, b = (hi-p)/d; if (a > b) [a, b] = [b, a]
    t0 = Math.max(t0, a); t1 = Math.min(t1, b)
  }
  return t0 < t1
}
function segClear(ox, oy, px, py, tx, ty) {
  const dx = px-ox-0.5, dy = py-oy-0.5, stX = dx > 0 ? 1 : -1, stY = dy > 0 ? 1 : -1
  const tdx = dx ? Math.abs(1/dx) : Infinity, tdy = dy ? Math.abs(1/dy) : Infinity
  let mx = 0.5*tdx, my = 0.5*tdy, x = ox, y = oy
  for (let s = 0, lim = Math.abs(tx-ox)+Math.abs(ty-oy)+2; s < lim; s++) {
    if (mx < my) { x += stX; mx += tdx } else { y += stY; my += tdy }
    if (x === tx && y === ty) return true
    if (G[y*W+x] && (!SHRINK || hitsBox(ox+0.5, oy+0.5, dx, dy, x+SHRINK, y+SHRINK, x+1-SHRINK, y+1-SHRINK))) return false
  }
  return false
}
function sees(ox, oy, tx, ty, n) {
  const E = 1e-4, dx = tx-ox, dy = ty-oy
  for (let k = 0; k < n; k++) { const u = (k+0.37)/n
    if (dx && segClear(ox, oy, dx > 0 ? tx+E : tx+1-E, ty+u, tx, ty)) return true
    if (dy && segClear(ox, oy, tx+u, dy > 0 ? ty+E : ty+1-E, tx, ty)) return true }
  return false
}
const truth = (ox, oy, tx, ty) => (ox === tx && oy === ty) || sees(ox, oy, tx, ty, 32) || sees(ox, oy, tx, ty, 512)
const throughCornerOnly = (ox, oy, tx, ty) => { SHRINK = 0.02; const v = sees(ox, oy, tx, ty, 512); SHRINK = 0; return v }

const median = a => { const s = [...a].sort((x, y) => x-y); return s[s.length >> 1] }

if (process.argv[2] === 'time') {             // child process: time one method
  const fn = METHODS[process.argv[3]], out = []
  for (let w = 0; w < 5; w++) for (let i = 0; i < NORIG; i++) fn(O[2*i], O[2*i+1], R)
  for (let round = 0; round < 5; round++) for (let i = 0; i < NORIG; i++) {
    const t0 = performance.now(); for (let q = 0; q < 200; q++) fn(O[2*i], O[2*i+1], R)
    out.push((performance.now()-t0)/200)
  }
  process.stdout.write(String(median(out)))
  return
}

console.log(`Node ${process.version}, ${W}x${W}, ${DENS*100}% walls, radius ${R}, ${NORIG} origins`)
const names = Object.keys(METHODS), stat = {}
for (const n of names) stat[n] = { missed: 0, shown: 0, throughWalls: 0 }
let visible = 0
for (let i = 0; i < NORIG; i++) {
  const ox = O[2*i], oy = O[2*i+1], got = {}
  for (const n of names) { METHODS[n](ox, oy, R); got[n] = MARK.map(v => v === STAMP ? 1 : 0) }
  for (let ty = Math.max(0, oy-R); ty <= Math.min(W-1, oy+R); ty++)
    for (let tx = Math.max(0, ox-R); tx <= Math.min(W-1, ox+R); tx++) {
      if ((tx-ox)**2+(ty-oy)**2 > R*R) continue
      const k = ty*W+tx, t = truth(ox, oy, tx, ty); let corner = -1
      if (t) visible++
      for (const n of names) {
        if (t && !got[n][k]) stat[n].missed++
        if (!t && got[n][k]) { stat[n].shown++
          if (corner < 0) corner = throughCornerOnly(ox, oy, tx, ty) ? 1 : 0
          if (!corner) stat[n].throughWalls++ }
      }
    }
}
console.log(`truly visible cells (reference): ${visible}`)
const us = {}; for (const n of names) us[n] = []
for (let round = 0; round < 3; round++)
  for (const n of [...names.slice(round), ...names.slice(0, round)])
    us[n].push(1000 * +execFileSync(process.execPath, [__filename, 'time', n]).toString())
const fix = median(us['shadowcasting + guard'])
console.log('method                    | us/call | vs guard | missed (% of visible) | hidden shown | through solid walls')
for (const n of names) { const s = stat[n], t = median(us[n]), pct = v => (100*v/visible).toFixed(1) + '%'
  console.log(`${n.padEnd(25)} | ${t.toFixed(2).padStart(7)} | ${(t/fix).toFixed(2).padStart(7)}x | ${String(s.missed).padStart(6)} (${pct(s.missed)}) | ${String(s.shown).padStart(5)} (${pct(s.shown)}) | ${String(s.throughWalls).padStart(5)} (${pct(s.throughWalls)})`) }
console.log(`50 units per turn (calculated): guard ${(50*fix/1000).toFixed(3)} ms, bresenham ${(50*median(us['bresenham to every cell'])/1000).toFixed(3)} ms`)

On our machine it printed:

Node v23.5.0, 256x256, 10% walls, radius 16, 20 origins
truly visible cells (reference): 6759
method                    | us/call | vs guard | missed (% of visible) | hidden shown | through solid walls
bresenham to every cell   |   12.71 |    3.10x |    959 (14.2%) |   891 (13.2%) |   466 (6.9%)
perimeter rays            |    3.56 |    0.87x |    551 (8.2%) |  1315 (19.5%) |   682 (10.1%)
shadowcasting as copied   |    6.70 |    1.63x |      0 (0.0%) |  1210 (17.9%) |   260 (3.8%)
shadowcasting + guard     |    4.10 |    1.00x |      0 (0.0%) |   978 (14.5%) |    36 (0.5%)
50 units per turn (calculated): guard 0.205 ms, bresenham 0.636 ms

Every count in those last five lines matches the full benchmark exactly. The timings do not match exactly. This smaller script runs one setting per process, where the full benchmark ran all 24, and perimeter rays came out 0.87x in three runs of this script against 1.04x in the full benchmark. The unguarded shadowcaster was 1.62x to 1.68x slower here, against 1.09x there. The ratio that held steady across both is the one in the opening sentence: shadowcasting at roughly a third of the cost of a line to every cell.