Grid Paths

Jump to: §7 Cube surface chase · §8 Sphere surface chase — the grid wrapped onto a 3D surface, with agents chasing a target.

For every target cell, the algorithm stores a complete shortest-path field: from each source cell, which direction(s) step toward the target, and the distance. When a wall is added between two cells, only the affected fields are repaired — paths are rerouted, and fully enclosed regions are detected as closed islands. This page replays the demo from paths.js step by step, and lets you experiment.

1 · Data design

The whole system is a few flat arrays on one grid object. Cells are addressed by a single index, index = y · colCount + x (so the grid is stored row-major).

Field	Shape	Meaning
`paths`	N×N table `paths[target][source]`	The heart of it. For every target cell there is a full field over all source cells. Each entry is `{ dir, dist }`: the direction(s) that step toward the target, and the distance in steps.
`dir`	4-bit mask	`N=1`, `S=2`, `W=4`, `E=8`, OR-combined. More than one bit means several equally-short paths exist (e.g. `N\|E` on a diagonal). `0` = the target itself.
`dist`	integer	Steps to the target. `0` at the target, `-1` means unreachable (sealed off).
`obstacles`	per-cell 4-bit mask	Which of a cell's four edges hold a wall. A wall is shared: adding one sets the bit on both adjacent cells (north of A ⇔ south of B).
`island`	per-cell int	Which closed region a cell belongs to (`0` = the original open region). Set when a wall fully encloses an area.
`islandCount`, `islandTargetCounts`	scalars / array	Number of regions and the cell-count of each. Used to detect an island split: if every blocked target equals the whole region's count, the region has been cut in two.

Cost note: this layout stores an explicit field for every target — O(N²) memory for an N-cell grid (N targets × N sources). A distance query is then an O(1) lookup, though walking an actual route still costs O(path length). And adding a wall is not a cheap local patch: AddObstacle scans every target's field to find blocked entries (FindBlockedTargets sweeps the whole grid per affected source) and re-resolves each one, so a single wall can touch work proportional to the entire table. The real saving grace is redundancy: neighboring targets have almost identical fields, so the table holds far less information than N² independent numbers — demonstrated in §5.

2 · Building the path data

InitializePaths(target) fills the field for one target on an empty grid, where the shortest path is just the Manhattan direction. It does this by region: the target, the four arms sharing the target's row/column, then the four diagonal quadrants. Click any cell to rebuild for a different target.

Click a cell to choose the target.

3 · Repairing paths as walls are added

Each frame shows the shortest-path field for one target. Arrows point along the shortest path toward the target; the number is the distance. Walls are the thick white edges.

Target ★ Source / island Changed this step Wall ↑ N ↓ S ← W → E · ∅ no path

4 · Interactive explorer

Click any cell to make it the target and see its shortest-path field recompute. Click a cell edge to drop a wall there — the field repairs incrementally, exactly like the algorithm. Unreachable cells (closed off) show ∅.

Target: 4, 4

Tip: build a pocket of walls around a cell and watch it become unreachable (a closed island) once every exit is sealed.

5 · Redundancy across targets (and how to store less than O(N²))

The O(N²) table looks expensive, but the fields are nowhere near independent. Move the target by one cell and most of the field is unchanged — and the part that does change (distance) follows a fixed rule. Here is target T next to a neighbor T′; every cell is colored by how its two entries compare. Click any cell to move T; pick which neighbor to compare against.

Neighbor T′:

What this implies for storage

Two facts fall out of the picture above:

Distance carries almost no new information. On an open grid, stepping the target one cell changes every cell's Manhattan distance by exactly ±1 (the shifted axis term moves by one, integers, so the absolute value can only tick up or down). The neighbor's entire distance field is therefore the previous one plus a single sign rule — there is nothing per-cell to store.
Direction barely reroutes. On an open grid, moving the target one cell produces zero genuine reroutes — every cell still has a shortest-path move it shares with the old field. A diagonal band of cells does change its set of co-optimal moves (e.g. S becomes S|E, or N|E becomes N) because dir records all equally-short first moves — but those are compatible refinements, not changes of route. Real reroutes (disjoint direction sets) only appear once obstacles force a detour.

