// Muse Engine 30 - mesh collider (Phase 30). Author: Muse Glimmer (muse-glimmer-30b, llama.cpp, 27 Sep 2026), coached by Grok Bot.
// Raw output: game/muse-authored/phase30/raw/engine/physics/mesh-collider.js (one minified line). This copy is the same code
// pretty-printed (formatting only) plus coach fixes marked "[coach fix Pn]"; the fix log is game/muse-authored/phase30/FIXES-P30.md.
// API: window.MuseMeshCollider.build(positions, {cell, walkableNy}) -> { stats, groundAt, groundAtDisc, wallHit, pushOut, raycast, findSpawn }
(function () {
  function barycentricXZ(px, pz, ax, az, bx, bz, cx, cz) {
    var v0x = bx - ax,
      v0z = bz - az,
      v1x = cx - ax,
      v1z = cz - az,
      v2x = px - ax,
      v2z = pz - az;
    var d00 = v0x * v0x + v0z * v0z;
    var d01 = v0x * v1x + v0z * v1z;
    var d11 = v1x * v1x + v1z * v1z;
    var d20 = v2x * v0x + v2z * v0z;
    var d21 = v2x * v1x + v2z * v1z;
    var denom = d00 * d11 - d01 * d01;
    if (Math.abs(denom) < 1e-12) return null;
    var inv = 1 / denom;
    var u = (d11 * d20 - d01 * d21) * inv;
    var v = (d00 * d21 - d01 * d20) * inv;
    if (u >= -1e-7 && v >= -1e-7 && u + v <= 1 + 1e-7) return [u, v];
    return null;
  }
  // [coach fix P3] Muse's closest-point routine did not follow Ericson 5.1.5 (vertex B region tested bc.bp, the edge regions
  // were guessed), so points next to a wall face read as "not touching". Replaced with the textbook version (same signature).
  function closestPointTri(px, py, pz, ax, ay, az, bx, by, bz, cx, cy, cz) {
    var abx = bx - ax, aby = by - ay, abz = bz - az, acx = cx - ax, acy = cy - ay, acz = cz - az;
    var apx = px - ax, apy = py - ay, apz = pz - az;
    var d1 = abx * apx + aby * apy + abz * apz, d2 = acx * apx + acy * apy + acz * apz;
    if (d1 <= 0 && d2 <= 0) return [ax, ay, az];
    var bpx = px - bx, bpy = py - by, bpz = pz - bz;
    var d3 = abx * bpx + aby * bpy + abz * bpz, d4 = acx * bpx + acy * bpy + acz * bpz;
    if (d3 >= 0 && d4 <= d3) return [bx, by, bz];
    var vc = d1 * d4 - d3 * d2;
    if (vc <= 0 && d1 >= 0 && d3 <= 0) { var v1 = d1 / (d1 - d3); return [ax + abx * v1, ay + aby * v1, az + abz * v1]; }
    var cpx = px - cx, cpy = py - cy, cpz = pz - cz;
    var d5 = abx * cpx + aby * cpy + abz * cpz, d6 = acx * cpx + acy * cpy + acz * cpz;
    if (d6 >= 0 && d5 <= d6) return [cx, cy, cz];
    var vb = d5 * d2 - d1 * d6;
    if (vb <= 0 && d2 >= 0 && d6 <= 0) { var w1 = d2 / (d2 - d6); return [ax + acx * w1, ay + acy * w1, az + acz * w1]; }
    var va = d3 * d6 - d5 * d4;
    if (va <= 0 && d4 - d3 >= 0 && d5 - d6 >= 0) { var w2 = (d4 - d3) / (d4 - d3 + (d5 - d6)); return [bx + (cx - bx) * w2, by + (cy - by) * w2, bz + (cz - bz) * w2]; }
    var den = 1 / (va + vb + vc), v = vb * den, w = vc * den;
    return [ax + abx * v + acx * w, ay + aby * v + acy * w, az + abz * v + acz * w];
  }
  window.MuseMeshCollider = {
    build: function (positions, opts) {
      opts = opts || {};
      var cell = opts.cell || 2.0;
      var walkableNy = opts.walkableNy !== undefined ? opts.walkableNy : 0.7;
      var n = (positions.length / 9) | 0;
      var triN = new Float32Array(n * 3),
        triMinY = new Float32Array(n),
        triMaxY = new Float32Array(n),
        triMinX = new Float32Array(n),
        triMaxX = new Float32Array(n),
        triMinZ = new Float32Array(n),
        triMaxZ = new Float32Array(n),
        walkable = new Uint8Array(n);
      var min = [Infinity, Infinity, Infinity],
        max = [-Infinity, -Infinity, -Infinity];
      for (var i = 0; i < n; i++) {
        var b = i * 9;
        var x0 = positions[b],
          y0 = positions[b + 1],
          z0 = positions[b + 2];
        var x1 = positions[b + 3],
          y1 = positions[b + 4],
          z1 = positions[b + 5];
        var x2 = positions[b + 6],
          y2 = positions[b + 7],
          z2 = positions[b + 8];
        // [coach fix P1] Muse skipped any triangle with two equal x, y OR z coordinates as "degenerate" - that dropped every
        // flat floor and axis-aligned wall (the test scene lost all 17k triangles). Only the area test below is kept.
        var e1x = x1 - x0,
          e1y = y1 - y0,
          e1z = z1 - z0;
        var e2x = x2 - x0,
          e2y = y2 - y0,
          e2z = z2 - z0;
        var nx = e1y * e2z - e1z * e2y,
          ny = e1z * e2x - e1x * e2z,
          nz = e1x * e2y - e1y * e2x;
        var len = Math.hypot(nx, ny, nz);
        if (len < 1e-10) {
          triN[i * 3 + 1] = -2;
          continue;
        }
        nx /= len;
        ny /= len;
        nz /= len;
        triN[i * 3] = nx;
        triN[i * 3 + 1] = ny;
        triN[i * 3 + 2] = nz;
        var mnx = Math.min(x0, x1, x2),
          mxx = Math.max(x0, x1, x2);
        var mnz = Math.min(z0, z1, z2),
          mxz = Math.max(z0, z1, z2);
        var mny = Math.min(y0, y1, y2),
          mxy = Math.max(y0, y1, y2);
        triMinX[i] = mnx;
        triMaxX[i] = mxx;
        triMinZ[i] = mnz;
        triMaxZ[i] = mxz;
        triMinY[i] = mny;
        triMaxY[i] = mxy;
        walkable[i] = ny >= walkableNy ? 1 : 0;
        min[0] = Math.min(min[0], mnx);
        min[1] = Math.min(min[1], mny);
        min[2] = Math.min(min[2], mnz);
        max[0] = Math.max(max[0], mxx);
        max[1] = Math.max(max[1], mxy);
        max[2] = Math.max(max[2], mxz);
      }
      var grid = {};
      for (var i = 0; i < n; i++) {
        if (triN[i * 3 + 1] === -2) continue;
        var ix0 = Math.floor(triMinX[i] / cell),
          ix1 = Math.floor(triMaxX[i] / cell);
        var iz0 = Math.floor(triMinZ[i] / cell),
          iz1 = Math.floor(triMaxZ[i] / cell);
        for (var ix = ix0; ix <= ix1; ix++) {
          for (var iz = iz0; iz <= iz1; iz++) {
            var k = ix + "," + iz;
            var arr = grid[k];
            if (!arr) {
              arr = [];
              grid[k] = arr;
            }
            arr.push(i);
          }
        }
      }
      var cells = 0;
      for (var k in grid) cells++;
      var collider = {
        stats: { tris: n, walkable: 0, walls: 0, cells: cells, min: min, max: max },
        _positions: positions,
        _triN: triN,
        _triMinY: triMinY,
        _triMaxY: triMaxY,
        _triMinX: triMinX,
        _triMaxX: triMaxX,
        _triMinZ: triMinZ,
        _triMaxZ: triMaxZ,
        _walkable: walkable,
        _grid: grid,
        _cell: cell,
        _walkableNy: walkableNy,
      };
      for (var i = 0; i < n; i++)
        if (walkable[i]) collider.stats.walkable++;
        else if (triN[i * 3 + 1] !== -2) collider.stats.walls++; // [coach fix P8] degenerate triangles are neither
      collider.groundAt = function (x, z, maxY) {
        var ix = Math.floor(x / cell),
          iz = Math.floor(z / cell);
        var k = ix + "," + iz;
        var arr = grid[k];
        if (!arr) return null;
        var best = null;
        for (var j = 0; j < arr.length; j++) {
          var i = arr[j];
          if (!walkable[i]) continue; // [coach fix P2] only WALKABLE triangles are ground (Muse also returned ceilings/undersides and steep slopes)
          if (triMinY[i] > maxY + 1e-5) continue;
          var b = i * 9;
          var x0 = positions[b],
            y0 = positions[b + 1],
            z0 = positions[b + 2];
          var x1 = positions[b + 3],
            y1 = positions[b + 4],
            z1 = positions[b + 5];
          var x2 = positions[b + 6],
            y2 = positions[b + 7],
            z2 = positions[b + 8];
          var bc = barycentricXZ(x, z, x0, z0, x1, z1, x2, z2);
          if (!bc) continue;
          var u = bc[0],
            v = bc[1];
          var w = 1 - u - v;
          var y = y0 * w + y1 * u + y2 * v;
          if (y > maxY + 1e-5) continue;
          if (best === null || y > best) best = y;
        }
        return best;
      };
      collider.groundAtDisc = function (x, z, r, maxY) {
        var off = r * 0.7;
        var ys = [];
        var g = collider.groundAt(x, z, maxY);
        if (g !== null) ys.push(g);
        var pts = [
          [x + off, z],
          [x - off, z],
          [x, z + off],
          [x, z - off],
        ];
        for (var p = 0; p < pts.length; p++) {
          var gx = pts[p][0],
            gz = pts[p][1];
          var gg = collider.groundAt(gx, gz, maxY);
          if (gg !== null) ys.push(gg);
        }
        if (ys.length === 0) return null;
        var m = ys[0];
        for (var k = 1; k < ys.length; k++) if (ys[k] > m) m = ys[k];
        return m;
      };
      collider.wallHit = function (x, z, r, yMin, yMax) {
        var step = Math.max(0.01, r * 0.9);
        var y = yMin + r;
        var end = yMax - r;
        // [coach fix P8] a cylinder shorter than 2r was never tested (returned false); test one sphere at its middle instead,
        // and always test a last sphere exactly at the top so the upper part of the cylinder is covered.
        if (y > end) { y = end = (yMin + yMax) / 2; }
        var lastDone = false;
        while (!lastDone) {
          if (y >= end) { y = end; lastDone = true; }
          var ix0 = Math.floor((x - r) / cell),
            ix1 = Math.floor((x + r) / cell);
          var iz0 = Math.floor((z - r) / cell),
            iz1 = Math.floor((z + r) / cell);
          for (var ix = ix0; ix <= ix1; ix++) {
            for (var iz = iz0; iz <= iz1; iz++) {
              var k = ix + "," + iz;
              var arr = grid[k];
              if (!arr) continue;
              for (var j = 0; j < arr.length; j++) {
                var i = arr[j];
                if (walkable[i]) continue;
                if (triMaxY[i] < y - r || triMinY[i] > y + r) continue;
                var b = i * 9;
                var ax = positions[b],
                  ay = positions[b + 1],
                  az = positions[b + 2];
                var bx = positions[b + 3],
                  by = positions[b + 4],
                  bz = positions[b + 5];
                var cx = positions[b + 6],
                  cy = positions[b + 7],
                  cz = positions[b + 8];
                var cp = closestPointTri(x, y, z, ax, ay, az, bx, by, bz, cx, cy, cz);
                var dx = x - cp[0],
                  dy = y - cp[1],
                  dz = z - cp[2];
                if (dx * dx + dy * dy + dz * dz < (r - 1e-7) * (r - 1e-7)) return true;
              }
            }
          }
          y += step;
        }
        return false;
      };
      // [coach fix P4] Muse's pushOut moved the player a fixed 0.5 m per iteration in the averaged direction (and re-added the
      // running total to x/z each pass), so touching a wall teleported the player. Rewritten: per pass, every sphere of the
      // stacked cylinder is tested against nearby wall triangles; the deepest horizontal penetration is resolved by exactly its depth.
      collider.pushOut = function (x, z, r, yMin, yMax) {
        var tx = 0, tz = 0, ys = [];
        var lo = yMin + r, hi = yMax - r;
        if (hi < lo) ys.push((yMin + yMax) / 2);
        else { var k = Math.max(1, Math.ceil((hi - lo) / (r * 0.9))); for (var q = 0; q <= k; q++) ys.push(lo + ((hi - lo) * q) / k); }
        for (var iter = 0; iter < 4; iter++) {
          var cxp = x + tx, czp = z + tz, bestPen = 0, bx0 = 0, bz0 = 0;
          var ix0 = Math.floor((cxp - r) / cell), ix1 = Math.floor((cxp + r) / cell), iz0 = Math.floor((czp - r) / cell), iz1 = Math.floor((czp + r) / cell);
          for (var ix = ix0; ix <= ix1; ix++) for (var iz = iz0; iz <= iz1; iz++) {
            var arr = grid[ix + "," + iz];
            if (!arr) continue;
            for (var j = 0; j < arr.length; j++) {
              var i = arr[j];
              if (walkable[i] || triN[i * 3 + 1] === -2 || triMaxY[i] < yMin || triMinY[i] > yMax) continue;
              var b = i * 9;
              for (var s = 0; s < ys.length; s++) {
                var sy = ys[s];
                var cp = closestPointTri(cxp, sy, czp, positions[b], positions[b + 1], positions[b + 2], positions[b + 3], positions[b + 4], positions[b + 5], positions[b + 6], positions[b + 7], positions[b + 8]);
                var ddx = cxp - cp[0], ddy = sy - cp[1], ddz = czp - cp[2];
                if (ddx * ddx + ddy * ddy + ddz * ddz >= r * r) continue;
                var hl = Math.hypot(ddx, ddz), pen;
                if (hl < 1e-6) { ddx = triN[i * 3]; ddz = triN[i * 3 + 2]; hl = Math.hypot(ddx, ddz); if (hl < 1e-6) continue; pen = r; }
                else pen = Math.sqrt(Math.max(0, r * r - ddy * ddy)) - hl;
                if (pen > bestPen) { bestPen = pen; bx0 = (ddx / hl) * pen; bz0 = (ddz / hl) * pen; }
              }
            }
          }
          if (bestPen <= 1e-5) break;
          tx += bx0 * 1.001; tz += bz0 * 1.001;
        }
        return [tx, tz];
      };
      // [coach fix P5] Muse's Moller-Trumbore algebra was wrong (u dropped the dx terms, v used e1.(s x e2), t = e1.(e1 x s) is always 0),
      // so the ray never hit anything; it also looked at a single cell per sample (diagonal rays skipped cells), re-created the
      // stamp array on every call and changed the stamp id every step (every triangle re-tested). Rewritten: textbook Moller-Trumbore,
      // samples every cell/2 along the ray and visits the 3x3 cells around each sample, one stamp per call, early exit after a hit.
      var rayStamp = new Uint32Array(n), rayStampId = 0;
      collider.raycast = function (ox, oy, oz, dx, dy, dz, maxT) {
        var len = Math.hypot(dx, dy, dz);
        if (len < 1e-12) return null;
        dx /= len; dy /= len; dz /= len;
        rayStampId++;
        if (rayStampId > 4000000000) { rayStamp.fill(0); rayStampId = 1; }
        var hlen = Math.hypot(dx, dz), step = cell * 0.5, bestT = maxT, bestI = -1;
        var nSteps = hlen < 1e-9 ? 0 : Math.ceil((maxT * hlen) / step);
        for (var sI = 0; sI <= nSteps; sI++) {
          var t = hlen < 1e-9 ? 0 : (sI * step) / hlen;
          if (bestI >= 0 && t > bestT + cell / Math.max(hlen, 1e-9)) break;
          var gx = Math.floor((ox + dx * t) / cell), gz = Math.floor((oz + dz * t) / cell);
          for (var ix = gx - 1; ix <= gx + 1; ix++) for (var iz = gz - 1; iz <= gz + 1; iz++) {
            var arr = grid[ix + "," + iz];
            if (!arr) continue;
            for (var j = 0; j < arr.length; j++) {
              var i = arr[j];
              if (rayStamp[i] === rayStampId) continue;
              rayStamp[i] = rayStampId;
              var b = i * 9, x0 = positions[b], y0 = positions[b + 1], z0 = positions[b + 2];
              var e1x = positions[b + 3] - x0, e1y = positions[b + 4] - y0, e1z = positions[b + 5] - z0;
              var e2x = positions[b + 6] - x0, e2y = positions[b + 7] - y0, e2z = positions[b + 8] - z0;
              var px_ = dy * e2z - dz * e2y, py_ = dz * e2x - dx * e2z, pz_ = dx * e2y - dy * e2x;
              var det = e1x * px_ + e1y * py_ + e1z * pz_;
              if (det > -1e-7 && det < 1e-7) continue;
              var inv = 1 / det, sx = ox - x0, sy = oy - y0, sz = oz - z0;
              var u = (sx * px_ + sy * py_ + sz * pz_) * inv;
              if (u < 0 || u > 1) continue;
              var qx = sy * e1z - sz * e1y, qy = sz * e1x - sx * e1z, qz = sx * e1y - sy * e1x;
              var v = (dx * qx + dy * qy + dz * qz) * inv;
              if (v < 0 || u + v > 1) continue;
              var tt = (e2x * qx + e2y * qy + e2z * qz) * inv;
              if (tt > 1e-7 && tt < bestT) { bestT = tt; bestI = i; }
            }
          }
        }
        if (bestI < 0) return null;
        return { t: bestT, x: ox + dx * bestT, y: oy + dy * bestT, z: oz + dz * bestT, nx: triN[bestI * 3], ny: triN[bestI * 3 + 1], nz: triN[bestI * 3 + 2], tri: bestI };
      };
      collider.findSpawn = function (hintX, hintZ, opts) {
        opts = opts || {};
        var maxY = collider.stats.max[1] + 1;
        var best = null,
          bestD = Infinity;
        var step = 0.5;
        var maxR = Math.max(
          Math.abs(collider.stats.max[0] - collider.stats.min[0]),
          Math.abs(collider.stats.max[2] - collider.stats.min[2]),
        );
        var rings = Math.ceil(maxR / step);
        // [coach fix P6] rings must reach the far side of the scene from the HINT (it may be off-centre or outside the bounds)
        var st_ = collider.stats, far = Math.max(Math.abs(hintX - st_.min[0]), Math.abs(hintX - st_.max[0]), Math.abs(hintZ - st_.min[2]), Math.abs(hintZ - st_.max[2]));
        rings = Math.min(4000, Math.ceil(far / step) + 1);
        // [coach fix P6] Muse sampled only 4 points per ring (the +/-X and +/-Z axes), so floor that was not on those two lines was
        // never found. Now every grid point on the square ring (0.5 m spacing) is tested, and the search stops at the first ring
        // that has a valid point (closest one on that ring wins) instead of scanning the whole scene.
        for (var r = 0; r <= rings; r++) {
          if (best) break;
          for (var a = 0; a < Math.max(1, 8 * r); a++) {
            var gi, gj, side = r === 0 ? 0 : Math.floor(a / (2 * r)), off = r === 0 ? 0 : (a % (2 * r)) - r;
            if (r === 0) { gi = 0; gj = 0; } else if (side === 0) { gi = off; gj = -r; } else if (side === 1) { gi = r; gj = off; } else if (side === 2) { gi = -off; gj = r; } else { gi = -r; gj = -off; }
            var x = hintX + gi * step;
            var z = hintZ + gj * step;
            if (x < collider.stats.min[0] || x > collider.stats.max[0] || z < collider.stats.min[2] || z > collider.stats.max[2]) continue;
            var ground = collider.groundAt(x, z, maxY);
            if (ground === null) continue;
            var disc = collider.groundAtDisc(x, z, 0.35, maxY);
            if (disc === null || Math.abs(disc - ground) > 0.25) continue;
            // [coach fix P7] groundAtDisc returns the MAX of its samples, so it "agreed" on a 0.4 m beam or wall top. Require every
            // one of the 4 support points to have floor within 0.25 m of the centre (the player's whole footprint is supported).
            var sup = true, so = 0.35;
            for (var sp = 0; sp < 4 && sup; sp++) { var gs = collider.groundAt(x + (sp === 0 ? so : sp === 1 ? -so : 0), z + (sp === 2 ? so : sp === 3 ? -so : 0), ground + 0.3); if (gs === null || Math.abs(gs - ground) > 0.25) sup = false; }
            if (!sup) continue;
            if (collider.wallHit(x, z, 0.35, ground + 0.3, ground + 1.8)) continue;
            var head = collider.raycast(x, ground + 0.1, z, 0, 1, 0, 1.9);
            if (head) continue;
            var d = Math.hypot(x - hintX, z - hintZ);
            if (d < bestD) {
              bestD = d;
              best = [x, ground, z];
            }
          }
        }
        return best;
      };
      return collider;
    },
  };
})();