/*!
 * levels.js — Procedural level generator
 * -------------------------------------------------------------
 * 100 levels across five difficulty tiers (Easy/Medium/Hard/Expert/
 * Insane). Every level is carved as a *perfect maze* (a spanning tree,
 * so there is always exactly one route between any two cells - this
 * guarantees every level is solvable by construction) using a seeded
 * RNG keyed off the level id, then dressed with tier-appropriate
 * mechanics: holes, spikes, ice/sticky floor, wind zones, speed pads,
 * checkpoints, moving obstacles, rotating barriers, switches, timed
 * gates, keys/doors and teleport portals.
 *
 * Gating mechanics (switch+gate / key+door) are placed so the switch
 * or key always sits on a branch off the main route *before* the gate
 * that blocks it, and the branch is always reachable without crossing
 * that same gate - so every level remains solvable even with a lock
 * on the direct path.
 */
(function (global) {
  'use strict';
  const LAB = (global.LAB = global.LAB || {});

  const TOTAL_LEVELS = 100;

  function clamp(v, lo, hi) { return v < lo ? lo : (v > hi ? hi : v); }

  // Deterministic PRNG (mulberry32) so a given level id always regenerates
  // the exact same layout - needed for level select / replay consistency.
  function mulberry32(seed) {
    return function () {
      seed |= 0; seed = (seed + 0x6D2B79F5) | 0;
      let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
      t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
      return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
    };
  }

  const TIERS = [
    { name: 'Easy', from: 1, to: 20 },
    { name: 'Medium', from: 21, to: 40 },
    { name: 'Hard', from: 41, to: 60 },
    { name: 'Expert', from: 61, to: 80 },
    { name: 'Insane', from: 81, to: 100 }
  ];

  function tierOf(id) {
    for (let i = 0; i < TIERS.length; i++) if (id >= TIERS[i].from && id <= TIERS[i].to) return i;
    return TIERS.length - 1;
  }
  function gridSizeOf(id) { return clamp(6 + Math.floor((id - 1) / 10), 6, 15); }

  function getMeta(id) {
    const t = tierOf(id);
    return { id, tier: t, tierName: TIERS[t].name, indexInTier: id - TIERS[t].from + 1, gridSize: gridSizeOf(id) };
  }

  // ---- Maze carve: randomized recursive backtracker ----------------------
  // Produces long winding corridors + occasional branches/dead-ends, which
  // matches the brief's "walls / dead ends / long corridors / tight
  // passages" requirement, and guarantees full connectivity by construction.
  function carveMaze(n, rng) {
    const cell = [];
    for (let r = 0; r < n; r++) { const row = []; for (let c = 0; c < n; c++) row.push({ N: true, E: true, S: true, W: true }); cell.push(row); }
    const visited = Array.from({ length: n }, () => new Array(n).fill(false));
    const DIRS = [['N', -1, 0, 'S'], ['E', 0, 1, 'W'], ['S', 1, 0, 'N'], ['W', 0, -1, 'E']];
    const stack = [[0, 0]];
    visited[0][0] = true;
    while (stack.length) {
      const [r, c] = stack[stack.length - 1];
      const options = [];
      for (let i = 0; i < DIRS.length; i++) {
        const [dir, dr, dc, opp] = DIRS[i];
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) options.push([dir, nr, nc, opp]);
      }
      if (!options.length) { stack.pop(); continue; }
      const [dir, nr, nc, opp] = options[Math.floor(rng() * options.length)];
      cell[r][c][dir] = false;
      cell[nr][nc][opp] = false;
      visited[nr][nc] = true;
      stack.push([nr, nc]);
    }
    return cell;
  }

  function openNeighbors(cell, n, r, c) {
    const out = [], cc = cell[r][c];
    if (!cc.N && r > 0) out.push([r - 1, c]);
    if (!cc.S && r < n - 1) out.push([r + 1, c]);
    if (!cc.E && c < n - 1) out.push([r, c + 1]);
    if (!cc.W && c > 0) out.push([r, c - 1]);
    return out;
  }

  function bfs(cell, n, start) {
    const dist = Array.from({ length: n }, () => new Array(n).fill(-1));
    const parent = Array.from({ length: n }, () => new Array(n).fill(null));
    const q = [start];
    dist[start[0]][start[1]] = 0;
    for (let qi = 0; qi < q.length; qi++) {
      const [r, c] = q[qi];
      const neighbors = openNeighbors(cell, n, r, c);
      for (let i = 0; i < neighbors.length; i++) {
        const [nr, nc] = neighbors[i];
        if (dist[nr][nc] === -1) { dist[nr][nc] = dist[r][c] + 1; parent[nr][nc] = [r, c]; q.push([nr, nc]); }
      }
    }
    return { dist, parent };
  }

  function farthestCell(dist, n) {
    let best = [0, 0], bd = -1;
    for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) if (dist[r][c] > bd) { bd = dist[r][c]; best = [r, c]; }
    return best;
  }
  function pathCells(parent, from) {
    const path = []; let cur = from;
    while (cur) { path.push(cur); cur = parent[cur[0]][cur[1]]; }
    return path.reverse();
  }
  function cellCenter(r, c, cs) { return { x: c * cs + cs / 2, y: r * cs + cs / 2 }; }
  function shuffle(arr, rng) { for (let i = arr.length - 1; i > 0; i--) { const j = Math.floor(rng() * (i + 1)); const t = arr[i]; arr[i] = arr[j]; arr[j] = t; } }

  function findLeaves(cell, n, exclude) {
    const leaves = [];
    for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) {
      const cc = cell[r][c];
      const openings = (cc.N ? 0 : 1) + (cc.S ? 0 : 1) + (cc.E ? 0 : 1) + (cc.W ? 0 : 1);
      if (openings === 1 && !exclude.has(r + ',' + c)) leaves.push([r, c]);
    }
    return leaves;
  }

  // Cells adjacent to the main path that lead into a side branch (subtree).
  function findBranchPoints(cell, n, path) {
    const onPath = new Set(path.map(p => p[0] + ',' + p[1]));
    const branches = [];
    for (let i = 1; i < path.length - 1; i++) {
      const [r, c] = path[i];
      const neighbors = openNeighbors(cell, n, r, c);
      for (let k = 0; k < neighbors.length; k++) {
        const [nr, nc] = neighbors[k];
        if (!onPath.has(nr + ',' + nc)) branches.push({ pathIndex: i, from: [r, c], into: [nr, nc] });
      }
    }
    return branches;
  }

  // Walk a few random steps into a branch's subtree (never back the way we came).
  function walkInto(cell, n, from, avoidBack, steps, rng) {
    let cur = from, prev = avoidBack;
    for (let i = 0; i < steps; i++) {
      const options = openNeighbors(cell, n, cur[0], cur[1]).filter(p => !(p[0] === prev[0] && p[1] === prev[1]));
      if (!options.length) break;
      const next = options[Math.floor(rng() * options.length)];
      prev = cur; cur = next;
    }
    return cur;
  }

  // ---- Geometry: cell grid -> wall rectangles keyed by "row,col" bucket --
  function buildGeometry(cell, n, cellSize, wallThickness) {
    const wallBuckets = {};
    const t = wallThickness;
    function addWall(r, c, rect) { const k = r + ',' + c; (wallBuckets[k] = wallBuckets[k] || []).push(rect); }
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        const x0 = c * cellSize, y0 = r * cellSize, cc = cell[r][c];
        // Only draw each interior wall once (from its N/W side) to avoid
        // duplicates; the far boundary (S of last row, E of last col) is
        // special-cased since no neighbouring cell ever claims it.
        if (cc.N) addWall(r, c, { x: x0 - t / 2, y: y0 - t / 2, w: cellSize + t, h: t });
        if (cc.W) addWall(r, c, { x: x0 - t / 2, y: y0 - t / 2, w: t, h: cellSize + t });
        if (r === n - 1 && cc.S) addWall(r, c, { x: x0 - t / 2, y: (y0 + cellSize) - t / 2, w: cellSize + t, h: t });
        if (c === n - 1 && cc.E) addWall(r, c, { x: (x0 + cellSize) - t / 2, y: y0 - t / 2, w: t, h: cellSize + t });
      }
    }
    return wallBuckets;
  }

  function generateLevel(id) {
    const meta = getMeta(id);
    const n = meta.gridSize;
    const rng = mulberry32(Math.imul(id, 2654435761) >>> 0);
    const cell = carveMaze(n, rng);
    const { dist, parent } = bfs(cell, n, [0, 0]);
    const finishCell = farthestCell(dist, n);
    const path = pathCells(parent, finishCell);

    const cellSize = 64;
    const wallThickness = 8 + meta.tier * 3; // thicker walls -> tighter gaps at higher tiers
    const wallBuckets = buildGeometry(cell, n, cellSize, wallThickness);

    const zones = [];
    const gates = {};
    const movingObstacles = [];
    const rotatingBars = [];
    const portalPairs = {};
    const exclude = new Set(['0,0', finishCell[0] + ',' + finishCell[1]]);

    const startC = cellCenter(0, 0, cellSize);
    const finishC = cellCenter(finishCell[0], finishCell[1], cellSize);
    zones.push({ type: 'finish', x: finishC.x - cellSize * 0.3, y: finishC.y - cellSize * 0.3, w: cellSize * 0.6, h: cellSize * 0.6, cx: finishC.x, cy: finishC.y });

    // --- Expert+/Insane: one gating mechanic (switch, timed switch, or key) ---
    const branches = findBranchPoints(cell, n, path);
    let gateCounter = 0;
    function placeGate(pathIndexAfterBranch, kind, branch) {
      const [r1, c1] = path[pathIndexAfterBranch - 1];
      const [r2, c2] = path[pathIndexAfterBranch];
      const gateId = 'gate' + (gateCounter++);
      const dr = r2 - r1;
      const midR = Math.min(r1, r2), midC = Math.min(c1, c2);
      const t = wallThickness;
      let rect;
      if (dr !== 0) rect = { x: midC * cellSize - t / 2, y: (midR + 1) * cellSize - t / 2, w: cellSize + t, h: t };
      else rect = { x: (midC + 1) * cellSize - t / 2, y: midR * cellSize - t / 2, w: t, h: cellSize + t };
      rect.gateId = gateId;
      const key = r1 + ',' + c1;
      (wallBuckets[key] = wallBuckets[key] || []).push(rect);

      const deep = walkInto(cell, n, branch.into, branch.from, 2 + (rng() * 3 | 0), rng);
      const dc2 = cellCenter(deep[0], deep[1], cellSize);
      if (kind === 'key') {
        gates[gateId] = { open: false, isDoor: true };
        zones.push({ type: 'key', x: dc2.x - 12, y: dc2.y - 12, w: 24, h: 24, doorId: gateId, collected: false });
      } else {
        gates[gateId] = { open: false, isDoor: false };
        zones.push({ type: 'switch', x: dc2.x - 14, y: dc2.y - 14, w: 28, h: 28, gateId, timed: kind === 'timedSwitch', timedDuration: 6, triggered: false });
      }
      exclude.add(deep[0] + ',' + deep[1]);
    }
    if (meta.tier >= 3 && branches.length && path.length > 6) {
      const kinds = ['switch', 'timedSwitch', 'key'];
      const kind = kinds[id % kinds.length];
      const branch = branches[Math.min(branches.length - 1, Math.floor((0.3 + rng() * 0.25) * branches.length))];
      const gateIdx = Math.min(path.length - 2, branch.pathIndex + 2 + (rng() * 3 | 0));
      if (gateIdx > branch.pathIndex) placeGate(gateIdx, kind, branch);
    }

    // --- Medium+: holes; Hard+: spikes too - placed on dead-end leaves -----
    if (meta.tier >= 1) {
      const leaves = findLeaves(cell, n, exclude);
      shuffle(leaves, rng);
      const budget = Math.min(leaves.length, Math.round(leaves.length * (0.25 + (meta.tier - 1) * 0.18)));
      for (let i = 0; i < budget; i++) {
        const [r, c] = leaves[i];
        const p = cellCenter(r, c, cellSize);
        const type = (meta.tier >= 2 && i % 2 === 1) ? 'spike' : 'hole';
        const size = type === 'hole' ? 22 : 15;
        zones.push({ type, x: p.x - size, y: p.y - size, w: size * 2, h: size * 2, cx: p.x, cy: p.y });
      }
    }

    // --- Medium+: ice + speed pads; Hard+: sticky + wind -------------------
    if (meta.tier >= 1 && path.length > 4) {
      const kinds = ['ice', 'speedpad'];
      if (meta.tier >= 2) kinds.push('sticky', 'wind');
      const count = 2 + meta.tier;
      for (let i = 0; i < count; i++) {
        const idx = 2 + Math.floor(rng() * Math.max(1, path.length - 4));
        const [r, c] = path[idx];
        const p = cellCenter(r, c, cellSize);
        const k = kinds[Math.floor(rng() * kinds.length)];
        if (k === 'wind') {
          const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
          const d = dirs[Math.floor(rng() * dirs.length)];
          zones.push({ type: 'wind', x: p.x - cellSize * 0.4, y: p.y - cellSize * 0.4, w: cellSize * 0.8, h: cellSize * 0.8, dirX: d[0], dirY: d[1] });
        } else if (k === 'speedpad') {
          zones.push({ type: 'speedpad', x: p.x - 16, y: p.y - 16, w: 32, h: 32 });
        } else {
          zones.push({ type: k, x: p.x - cellSize * 0.42, y: p.y - cellSize * 0.42, w: cellSize * 0.84, h: cellSize * 0.84 });
        }
      }
    }

    // --- Medium+: checkpoints, more of them at higher tiers ----------------
    if (meta.tier >= 1 && path.length > 6) {
      const num = meta.tier;
      const step = Math.floor(path.length / (num + 1));
      for (let k = 1; k <= num; k++) {
        const idx = Math.min(path.length - 2, k * step);
        const [r, c] = path[idx];
        const p = cellCenter(r, c, cellSize);
        zones.push({ type: 'checkpoint', x: p.x - 14, y: p.y - 14, w: 28, h: 28, cx: p.x, cy: p.y, triggered: false });
      }
    }

    // --- Hard+: moving obstacles --------------------------------------------
    if (meta.tier >= 2) {
      const num = meta.tier - 1;
      for (let i = 0; i < num; i++) {
        const idx = 3 + Math.floor(rng() * Math.max(1, path.length - 6));
        const [r, c] = path[idx];
        const p = cellCenter(r, c, cellSize);
        const horiz = rng() < 0.5;
        const span = cellSize * 0.32;
        movingObstacles.push({
          x0: p.x - (horiz ? span : 0), x1: p.x + (horiz ? span : 0),
          y0: p.y - (!horiz ? span : 0), y1: p.y + (!horiz ? span : 0),
          x: p.x, y: p.y, radius: 13, speed: 1.4 + rng(), phase: rng() * 6.283, hazard: true
        });
      }
    }

    // --- Expert+: rotating barriers at wider junctions ----------------------
    if (meta.tier >= 3) {
      const num = meta.tier - 2;
      const junctions = path.filter((p, i) => i > 1 && i < path.length - 2 && openNeighbors(cell, n, p[0], p[1]).length >= 3);
      shuffle(junctions, rng);
      for (let i = 0; i < num && i < junctions.length; i++) {
        const [r, c] = junctions[i];
        const p = cellCenter(r, c, cellSize);
        rotatingBars.push({ cx: p.x, cy: p.y, length: cellSize * 0.75, thickness: 10, baseAngle: rng() * 6.283, angularSpeed: (0.6 + rng() * 0.5) * (rng() < 0.5 ? 1 : -1), angle: 0, tipSpeed: 0 });
      }
    }

    // --- Insane only: one teleport portal pair ------------------------------
    if (meta.tier >= 4 && path.length > 10) {
      const a = path[3 + (rng() * 3 | 0)];
      const b = path[path.length - 4 - (rng() * 3 | 0)];
      const pa = cellCenter(a[0], a[1], cellSize), pb = cellCenter(b[0], b[1], cellSize);
      const zoneA = { type: 'portal', x: pa.x - 16, y: pa.y - 16, w: 32, h: 32, pairId: 'p1', cx: pb.x, cy: pb.y, color: 'a' };
      const zoneB = { type: 'portal', x: pb.x - 16, y: pb.y - 16, w: 32, h: 32, pairId: 'p1', cx: pa.x, cy: pa.y, color: 'b' };
      zones.push(zoneA, zoneB);
      portalPairs.p1 = [zoneA, zoneB];
    }

    const pixelWidth = n * cellSize, pixelHeight = n * cellSize, B = 400;
    const boundary = {
      top: { x: -B, y: -B, w: pixelWidth + 2 * B, h: B },
      bottom: { x: -B, y: pixelHeight, w: pixelWidth + 2 * B, h: B },
      left: { x: -B, y: -B, w: B, h: pixelHeight + 2 * B },
      right: { x: pixelWidth, y: -B, w: B, h: pixelHeight + 2 * B }
    };

    return {
      id, tier: meta.tier, tierName: meta.tierName, cols: n, rows: n, cellSize,
      pixelWidth, pixelHeight, wallBuckets, boundary, zones, gates,
      movingObstacles, rotatingBars, portalPairs,
      start: { x: startC.x, y: startC.y },
      parLength: path.length
    };
  }

  LAB.Levels = {
    TOTAL_LEVELS, TIERS, getMeta, generateLevel,
    _internal: { carveMaze, bfs, openNeighbors, mulberry32, farthestCell, pathCells }
  };
})(typeof window !== 'undefined' ? window : globalThis);
