Bigger Maps & Pathing

This is chapter two of an interactive book about data-oriented design. Chapter 1 was two tanks on a single grid of walls. Chapter 2 grows the world to a 4×4 arrangement of screen-grids and adds pathing: a tank you give a destination, and it routes itself there along the shortest wall-free way, across screens and around the world's wrap. As before, every data structure below is live — it reads and pokes the running game's memory directly.

The whole chapter is one idea applied twice: the path is a table, and a moving tank just does a lookup. Working out the shortest route is the expensive part, so we do it once against the rarely-changing walls and store the answer; per tick a tank reads the next step. The art is making the stored answer small.

The world is one big toroidal grid, organised as screens

Mechanically there is a single (4·20)×(4·15) = 80×60 toroidal grid. The 4×4 split into 20×15 screens is an organisation — for display (the viewport shows one screen), for scrolling, and for the two-level pathing below. A tank crosses from one screen into its neighbour wherever the border cell and the neighbouring cell are both open — exactly chapter 1's "depends only on the wall on the far side" rule, now applied at every inner screen edge and at the outer wrap. Each screen border has 0, 1, or 2 matching openings — not every border connects, but a randomised spanning tree forces enough that no screen is an island, and the generator fails the build if one is. Each of the 16 screens also has a distinct interior — blocks, pillars, rooms, dead-ends, a maze, an enclosed island of unreachable cells (route a tank into one — no path) — so they are easy to tell apart and each gives the flow field below something different to solve. Tap the screen badge to open the picker and look around:

The viewport is presentation only: which screen you look at never changes the simulation. A tank keeps pathing whether or not its screen is in view — open the picker and look elsewhere and it carries on.

One kind of tank, three states

All the tanks are identical. Each carries a small state you cycle by tapping it: auto-path (tap a cell and it routes there), manual (you drive it — the on-screen pad and W/S/A/D appear in this state), or unselected (it keeps following any route it has). At most one tank is selected at a time, and its screen is followed: when it drives across a border, the new screen slides in. A tank's one input byte comes from one of two sources — the controls or the path lookup — and both feed the same turn/move transforms. The state picks the source; the data and the movement are the same.

Level 1 — within a screen: all-pairs, stored as distance

Inside one screen you route any cell to any cell — the all-pairs table the grid-paths project builds. 300 cells make ~90,000 ordered pairs; the table below packs that into 45 KB.

The key move: store the metric, derive the arrow. Distance is symmetric (dist(a,b) == dist(b,a)), so we keep one byte per unordered pair — the upper triangle. Direction is asymmetric, so we derive it at runtime: the next step from a cell toward a target is the neighbour whose stored distance to the target is one less. One table serves both the per-tick arrow and the Level-2 weights below. Pick a target cell and watch its flow field — the arrow each cell takes to reach it, derived live from the distances:

How big is one entry? Each distance is built from the grid, so it is small and bounded, and the bound is provable. A shortest path inside a screen never revisits a cell, and no 2×2 block can sit entirely on one (four cells would close a loop), so at most three of every four cells lie on it: the longest in-screen distance is at most 300 − 10·7 − 1 = 229. That fits one byte (255 is reserved for "unreachable"), guaranteed at compile time by a _Static_assert. The build also measures the actual longest distance — shown in the counters above — so a screen that ever exceeded the byte would be caught.

So one entry is one byte: 45,150 pairs = 45 KB per screen, 706 KB for all 16. The table is filled by a breadth-first search on init, rebuilt for one screen when you edit a wall there, and read by a lookup every tick. Toggle walls in the current screen and watch the flow field re-solve:

Level 2 — between screens: a next-hop matrix over edge points

The connecting edge points are the open border cells whose neighbour across the border is also open — the matching gaps. Over just those points we build a second all-pairs table: for a start point A and an end point B, the next edge point on the shortest route (and its length). The win is that this is built on top of Level 1: two edge points on the same screen are joined by an edge weighted with that screen's Level-1 distance; crossing a matched border costs 1. Level 2 reuses the distances Level 1 already stored, and a small Floyd–Warshall fills the matrix. With the default map there are only ~80 edge points, so the matrix is tiny.

Composing the two levels into a route

When you click a destination, we fold the matrix into a tiny per-tank vector: for every edge point, the shortest remaining distance to the goal (Level-2 distance to a goal-screen entry point, plus that screen's Level-1 distance in to the goal cell). That fold happens once, when the destination changes — not per tick. After that, each tick a routing tank in screen S either follows S's Level-1 flow straight to the goal (if it's there and reachable) or picks the exit edge point that minimises distance-to-the-exit + 1 + remaining-from-its-partner — a handful of table reads. Because every step strictly decreases the true remaining distance, the route is the globally shortest one and never enters a wall; an unreachable destination produces no path at all, shown as such. Each routing tank's path is drawn in its own colour, read from the same tables it follows; where two paths share a cell the marker splits into coloured strips so both stay visible.

Tune the pace and drive a tank (tap it twice to make it manual) into things to feel the inherited chapter-1 movement (slide along walls, auto-steer out of corners) — the auto-pathing tanks ride on top of the very same model:

What this bought us

Static memory, integer math, flat tables: a 4×4 world with self-routing tanks in a few kilobytes of WebAssembly plus under a megabyte of packed integer tables, all sized to their real domain and printable on this page. Each table has a stated job — how often it is built, how often it is read, and why it is shaped the way it is. The simulation is separated from rendering and wasm, so the whole thing, pathing included, is tested natively with no browser or GPU.

Source for this chapter: sim.c · grid_paths.c · edge_paths.c · tanks_path.c · render.c · wasm.c · test.c · README · CONTRACT