Maze Carve and Solve

<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/bundles/anime.umd.min.js"></script>
<script>
  (function () {
    // Maze Carve and Solve: a digger wanders the grid, knocking down walls
    // into cells it hasn't visited and backing up when it's boxed in, until
    // the whole grid is one perfect maze. Then a flood spreads from the
    // entrance, filling every passage in step order, and when it reaches the
    // exit the shortest path draws itself back through it. With data-loop it
    // holds, fades and carves a new maze. Paused when off screen.
    // Usage: <div data-maze-carve-and-solve style="height:360px"></div>
    // Optional: data-cell (cell size in px, default fits about 15 cells down
    // the box), data-speed (speed multiplier, default 1), data-path (colour of
    // the solved path, default #ec4899), data-loop (carve another maze).
    var DEFAULTS = { speed: 1, path: '#ec4899', carve: 4200, flood: 1600, trace: 1100, hold: 2200 };
    var FLOOR = '#f5f3ff', DIG = '#fbcfe8', HEAD = '#db2777', WAVE = [[153, 246, 228], [196, 181, 253]];
    var DIRS = [[0, -1], [1, 0], [0, 1], [-1, 0]];

    var css =
      '[data-maze-carve-and-solve]{position:relative;isolation:isolate;overflow:hidden}' +
      '.mzs-canvas{position:absolute;inset:0;width:100%;height:100%;z-index:-1}';
    var style = document.createElement('style');
    style.textContent = css;
    document.head.appendChild(style);

    function reduced() { return window.matchMedia('(prefers-reduced-motion: reduce)').matches; }

    function build(el) {
      var d = el.dataset;
      var canvas = document.createElement('canvas');
      canvas.className = 'mzs-canvas';
      canvas.setAttribute('aria-hidden', 'true');
      el.insertBefore(canvas, el.firstChild);
      var ctx = canvas.getContext('2d');
      var speed = +d.speed || DEFAULTS.speed;
      var pathColor = d.path || DEFAULTS.path;
      var loop = d.loop !== undefined && d.loop !== 'false';
      var w = 0, h = 0, dpr = 1, cs = 20, wall = 4, cols = 1, rows = 1, ox = 0, oy = 0;
      // Per cell: open walls (bits for N E S W), state (0 rock, 1 on the stack, 2 done), flood distance.
      var open, state, dist, stack, path, maxDist = 0, goal = 0;
      var phase = 'carve', carry = 0, reach = 0, traced = 0, age = 0, fading = false;

      function resize() {
        var nw = el.clientWidth, nh = el.clientHeight;
        if (nw === w && nh === h) return false;
        w = nw; h = nh;
        dpr = Math.min(2, window.devicePixelRatio || 1);
        canvas.width = Math.round(w * dpr);
        canvas.height = Math.round(h * dpr);
        var pad = Math.max(10, Math.min(w, h) * 0.05);
        cs = +d.cell || Math.max(9, Math.round((Math.min(w, h) - pad * 2) / 15));
        cols = Math.max(2, Math.floor((w - pad * 2) / cs));
        rows = Math.max(2, Math.floor((h - pad * 2) / cs));
        wall = Math.max(2, Math.round(cs * 0.28));
        ox = Math.round((w - cols * cs) / 2);
        oy = Math.round((h - rows * cs) / 2);
        return true;
      }

      function start() {
        var n = cols * rows;
        open = new Uint8Array(n);
        state = new Uint8Array(n);
        dist = new Int32Array(n).fill(-1);
        stack = [0];
        state[0] = 1;
        path = [];
        phase = 'carve';
        carry = reach = traced = age = 0;
        canvas.style.opacity = 1;
      }

      // One move of the digger: into a random unvisited neighbour, or back up.
      function dig() {
        if (!stack.length) return false;
        var c = stack[stack.length - 1], x = c % cols, y = (c / cols) | 0, ways = [];
        for (var i = 0; i < 4; i++) {
          var nx = x + DIRS[i][0], ny = y + DIRS[i][1];
          if (nx >= 0 && ny >= 0 && nx < cols && ny < rows && !state[ny * cols + nx]) ways.push(i);
        }
        if (!ways.length) {
          state[c] = 2;
          stack.pop();
          return stack.length > 0;
        }
        var k = ways[Math.floor(Math.random() * ways.length)], m = (y + DIRS[k][1]) * cols + x + DIRS[k][0];
        open[c] |= 1 << k;
        open[m] |= 1 << ((k + 2) % 4);
        state[m] = 1;
        stack.push(m);
        return true;
      }

      // Distances from the entrance, and the shortest path back from the exit.
      function solve() {
        var q = [0], head = 0;
        dist[0] = 0;
        while (head < q.length) {
          var c = q[head++], x = c % cols, y = (c / cols) | 0;
          for (var i = 0; i < 4; i++) {
            if (!(open[c] & (1 << i))) continue;
            var m = (y + DIRS[i][1]) * cols + x + DIRS[i][0];
            if (dist[m] < 0) { dist[m] = dist[c] + 1; q.push(m); }
          }
        }
        goal = cols * rows - 1;
        maxDist = dist[goal];
        path = [goal];
        for (var at = goal; at !== 0;) {
          var ax = at % cols, ay = (at / cols) | 0;
          for (var j = 0; j < 4; j++) {
            if (!(open[at] & (1 << j))) continue;
            var p = (ay + DIRS[j][1]) * cols + ax + DIRS[j][0];
            if (dist[p] === dist[at] - 1) { at = p; break; }
          }
          path.push(at);
        }
        path.reverse();
      }

      function centre(c) {
        return [ox + (c % cols) * cs + cs / 2, oy + ((c / cols) | 0) * cs + cs / 2];
      }

      function cellColor(c) {
        if (phase !== 'carve' && dist[c] >= 0 && dist[c] <= reach) {
          var k = Math.min(1, dist[c] / Math.max(1, maxDist)), a = WAVE[0], b = WAVE[1];
          return 'rgb(' + Math.round(a[0] + (b[0] - a[0]) * k) + ',' + Math.round(a[1] + (b[1] - a[1]) * k) + ',' + Math.round(a[2] + (b[2] - a[2]) * k) + ')';
        }
        return state[c] === 1 ? DIG : FLOOR;
      }

      function draw() {
        ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
        ctx.clearRect(0, 0, w, h);
        var inner = cs - wall, half = wall / 2;
        for (var c = 0; c < cols * rows; c++) {
          if (!state[c]) continue;
          var x = ox + (c % cols) * cs + half, y = oy + ((c / cols) | 0) * cs + half;
          ctx.fillStyle = cellColor(c);
          ctx.fillRect(x, y, inner, inner);
          // Knock through to the east and south (the others are drawn by the neighbour).
          if (open[c] & 2) ctx.fillRect(x + inner - 0.5, y, wall + 1, inner);
          if (open[c] & 4) ctx.fillRect(x, y + inner - 0.5, inner, wall + 1);
        }
        if (phase === 'carve' && stack.length) {
          var hc = centre(stack[stack.length - 1]);
          ctx.fillStyle = HEAD;
          ctx.beginPath();
          ctx.arc(hc[0], hc[1], inner * 0.38, 0, Math.PI * 2);
          ctx.fill();
        }
        if (phase !== 'carve') {
          // Entrance and exit.
          var s = centre(0), e = centre(cols * rows - 1);
          ctx.fillStyle = '#10b981';
          ctx.beginPath();
          ctx.arc(s[0], s[1], inner * 0.32, 0, Math.PI * 2);
          ctx.fill();
          ctx.fillStyle = pathColor;
          ctx.beginPath();
          ctx.arc(e[0], e[1], inner * 0.32, 0, Math.PI * 2);
          ctx.fill();
        }
        if (traced > 0) {
          var n = Math.min(path.length - 1, traced), whole = Math.floor(n);
          ctx.strokeStyle = pathColor;
          ctx.lineWidth = Math.max(2, inner * 0.36);
          ctx.lineCap = ctx.lineJoin = 'round';
          ctx.beginPath();
          var p0 = centre(path[0]), tip = p0;
          ctx.moveTo(p0[0], p0[1]);
          for (var i = 1; i <= whole; i++) { tip = centre(path[i]); ctx.lineTo(tip[0], tip[1]); }
          if (whole < path.length - 1) {
            var a = centre(path[whole]), b = centre(path[whole + 1]), f = n - whole;
            tip = [a[0] + (b[0] - a[0]) * f, a[1] + (b[1] - a[1]) * f];
            ctx.lineTo(tip[0], tip[1]);
          }
          ctx.stroke();
          ctx.fillStyle = '#fff';
          ctx.beginPath();
          ctx.arc(tip[0], tip[1], Math.max(2, inner * 0.2), 0, Math.PI * 2);
          ctx.fill();
        }
      }

      function tick(dt) {
        age += dt;
        if (phase === 'carve') {
          // Two moves per cell (in and back out), spread over the carve time.
          carry += dt * cols * rows * 2 / DEFAULTS.carve * speed;
          while (carry >= 1) {
            carry--;
            if (!dig()) { solve(); phase = 'flood'; age = 0; break; }
          }
        } else if (phase === 'flood') {
          reach = (age / DEFAULTS.flood * speed) * (maxDist + 4);
          if (reach >= maxDist + 4) { phase = 'trace'; age = 0; }
        } else if (phase === 'trace') {
          reach = 1e9;
          traced = Math.min(path.length - 1, age / DEFAULTS.trace * speed * (path.length - 1));
          if (traced >= path.length - 1) { phase = 'hold'; age = 0; }
        } else if (phase === 'hold' && loop && !fading && age > DEFAULTS.hold) {
          fading = true;
          anime.animate(canvas, {
            opacity: 0, duration: 600, ease: 'inOut(2)',
            onComplete: function () { fading = false; start(); }
          });
        }
      }

      function still() {
        start();
        while (dig());
        solve();
        reach = 1e9;
        traced = path.length - 1;
        phase = 'hold';
        draw();
      }

      resize();
      start();
      if (reduced()) {
        still();
        if (window.ResizeObserver) new ResizeObserver(function () { if (resize()) still(); }).observe(el);
        return;
      }
      if (window.ResizeObserver) new ResizeObserver(function () { if (resize()) start(); }).observe(el);

      var last = 0;
      var timer = anime.createTimer({
        loop: true,
        duration: 1000,
        autoplay: false,
        onUpdate: function () {
          var now = performance.now();
          var dt = last ? Math.min(50, now - last) : 16;
          last = now;
          tick(dt);
          draw();
        }
      });
      // Pause while off screen to save battery.
      new IntersectionObserver(function (entries) {
        if (entries[0].isIntersecting) { last = 0; timer.play(); } else timer.pause();
      }).observe(el);
    }

    function init() {
      document.querySelectorAll('[data-maze-carve-and-solve]').forEach(function (el) {
        if (el._mzs) return;
        el._mzs = true;
        build(el);
      });
    }

    if (document.readyState === 'loading') document.addEventListener('DOMContentLoaded', init);
    else init();
  })();
</script>

<div data-maze-carve-and-solve data-loop style="height: 360px; background: #1a1033"></div>