Made of little things.

import * as THREE from 'three';
import type { Solid } from './types.js';

export const RADIUS = 0.24;
export const HEIGHT = 1.0;
export const CROUCH_HEIGHT = 0.66;
export const STEP_UP = 0.3;
/** Ledge tops this far above the feet can be grabbed while airborne. */
export const GRAB_MIN = 0.75;
export const GRAB_MAX = 1.75;
/** Feet sit this far below the ledge while hanging. */
export const HANG_DROP = 1.0;
/** Root stands this far out from the wall while hanging (more than RADIUS, so the body never overlaps the ledge). */
export const HANG_OUT = 0.27;

export interface Body {
  pos: THREE.Vector3;
  vel: THREE.Vector3;
  height: number;
  onGround: boolean;
  support: Solid | null;
}

function overlaps(s: Solid, x: number, y: number, z: number, h: number, r: number): boolean {
  if (!(x + r > s.minX && x - r < s.maxX && z + r > s.minZ && z - r < s.maxZ && y + h > s.minY && y < s.maxY)) return false;
  if (!s.round) return true;
  const R = (s.maxX - s.minX) / 2;
  return Math.hypot(x - (s.minX + s.maxX) / 2, z - (s.minZ + s.maxZ) / 2) < R + r;
}

/** Does a footprint of radius r at (x, z) reach over a solid's top? */
function under(s: Solid, x: number, z: number, r: number): boolean {
  if (x + r <= s.minX || x - r >= s.maxX || z + r <= s.minZ || z - r >= s.maxZ) return false;
  if (!s.round) return true;
  return Math.hypot(x - (s.minX + s.maxX) / 2, z - (s.minZ + s.maxZ) / 2) < (s.maxX - s.minX) / 2 + r;
}

/** Push a body of radius r at p out of a round solid, straight away from its centre. */
function pushRound(s: Solid, p: THREE.Vector3, r: number): void {
  const cx = (s.minX + s.maxX) / 2;
  const cz = (s.minZ + s.maxZ) / 2;
  let dx = p.x - cx;
  let dz = p.z - cz;
  const d = Math.hypot(dx, dz);
  if (d < 1e-5) {
    dx = 1;
    dz = 0;
  } else {
    dx /= d;
    dz /= d;
  }
  const out = (s.maxX - s.minX) / 2 + r + 1e-4;
  p.x = cx + dx * out;
  p.z = cz + dz * out;
}

export interface Ledge {
  solid: Solid;
  /** Outward face normal (horizontal unit vector). */
  normal: THREE.Vector3;
  /**
   * Direction along the edge (+X or +Z for furniture; any level direction on the train).
   * `min`/`max` are positions along it, measured as dot(point, tangent).
   */
  tangent: THREE.Vector3;
  /** Point on the top edge closest to the fighter. */
  point: THREE.Vector3;
  /** Allowed range of the edge coordinate along the tangent. */
  min: number;
  max: number;
}

export class World {
  /** Extra ledges that aren't boxes on the axes (the edges of the moving train cars). */
  movingLedges: ((pos: THREE.Vector3, dir: THREE.Vector3) => { ledge: Ledge; score: number } | null) | null = null;

  constructor(readonly solids: Solid[]) {}

  /** Move a body through the world, resolving each axis against the boxes. */
  move(body: Body, dt: number): { hitWall: boolean; landed: boolean; landSpeed: number } {
    const steps = Math.max(1, Math.ceil((Math.abs(body.vel.x) + Math.abs(body.vel.y) + Math.abs(body.vel.z)) * dt / 0.12));
    const h = dt / steps;
    let hitWall = false;
    let landed = false;
    let landSpeed = 0;
    this.depenetrate(body);
    const wasGround = body.onGround;
    body.onGround = false;
    for (let i = 0; i < steps; i++) {
      hitWall = this.axis(body, 'x', body.vel.x * h, wasGround) || hitWall;
      hitWall = this.axis(body, 'z', body.vel.z * h, wasGround) || hitWall;
      const vy = body.vel.y;
      const r = this.vertical(body, vy * h);
      if (r === 'floor') {
        if (!wasGround && !landed) {
          landed = true;
          landSpeed = -vy;
        }
      }
    }
    // Stay glued to the floor when walking down tiny steps.
    if (!body.onGround && wasGround && body.vel.y <= 0) {
      const below = this.groundBelow(body.pos.x, body.pos.y + 0.01, body.pos.z, RADIUS * 0.8);
      if (below && body.pos.y - below.maxY < STEP_UP) {
        body.pos.y = below.maxY;
        body.onGround = true;
        body.support = below;
        body.vel.y = 0;
      }
    }
    return { hitWall, landed, landSpeed };
  }

