Skip to content
Computational Lab.

A*

Finding structure through informed search.

Intermediate / graph / search / heuristic

A* searches a weighted grid by expanding the most promising node first. Each candidate is ranked by f(n) = g(n) + h(n): the cost paid so far plus an admissible estimate of what remains. When the heuristic never overestimates, the first path A* finds is provably the shortest one.

Tagged: search, heuristic, pathfinding, priority queue

Live simulation

Drag on the grid to draw or erase walls; the search restarts instantly.

Speed

Drag on the grid to draw or erase walls; the search restarts instantly.

Mathematics

A* ranks every candidate cell by one number: the cost already paid plus an optimistic estimate of the cost still to come. When the estimate never overestimates, the first path A* hands back is provably optimal.

f(n) = g(n) + h(n)

admissible: 0 ≤ h(n) ≤ h*(n) for every node n

manhattan: h(n) = |x_n − x_goal| + |y_n − y_goal|

Manhattan distance is admissible on a 4-connected grid because a path cannot do better than moving one unit closer per step. Dijkstra is the special case h(n) = 0: optimal, but blind. Greedy best-first keeps only h(n): fast, with no optimality guarantee. The three modes here share one binary-heap open set, so the node counts you see are a fair comparison.

How it works

The grid is a flat typed array; walls, closed marks, and g-scores are one array each. The open set is a binary min-heap over integer node indices with a parallel key array, so each push or pop is O(log n) with no object allocation.

Each tick expands a fixed number of nodes: pop the cheapest open node, close it, and relax its four neighbors. If a neighbor's tentative g-score beats its current one, the score and parent pointer are updated and it is pushed with a new key. Reaching the goal triggers a walk back through the parent pointers to reconstruct the path.

Drawing a wall with the pointer re-runs the search immediately over the same map, so you can watch the frontier route around your edit.

Implementation

