// Generated by scripts/generate-bite-sized-navigation.ts; edit the shared TypeScript source.

// src/game/partyNavigation.ts
var PARTY_NAVIGATION_WELD_TOLERANCE = 1e-3;
var DISTANCE_EPSILON = 1e-9;
function pointComponents(point) {
  const values = "x" in point ? [point.x, point.y, point.z] : [point[0], point[1], point[2]];
  if (!values.every(Number.isFinite)) {
    throw new Error("Party navigation points must contain finite coordinates.");
  }
  return values;
}
function distanceSquared(left, right) {
  const dx = right[0] - left[0];
  const dy = right[1] - left[1];
  const dz = right[2] - left[2];
  return dx * dx + dy * dy + dz * dz;
}
function distance(left, right) {
  return Math.sqrt(distanceSquared(left, right));
}
function buildPartyNavigationTriangleNodes(triangles, positions) {
  const centroids = triangles.map(([a, b, c]) => Object.freeze([
    (positions[a][0] + positions[b][0] + positions[c][0]) / 3,
    (positions[a][1] + positions[b][1] + positions[c][1]) / 3,
    (positions[a][2] + positions[b][2] + positions[c][2]) / 3
  ]));
  const edgeOwners = /* @__PURE__ */ new Map();
  triangles.forEach(([a, b, c], triangleId) => {
    for (const [left, right] of [[a, b], [b, c], [c, a]]) {
      const portal = Object.freeze([
        Math.min(left, right),
        Math.max(left, right)
      ]);
      const key = `${portal[0]},${portal[1]}`;
      const owners = edgeOwners.get(key);
      if (owners) owners.push({ triangleId, portal });
      else edgeOwners.set(key, [{ triangleId, portal }]);
    }
  });
  const neighbors = triangles.map(() => []);
  for (const owners of edgeOwners.values()) {
    for (let leftIndex = 0; leftIndex < owners.length; leftIndex += 1) {
      for (let rightIndex = leftIndex + 1; rightIndex < owners.length; rightIndex += 1) {
        const left = owners[leftIndex];
        const right = owners[rightIndex];
        const cost = distance(centroids[left.triangleId], centroids[right.triangleId]);
        neighbors[left.triangleId].push(Object.freeze({
          to: right.triangleId,
          portal: left.portal,
          cost
        }));
        neighbors[right.triangleId].push(Object.freeze({
          to: left.triangleId,
          portal: right.portal,
          cost
        }));
      }
    }
  }
  return Object.freeze(centroids.map((centroid, id) => Object.freeze({
    id,
    centroid,
    neighbors: Object.freeze(neighbors[id].sort((left, right) => left.to - right.to || left.portal[0] - right.portal[0] || left.portal[1] - right.portal[1]))
  })));
}
function findNearestPartyNavigationNode(graph, point, maxDistance = Number.POSITIVE_INFINITY) {
  const target = pointComponents(point);
  const limit = Number.isFinite(maxDistance) ? Math.max(0, maxDistance) : Number.POSITIVE_INFINITY;
  let nearest = null;
  let nearestDistanceSquared = limit * limit;
  for (const node of graph.nodes) {
    const candidateDistanceSquared = distanceSquared(target, node.position);
    if (candidateDistanceSquared < nearestDistanceSquared - DISTANCE_EPSILON || Math.abs(candidateDistanceSquared - nearestDistanceSquared) <= DISTANCE_EPSILON && (nearest === null || node.id < nearest.id)) {
      nearest = node;
      nearestDistanceSquared = candidateDistanceSquared;
    }
  }
  return nearest ? Object.freeze({ node: nearest, distance: Math.sqrt(nearestDistanceSquared) }) : null;
}
function closestPointOnSegment(point, start, end) {
  const segmentX = end[0] - start[0];
  const segmentY = end[1] - start[1];
  const segmentZ = end[2] - start[2];
  const lengthSquared = segmentX * segmentX + segmentY * segmentY + segmentZ * segmentZ;
  if (lengthSquared <= DISTANCE_EPSILON) return [start[0], start[1], start[2]];
  const projection = Math.max(0, Math.min(1, ((point[0] - start[0]) * segmentX + (point[1] - start[1]) * segmentY + (point[2] - start[2]) * segmentZ) / lengthSquared));
  return [
    start[0] + segmentX * projection,
    start[1] + segmentY * projection,
    start[2] + segmentZ * projection
  ];
}
function closestPointOnTriangle(point, a, b, c) {
  const ab = [b[0] - a[0], b[1] - a[1], b[2] - a[2]];
  const ac = [c[0] - a[0], c[1] - a[1], c[2] - a[2]];
  const crossX = ab[1] * ac[2] - ab[2] * ac[1];
  const crossY = ab[2] * ac[0] - ab[0] * ac[2];
  const crossZ = ab[0] * ac[1] - ab[1] * ac[0];
  if (crossX * crossX + crossY * crossY + crossZ * crossZ <= DISTANCE_EPSILON) {
    const candidates = [
      closestPointOnSegment(point, a, b),
      closestPointOnSegment(point, b, c),
      closestPointOnSegment(point, c, a)
    ];
    return candidates.reduce((best, candidate) => distanceSquared(point, candidate) < distanceSquared(point, best) - DISTANCE_EPSILON ? candidate : best);
  }
  const ap = [point[0] - a[0], point[1] - a[1], point[2] - a[2]];
  const d1 = ab[0] * ap[0] + ab[1] * ap[1] + ab[2] * ap[2];
  const d2 = ac[0] * ap[0] + ac[1] * ap[1] + ac[2] * ap[2];
  if (d1 <= 0 && d2 <= 0) return [a[0], a[1], a[2]];
  const bp = [point[0] - b[0], point[1] - b[1], point[2] - b[2]];
  const d3 = ab[0] * bp[0] + ab[1] * bp[1] + ab[2] * bp[2];
  const d4 = ac[0] * bp[0] + ac[1] * bp[1] + ac[2] * bp[2];
  if (d3 >= 0 && d4 <= d3) return [b[0], b[1], b[2]];
  const vc = d1 * d4 - d3 * d2;
  if (vc <= 0 && d1 >= 0 && d3 <= 0) {
    const along = d1 / (d1 - d3);
    return [a[0] + ab[0] * along, a[1] + ab[1] * along, a[2] + ab[2] * along];
  }
  const cp = [point[0] - c[0], point[1] - c[1], point[2] - c[2]];
  const d5 = ab[0] * cp[0] + ab[1] * cp[1] + ab[2] * cp[2];
  const d6 = ac[0] * cp[0] + ac[1] * cp[1] + ac[2] * cp[2];
  if (d6 >= 0 && d5 <= d6) return [c[0], c[1], c[2]];
  const vb = d5 * d2 - d1 * d6;
  if (vb <= 0 && d2 >= 0 && d6 <= 0) {
    const along = d2 / (d2 - d6);
    return [a[0] + ac[0] * along, a[1] + ac[1] * along, a[2] + ac[2] * along];
  }
  const va = d3 * d6 - d5 * d4;
  if (va <= 0 && d4 - d3 >= 0 && d5 - d6 >= 0) {
    const along = (d4 - d3) / (d4 - d3 + (d5 - d6));
    return [
      b[0] + (c[0] - b[0]) * along,
      b[1] + (c[1] - b[1]) * along,
      b[2] + (c[2] - b[2]) * along
    ];
  }
  const denominator = 1 / (va + vb + vc);
  const alongB = vb * denominator;
  const alongC = vc * denominator;
  return [
    a[0] + ab[0] * alongB + ac[0] * alongC,
    a[1] + ab[1] * alongB + ac[1] * alongC,
    a[2] + ab[2] * alongB + ac[2] * alongC
  ];
}
function findNearestPartyNavigationSurface(graph, point, maxDistance = Number.POSITIVE_INFINITY) {
  const triangles = graph.triangles;
  if (!triangles?.length) {
    const nearest = findNearestPartyNavigationNode(graph, point, maxDistance);
    return nearest ? Object.freeze({
      position: nearest.node.position,
      triangleId: -1,
      distance: nearest.distance
    }) : null;
  }
  const target = pointComponents(point);
  const limit = Number.isFinite(maxDistance) ? Math.max(0, maxDistance) : Number.POSITIVE_INFINITY;
  let nearestPosition = null;
  let nearestTriangleId = -1;
  let nearestDistanceSquared = limit * limit;
  for (let triangleId = 0; triangleId < triangles.length; triangleId += 1) {
    const [a, b, c] = triangles[triangleId];
    const candidate = closestPointOnTriangle(
      target,
      graph.nodes[a].position,
      graph.nodes[b].position,
      graph.nodes[c].position
    );
    const candidateDistanceSquared = distanceSquared(target, candidate);
    if (candidateDistanceSquared < nearestDistanceSquared - DISTANCE_EPSILON || Math.abs(candidateDistanceSquared - nearestDistanceSquared) <= DISTANCE_EPSILON && (nearestTriangleId < 0 || triangleId < nearestTriangleId)) {
      nearestPosition = candidate;
      nearestTriangleId = triangleId;
      nearestDistanceSquared = candidateDistanceSquared;
    }
  }
  return nearestPosition ? Object.freeze({
    position: Object.freeze([...nearestPosition]),
    triangleId: nearestTriangleId,
    distance: Math.sqrt(nearestDistanceSquared)
  }) : null;
}
function pointToSegmentDistance(point, start, end) {
  return distance(point, closestPointOnSegment(point, start, end));
}
function simplifyPartyNavigationPath(points, tolerance = PARTY_NAVIGATION_WELD_TOLERANCE) {
  const safeTolerance = Number.isFinite(tolerance) ? Math.max(0, tolerance) : 0;
  const simplified = [];
  for (const rawPoint of points) {
    const point = Object.freeze([...pointComponents(rawPoint)]);
    if (simplified.length && distance(simplified[simplified.length - 1], point) <= safeTolerance) continue;
    simplified.push(point);
    while (simplified.length >= 3) {
      const end = simplified[simplified.length - 1];
      const middle = simplified[simplified.length - 2];
      const start = simplified[simplified.length - 3];
      if (pointToSegmentDistance(middle, start, end) > safeTolerance) break;
      simplified.splice(simplified.length - 2, 1);
    }
  }
  return Object.freeze(simplified);
}
function compareOpenEntries(left, right) {
  return left.f - right.f || left.h - right.h || left.id - right.id;
}
var OpenHeap = class {
  entries = [];
  get length() {
    return this.entries.length;
  }
  push(entry) {
    const entries = this.entries;
    entries.push(entry);
    let index = entries.length - 1;
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (compareOpenEntries(entries[parent], entry) <= 0) break;
      entries[index] = entries[parent];
      index = parent;
    }
    entries[index] = entry;
  }
  pop() {
    const entries = this.entries;
    if (!entries.length) return null;
    const first = entries[0];
    const last = entries.pop();
    if (entries.length) {
      let index = 0;
      while (true) {
        const left = index * 2 + 1;
        if (left >= entries.length) break;
        const right = left + 1;
        const bestChild = right < entries.length && compareOpenEntries(entries[right], entries[left]) < 0 ? right : left;
        if (compareOpenEntries(entries[bestChild], last) >= 0) break;
        entries[index] = entries[bestChild];
        index = bestChild;
      }
      entries[index] = last;
    }
    return first;
  }
};
function findPartyNavigationNodePath(graph, startId, endId) {
  if (startId === endId) return Object.freeze([startId]);
  const nodeCount = graph.nodes.length;
  const cameFrom = new Int32Array(nodeCount);
  cameFrom.fill(-1);
  const scores = new Float64Array(nodeCount);
  scores.fill(Number.POSITIVE_INFINITY);
  scores[startId] = 0;
  const closed = new Uint8Array(nodeCount);
  const open = new OpenHeap();
  const initialHeuristic = distance(graph.nodes[startId].position, graph.nodes[endId].position);
  open.push({ id: startId, g: 0, h: initialHeuristic, f: initialHeuristic });
  while (open.length) {
    const current = open.pop();
    if (closed[current.id] || current.g > scores[current.id] + DISTANCE_EPSILON) continue;
    if (current.id === endId) break;
    closed[current.id] = 1;
    for (const edge of graph.nodes[current.id].neighbors) {
      if (closed[edge.to]) continue;
      const tentative = scores[current.id] + edge.cost;
      if (tentative >= scores[edge.to] - DISTANCE_EPSILON) continue;
      cameFrom[edge.to] = current.id;
      scores[edge.to] = tentative;
      const heuristic = distance(graph.nodes[edge.to].position, graph.nodes[endId].position);
      open.push({ id: edge.to, g: tentative, h: heuristic, f: tentative + heuristic });
    }
  }
  if (cameFrom[endId] < 0) return null;
  const nodeIds = [endId];
  let cursor = endId;
  while (cursor !== startId && nodeIds.length <= nodeCount) {
    cursor = cameFrom[cursor];
    if (cursor < 0) return null;
    nodeIds.push(cursor);
  }
  if (cursor !== startId) return null;
  nodeIds.reverse();
  return Object.freeze(nodeIds);
}
function findPartyNavigationTrianglePath(triangleNodes, startId, endId, blocked) {
  if (blocked?.[startId] || blocked?.[endId]) return null;
  if (startId === endId) return Object.freeze([startId]);
  const nodeCount = triangleNodes.length;
  const cameFrom = new Int32Array(nodeCount);
  cameFrom.fill(-1);
  const scores = new Float64Array(nodeCount);
  scores.fill(Number.POSITIVE_INFINITY);
  scores[startId] = 0;
  const closed = new Uint8Array(nodeCount);
  const open = new OpenHeap();
  const initialHeuristic = distance(triangleNodes[startId].centroid, triangleNodes[endId].centroid);
  open.push({ id: startId, g: 0, h: initialHeuristic, f: initialHeuristic });
  while (open.length) {
    const current = open.pop();
    if (closed[current.id] || current.g > scores[current.id] + DISTANCE_EPSILON) continue;
    if (current.id === endId) break;
    closed[current.id] = 1;
    for (const edge of triangleNodes[current.id].neighbors) {
      if (blocked?.[edge.to] || closed[edge.to]) continue;
      const tentative = scores[current.id] + edge.cost;
      if (tentative >= scores[edge.to] - DISTANCE_EPSILON) continue;
      cameFrom[edge.to] = current.id;
      scores[edge.to] = tentative;
      const heuristic = distance(triangleNodes[edge.to].centroid, triangleNodes[endId].centroid);
      open.push({ id: edge.to, g: tentative, h: heuristic, f: tentative + heuristic });
    }
  }
  if (cameFrom[endId] < 0) return null;
  const triangleIds = [endId];
  let cursor = endId;
  while (cursor !== startId && triangleIds.length <= nodeCount) {
    cursor = cameFrom[cursor];
    if (cursor < 0) return null;
    triangleIds.push(cursor);
  }
  if (cursor !== startId) return null;
  triangleIds.reverse();
  return Object.freeze(triangleIds);
}
function findPartyNavigationNodeSnappedPath(graph, start, end, options) {
  const maxSnapDistance = options.maxSnapDistance ?? Number.POSITIVE_INFINITY;
  const startMatch = findNearestPartyNavigationNode(
    graph,
    start,
    options.maxStartSnapDistance ?? maxSnapDistance
  );
  const endMatch = findNearestPartyNavigationNode(
    graph,
    end,
    options.maxEndSnapDistance ?? maxSnapDistance
  );
  if (!startMatch || !endMatch) return null;
  const nodeIds = findPartyNavigationNodePath(graph, startMatch.node.id, endMatch.node.id);
  return nodeIds ? simplifyPartyNavigationPath(
    nodeIds.map((id) => graph.nodes[id].position),
    options.simplifyTolerance ?? graph.weldTolerance
  ) : null;
}
function findPartyNavigationPath(graph, start, end, options = {}) {
  if (!graph.triangles?.length) {
    return findPartyNavigationNodeSnappedPath(graph, start, end, options);
  }
  const maxSnapDistance = options.maxSnapDistance ?? Number.POSITIVE_INFINITY;
  const startMatch = findNearestPartyNavigationSurface(
    graph,
    start,
    options.maxStartSnapDistance ?? maxSnapDistance
  );
  const endMatch = findNearestPartyNavigationSurface(
    graph,
    end,
    options.maxEndSnapDistance ?? maxSnapDistance
  );
  if (!startMatch || !endMatch) return null;
  const triangleNodes = graph.triangleNodes?.length === graph.triangles.length ? graph.triangleNodes : buildPartyNavigationTriangleNodes(
    graph.triangles,
    graph.nodes.map((node) => node.position)
  );
  const blocked = new Uint8Array(triangleNodes.length);
  const maximumReroutes = Math.min(64, triangleNodes.length);
  for (let reroute = 0; reroute <= maximumReroutes; reroute += 1) {
    const triangleIds = findPartyNavigationTrianglePath(
      triangleNodes,
      startMatch.triangleId,
      endMatch.triangleId,
      blocked
    );
    if (!triangleIds) return null;
    const path = [startMatch.position];
    for (let index = 0; index < triangleIds.length - 1; index += 1) {
      const from = triangleIds[index];
      const to = triangleIds[index + 1];
      const transition = triangleNodes[from].neighbors.find((edge) => edge.to === to);
      if (!transition) return null;
      const [a, b] = transition.portal;
      const left = graph.nodes[a].position;
      const right = graph.nodes[b].position;
      path.push(Object.freeze([
        (left[0] + right[0]) / 2,
        (left[1] + right[1]) / 2,
        (left[2] + right[2]) / 2
      ]));
    }
    path.push(endMatch.position);
    let rejectedSegment = -1;
    if (options.routeSegmentAllowed) {
      for (let index = 0; index < path.length - 1; index += 1) {
        if (!options.routeSegmentAllowed(path[index], path[index + 1])) {
          rejectedSegment = index;
          break;
        }
      }
    }
    if (rejectedSegment < 0) return Object.freeze(path);
    if (triangleIds.length <= 1 || reroute >= maximumReroutes) return null;
    const blockedTriangleId = rejectedSegment === 0 ? triangleIds[1] : rejectedSegment === triangleIds.length - 1 ? triangleIds[triangleIds.length - 2] : triangleIds[rejectedSegment];
    if (blocked[blockedTriangleId]) return null;
    blocked[blockedTriangleId] = 1;
  }
  return null;
}

