app = {
// ── constants ────────────────────────────────────────────────────────────
const COLS = 30, ROWS = 18, CELL = 28;
const W = COLS * CELL, H = ROWS * CELL;
// ── colours ──────────────────────────────────────────────────────────────
const C = {
bg: "#0f1117", grid: "#1e2130",
empty: "#12151f", wall: "#353a50",
start: "#4a8fe8", end: "#e85a4a",
open: "#0d2a4a", openBdr: "#4a8fe8",
closed: "#0a2318", clsBdr: "#3a9e60",
path: "#f5a623", pathBdr: "#f5a623",
gText: "#3a9e60", fText: "#f5a623",
text: "#e2e4ef", muted: "#6b7094",
surface: "#1a1d27", border: "#2e3347",
};
// ── helpers ───────────────────────────────────────────────────────────────
const key = (r, c) => `${r},${c}`;
function heuristicFn(r1, c1, r2, c2, type) {
const dr = Math.abs(r1 - r2), dc = Math.abs(c1 - c2);
if (type === "manhattan") return dr + dc;
if (type === "euclidean") return Math.sqrt(dr*dr + dc*dc);
if (type === "chebyshev") return Math.max(dr, dc);
if (type === "zero (Dijkstra)") return 0;
return dr + dc;
}
// ── state ─────────────────────────────────────────────────────────────────
let walls = Array.from({length: ROWS}, () => new Array(COLS).fill(false));
let start = {r: 3, c: 3};
let end = {r: ROWS - 4, c: COLS - 4};
let openSet = [], closedSet = new Set();
let cameFrom = {}, gScore = {}, fScore = {};
let path = [];
let running = false, done = false, iter = 0, status = "idle";
let heuristic = "manhattan", weight = 1, diagonal = false, editMode = "wall";
let animating = false, animDelay = 50, animTimer = null;
// ── search logic ──────────────────────────────────────────────────────────
function initSearch() {
const sk = key(start.r, start.c);
openSet = [{r: start.r, c: start.c}];
closedSet = new Set();
cameFrom = {};
gScore = {[sk]: 0};
fScore = {[sk]: heuristicFn(start.r, start.c, end.r, end.c, heuristic)};
path = [];
running = true;
done = false;
iter = 0;
status = "searching…";
}
function stepOnce() {
if (!running || done) return;
if (openSet.length === 0) {
running = false; done = true; status = "no path found"; return;
}
let bestIdx = 0;
for (let i = 1; i < openSet.length; i++) {
const fi = fScore[key(openSet[i].r, openSet[i].c)] ?? Infinity;
const fb = fScore[key(openSet[bestIdx].r, openSet[bestIdx].c)] ?? Infinity;
if (fi < fb) bestIdx = i;
}
const cur = openSet.splice(bestIdx, 1)[0];
const ck = key(cur.r, cur.c);
if (cur.r === end.r && cur.c === end.c) {
let k = ck;
while (cameFrom[k]) { path.push(k); k = cameFrom[k]; }
path.push(key(start.r, start.c));
running = false; done = true;
status = `done — ${path.length - 1} steps`;
return;
}
closedSet.add(ck);
iter++;
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
if (diagonal) dirs.push(...[[1,1],[1,-1],[-1,1],[-1,-1]]);
for (const [dr, dc] of dirs) {
const nr = cur.r + dr, nc = cur.c + dc;
if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) continue;
if (walls[nr][nc]) continue;
const nk = key(nr, nc);
if (closedSet.has(nk)) continue;
const moveCost = (dr !== 0 && dc !== 0) ? Math.SQRT2 : 1;
const tentG = (gScore[ck] ?? Infinity) + moveCost;
if (tentG < (gScore[nk] ?? Infinity)) {
cameFrom[nk] = ck;
gScore[nk] = tentG;
const h = heuristicFn(nr, nc, end.r, end.c, heuristic);
fScore[nk] = tentG + weight * h;
if (!openSet.find(n => n.r === nr && n.c === nc))
openSet.push({r: nr, c: nc});
}
}
}
function runToCompletion() {
if (!running && !done) initSearch();
while (running && !done) stepOnce();
}
function resetSearch() {
openSet = []; closedSet = new Set(); cameFrom = {}; gScore = {}; fScore = {};
path = []; running = false; done = false; iter = 0; status = "idle";
}
function stopAnim() {
animating = false;
if (animTimer) { clearTimeout(animTimer); animTimer = null; }
btnAnimate.textContent = "▶ Animate";
btnAnimate.style.color = "#4a8fe8";
btnAnimate.style.borderColor = "#4a8fe8";
}
function animTick() {
if (!animating) return;
if (!running && !done) initSearch();
stepOnce();
draw();
if (!done) {
animTimer = setTimeout(animTick, animDelay);
} else {
stopAnim();
}
}
function startAnim() {
if (done) resetSearch();
animating = true;
btnAnimate.textContent = "⏸ Pause";
btnAnimate.style.color = "#e8a84a";
btnAnimate.style.borderColor = "#e8a84a";
animTick();
}
function generateMaze() {
walls = Array.from({length: ROWS}, () => new Array(COLS).fill(false));
for (let r = 0; r < ROWS; r++) walls[r][0] = walls[r][COLS-1] = true;
for (let c = 0; c < COLS; c++) walls[0][c] = walls[ROWS-1][c] = true;
function divide(r1, c1, r2, c2) {
if (r2 - r1 < 2 || c2 - c1 < 2) return;
const horiz = (r2 - r1) > (c2 - c1);
if (horiz) {
const wr = r1 + 1 + 2 * Math.floor(Math.random() * Math.floor((r2 - r1) / 2));
const hole = c1 + Math.floor(Math.random() * (c2 - c1 + 1));
for (let c = c1; c <= c2; c++) if (c !== hole) walls[wr][c] = true;
divide(r1, c1, wr - 1, c2); divide(wr + 1, c1, r2, c2);
} else {
const wc = c1 + 1 + 2 * Math.floor(Math.random() * Math.floor((c2 - c1) / 2));
const hole = r1 + Math.floor(Math.random() * (r2 - r1 + 1));
for (let r = r1; r <= r2; r++) if (r !== hole) walls[r][wc] = true;
divide(r1, c1, r2, wc - 1); divide(r1, wc + 1, r2, c2);
}
}
divide(1, 1, ROWS - 2, COLS - 2);
resetSearch();
}
// ── draw ──────────────────────────────────────────────────────────────────
function draw() {
ctx.fillStyle = C.bg;
ctx.fillRect(0, 0, W, H);
const openKeys = new Set(openSet.map(n => key(n.r, n.c)));
const pathSet = new Set(path);
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
const x = c * CELL, y = r * CELL, k = key(r, c);
const isStart = r === start.r && c === start.c;
const isEnd = r === end.r && c === end.c;
const isWall = walls[r][c];
const isPath = pathSet.has(k) && !isStart && !isEnd;
const isOpen = openKeys.has(k) && !isStart && !isEnd;
const isClosed = closedSet.has(k) && !isStart && !isEnd;
if (isWall) ctx.fillStyle = C.wall;
else if (isStart) ctx.fillStyle = C.start;
else if (isEnd) ctx.fillStyle = C.end;
else if (isPath) ctx.fillStyle = C.path;
else if (isOpen) ctx.fillStyle = C.open;
else if (isClosed) ctx.fillStyle = C.closed;
else ctx.fillStyle = C.empty;
ctx.fillRect(x + 1, y + 1, CELL - 2, CELL - 2);
if (isOpen) { ctx.strokeStyle = C.openBdr; ctx.lineWidth = 0.5; ctx.strokeRect(x+1,y+1,CELL-2,CELL-2); }
if (isClosed) { ctx.strokeStyle = C.clsBdr; ctx.lineWidth = 0.5; ctx.strokeRect(x+1,y+1,CELL-2,CELL-2); }
if (isPath) { ctx.strokeStyle = C.pathBdr; ctx.lineWidth = 1; ctx.strokeRect(x+1,y+1,CELL-2,CELL-2); }
if (!isWall && !isStart && !isEnd) {
const g = gScore[k], f = fScore[k];
if (g !== undefined) {
ctx.font = `${Math.max(7, CELL * 0.27)}px monospace`;
ctx.fillStyle = C.gText;
ctx.fillText("g:" + g.toFixed(1), x + 2, y + CELL * 0.42);
ctx.fillStyle = C.fText;
ctx.fillText("f:" + f.toFixed(1), x + 2, y + CELL * 0.78);
}
}
if (isStart || isEnd) {
ctx.fillStyle = "#fff"; ctx.font = `bold ${CELL * 0.38}px monospace`;
ctx.textAlign = "center"; ctx.textBaseline = "middle";
ctx.fillText(isStart ? "S" : "E", x + CELL / 2, y + CELL / 2);
ctx.textAlign = "left"; ctx.textBaseline = "alphabetic";
}
}
}
ctx.strokeStyle = C.grid; ctx.lineWidth = 0.4;
for (let r = 0; r <= ROWS; r++) { ctx.beginPath(); ctx.moveTo(0, r*CELL); ctx.lineTo(W, r*CELL); ctx.stroke(); }
for (let c = 0; c <= COLS; c++) { ctx.beginPath(); ctx.moveTo(c*CELL, 0); ctx.lineTo(c*CELL, H); ctx.stroke(); }
updateStats();
}
function updateStats() {
statOpen.textContent = openSet.length;
statClosed.textContent = closedSet.size;
statPath.textContent = path.length > 0 ? path.length - 1 : "—";
statIter.textContent = iter;
statStatus.textContent = status;
}
// ── build DOM ─────────────────────────────────────────────────────────────
const root = document.createElement("div");
root.style.cssText = "font-family:monospace;display:flex;flex-direction:column;gap:10px;padding:0.5rem 0";
function mkBtn(label, primary = false) {
const b = document.createElement("button");
b.textContent = label;
b.style.cssText = `font-size:12px;font-family:monospace;padding:5px 11px;
border:0.5px solid ${primary ? "#4a8fe8" : "#2e3347"};border-radius:6px;
background:#1a1d27;color:${primary ? "#4a8fe8" : "#e2e4ef"};cursor:pointer`;
b.onmouseenter = () => b.style.background = "#22263a";
b.onmouseleave = () => b.style.background = "#1a1d27";
return b;
}
const btnRow = document.createElement("div");
btnRow.style.cssText = "display:flex;flex-wrap:wrap;gap:6px;align-items:center";
const btnAnimate = mkBtn("▶ Animate", true);
const btnStep = mkBtn("Step →");
const btnReset = mkBtn("Reset");
const btnClear = mkBtn("Clear walls");
const btnMaze = mkBtn("Gen maze");
btnRow.append(btnAnimate, btnStep, btnReset, btnClear, btnMaze);
function mkGroup(...children) {
const g = document.createElement("div");
g.style.cssText = "display:flex;align-items:center;gap:7px;background:#1a1d27;border:0.5px solid #2e3347;border-radius:6px;padding:5px 10px";
children.forEach(c => g.appendChild(c));
return g;
}
function mkLabel(text) {
const l = document.createElement("label");
l.textContent = text;
l.style.cssText = "font-size:12px;color:#6b7094;white-space:nowrap";
return l;
}
function mkSelect(options, val) {
const s = document.createElement("select");
s.style.cssText = "font-size:12px;font-family:monospace;background:#1a1d27;color:#e2e4ef;border:none;outline:none";
options.forEach(o => {
const op = document.createElement("option");
op.value = op.textContent = o;
if (o === val) op.selected = true;
s.appendChild(op);
});
return s;
}
const selHeuristic = mkSelect(["manhattan","euclidean","chebyshev","zero (Dijkstra)"], "manhattan");
const selMode = mkSelect(["wall","erase","set start","set end"], "wall");
const weightSlider = document.createElement("input");
weightSlider.type = "range"; weightSlider.min = 0; weightSlider.max = 5;
weightSlider.step = 0.1; weightSlider.value = 1;
weightSlider.style.cssText = "width:80px;accent-color:#4a8fe8";
const weightVal = document.createElement("span");
weightVal.textContent = "1.0";
weightVal.style.cssText = "font-size:12px;min-width:26px;color:#e2e4ef";
const diagCheck = document.createElement("input");
diagCheck.type = "checkbox";
diagCheck.style.cssText = "accent-color:#4a8fe8";
const speedSlider = document.createElement("input");
speedSlider.type = "range"; speedSlider.min = 0; speedSlider.max = 4;
speedSlider.step = 1; speedSlider.value = 2;
speedSlider.style.cssText = "width:70px;accent-color:#4a8fe8";
const speedLabels = ["0.5×", "1×", "2×", "5×", "20×"];
const speedVal = document.createElement("span");
speedVal.textContent = speedLabels[2];
speedVal.style.cssText = "font-size:12px;min-width:30px;color:#e2e4ef";
const optRow = document.createElement("div");
optRow.style.cssText = "display:flex;flex-wrap:wrap;gap:8px;align-items:center";
optRow.append(
mkGroup(mkLabel("heuristic"), selHeuristic),
mkGroup(mkLabel("weight (w)"), weightSlider, weightVal),
mkGroup(mkLabel("speed"), speedSlider, speedVal),
mkGroup(mkLabel("diagonal"), diagCheck),
mkGroup(mkLabel("edit mode"), selMode),
);
const canvas = document.createElement("canvas");
canvas.width = W; canvas.height = H;
canvas.style.cssText = `display:block;width:100%;max-width:${W}px;border-radius:6px;cursor:crosshair;border:0.5px solid #2e3347`;
const ctx = canvas.getContext("2d");
const statsRow = document.createElement("div");
statsRow.style.cssText = "display:flex;flex-wrap:wrap;gap:8px";
function mkStat(label) {
const d = document.createElement("div");
d.style.cssText = "background:#1a1d27;border:0.5px solid #2e3347;border-radius:6px;padding:5px 10px;font-size:12px;color:#6b7094";
const v = document.createElement("span");
v.style.cssText = "color:#e2e4ef;font-weight:500;margin-left:5px";
d.append(label, v); statsRow.appendChild(d); return v;
}
const statOpen = mkStat("open set");
const statClosed = mkStat("closed set");
const statPath = mkStat("path length");
const statIter = mkStat("iterations");
const statStatus = mkStat("status");
const legend = document.createElement("div");
legend.style.cssText = "display:flex;flex-wrap:wrap;gap:10px;font-size:11px;color:#6b7094";
[["#4a8fe8","start (S)"],["#e85a4a","end (E)"],["#353a50","wall"],
["#0d2a4a","open set"],["#0a2318","closed set"],["#f5a623","path"]]
.forEach(([bg, lbl]) => {
const d = document.createElement("div");
d.style.cssText = "display:flex;align-items:center;gap:4px";
const sw = document.createElement("div");
sw.style.cssText = `width:12px;height:12px;border-radius:2px;background:${bg};flex-shrink:0`;
d.append(sw, lbl); legend.appendChild(d);
});
const note = document.createElement("span");
note.textContent = "· cells show g (cost so far) and f = g + w·h";
legend.appendChild(note);
root.append(btnRow, optRow, canvas, statsRow, legend);
// ── event handlers ────────────────────────────────────────────────────────
btnAnimate.onclick = () => {
if (animating) { stopAnim(); } else { startAnim(); }
};
btnStep.onclick = () => { stopAnim(); if (!running && !done) initSearch(); stepOnce(); draw(); };
btnReset.onclick = () => { stopAnim(); resetSearch(); draw(); };
btnClear.onclick = () => {
stopAnim();
walls = Array.from({length: ROWS}, () => new Array(COLS).fill(false));
resetSearch(); draw();
};
btnMaze.onclick = () => { stopAnim(); generateMaze(); draw(); };
selHeuristic.onchange = e => { heuristic = e.target.value; stopAnim(); resetSearch(); draw(); };
selMode.onchange = e => { editMode = e.target.value; };
weightSlider.oninput = e => {
weight = parseFloat(e.target.value);
weightVal.textContent = weight.toFixed(1);
stopAnim(); resetSearch(); draw();
};
const delayMap = [200, 100, 50, 20, 5];
speedSlider.oninput = e => {
const idx = parseInt(e.target.value);
animDelay = delayMap[idx];
speedVal.textContent = speedLabels[idx];
};
diagCheck.onchange = e => { diagonal = e.target.checked; stopAnim(); resetSearch(); draw(); };
let painting = false;
function cellAt(e) {
const rect = canvas.getBoundingClientRect();
const scale = W / rect.width;
return {
r: Math.floor((e.clientY - rect.top) * scale / CELL),
c: Math.floor((e.clientX - rect.left) * scale / CELL),
};
}
function applyEdit(r, c) {
if (r < 0 || r >= ROWS || c < 0 || c >= COLS) return;
if (editMode === "wall") {
if ((r === start.r && c === start.c) || (r === end.r && c === end.c)) return;
walls[r][c] = true;
} else if (editMode === "erase") {
walls[r][c] = false;
} else if (editMode === "set start") {
if (walls[r][c]) return;
start = {r, c};
} else if (editMode === "set end") {
if (walls[r][c]) return;
end = {r, c};
}
resetSearch(); draw();
}
canvas.addEventListener("pointerdown", e => {
stopAnim();
painting = true;
canvas.setPointerCapture(e.pointerId);
const {r, c} = cellAt(e); applyEdit(r, c);
});
canvas.addEventListener("pointermove", e => {
if (painting) { const {r, c} = cellAt(e); applyEdit(r, c); }
});
canvas.addEventListener("pointerup", () => { painting = false; });
draw();
return root;
}A* Pathfinding Algorithm
Reuse
Citation
BibTeX citation:
@online{untitled,
author = {},
title = {A* {Pathfinding} {Algorithm}},
url = {https://andreasbogossian.com/posts/a-star/},
langid = {en}
}
For attribution, please cite this work as:
“A* Pathfinding Algorithm.” n.d. https://andreasbogossian.com/posts/a-star/.