$sloprun.dev

Maze Generator & Solver

demo sandbox: allow-scripts · csp: default-src 'none'

sandboxed and isolated in your browser · never enter a real password in a demo

▶ 7 ran · ✓ 0 worked
i ran it — no login needed:
share: preview embed ↗
post it anywhere:
email the card:

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.

Embed this demo — put a runnable demo in your blog post

Paste this where you write. It renders a live, runnable demo inline anywhere raw HTML / iframes are allowed — Ghost, WordPress, Notion, Discourse, your own site.

<iframe src="https://sloprun.dev/embed/maze-solver" width="100%" height="640" loading="lazy" allow="" style="border:1px solid #E3E2DC;border-radius:10px" title="Maze Generator & Solver — a runnable demo on sloprun.dev"></iframe>
preview ↗

On Medium and dev.to the plain link becomes a rich preview card that links back here — they don't run third-party iframes, so paste the URL there and the reader clicks through to run it. https://sloprun.dev/p/maze-solver

Source

the code you see is the code that just ran raw ↗
Source — the code you see is the code that just ran 1030 lines 42.2 KB index.html
demos/maze-solver/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 &amp; 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 &amp; 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&#42; 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">&#215;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 &amp; 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&#42; 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 &middot; a&#42; &minus;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 &#215; 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> &middot; <span id="cellsV">576</span> cells</div>
      </section>

    </div>

  </main>

  <footer>demo &middot; 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 ? "&mdash;"
        : String(opened) + '<span class="u">/' + maze.N + "</span>";
      b.pathEl.innerHTML = solved
        ? String(R.path.length) + '<span class="u">&nbsp;cells</span>'
        : "&mdash;";
      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 &mdash; 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&hellip; 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 ? "&lt;1%" : saved + "%";
      var same = B.bfs.r.path.length === B.ast.r.path.length;
      verdictEl.innerHTML = tie
        ? "<b>A tie</b> &mdash; 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&#42;" : "Breadth-first") + "</b> got there first, opening " +
          "<span class=\"big\">" + savedTxt + "</span> fewer cells &mdash; " +
          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 ? "&minus;" : avg < 0 ? "+" : "";
    avgV.innerHTML = "across " + runs + " maze" + (runs === 1 ? "" : "s") +
      " &middot; a&#42; " + 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 total

No comments yet. If you ran it, say what happened.

Report this post

Goes straight to the moderation queue. Enough independent reports and the post is suspended automatically until a human looks.

what is wrong