// src/game/partySpawnSlots.ts
function derivePartySpawnSlots(spawn, partySize = 5) {
  const size = Math.max(1, Math.min(5, Math.trunc(partySize)));
  const offsets = [
    [0, 0],
    [-1.65, -1.8],
    [1.65, -1.8],
    [-3.05, -3.5],
    [3.05, -3.5]
  ];
  const sin = Math.sin(spawn.yaw);
  const cos = Math.cos(spawn.yaw);
  return Object.freeze(offsets.slice(0, size).map(([lateral, forward]) => ({
    footPosition: [
      spawn.footPosition[0] + lateral * cos + forward * sin,
      spawn.footPosition[1],
      spawn.footPosition[2] - lateral * sin + forward * cos
    ],
    yaw: spawn.yaw
  })));
}

// src/game/biteSizedSpotNavigation.ts
function biteSizedRouteSegmentClear(blockers, from, to) {
  return blockers.every((blocker) => {
    const sin = Math.sin(blocker.yaw), cos = Math.cos(blocker.yaw);
    const local = (point) => {
      const x = point[0] - blocker.position[0], z = point[2] - blocker.position[2];
      return [x * cos - z * sin, point[1] - blocker.position[1], x * sin + z * cos];
    };
    const start = local(from), end = local(to);
    let enter = 0, leave = 1;
    for (let axis = 0; axis < 3; axis++) {
      const extent = blocker.halfExtents[axis] + (axis === 1 ? 1 : 0.34);
      const delta = end[axis] - start[axis];
      if (Math.abs(delta) < 1e-9) {
        if (Math.abs(start[axis]) > extent) return true;
        continue;
      }
      const first = (-extent - start[axis]) / delta, second = (extent - start[axis]) / delta;
      enter = Math.max(enter, Math.min(first, second));
      leave = Math.min(leave, Math.max(first, second));
      if (enter > leave) return true;
    }
    return false;
  });
}
function validateBiteSizedSpotNavigation(spot, graph, regions, blockers = []) {
  const start = findNearestPartyNavigationSurface(graph, spot.partySpawn.footPosition, 0.75);
  if (!start) throw new Error(`${spot.name}: Party anchor is off the walkable floor. Move its spawn point.`);
  const points = [
    ...derivePartySpawnSlots(spot.partySpawn).map((s, i) => ({ label: `Party member ${i + 1}`, position: s.footPosition, snapDistance: i === 0 ? 0.75 : 6 })),
    ...spot.mobs.map((m, i) => ({ label: `Mob ${i + 1}`, position: m.position })),
    { label: "Boss", position: spot.bossSpawn.footPosition }
  ];
  for (const point of points) {
    const match = findNearestPartyNavigationSurface(graph, point.position, point.snapDistance ?? 0.75);
    if (!match) throw new Error(`${spot.name}: ${point.label} is off the walkable floor. Move its spawn point.`);
    if (!biteSizedRouteSegmentClear(blockers, match.position, match.position)) throw new Error(`${spot.name}: ${point.label} is inside a route blocker.`);
    const reachable = regions ? regions[start.triangleId] === regions[match.triangleId] : findPartyNavigationPath(graph, start.position, match.position, {
      maxSnapDistance: 0.75,
      routeSegmentAllowed: (from, to) => biteSizedRouteSegmentClear(blockers, from, to)
    });
    if (!reachable) throw new Error(`${spot.name}: ${point.label} cannot be reached from the party start.`);
  }
}
export {
  biteSizedRouteSegmentClear,
  validateBiteSizedSpotNavigation
};