So instead of N independent N-entry fields, keep a few anchor fields and store every other target as a sparse diff from an adjacent one: only the cells whose direction flipped (a minority), plus the per-axis distance sign — the distance field itself is reconstructed, not stored. Any field is then a walk of diffs from the nearest anchor.

The stronger statement is that the whole table is just deviations from the analytic Manhattan field. A fully open grid needs essentially O(1) storage — the distance is a formula and directions follow from the sign of (source − target). Real information only appears where geometry breaks: at obstacles. Switch to "With demo walls" and slide T around — far from the walls neighbors still match ~75%, but a pair straddling a wall can drop to a few percent. That is where the diffs concentrate, so storage scales with the number of obstacles, not with N².

6 · Building the table incrementally — and why iteration order matters

The same property that saves storage also saves construction work. The original code calls InitializePaths independently for every target — N full fields, O(N²) total. But §5 showed an adjacent target's field is almost the same. So build each target's field by cloning an already-built neighbor and patching the difference:

buildTable(order):                       // order = sequence of all N targets
  field[order[0]] = fromScratch(order[0]) // one full build  — O(N)
  for k in 1 .. N-1:
    p = order[k-1];  t = order[k]
    if adjacent(p, t):                    // one step away ⇒ use the property
      field[t] = clone(field[p])
      patchStep(field[t], p→t)            //   distances shift ±1   (closed form, no search)
                                          //   only the "wavefront" band re-evaluates direction
                                          //   genuine reroutes appear only where obstacles bite
    else:                                 // a jump ⇒ neighbor is useless
      field[t] = fromScratch(t)           //   fall back to a full rebuild

The cost of patchStep is the number of cells whose direction must be re-evaluated — small for an adjacent step (the wavefront from §5), large for a jump. So the total work depends entirely on the iteration order: an order whose consecutive targets are always neighbors pays the small cost every time; one that jumps across the grid keeps paying for near-full rebuilds. Pick an order below and scrub through the construction — red segments are jumps.

Reading the numbers

Adjacency is everything. Row-major and column-major are cheap inside a row/column but take a full-width jump at every wrap (7 of them on an 8×8), and each jump costs almost a rebuild. Boustrophedon (snake) removes those jumps by reversing direction each row, so every consecutive pair is adjacent — travel drops to the minimum N²−1.
Morton / Z-order looks local but its quadrant seams are discontinuities: it has the most jumps and the worst total, a caution that "a space-filling curve" is not automatically a good order.
Hilbert ties boustrophedon on an open grid (both jump-free) but wins once walls exist: its 2D locality keeps successive targets inside the same region, so it crosses obstacle boundaries less often and accumulates fewer reroutes. Flip to "With demo walls" and compare the totals — the curve that respects 2D neighborhoods pays off exactly when the field has real structure.

7 · Cube surface chase (the grid wrapped on a cube)

One F×F grid is wrapped over all six faces of a cube. All pathing/chase logic runs on the 2D grid with edge-wrap rules (each face border folds 90° onto its neighbor); only the rendering is 3D. Walls live on the edges between cells and are extruded as raised slabs. A wrap-aware shortest-path field floods from the moving target; the agents descend it, moving smoothly across faces. The flat net shows the same 2D state being wrapped. Drag to orbit · click the cube or the net to drop the target.

2D — the unfolded grid (flat)

target agent wall (edge) distance field

Speed

Grid F

Agents

Walls %

target wanders

distance field

face labels

8 · Sphere surface chase (equal-area octahedral map)

Same idea on a sphere. A single F×F grid — the unit square — is wrapped onto the sphere with the equal-area octahedral map of Clarberg (2008): center → north pole, the four corners → south pole, the rim → equator. The chase runs on that flat square; its boundary folds with the octahedral wrap, and the cell adjacency near the poles is built geometrically so the field and agents flow smoothly over the surface. Walls are extruded as raised slabs on the sphere (the flat square shows the same walls as lines), and the distance field wraps onto the sphere as its texture. Drag to orbit · click the sphere or the square to drop the target.

2D — the unit square (flat)