0 reported it broke · the ▶ count is distinct visitors who ran it, counted once each, anonymously
A maze is carved live by recursive backtracking, then breadth-first search and A* race through identical copies of it, one cell per turn, leaving heatmaps of everywhere they looked. Because a carved maze has exactly one route between any two cells, both searches always come back with the same route — the only thing that differs is how many dead ends each had to open first, which turns the comparison into a clean read on what a heuristic actually buys you. The honest answer is "less than the textbook picture suggests": A* usually opens around 10% fewer cells than a blind sweep, occasionally a third fewer, and now and then almost none, because walls keep breaking the straight-line guess. Hit Regenerate a few times to watch the running average settle far below the headline number on any single maze.
Source — the code you see is the code that just ran 1030 lines 42.2 KB index.html
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1, viewport-fit=cover">
<title>Maze Generator & Solver — sloprun.dev</title>
<style>
/* ── sloprun design tokens (verbatim from demos/tokens.css) ───────────────── */
:root {
--bg: #F6F6F3; /* neutral paper, not cream */
--surface: #FFFFFF;
--ink: #1A1D21;
--muted: #5A6068;
--line: #E3E2DC;
--accent: #C05600; /* phosphor amber, darkened for light bg */
--accent-soft: #FFF3E6;
--run: #1A7F37; /* earned green */
--run-soft: #E7F4EA;
--danger: #C93C37;
--radius: 10px;
--font-sans: system-ui, -apple-system, "Segoe UI", sans-serif;
--font-mono: ui-monospace, "SF Mono", "Cascadia Code", Menlo, Consolas, monospace;
}
@media (prefers-color-scheme: dark) {
:root:not([data-theme="light"]) {
--bg: #14161A; --surface: #1C1F26; --ink: #E8E6E1; --muted: #9AA0A8;
--line: #2A2E36; --accent: #FFB454; --accent-soft: #2A2118;
--run: #3FB950; --run-soft: #16281B; --danger: #F47067;
}
}
:root[data-theme="dark"] {
--bg: #14161A; --surface: #1C1F26; --ink: #E8E6E1; --muted: #9AA0A8;
--line: #2A2E36; --accent: #FFB454; --accent-soft: #2A2118;
--run: #3FB950; --run-soft: #16281B; --danger: #F47067;
}
body { background: var(--bg); color: var(--ink); font-family: var(--font-sans); }
/* ── end tokens ───────────────────────────────────────────────────────────── */
/* demo-local additions (shadows need alpha; tokens are opaque hex) */
:root { --shadow: 0 1px 2px rgba(26,29,33,.05); }
@media (prefers-color-scheme: dark) {
:root:not([data-theme="light"]) { --shadow: 0 1px 2px rgba(0,0,0,.35); }
}
:root[data-theme="dark"] { --shadow: 0 1px 2px rgba(0,0,0,.35); }
* { box-sizing: border-box; }
html, body { margin: 0; padding: 0; }
html { -webkit-text-size-adjust: 100%; }
body { min-height: 100%; overflow-x: hidden; }
.wrap {
max-width: 1140px; margin: 0 auto; padding: 22px 16px 26px;
display: flex; flex-direction: column; gap: 16px;
}
/* header */
h1 { margin: 0 0 6px; font-size: clamp(21px, 3.6vw, 29px); letter-spacing: -.021em; line-height: 1.15; }
.lede { margin: 0; max-width: 68ch; color: var(--muted); font-size: 14.5px; line-height: 1.55; }
.lede b { color: var(--ink); font-weight: 600; }
/* layout */
.stage { display: grid; grid-template-columns: minmax(0,1fr) 282px; gap: 16px; align-items: start; }
@media (max-width: 940px) { .stage { grid-template-columns: minmax(0,1fr); } }
.boards { display: grid; grid-template-columns: repeat(2, minmax(0,1fr)); gap: 14px; }
@media (max-width: 620px) { .boards { grid-template-columns: minmax(0,1fr); } }
.card {
background: var(--surface); border: 1px solid var(--line);
border-radius: var(--radius); padding: 12px 13px; box-shadow: var(--shadow);
}
.card > h2 {
margin: 0 0 10px; font-family: var(--font-mono); font-size: 10.5px;
letter-spacing: .1em; text-transform: uppercase; color: var(--muted); font-weight: 600;
}
/* boards */
.board { display: flex; flex-direction: column; gap: 10px; }
.bhead { display: flex; align-items: flex-start; justify-content: space-between; gap: 8px; }
.btitle { min-width: 0; display: flex; align-items: center; gap: 6px; flex-wrap: wrap; }
.bname {
margin: 0; font-family: var(--font-mono); font-size: 11.5px; font-weight: 600;
letter-spacing: .085em; text-transform: uppercase; color: var(--ink);
}
.bsub { margin: 3px 0 0; font-size: 11.5px; line-height: 1.35; color: var(--muted); min-height: 2.7em; }
.badge {
font-family: var(--font-mono); font-size: 9.5px; letter-spacing: .09em; text-transform: uppercase;
color: var(--accent); background: var(--accent-soft); border-radius: 999px; padding: 2px 7px;
}
.badge[hidden] { display: none; }
.pill {
display: inline-flex; align-items: center; gap: 6px; flex: none;
font-family: var(--font-mono); font-size: 10.5px; letter-spacing: .04em;
padding: 3px 9px 3px 7px; border-radius: 999px;
border: 1px solid var(--line); color: var(--muted); background: var(--bg);
}
.pill .dot { width: 6px; height: 6px; border-radius: 50%; background: var(--muted); flex: none; }
.pill.busy { color: var(--accent); border-color: var(--accent); background: var(--accent-soft); }
.pill.busy .dot { background: var(--accent); animation: blink 1s steps(2, end) infinite; }
.pill.done { color: var(--run); background: var(--run-soft); border-color: transparent; }
.pill.done .dot { background: var(--run); }
@keyframes blink { 50% { opacity: .25; } }
.bwrap {
position: relative; border: 1px solid var(--line); border-radius: 8px;
background: var(--surface); overflow: hidden; aspect-ratio: 1 / 1;
}
canvas { display: block; width: 100%; height: 100%; }
.bstats { display: grid; grid-template-columns: repeat(2, minmax(0,1fr)); gap: 10px; }
.stat { display: flex; flex-direction: column; gap: 2px; min-width: 0; }
.stat .v {
font-family: var(--font-mono); font-size: 19px; line-height: 1.05;
font-variant-numeric: tabular-nums; letter-spacing: -.02em;
}
.stat .v .u { font-size: 11px; color: var(--muted); margin-left: 2px; letter-spacing: 0; }
.stat .k {
font-family: var(--font-mono); font-size: 9.5px; letter-spacing: .09em;
text-transform: uppercase; color: var(--muted);
}
/* panel */
.panel { display: flex; flex-direction: column; gap: 12px; }
.stepline {
display: flex; align-items: baseline; justify-content: space-between; gap: 8px;
font-family: var(--font-mono); font-size: 12px; color: var(--muted);
font-variant-numeric: tabular-nums; margin-bottom: 6px;
}
.stepline .n { color: var(--ink); }
.prog { height: 5px; border-radius: 3px; background: var(--line); overflow: hidden; }
.prog i { display: block; height: 100%; width: 0; background: var(--accent); }
.row { display: flex; flex-wrap: wrap; gap: 7px; margin-top: 11px; }
.row > button { flex: 1 1 auto; }
button {
font: inherit; font-size: 13px; font-family: var(--font-sans);
color: var(--ink); background: var(--surface);
border: 1px solid var(--line); border-radius: 8px;
padding: 7px 11px; cursor: pointer; line-height: 1.2;
transition: border-color .12s ease, color .12s ease, background .12s ease;
}
button:hover:not(:disabled) { border-color: var(--accent); color: var(--accent); }
button:focus-visible { outline: 2px solid var(--accent); outline-offset: 2px; }
button:disabled { opacity: .42; cursor: not-allowed; }
button.primary { background: var(--accent); color: var(--surface); border-color: var(--accent); font-weight: 600; }
button.primary:hover:not(:disabled) { color: var(--surface); filter: brightness(1.07); }
/* comparison bars */
.cmp { display: flex; flex-direction: column; gap: 9px; }
.cmpRow { display: grid; grid-template-columns: 1fr; gap: 4px; }
.cmpTop { display: flex; align-items: baseline; justify-content: space-between; gap: 8px; }
.cmpTop .lb {
font-family: var(--font-mono); font-size: 9.5px; letter-spacing: .09em;
text-transform: uppercase; color: var(--muted);
}
.cmpTop .n { font-family: var(--font-mono); font-size: 12px; font-variant-numeric: tabular-nums; }
.bar { height: 8px; border-radius: 4px; background: var(--line); overflow: hidden; }
.bar i { display: block; height: 100%; border-radius: 4px; background: var(--muted); width: 0; }
.cmpRow.alt .bar i { background: var(--accent); }
.verdict { margin: 11px 0 0; font-size: 12.5px; line-height: 1.5; color: var(--muted); }
.verdict b { color: var(--ink); font-weight: 600; }
.verdict .big { font-family: var(--font-mono); color: var(--accent); font-size: 13px; }
.verdict .ok { color: var(--run); }
/* legend */
.legend { display: flex; align-items: center; gap: 8px; margin-top: 11px; }
.legend .gr { flex: 1 1 auto; height: 6px; border-radius: 3px; }
.legend .lbl {
font-family: var(--font-mono); font-size: 9.5px; letter-spacing: .07em;
text-transform: uppercase; color: var(--muted);
}
.keys { display: flex; flex-wrap: wrap; gap: 10px; margin-top: 10px; }
.keys span { display: inline-flex; align-items: center; gap: 5px; font-size: 11.5px; color: var(--muted); }
.keys i { width: 10px; height: 10px; border-radius: 3px; flex: none; }
/* controls */
.ctl { display: block; margin-bottom: 13px; }
.ctl:last-child { margin-bottom: 0; }
.ctl-top { display: flex; justify-content: space-between; align-items: baseline; gap: 8px; margin-bottom: 3px; }
.ctl-top label { font-size: 13px; }
.ctl-top .val { font-family: var(--font-mono); font-size: 12px; color: var(--muted); font-variant-numeric: tabular-nums; }
.ctl.off .ctl-top label, .ctl.off .ctl-top .val { opacity: .45; }
input[type=range] {
-webkit-appearance: none; appearance: none; display: block;
width: 100%; height: 20px; margin: 0; background: transparent; cursor: pointer;
}
input[type=range]::-webkit-slider-runnable-track { height: 4px; border-radius: 2px; background: var(--line); }
input[type=range]::-webkit-slider-thumb {
-webkit-appearance: none; width: 15px; height: 15px; margin-top: -5.5px;
border-radius: 50%; background: var(--accent); border: 2px solid var(--surface);
box-shadow: 0 0 0 1px var(--line);
}
input[type=range]::-moz-range-track { height: 4px; border-radius: 2px; background: var(--line); }
input[type=range]::-moz-range-thumb {
width: 13px; height: 13px; border-radius: 50%; background: var(--accent);
border: 2px solid var(--surface); box-shadow: 0 0 0 1px var(--line);
}
input[type=range]:focus-visible { outline: 2px solid var(--accent); outline-offset: 2px; border-radius: 6px; }
input[type=range]:disabled { opacity: .4; cursor: not-allowed; }
.switch { display: flex; align-items: center; gap: 9px; cursor: pointer; font-size: 13px; margin-top: 12px; }
.switch input { position: absolute; opacity: 0; width: 0; height: 0; }
.track {
width: 34px; height: 19px; border-radius: 999px; background: var(--line);
border: 1px solid var(--line); position: relative; flex: none; transition: background .15s ease;
}
.track::after {
content: ""; position: absolute; top: 1.5px; left: 2px; width: 14px; height: 14px;
border-radius: 50%; background: var(--surface); transition: transform .15s ease;
box-shadow: 0 1px 2px rgba(0,0,0,.25);
}
.switch input:checked + .track { background: var(--accent); border-color: var(--accent); }
.switch input:checked + .track::after { transform: translateX(15px); }
.switch input:focus-visible + .track { outline: 2px solid var(--accent); outline-offset: 2px; }
.meta {
font-family: var(--font-mono); font-size: 11px; color: var(--muted);
letter-spacing: .03em; margin-top: 11px;
}
.note { margin: 10px 0 0; font-size: 11.5px; line-height: 1.4; color: var(--muted); }
.note[hidden] { display: none; }
footer {
font-family: var(--font-mono); font-size: 11px; color: var(--muted);
letter-spacing: .05em; padding-top: 2px;
}
.sr-only {
position: absolute; width: 1px; height: 1px; padding: 0; margin: -1px;
overflow: hidden; clip: rect(0 0 0 0); white-space: nowrap; border: 0;
}
@media (prefers-reduced-motion: reduce) {
*, *::before, *::after { transition-duration: .001ms !important; animation-duration: .001ms !important; animation-iteration-count: 1 !important; }
}
</style>
</head>
<body>
<div class="wrap">
<header>
<h1>Maze Generator & Solver</h1>
<p class="lede">
A maze gets carved by <b>recursive backtracking</b>, then two ways of finding the way out
race through identical copies of it, one cell per turn. <b>Breadth-first</b> spreads evenly in
every direction; <b>A*</b> leans toward the exit. Both come back with the same route every
time — the only question is how many dead ends each opens first, and that swings a lot from
maze to maze. Hit <b>Regenerate</b> a few times and watch the margin move.
</p>
</header>
<main class="stage">
<div class="boards" id="boards">
<section class="card board" aria-labelledby="nameBfs">
<div class="bhead">
<div>
<div class="btitle">
<h2 class="bname" id="nameBfs">Breadth-first</h2>
<span class="badge" id="badgeBfs" hidden>first</span>
</div>
<p class="bsub">Fans out evenly. No idea where the exit is.</p>
</div>
<span class="pill" id="pillBfs"><span class="dot"></span><span id="pillBfsT">ready</span></span>
</div>
<div class="bwrap">
<canvas id="cvBfs" role="img" aria-label="Breadth-first search map.">
A map of the maze showing which cells breadth-first search opened.
</canvas>
</div>
<div class="bstats">
<div class="stat"><span class="v" id="bfsOpen">—</span><span class="k">cells opened</span></div>
<div class="stat"><span class="v" id="bfsPath">—</span><span class="k">route length</span></div>
</div>
</section>
<section class="card board" aria-labelledby="nameAst">
<div class="bhead">
<div>
<div class="btitle">
<h2 class="bname" id="nameAst">A* search</h2>
<span class="badge" id="badgeAst" hidden>first</span>
</div>
<p class="bsub">Same steps, but prefers cells that look closer to the exit.</p>
</div>
<span class="pill" id="pillAst"><span class="dot"></span><span id="pillAstT">ready</span></span>
</div>
<div class="bwrap">
<canvas id="cvAst" role="img" aria-label="A star search map.">
A map of the maze showing which cells A* search opened.
</canvas>
</div>
<div class="bstats">
<div class="stat"><span class="v" id="astOpen">—</span><span class="k">cells opened</span></div>
<div class="stat"><span class="v" id="astPath">—</span><span class="k">route length</span></div>
</div>
</section>
</div>
<div class="panel">
<section class="card" aria-label="Race controls">
<h2>Race</h2>
<div class="stepline">
<span><span id="stepLbl">turn</span> <span class="n" id="stepV">0</span> / <span id="stepT">0</span></span>
<span id="phaseV">solved</span>
</div>
<div class="prog" aria-hidden="true"><i id="progBar"></i></div>
<div class="row">
<button type="button" class="primary" id="raceBtn">Race again</button>
<button type="button" id="regenBtn">Regenerate</button>
</div>
<div class="ctl" style="margin-top:13px" id="speedCtl">
<div class="ctl-top">
<label for="speed">Speed</label><span class="val" id="speedV" aria-hidden="true">×1.0</span>
</div>
<input type="range" id="speed" min="0.25" max="4" step="0.25" value="1">
</div>
<label class="switch" for="anim">
<input type="checkbox" id="anim" checked>
<span class="track" aria-hidden="true"></span>
<span>Animate carving & search</span>
</label>
<p class="note" id="rmNote" hidden>Your system asks for reduced motion, so animation starts off. Turn it on above if you want to watch.</p>
</section>
<section class="card" aria-label="Result">
<h2>Result</h2>
<div class="cmp">
<div class="cmpRow">
<div class="cmpTop"><span class="lb">breadth-first</span><span class="n" id="cmpBfs">—</span></div>
<div class="bar"><i id="barBfs"></i></div>
</div>
<div class="cmpRow alt">
<div class="cmpTop"><span class="lb">a* search</span><span class="n" id="cmpAst">—</span></div>
<div class="bar"><i id="barAst"></i></div>
</div>
</div>
<p class="verdict" id="verdict">Both searches are ready.</p>
<div class="meta" id="avgV">across 1 maze · a* −0%</div>
<div class="legend" aria-hidden="true">
<span class="lbl">early</span>
<span class="gr" id="legendGr"></span>
<span class="lbl">late</span>
</div>
<div class="keys" aria-hidden="true">
<span><i id="keyFront"></i>on the edge</span>
<span><i id="keyPath"></i>the route out</span>
</div>
</section>
<section class="card" aria-label="Maze">
<h2>Maze</h2>
<div class="ctl">
<div class="ctl-top">
<label for="size">Size</label><span class="val" id="sizeV" aria-hidden="true">24 × 24</span>
</div>
<input type="range" id="size" min="8" max="40" step="1" value="24">
</div>
<div class="meta">seed <span id="seedV">11104</span> · <span id="cellsV">576</span> cells</div>
</section>
</div>
</main>
<footer>demo · sloprun.dev</footer>
</div>
<div class="sr-only" role="status" aria-live="polite" id="live"></div>
<script>
(function () {
"use strict";
/* ── theme plumbing ─────────────────────────────────────────────────────── */
var root = document.documentElement;
var mqDark = window.matchMedia ? matchMedia("(prefers-color-scheme: dark)") : null;
var mqRM = window.matchMedia ? matchMedia("(prefers-reduced-motion: reduce)") : null;
var reduced = !!(mqRM && mqRM.matches);
window.addEventListener("message", function (e) {
var d = e.data;
if (d && d.type === "sloprun:theme" && (d.theme === "light" || d.theme === "dark")) {
root.setAttribute("data-theme", d.theme);
readTheme(); paint();
}
});
if (mqDark) {
var onScheme = function () { readTheme(); paint(); };
if (mqDark.addEventListener) mqDark.addEventListener("change", onScheme);
else if (mqDark.addListener) mqDark.addListener(onScheme);
}
/* ── colour ─────────────────────────────────────────────────────────────── */
var COL = {
surface: [255,255,255], ink: [26,29,33],
accent: [192,86,0], accentSoft: [255,243,230], run: [26,127,55]
};
var RAMP_N = 32, ramp = [], css = {};
function hexToRgb(h) {
h = String(h).trim();
if (h.charAt(0) === "#") h = h.slice(1);
if (h.length === 3) h = h.charAt(0)+h.charAt(0)+h.charAt(1)+h.charAt(1)+h.charAt(2)+h.charAt(2);
if (h.length !== 6) return null;
var n = parseInt(h, 16);
if (isNaN(n)) return null;
return [(n >> 16) & 255, (n >> 8) & 255, n & 255];
}
function tok(name, fb) {
var v = getComputedStyle(root).getPropertyValue(name);
return hexToRgb(v) || fb;
}
function rgb(c) { return "rgb(" + c[0] + "," + c[1] + "," + c[2] + ")"; }
function rgba(c, a) { return "rgba(" + c[0] + "," + c[1] + "," + c[2] + "," + a + ")"; }
function mix(a, b, t) {
return [Math.round(a[0]+(b[0]-a[0])*t), Math.round(a[1]+(b[1]-a[1])*t), Math.round(a[2]+(b[2]-a[2])*t)];
}
function readTheme() {
COL.surface = tok("--surface", COL.surface);
COL.ink = tok("--ink", COL.ink);
COL.accent = tok("--accent", COL.accent);
COL.accentSoft = tok("--accent-soft", COL.accentSoft);
COL.run = tok("--run", COL.run);
ramp.length = 0;
for (var k = 0; k < RAMP_N; k++) {
var t = 0.34 + 0.66 * (k / (RAMP_N - 1));
ramp.push(rgb(mix(COL.accentSoft, COL.accent, t)));
}
css.surface = rgb(COL.surface);
css.wall = rgba(COL.ink, 0.88);
css.frontier = rgb(mix(COL.accentSoft, COL.accent, 0.12));
css.frontDot = rgba(COL.accent, 0.42);
css.carveOn = rgb(mix(COL.accentSoft, COL.accent, 0.16));
css.head = rgb(COL.accent);
css.run = rgb(COL.run);
css.runGlow = rgba(COL.run, 0.5);
css.start = rgba(COL.ink, 0.72);
css.goalRing = rgb(COL.accent);
var gr = document.getElementById("legendGr");
if (gr) gr.style.background = "linear-gradient(90deg," + ramp[0] + "," + ramp[RAMP_N - 1] + ")";
var kf = document.getElementById("keyFront"), kp = document.getElementById("keyPath");
if (kf) { kf.style.background = css.frontier; kf.style.boxShadow = "inset 0 0 0 1px " + rgba(COL.accent, .35); }
if (kp) kp.style.background = css.run;
}
/* ── dom ────────────────────────────────────────────────────────────────── */
var $ = function (id) { return document.getElementById(id); };
var boardsEl = $("boards");
var raceBtn = $("raceBtn"), regenBtn = $("regenBtn");
var speedEl = $("speed"), speedV = $("speedV"), speedCtl = $("speedCtl");
var animEl = $("anim"), rmNote = $("rmNote");
var sizeEl = $("size"), sizeV = $("sizeV"), seedV = $("seedV"), cellsV = $("cellsV");
var stepV = $("stepV"), stepT = $("stepT"), stepLbl = $("stepLbl"),
phaseV = $("phaseV"), progBar = $("progBar");
var verdictEl = $("verdict"), avgV = $("avgV"), live = $("live");
var B = {
bfs: {
cv: $("cvBfs"), ctx: $("cvBfs").getContext("2d"),
open: $("bfsOpen"), pathEl: $("bfsPath"),
pill: $("pillBfs"), pillT: $("pillBfsT"), badge: $("badgeBfs"),
cmp: $("cmpBfs"), bar: $("barBfs"), label: "Breadth-first search"
},
ast: {
cv: $("cvAst"), ctx: $("cvAst").getContext("2d"),
open: $("astOpen"), pathEl: $("astPath"),
pill: $("pillAst"), pillT: $("pillAstT"), badge: $("badgeAst"),
cmp: $("cmpAst"), bar: $("barAst"), label: "A star search"
}
};
var LIST = [B.bfs, B.ast];
/* ── maze generation: recursive backtracker ─────────────────────────────── */
var OPP = { 1: 4, 2: 8, 4: 1, 8: 2 };
function mulberry32(a) {
return function () {
a |= 0; a = a + 0x6D2B79F5 | 0;
var t = Math.imul(a ^ a >>> 15, 1 | a);
t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t;
return ((t ^ t >>> 14) >>> 0) / 4294967296;
};
}
function genMaze(n, seed) {
var N = n * n;
var w = new Uint8Array(N); w.fill(15); /* 1=N 2=E 4=S 8=W, bit set = wall */
var seen = new Uint8Array(N);
var rnd = mulberry32(seed >>> 0);
var stack = [0], carve = [{ c: 0, from: -1, d: 0 }];
seen[0] = 1;
var pick = [0, 0, 0, 0, 0, 0, 0, 0];
while (stack.length) {
var c = stack[stack.length - 1];
var x = c % n, y = (c / n) | 0, k = 0;
if (y > 0 && !seen[c - n]) { pick[k++] = c - n; pick[k++] = 1; }
if (x < n - 1 && !seen[c + 1]) { pick[k++] = c + 1; pick[k++] = 2; }
if (y < n - 1 && !seen[c + n]) { pick[k++] = c + n; pick[k++] = 4; }
if (x > 0 && !seen[c - 1]) { pick[k++] = c - 1; pick[k++] = 8; }
if (!k) { stack.pop(); continue; }
var j = ((rnd() * (k / 2)) | 0) * 2;
var nb = pick[j], d = pick[j + 1];
w[c] &= ~d; w[nb] &= ~OPP[d];
seen[nb] = 1; stack.push(nb);
carve.push({ c: nb, from: c, d: d });
}
return { n: n, N: N, w: w, carve: carve, seed: seed };
}
/* ── searches ───────────────────────────────────────────────────────────── */
function nbrs(m, c, out) {
var n = m.n, w = m.w[c], k = 0;
if (!(w & 1)) out[k++] = c - n;
if (!(w & 2)) out[k++] = c + 1;
if (!(w & 4)) out[k++] = c + n;
if (!(w & 8)) out[k++] = c - 1;
return k;
}
function trace(par, goal) {
var p = [], c = goal, guard = 0;
while (c !== -1 && guard++ < 1e6) { p.push(c); if (c === 0) break; c = par[c]; }
p.reverse();
return p;
}
function Heap() { this.f = []; this.h = []; this.c = []; this.n = 0; }
Heap.prototype.less = function (a, b) {
return this.f[a] < this.f[b] || (this.f[a] === this.f[b] && this.h[a] < this.h[b]);
};
Heap.prototype.swap = function (a, b) {
var t;
t = this.f[a]; this.f[a] = this.f[b]; this.f[b] = t;
t = this.h[a]; this.h[a] = this.h[b]; this.h[b] = t;
t = this.c[a]; this.c[a] = this.c[b]; this.c[b] = t;
};
Heap.prototype.push = function (f, h, c) {
var i = this.n++;
this.f[i] = f; this.h[i] = h; this.c[i] = c;
while (i > 0) { var p = (i - 1) >> 1; if (!this.less(i, p)) break; this.swap(i, p); i = p; }
};
Heap.prototype.pop = function () {
var top = this.c[0];
this.n--;
if (this.n > 0) {
this.f[0] = this.f[this.n]; this.h[0] = this.h[this.n]; this.c[0] = this.c[this.n];
var i = 0;
for (;;) {
var l = 2 * i + 1, r = l + 1, m = i;
if (l < this.n && this.less(l, m)) m = l;
if (r < this.n && this.less(r, m)) m = r;
if (m === i) break;
this.swap(m, i); i = m;
}
}
return top;
};
function search(m, kind) {
var n = m.n, N = m.N, goal = N - 1;
var ord = new Int32Array(N), dsc = new Int32Array(N), par = new Int32Array(N);
ord.fill(-1); dsc.fill(-1); par.fill(-1);
var seq = [], dseq = [], out = [0, 0, 0, 0];
var step = 0, goalStep = -1, c, k, j, nb;
if (kind === "bfs") {
var q = new Int32Array(N), head = 0, tail = 0, seen = new Uint8Array(N);
q[tail++] = 0; seen[0] = 1; dsc[0] = 0; dseq.push(0);
while (head < tail) {
c = q[head++];
ord[c] = step; seq.push(c);
if (c === goal) { goalStep = step; break; }
k = nbrs(m, c, out);
for (j = 0; j < k; j++) {
nb = out[j];
if (!seen[nb]) { seen[nb] = 1; par[nb] = c; dsc[nb] = step; dseq.push(nb); q[tail++] = nb; }
}
step++;
}
} else {
var g = new Int32Array(N); g.fill(0x3fffffff);
var gx = n - 1, gy = n - 1;
var hOf = function (i) { return (gx - (i % n)) + (gy - ((i / n) | 0)); };
var heap = new Heap();
g[0] = 0; dsc[0] = 0; dseq.push(0);
heap.push(hOf(0), hOf(0), 0);
while (heap.n) {
c = heap.pop();
if (ord[c] !== -1) continue; /* stale duplicate */
ord[c] = step; seq.push(c);
if (c === goal) { goalStep = step; break; }
k = nbrs(m, c, out);
for (j = 0; j < k; j++) {
nb = out[j];
var ng = g[c] + 1;
if (ng < g[nb]) {
g[nb] = ng; par[nb] = c;
if (dsc[nb] === -1) { dsc[nb] = step; dseq.push(nb); }
heap.push(ng + hOf(nb), hOf(nb), nb);
}
}
step++;
}
}
return {
ord: ord, dsc: dsc, seq: seq, dseq: dseq,
path: goalStep >= 0 ? trace(par, goal) : [],
goalStep: goalStep, expanded: goalStep + 1
};
}
/* ── state ──────────────────────────────────────────────────────────────── */
var maze = null, MAXO = 1, totalSteps = 1;
var mode = "idle"; /* idle | carve | race | flash */
var raceT = 0, carveT = 0, rafId = 0, lastTs = 0, speed = 1, animate = !reduced;
var wcur = null, applied = 0, flashTimer = 0;
function build(n, seed) {
maze = genMaze(n, seed);
B.bfs.r = search(maze, "bfs");
B.ast.r = search(maze, "astar");
MAXO = Math.max(1, B.bfs.r.goalStep, B.ast.r.goalStep);
totalSteps = MAXO + 1;
B.bfs.pathT = 0; B.ast.pathT = 0;
wcur = null; applied = 0;
seedV.textContent = String(seed);
cellsV.textContent = String(maze.N);
stepT.textContent = String(totalSteps);
LIST.forEach(measure);
}
/* ── geometry ───────────────────────────────────────────────────────────── */
function measure(b) {
var dpr = Math.min(2, window.devicePixelRatio || 1);
/* measure the canvas box itself — the wrapper's rect includes its 1px
border, which would size the bitmap 2px larger than it is drawn and
leave every wall softly rescaled. */
var rect = b.cv.getBoundingClientRect();
var rw = rect.width, rh = rect.height;
if (!rw || !rh) {
var pr = b.cv.parentNode.getBoundingClientRect();
rw = rw || pr.width; rh = rh || pr.height || pr.width || rw;
}
var w = Math.max(80, Math.round(rw * dpr));
var h = Math.max(80, Math.round((rh || rw) * dpr));
if (b.cv.width !== w) b.cv.width = w;
if (b.cv.height !== h) b.cv.height = h;
var n = maze ? maze.n : 24;
var s = Math.min(w, h);
var lw = Math.max(1, Math.round(s / n * 0.085));
var pad = Math.ceil(lw / 2) + 1;
var cs = (s - 2 * pad) / n;
b.geo = { ox: (w - s) / 2 + pad, oy: (h - s) / 2 + pad, cs: cs, lw: lw, n: n };
b.wp = wallPath(maze ? maze.w : null, b.geo);
}
function wallPath(w, geo) {
var p = new Path2D();
if (!w) return p;
var n = geo.n, cs = geo.cs, ox = geo.ox, oy = geo.oy, x, y, i, X, Y;
for (y = 0; y < n; y++) {
for (x = 0; x < n; x++) {
i = y * n + x; X = ox + x * cs; Y = oy + y * cs;
if (w[i] & 1) { p.moveTo(X, Y); p.lineTo(X + cs, Y); }
if (w[i] & 8) { p.moveTo(X, Y); p.lineTo(X, Y + cs); }
if (x === n - 1 && (w[i] & 2)) { p.moveTo(X + cs, Y); p.lineTo(X + cs, Y + cs); }
if (y === n - 1 && (w[i] & 4)) { p.moveTo(X, Y + cs); p.lineTo(X + cs, Y + cs); }
}
}
return p;
}
/* ── painting ───────────────────────────────────────────────────────────── */
function revealed(b) {
if (mode === "carve") return 0;
var r = Math.floor(raceT);
if (r > b.r.expanded) r = b.r.expanded;
return r < 0 ? 0 : r;
}
function cellRect(ctx, geo, c) {
var n = geo.n, cs = geo.cs;
ctx.fillRect(geo.ox + (c % n) * cs, geo.oy + ((c / n) | 0) * cs, cs + 0.6, cs + 0.6);
}
function cx(geo, c) { return geo.ox + (c % geo.n) * geo.cs + geo.cs / 2; }
function cy(geo, c) { return geo.oy + ((c / geo.n) | 0) * geo.cs + geo.cs / 2; }
function paintBoard(b) {
var ctx = b.ctx, geo = b.geo;
if (!geo || !maze) return;
var cs = geo.cs, i, c, k;
ctx.setTransform(1, 0, 0, 1, 0, 0);
ctx.fillStyle = css.surface;
ctx.fillRect(0, 0, b.cv.width, b.cv.height);
if (mode === "carve") {
var cr = Math.min(maze.carve.length, Math.max(0, Math.floor(carveT)));
syncCarve(cr);
ctx.fillStyle = css.carveOn;
for (i = 0; i < cr; i++) cellRect(ctx, geo, maze.carve[i].c);
if (cr > 0) { ctx.fillStyle = css.head; cellRect(ctx, geo, maze.carve[cr - 1].c); }
ctx.strokeStyle = css.wall;
ctx.lineWidth = geo.lw;
ctx.lineCap = "square";
ctx.stroke(wallPath(wcur, geo));
return;
}
var r = revealed(b), R = b.r;
/* explored cells, coloured by when they were opened (shared scale) */
var prevK = -1;
for (i = 0; i < r && i < R.seq.length; i++) {
k = (i * (RAMP_N - 1) / MAXO) | 0;
if (k > RAMP_N - 1) k = RAMP_N - 1;
if (k !== prevK) { ctx.fillStyle = ramp[k]; prevK = k; }
cellRect(ctx, geo, R.seq[i]);
}
/* cells sitting on the edge of the search, seen but not opened yet */
ctx.fillStyle = css.frontier;
for (i = 0; i < R.dseq.length; i++) {
c = R.dseq[i];
if (R.dsc[c] >= r) break;
if (R.ord[c] < 0 || R.ord[c] >= r) cellRect(ctx, geo, c);
}
if (cs > 7) {
ctx.fillStyle = css.frontDot;
for (i = 0; i < R.dseq.length; i++) {
c = R.dseq[i];
if (R.dsc[c] >= r) break;
if (R.ord[c] < 0 || R.ord[c] >= r) {
ctx.beginPath();
ctx.arc(cx(geo, c), cy(geo, c), cs * 0.13, 0, 6.2832);
ctx.fill();
}
}
}
/* walls */
ctx.strokeStyle = css.wall;
ctx.lineWidth = geo.lw;
ctx.lineCap = "square";
ctx.stroke(b.wp);
/* the route out */
var solved = r > R.goalStep && R.goalStep >= 0;
if (solved && R.path.length > 1 && b.pathT > 0) {
var total = (R.path.length - 1) * cs;
var vis = total * b.pathT;
ctx.lineJoin = "round"; ctx.lineCap = "round";
ctx.setLineDash([vis, total + cs]);
ctx.beginPath();
ctx.moveTo(cx(geo, R.path[0]), cy(geo, R.path[0]));
for (i = 1; i < R.path.length; i++) ctx.lineTo(cx(geo, R.path[i]), cy(geo, R.path[i]));
ctx.strokeStyle = css.surface;
ctx.lineWidth = Math.max(2, cs * 0.36);
ctx.stroke();
ctx.shadowColor = css.runGlow;
ctx.shadowBlur = Math.max(2, cs * 0.5);
ctx.strokeStyle = css.run;
ctx.lineWidth = Math.max(1.4, cs * 0.24);
ctx.stroke();
ctx.shadowBlur = 0;
ctx.setLineDash([]);
ctx.lineCap = "square";
}
/* start and exit markers */
var rad = Math.max(2, cs * 0.2);
ctx.fillStyle = css.start;
ctx.beginPath(); ctx.arc(cx(geo, 0), cy(geo, 0), rad * 1.05, 0, 6.2832); ctx.fill();
ctx.strokeStyle = css.surface;
ctx.lineWidth = Math.max(1, cs * 0.08);
ctx.stroke();
var g = maze.N - 1;
if (solved && b.pathT > 0.6) {
ctx.fillStyle = css.run;
ctx.beginPath(); ctx.arc(cx(geo, g), cy(geo, g), rad * 1.15, 0, 6.2832); ctx.fill();
} else {
ctx.strokeStyle = css.goalRing;
ctx.lineWidth = Math.max(1.4, cs * 0.14);
ctx.beginPath(); ctx.arc(cx(geo, g), cy(geo, g), rad, 0, 6.2832); ctx.stroke();
}
}
function syncCarve(cr) {
if (!wcur || cr < applied) {
wcur = new Uint8Array(maze.N); wcur.fill(15); applied = 0;
}
while (applied < cr) {
var e = maze.carve[applied++];
if (e.from >= 0) { wcur[e.from] &= ~e.d; wcur[e.c] &= ~OPP[e.d]; }
}
}
function paint() {
LIST.forEach(paintBoard);
readout();
}
/* ── readout ────────────────────────────────────────────────────────────── */
function pct(a, b) { return Math.round(a / b * 100); }
function readout() {
if (!maze) return;
var carving = mode === "carve";
var maxExp = Math.max(B.bfs.r.expanded, B.ast.r.expanded, 1);
var bothSolved = true;
LIST.forEach(function (b) {
var r = revealed(b), R = b.r;
var solved = r > R.goalStep && R.goalStep >= 0;
if (!solved) bothSolved = false;
var opened = carving ? 0 : Math.min(r, R.expanded);
b.open.innerHTML = carving ? "—"
: String(opened) + '<span class="u">/' + maze.N + "</span>";
b.pathEl.innerHTML = solved
? String(R.path.length) + '<span class="u"> cells</span>'
: "—";
b.cmp.textContent = carving ? "—" : String(opened);
b.bar.style.width = (carving ? 0 : opened / maxExp * 100) + "%";
b.pill.className = "pill" + (carving ? "" : solved ? " done" : " busy");
b.pillT.textContent = carving ? "waiting" : solved ? "solved" : "searching";
});
var win = B.bfs.r.expanded <= B.ast.r.expanded ? B.bfs : B.ast;
var lose = win === B.bfs ? B.ast : B.bfs;
var tie = B.bfs.r.expanded === B.ast.r.expanded;
LIST.forEach(function (b) {
var r = revealed(b);
b.badge.hidden = !(!tie && b === win && !carving && r > b.r.goalStep);
});
if (carving) {
var cr = Math.min(maze.carve.length, Math.max(0, Math.floor(carveT)));
stepLbl.textContent = "carved";
stepV.textContent = String(cr);
stepT.textContent = String(maze.carve.length);
progBar.style.width = Math.min(100, cr / maze.carve.length * 100) + "%";
} else {
var st = Math.min(totalSteps, Math.floor(raceT));
stepLbl.textContent = "turn";
stepV.textContent = String(st);
stepT.textContent = String(totalSteps);
progBar.style.width = st / totalSteps * 100 + "%";
}
phaseV.textContent = carving ? "carving"
: (mode === "race" || mode === "flash") ? "racing"
: bothSolved ? "solved" : "ready";
if (carving) {
verdictEl.innerHTML = "Carving the maze — the walker digs until it is boxed in, then backs up to the last cell with an unvisited neighbour.";
} else if (!bothSolved) {
verdictEl.innerHTML = "Searching… each side opens one cell per turn.";
} else {
var saved = Math.round((1 - win.r.expanded / Math.max(1, lose.r.expanded)) * 100);
/* a margin of a few cells on a big maze rounds to zero — say so honestly
rather than claiming "0% fewer" */
var savedTxt = saved < 1 ? "<1%" : saved + "%";
var same = B.bfs.r.path.length === B.ast.r.path.length;
verdictEl.innerHTML = tie
? "<b>A tie</b> — both opened <span class=\"big\">" + B.bfs.r.expanded + "</span> cells on this maze. " +
(same ? "Same route out, <b>" + B.bfs.r.path.length + "</b> cells long." : "")
: "<b>" + (win === B.ast ? "A*" : "Breadth-first") + "</b> got there first, opening " +
"<span class=\"big\">" + savedTxt + "</span> fewer cells — " +
win.r.expanded + " against " + lose.r.expanded + " of " + maze.N + ". " +
(same ? "Both came back with the <span class=\"ok\">same route</span>, <b>" + B.bfs.r.path.length + "</b> cells long." : "");
}
}
function describe() {
LIST.forEach(function (b) {
var R = b.r;
b.cv.setAttribute("aria-label",
b.label + " map: " + R.expanded + " of " + maze.N + " cells opened (" +
pct(R.expanded, maze.N) + " percent), route out is " + R.path.length + " cells long.");
});
}
/* ── animation ──────────────────────────────────────────────────────────── */
function stopLoop() { if (rafId) cancelAnimationFrame(rafId); rafId = 0; lastTs = 0; }
function loop(ts) {
rafId = requestAnimationFrame(loop);
var dt = lastTs ? Math.min(0.05, (ts - lastTs) / 1000) : 0.016;
lastTs = ts;
if (mode === "carve") {
carveT += Math.max(120, maze.carve.length / 1.1) * speed * dt;
if (carveT >= maze.carve.length) { carveT = maze.carve.length; startRace(); }
} else if (mode === "race") {
raceT += Math.max(60, totalSteps / 2.2) * speed * dt;
var done = raceT >= totalSteps;
if (done) raceT = totalSteps;
LIST.forEach(function (b) {
if (Math.floor(raceT) > b.r.goalStep) b.pathT = Math.min(1, b.pathT + dt / 0.42);
});
if (done && B.bfs.pathT >= 1 && B.ast.pathT >= 1) { finish(true); return; }
} else { stopLoop(); return; }
paint();
}
function startLoop() { if (!rafId) { lastTs = 0; rafId = requestAnimationFrame(loop); } }
function startCarve() {
clearTimeout(flashTimer);
mode = "carve"; carveT = 0; wcur = null; applied = 0;
raceT = 0; B.bfs.pathT = 0; B.ast.pathT = 0;
raceBtn.textContent = "Stop";
paint(); startLoop();
}
function startRace() {
mode = "race"; raceT = 0; B.bfs.pathT = 0; B.ast.pathT = 0;
raceBtn.textContent = "Stop";
paint(); startLoop();
}
function finish(announce) {
clearTimeout(flashTimer);
stopLoop();
mode = "idle"; raceT = totalSteps; carveT = 0;
B.bfs.pathT = 1; B.ast.pathT = 1;
raceBtn.disabled = false;
raceBtn.textContent = "Race again";
paint(); describe();
if (announce) {
var win = B.bfs.r.expanded <= B.ast.r.expanded ? B.bfs : B.ast;
var lose = win === B.bfs ? B.ast : B.bfs;
say(B.bfs.r.expanded === B.ast.r.expanded
? "Tie. Both opened " + B.bfs.r.expanded + " cells."
: win.label + " finished first, opening " + win.r.expanded + " cells against " +
lose.r.expanded + ". Both routes are " + B.bfs.r.path.length + " cells long.");
}
}
var runs = 0, sumSaved = 0;
function tally() {
runs++;
sumSaved += 1 - B.ast.r.expanded / Math.max(1, B.bfs.r.expanded);
var avg = Math.round(sumSaved / runs * 100);
var sign = avg > 0 ? "−" : avg < 0 ? "+" : "";
avgV.innerHTML = "across " + runs + " maze" + (runs === 1 ? "" : "s") +
" · a* " + sign + Math.abs(avg) + "% cells opened";
}
var sayTimer = 0;
function say(msg) {
clearTimeout(sayTimer);
sayTimer = setTimeout(function () { live.textContent = msg; }, 140);
}
/* ── controls ───────────────────────────────────────────────────────────── */
raceBtn.addEventListener("click", function () {
if (mode === "carve" || mode === "race") { finish(false); say("Race stopped, result shown."); return; }
if (animate) { startRace(); return; }
/* reduced motion / animation off: clear, then resolve in one discrete step */
clearTimeout(flashTimer);
mode = "flash"; raceT = 0; B.bfs.pathT = 0; B.ast.pathT = 0;
raceBtn.disabled = true;
paint();
flashTimer = setTimeout(function () { finish(true); }, 280);
});
regenBtn.addEventListener("click", function () {
stopLoop(); clearTimeout(flashTimer); raceBtn.disabled = false;
build(+sizeEl.value, (Math.random() * 900000 + 1000) | 0);
tally();
if (animate) startCarve();
else { finish(false); say("New maze, solved. " + B.ast.r.expanded + " cells opened by A star, " + B.bfs.r.expanded + " by breadth-first."); }
});
sizeEl.addEventListener("input", function () {
var n = +sizeEl.value;
sizeV.textContent = n + " × " + n;
stopLoop(); clearTimeout(flashTimer); raceBtn.disabled = false;
build(n, maze ? maze.seed : 20260813);
finish(false);
});
/* one tally per settled size, not per input event while dragging */
sizeEl.addEventListener("change", function () { tally(); });
speedEl.addEventListener("input", function () {
speed = +speedEl.value;
speedV.textContent = "×" + (speed === (speed | 0) ? speed.toFixed(1) : String(speed));
});
animEl.addEventListener("change", function () {
animate = animEl.checked;
speedEl.disabled = !animate;
speedCtl.classList.toggle("off", !animate);
if (!animate && (mode === "carve" || mode === "race")) finish(false);
});
/* ── boot ───────────────────────────────────────────────────────────────── */
readTheme();
speed = +speedEl.value;
speedV.textContent = "×1.0";
sizeV.textContent = sizeEl.value + " × " + sizeEl.value;
animEl.checked = animate;
speedEl.disabled = !animate;
speedCtl.classList.toggle("off", !animate);
rmNote.hidden = !reduced;
build(+sizeEl.value, 11104);
tally();
finish(false);
if (window.ResizeObserver) {
new ResizeObserver(function () { LIST.forEach(measure); paint(); }).observe(boardsEl);
} else {
window.addEventListener("resize", function () { LIST.forEach(measure); paint(); });
}
})();
</script>
</body>
</html>
source-visible by construction · nothing is published here without its code
Comments
0 totalNo comments yet. If you ran it, say what happened.