src/engine/experiments/a-star.ts · 363 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, PointerState, ThemeColors } from "../core/types";
3
4type Algorithm = "astar" | "dijkstra" | "greedy";
5
6/**
7 * Incremental informed search on a 4-connected grid. One tick expands a fixed
8 * number of nodes, so stepping shows the frontier grow. Dijkstra (h = 0) and
9 * greedy best-first (key = h) run through the same machinery for honest
10 * comparison against A*.
11 */
12export class AStarExperiment extends BaseExperiment {
13 readonly id = "a-star";
14
15 private cols = 0;
16 private rows = 0;
17 private offsetX = 0;
18 private offsetY = 0;
19 private walls = new Uint8Array(0);
20 private closed = new Uint8Array(0);
21 private gScore = new Float32Array(0);
22 private cameFrom = new Int32Array(0);
23 private heapIndex = new Int32Array(0);
24 private heap = new Int32Array(0);
25 private heapKeys = new Float32Array(0);
26 private heapSize = 0;
27 private start = 0;
28 private goal = 0;
29 private status: "running" | "found" | "exhausted" = "running";
30 private expanded = 0;
31 private path: number[] = [];
32 private current = -1;
33 private paintWall: 0 | 1 = 1;
34 private pointerDown = false;
35
36 protected params(): ParameterDef[] {
37 return [
38 {
39 key: "algorithm",
40 label: "Algorithm",
41 options: [
42 { value: "astar", label: "A*" },
43 { value: "dijkstra", label: "Dijkstra" },
44 { value: "greedy", label: "Greedy best-first" },
45 ],
46 defaultValue: "astar",
47 },
48 {
49 key: "heuristic",
50 label: "Heuristic",
51 options: [
52 { value: "manhattan", label: "Manhattan" },
53 { value: "euclidean", label: "Euclidean" },
54 { value: "chebyshev", label: "Chebyshev" },
55 { value: "octile", label: "Octile" },
56 ],
57 defaultValue: "manhattan",
58 },
59 { key: "cell", label: "Grid cell", min: 8, max: 24, step: 1, defaultValue: 14, unit: "px" },
60 { key: "density", label: "Obstacle density", min: 0, max: 45, step: 1, defaultValue: 28, unit: "%" },
61 { key: "rate", label: "Expansions per tick", min: 1, max: 30, step: 1, defaultValue: 3 },
62 ];
63 }
64
65 protected onReset(): void {
66 this.cols = Math.max(10, Math.floor(this.width / this.num("cell")));
67 this.rows = Math.max(10, Math.floor(this.height / this.num("cell")));
68 this.offsetX = Math.floor((this.width - this.cols * this.num("cell")) / 2);
69 this.offsetY = Math.floor((this.height - this.rows * this.num("cell")) / 2);
70 const n = this.cols * this.rows;
71 this.walls = new Uint8Array(n);
72 this.closed = new Uint8Array(n);
73 this.gScore = new Float32Array(n);
74 this.cameFrom = new Int32Array(n);
75 this.heapIndex = new Int32Array(n);
76 this.heap = new Int32Array(n);
77 this.heapKeys = new Float32Array(n);
78 const density = this.num("density") / 100;
79 for (let i = 0; i < n; i++) this.walls[i] = this.rng() < density ? 1 : 0;
80 const startY = this.rows >> 1;
81 const goalY = this.rows >> 1;
82 this.start = startY * this.cols + 1;
83 this.goal = goalY * this.cols + (this.cols - 2);
84 this.walls[this.start] = 0;
85 this.walls[this.goal] = 0;
86 this.beginRun();
87 }
88
89 /** Re-run the search over the current walls without re-rolling the map. */
90 private beginRun(): void {
91 const n = this.cols * this.rows;
92 this.closed.fill(0);
93 this.gScore.fill(Infinity);
94 this.cameFrom.fill(-1);
95 this.heapSize = 0;
96 for (let i = 0; i < n; i++) this.heapIndex[i] = -1;
97 this.status = "running";
98 this.expanded = 0;
99 this.path = [];
100 this.current = -1;
101 this.gScore[this.start] = 0;
102 this.push(this.start, this.keyFor(this.start, 0));
103 }
104
105 protected onParameterChange(key: string): void {
106 if (key === "cell" || key === "density") this.reset();
107 else if (key === "algorithm" || key === "heuristic" || key === "rate") this.beginRun();
108 }
109
110 resize(width: number, height: number): void {
111 this.width = width;
112 this.height = height;
113 this.reset();
114 }
115
116 // --- binary min-heap keyed by f (or h for greedy) ---
117
118 private push(node: number, key: number): void {
119 let i = this.heapSize++;
120 this.heap[i] = node;
121 this.heapKeys[i] = key;
122 this.heapIndex[node] = i;
123 while (i > 0) {
124 const parent = (i - 1) >> 1;
125 if (this.heapKeys[parent] <= this.heapKeys[i]) break;
126 this.swapEntries(i, parent);
127 i = parent;
128 }
129 }
130
131 private pop(): number {
132 const top = this.heap[0];
133 this.heapIndex[top] = -1;
134 this.heapSize -= 1;
135 if (this.heapSize > 0) {
136 this.heap[0] = this.heap[this.heapSize];
137 this.heapKeys[0] = this.heapKeys[this.heapSize];
138 this.heapIndex[this.heap[0]] = 0;
139 let i = 0;
140 while (true) {
141 const left = i * 2 + 1;
142 const right = left + 1;
143 let smallest = i;
144 if (left < this.heapSize && this.heapKeys[left] < this.heapKeys[smallest]) smallest = left;
145 if (right < this.heapSize && this.heapKeys[right] < this.heapKeys[smallest]) smallest = right;
146 if (smallest === i) break;
147 this.swapEntries(i, smallest);
148 i = smallest;
149 }
150 }
151 return top;
152 }
153
154 private swapEntries(a: number, b: number): void {
155 const node = this.heap[a];
156 this.heap[a] = this.heap[b];
157 this.heap[b] = node;
158 const key = this.heapKeys[a];
159 this.heapKeys[a] = this.heapKeys[b];
160 this.heapKeys[b] = key;
161 this.heapIndex[this.heap[a]] = a;
162 this.heapIndex[this.heap[b]] = b;
163 }
164
165 private heuristic(node: number): number {
166 const dx = Math.abs((node % this.cols) - (this.goal % this.cols));
167 const dy = Math.abs(Math.floor(node / this.cols) - Math.floor(this.goal / this.cols));
168 switch (this.str("heuristic")) {
169 case "euclidean":
170 return Math.sqrt(dx * dx + dy * dy);
171 case "chebyshev":
172 return Math.max(dx, dy);
173 case "octile": {
174 const min = Math.min(dx, dy);
175 return dx + dy + (Math.SQRT2 - 2) * min;
176 }
177 default:
178 return dx + dy; // manhattan
179 }
180 }
181
182 private keyFor(node: number, g: number): number {
183 const h = this.heuristic(node);
184 const algorithm = this.str("algorithm") as Algorithm;
185 if (algorithm === "dijkstra") return g;
186 if (algorithm === "greedy") return h;
187 return g + h;
188 }
189
190 protected onUpdate(): void {
191 if (this.status !== "running") return;
192 const rate = this.num("rate");
193 for (let k = 0; k < rate && this.status === "running"; k++) this.expandOne();
194 }
195
196 private expandOne(): void {
197 if (this.heapSize === 0) {
198 this.status = "exhausted";
199 return;
200 }
201 const node = this.pop();
202 if (this.closed[node]) return;
203 this.closed[node] = 1;
204 this.current = node;
205 this.expanded += 1;
206 if (node === this.goal) {
207 this.reconstruct();
208 this.status = "found";
209 return;
210 }
211 const x = node % this.cols;
212 const y = (node / this.cols) | 0;
213 const neighbors = [
214 x > 0 ? node - 1 : -1,
215 x < this.cols - 1 ? node + 1 : -1,
216 y > 0 ? node - this.cols : -1,
217 y < this.rows - 1 ? node + this.cols : -1,
218 ];
219 const stepCost = this.str("heuristic") === "euclidean" ? 1 : 1; // 4-connected: cost 1
220 for (const next of neighbors) {
221 if (next < 0 || this.walls[next] || this.closed[next]) continue;
222 const tentative = this.gScore[node] + stepCost;
223 if (tentative < this.gScore[next]) {
224 this.gScore[next] = tentative;
225 this.cameFrom[next] = node;
226 this.push(next, this.keyFor(next, tentative));
227 }
228 }
229 }
230
231 private reconstruct(): void {
232 this.path = [];
233 let node = this.goal;
234 while (node !== -1 && node !== this.start) {
235 this.path.push(node);
236 node = this.cameFrom[node];
237 }
238 this.path.push(this.start);
239 this.path.reverse();
240 }
241
242 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
243 const { cols, rows, offsetX, offsetY } = this;
244 const cell = this.num("cell");
245 ctx.fillStyle = theme.bg;
246 ctx.fillRect(0, 0, this.width, this.height);
247 for (let y = 0; y < rows; y++) {
248 for (let x = 0; x < cols; x++) {
249 const node = y * cols + x;
250 const px = offsetX + x * cell;
251 const py = offsetY + y * cell;
252 if (this.walls[node]) {
253 ctx.fillStyle = theme.fgTertiary;
254 ctx.fillRect(px, py, cell - 1, cell - 1);
255 } else if (this.closed[node]) {
256 ctx.fillStyle = theme.raised;
257 ctx.fillRect(px + 1, py + 1, cell - 2, cell - 2);
258 }
259 }
260 }
261 // Open set (frontier)
262 ctx.fillStyle = theme.viz[1];
263 for (let i = 0; i < this.heapSize; i++) {
264 const node = this.heap[i];
265 if (this.closed[node]) continue;
266 const px = offsetX + (node % cols) * cell;
267 const py = offsetY + Math.floor(node / cols) * cell;
268 ctx.fillRect(px + 1, py + 1, cell - 2, cell - 2);
269 }
270 if (this.current >= 0 && this.status === "running") {
271 ctx.fillStyle = theme.accentStrong;
272 ctx.fillRect(
273 offsetX + (this.current % cols) * cell + 1,
274 offsetY + Math.floor(this.current / cols) * cell + 1,
275 cell - 2,
276 cell - 2,
277 );
278 }
279 // Path
280 if (this.path.length > 1) {
281 ctx.strokeStyle = theme.accent;
282 ctx.lineWidth = Math.max(2, cell * 0.3);
283 ctx.lineJoin = "round";
284 ctx.lineCap = "round";
285 ctx.beginPath();
286 for (let i = 0; i < this.path.length; i++) {
287 const node = this.path[i];
288 const cx = offsetX + (node % cols) * cell + cell / 2;
289 const cy = offsetY + Math.floor(node / cols) * cell + cell / 2;
290 if (i === 0) ctx.moveTo(cx, cy);
291 else ctx.lineTo(cx, cy);
292 }
293 ctx.stroke();
294 }
295 // Markers
296 ctx.fillStyle = theme.viz[2];
297 ctx.fillRect(
298 offsetX + (this.start % cols) * cell + 2,
299 offsetY + Math.floor(this.start / cols) * cell + 2,
300 cell - 4,
301 cell - 4,
302 );
303 ctx.strokeStyle = theme.accent;
304 ctx.lineWidth = 2;
305 ctx.strokeRect(
306 offsetX + (this.goal % cols) * cell + 2,
307 offsetY + Math.floor(this.goal / cols) * cell + 2,
308 cell - 4,
309 cell - 4,
310 );
311 }
312
313 onPointer(state: PointerState): void {
314 if (!state.inside || this.walls.length === 0) return;
315 if (!state.down) {
316 this.pointerDown = false;
317 return;
318 }
319 const cell = this.num("cell");
320 const x = Math.floor((state.x - this.offsetX) / cell);
321 const y = Math.floor((state.y - this.offsetY) / cell);
322 if (x < 0 || y < 0 || x >= this.cols || y >= this.rows) return;
323 const node = y * this.cols + x;
324 if (node === this.start || node === this.goal) return;
325 if (!this.pointerDown) {
326 this.pointerDown = true;
327 this.paintWall = this.walls[node] === 0 ? 1 : 0;
328 }
329 if (this.walls[node] !== this.paintWall) {
330 this.walls[node] = this.paintWall;
331 this.beginRun();
332 }
333 }
334
335 getMetrics() {
336 const algorithm = this.str("algorithm");
337 const heuristic = this.str("heuristic");
338 return {
339 algorithm: algorithm === "astar" ? `A* (${heuristic})` : algorithm === "dijkstra" ? "Dijkstra" : "Greedy",
340 openSet: this.heapSize,
341 closedSet: this.expanded,
342 pathLength: this.status === "found" ? this.path.length : "n/a",
343 pathCost: this.status === "found" ? this.gScore[this.goal].toFixed(0) : "n/a",
344 status:
345 this.status === "found" ? "Path found" : this.status === "exhausted" ? "No path" : "Searching",
346 };
347 }
348
349 describe(): string {
350 if (this.status === "found") {
351 return `Path found: ${this.path.length} cells long, cost ${this.gScore[this.goal].toFixed(0)} after expanding ${this.expanded} nodes.`;
352 }
353 if (this.status === "exhausted") {
354 return "No path exists: the open set is empty and the goal was never reached.";
355 }
356 return `Searching: ${this.expanded} nodes expanded, ${this.heapSize} in the open set.`;
357 }
358
359 entities(): number {
360 return this.cols * this.rows;
361 }
362}
363

Performance

Time per tick
O(E log V) worst case; each tick expands a fixed number of nodes
Space
O(V): scores, parents, and the heap
Notes
Greedy mode expands the fewest nodes; Dijkstra the most; A* sits between them and is the only one of the three that is both optimal and informed.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.