  /**
   * If the body already overlaps a box (after hanging, climbing or being shoved),
   * push it out along the shallowest direction instead of letting a later axis
   * step fling it across the box.
   */
  private depenetrate(body: Body): void {
    const p = body.pos;
    for (let iter = 0; iter < 3; iter++) {
      let moved = false;
      for (const s of this.solids) {
        if (!overlaps(s, p.x, p.y + 0.001, p.z, body.height, RADIUS)) continue;
        if (s.round) {
          const R = (s.maxX - s.minX) / 2;
          const d = Math.hypot(p.x - (s.minX + s.maxX) / 2, p.z - (s.minZ + s.maxZ) / 2);
          if (s.maxY - p.y <= STEP_UP && s.maxY - p.y < R + RADIUS - d) p.y = s.maxY;
          else pushRound(s, p, RADIUS);
          moved = true;
          continue;
        }
        const options: [number, 'x' | 'y' | 'z', number][] = [
          [p.x + RADIUS - s.minX, 'x', s.minX - RADIUS - 1e-4],
          [s.maxX - (p.x - RADIUS), 'x', s.maxX + RADIUS + 1e-4],
          [p.z + RADIUS - s.minZ, 'z', s.minZ - RADIUS - 1e-4],
          [s.maxZ - (p.z - RADIUS), 'z', s.maxZ + RADIUS + 1e-4],
          // Stepping up onto a low lip is fine; never pop on top of something tall.
          [s.maxY - p.y <= STEP_UP ? s.maxY - p.y : Infinity, 'y', s.maxY],
        ];
        options.sort((a, b) => a[0] - b[0]);
        const [, axis, value] = options[0]!;
        p[axis] = value;
        if (axis !== 'y') body.vel[axis] = 0;
        moved = true;
      }
      if (!moved) break;
    }
  }

  private axis(body: Body, axis: 'x' | 'z', delta: number, grounded: boolean): boolean {
    if (delta === 0) return false;
    const p = body.pos;
    p[axis] += delta;
    let hit = false;
    for (const s of this.solids) {
      if (!overlaps(s, p.x, p.y + 0.001, p.z, body.height, RADIUS)) continue;
      // Small lips are stepped onto rather than blocking.
      if (grounded && s.maxY - p.y <= STEP_UP && !this.blocked(p.x, s.maxY, p.z, body.height)) {
        p.y = s.maxY;
        continue;
      }
      if (s.round) {
        pushRound(s, p, RADIUS);
        hit = true;
        continue;
      }
      // Push back out on the side we came from (judged by where the centre was before
      // this step), never through to the far side of the box.
      const before = p[axis] - delta;
      const min = axis === 'x' ? s.minX : s.minZ;
      const max = axis === 'x' ? s.maxX : s.maxZ;
      p[axis] = before < (min + max) / 2 ? min - RADIUS - 1e-4 : max + RADIUS + 1e-4;
      body.vel[axis] = 0;
      hit = true;
    }
    return hit;
  }

  private vertical(body: Body, delta: number): 'floor' | 'ceiling' | null {
    const p = body.pos;
    p.y += delta;
    let result: 'floor' | 'ceiling' | null = null;
    for (const s of this.solids) {
      if (!overlaps(s, p.x, p.y, p.z, body.height, RADIUS * 0.92)) continue;
      if (delta <= 0) {
        p.y = s.maxY;
        body.vel.y = 0;
        body.onGround = true;
        body.support = s;
        result = 'floor';
      } else {
        p.y = s.minY - body.height - 1e-4;
        body.vel.y = 0;
        result = 'ceiling';
      }
    }
    if (delta <= 0 && result === null) {
      // Resting exactly on a surface: keep the ground flag without jitter.
      const s = this.groundBelow(p.x, p.y + 1e-3, p.z, RADIUS * 0.92);
      if (s && p.y - s.maxY < 1e-3) {
        body.onGround = true;
        body.support = s;
        result = 'floor';
      }
    }
    return result;
  }

  /** Is a standing box at (x, y, z) obstructed? */
  blocked(x: number, y: number, z: number, h: number, r = RADIUS): boolean {
    for (const s of this.solids) if (overlaps(s, x, y + 0.002, z, h - 0.004, r)) return true;
    return false;
  }

  /** Like blocked(), ignoring things that move (the toy train). */
  blockedStatic(x: number, y: number, z: number, h: number, r = RADIUS): boolean {
    for (const s of this.solids) if (!s.moving && overlaps(s, x, y + 0.002, z, h - 0.004, r)) return true;
    return false;
  }

  /** Highest solid top at or below y under the given footprint. */
  groundBelow(x: number, y: number, z: number, r = 0.05): Solid | null {
    let best: Solid | null = null;
    for (const s of this.solids) {
      if (!under(s, x, z, r)) continue;
      if (s.maxY > y + 1e-3) continue;
      if (!best || s.maxY > best.maxY) best = s;
    }
    return best;
  }

  /** Height of the floor under a point (used for shadows, items and markers). */
  heightAt(x: number, y: number, z: number): number {
    return this.groundBelow(x, y, z)?.maxY ?? 0;
  }

  /**
   * Look for a grabbable ledge in front of an airborne fighter at `pos`
   * reaching toward `dir` (horizontal unit vector).
   */
  findLedge(pos: THREE.Vector3, dir: THREE.Vector3): Ledge | null {
    let best: Ledge | null = null;
    let bestScore = Infinity;
    for (const s of this.solids) {
      if (s.grab === false) continue;
      const rise = s.maxY - pos.y;
      if (rise < GRAB_MIN || rise > GRAB_MAX) continue;
      if (s.round) {
        // The rim of a round top: the ledge is the point of the rim nearest the samurai.
        const cx = (s.minX + s.maxX) / 2;
        const cz = (s.minZ + s.maxZ) / 2;
        const R = (s.maxX - s.minX) / 2;
        const d = Math.hypot(pos.x - cx, pos.z - cz);
        if (d < 1e-4) continue;
        const nx = (pos.x - cx) / d;
        const nz = (pos.z - cz) / d;
        if (nx * dir.x + nz * dir.z > -0.35) continue;
        const out = d - R;
        if (out < RADIUS - 0.12 || out > RADIUS + 0.32) continue;
        const px = cx + nx * R;
        const pz = cz + nz * R;
        if (this.blocked(px - nx * 0.32, s.maxY, pz - nz * 0.32, 0.66, 0.2)) continue;
        if (this.blockedExcept(px + nx * HANG_OUT, s.maxY - HANG_DROP, pz + nz * HANG_OUT, HANG_DROP - 0.05, RADIUS - 0.01, s)) continue;
        const score = Math.abs(out - RADIUS) + Math.abs(rise - 1.15) * 0.3;
        if (score < bestScore) {
          bestScore = score;
          const tangent = new THREE.Vector3(-nz, 0, nx);
          const point = new THREE.Vector3(px, s.maxY, pz);
          const at = point.dot(tangent);
          // A curved rim can't be shimmied along a straight line: the hold is a single spot.
          best = { solid: s, normal: new THREE.Vector3(nx, 0, nz), tangent, point, min: at, max: at };
        }
        continue;
      }
      // Each vertical face: outward normal, distance from the fighter to the face plane.
      const faces: [number, number, number, number, number][] = [
        // nx, nz, plane, range min, range max (along the tangent axis)
        [-1, 0, s.minX, s.minZ, s.maxZ],
        [1, 0, s.maxX, s.minZ, s.maxZ],
        [0, -1, s.minZ, s.minX, s.maxX],
        [0, 1, s.maxZ, s.minX, s.maxX],
      ];
      for (const [nx, nz, plane, lo, hi] of faces) {
        if (nx * dir.x + nz * dir.z > -0.35) continue; // must be reaching into the face
        const out = nx !== 0 ? (pos.x - plane) * nx : (pos.z - plane) * nz;
        if (out < RADIUS - 0.12 || out > RADIUS + 0.32) continue;
        const along = nx !== 0 ? pos.z : pos.x;
        const min = lo + 0.14;
        const max = hi - 0.14;
        if (max <= min || along < min - 0.05 || along > max + 0.05) continue;
        const a = Math.min(max, Math.max(min, along));
        const px = nx !== 0 ? plane : a;
        const pz = nx !== 0 ? a : plane;
        // Room above the ledge to climb onto it, and room for the body to hang.
        const inX = px - nx * 0.32;
        const inZ = pz - nz * 0.32;
        if (this.blocked(inX, s.maxY, inZ, 0.66, 0.2)) continue;
        const hx = px + nx * HANG_OUT;
        const hz = pz + nz * HANG_OUT;
        if (this.blockedExcept(hx, s.maxY - HANG_DROP, hz, HANG_DROP - 0.05, RADIUS - 0.01, s)) continue;
        const score = Math.abs(out - RADIUS) + Math.abs(rise - 1.15) * 0.3;
        if (score < bestScore) {
          bestScore = score;
          best = {
            solid: s,
            normal: new THREE.Vector3(nx, 0, nz),
            tangent: nx !== 0 ? new THREE.Vector3(0, 0, 1) : new THREE.Vector3(1, 0, 0),
            point: new THREE.Vector3(px, s.maxY, pz),
            min,
            max,
          };
        }
      }
    }
    const moving = this.movingLedges?.(pos, dir);
    if (moving && moving.score < bestScore) return moving.ledge;
    return best;
  }

  private blockedExcept(x: number, y: number, z: number, h: number, r: number, skip: Solid): boolean {
    for (const s of this.solids) if (s !== skip && overlaps(s, x, y, z, h, r)) return true;
    return false;
  }

  /** Line-of-sight test between two points (true if a solid lies between them). */
  occluded(a: THREE.Vector3, b: THREE.Vector3): boolean {
    _ray.set(a, _dir.subVectors(b, a).normalize());
    const len = a.distanceTo(b);
    for (const s of this.solids) {
      _box.min.set(s.minX, s.minY, s.minZ);
      _box.max.set(s.maxX, s.maxY, s.maxZ);
      const hit = _ray.intersectBox(_box, _hit);
      if (hit && hit.distanceTo(a) < len - 0.05) return true;
    }
    return false;
  }
}

const _ray = new THREE.Ray();
const _dir = new THREE.Vector3();
const _box = new THREE.Box3();
const _hit = new THREE.Vector3();