Made of little things.

/**
 * Deterministic obstacle placement and collision volumes. Each obstacle kind has
 * a unit-scale local template (Y up, base at origin) shared with the mesh
 * builders in src/world/obstacle-meshes.ts.
 */
import { Matrix4, Quaternion, Vector3 } from 'three';
import { PLANET_RADIUS, WORLD_SEED } from './constants.ts';
import { mulberry32 } from './noise.ts';
import { RIFT, riftCoordinates, terrainHeight } from './terrain.ts';

export type ObstacleKind =
  | 'arch'
  | 'spire'
  | 'hoodoo'
  | 'island'
  | 'halo'
  | 'lighthouse'
  | 'windmill'
  | 'tree'
  | 'pine'
  | 'cloud';

export type Obstacle = {
  kind: ObstacleKind;
  matrix: Matrix4;
  /** World-space centre and radius of the whole object, for spacing. */
  center: Vector3;
  radius: number;
  scale: number;
};

type Sphere = [x: number, y: number, z: number, r: number];

function ringSpheres(count: number, radius: number, tube: number, arc = Math.PI * 2): Sphere[] {
  const out: Sphere[] = [];
  for (let i = 0; i <= count; i++) {
    const a = (arc * i) / count;
    out.push([Math.cos(a) * radius, Math.sin(a) * radius, 0, tube]);
  }
  return out;
}

/** Local collision spheres for each kind (unit scale). */
export const COLLIDERS: Record<ObstacleKind, Sphere[]> = {
  arch: [...ringSpheres(14, 1, 0.26, Math.PI), [1, -0.4, 0, 0.33], [-1, -0.4, 0, 0.33]],
  spire: [0.05, 0.2, 0.35, 0.5, 0.65, 0.8, 0.92].map((y) => [0, y, 0, 0.13 * (1 - y) + 0.03] as Sphere),
  hoodoo: [
    [0, 0.15, 0, 0.15],
    [0, 0.45, 0, 0.13],
    [0, 0.75, 0, 0.13],
    [0, 1.02, 0, 0.17],
    ...Array.from({ length: 8 }, (_, i): Sphere => {
      const a = (i / 8) * Math.PI * 2;
      return [Math.cos(a) * 0.36, 1.02, Math.sin(a) * 0.36, 0.14];
    }),
  ],
  island: [
    [0, -0.15, 0, 0.75],
    ...Array.from({ length: 6 }, (_, i): Sphere => {
      const a = (i / 6) * Math.PI * 2;
      return [Math.cos(a) * 0.62, -0.05, Math.sin(a) * 0.62, 0.38];
    }),
    [0, -0.8, 0, 0.42],
    [0, 0.35, 0, 0.3],
  ],
  halo: ringSpheres(24, 1, 0.14),
  lighthouse: [0.1, 0.3, 0.5, 0.7, 0.9, 1.05].map((y) => [0, y, 0, 0.13] as Sphere),
  windmill: [
    [0, 0.15, 0, 0.17],
    [0, 0.45, 0, 0.14],
    [0, 0.75, 0, 0.13],
    [0, 0.95, 0.2, 0.5],
  ],
  tree: [
    [0, 0.25, 0, 0.18],
    [0, 0.6, 0, 0.3],
  ],
  pine: [
    [0, 0.3, 0, 0.22],
    [0, 0.7, 0, 0.16],
  ],
  cloud: [],
};

const UP = new Vector3(0, 1, 0);

function randomDirection(random: () => number): Vector3 {
  const u = random() * 2 - 1;
  const theta = random() * Math.PI * 2;
  const r = Math.sqrt(1 - u * u);
  return new Vector3(r * Math.cos(theta), u, r * Math.sin(theta));
}

/** Point at angular offset (dx, dz) radians around `dir` in its local tangent frame. */
function offsetDirection(dir: Vector3, dx: number, dz: number): Vector3 {
  const t1 = new Vector3().crossVectors(dir, Math.abs(dir.y) < 0.9 ? UP : new Vector3(1, 0, 0)).normalize();
  const t2 = new Vector3().crossVectors(dir, t1);
  return dir.clone().addScaledVector(t1, dx).addScaledVector(t2, dz).normalize();
}

function slope(dir: Vector3): number {
  const h0 = terrainHeight(dir.x, dir.y, dir.z);
  let max = 0;
  for (const [dx, dz] of [
    [0.01, 0],
    [-0.01, 0],
    [0, 0.01],
    [0, -0.01],
  ] as const) {
    const d = offsetDirection(dir, dx, dz);
    max = Math.max(max, Math.abs(terrainHeight(d.x, d.y, d.z) - h0));
  }
  return max / (0.01 * PLANET_RADIUS);
}

function lowestGround(dir: Vector3, footprint: number): number {
  let min = terrainHeight(dir.x, dir.y, dir.z);
  const ang = footprint / PLANET_RADIUS;
  for (let i = 0; i < 6; i++) {
    const a = (i / 6) * Math.PI * 2;
    const d = offsetDirection(dir, Math.cos(a) * ang, Math.sin(a) * ang);
    min = Math.min(min, terrainHeight(d.x, d.y, d.z));
  }
  return min;
}

function makeMatrix(dir: Vector3, altitude: number, spin: number, scale: number | Vector3, tilt = 0): Matrix4 {
  const q = new Quaternion().setFromUnitVectors(UP, dir);
  q.multiply(new Quaternion().setFromAxisAngle(UP, spin));
  if (tilt) q.multiply(new Quaternion().setFromAxisAngle(new Vector3(1, 0, 0), tilt));
  const s = typeof scale === 'number' ? new Vector3(scale, scale, scale) : scale;
  return new Matrix4().compose(dir.clone().multiplyScalar(PLANET_RADIUS + altitude), q, s);
}

export type ObstacleField = {
  obstacles: Obstacle[];
  hits(p: Vector3, r: number): boolean;
  colliderCount: number;
};

export function generateObstacles(seed = WORLD_SEED): ObstacleField {
  const random = mulberry32(seed ^ 0x5eed);
  const obstacles: Obstacle[] = [];
  const range = (a: number, b: number) => a + (b - a) * random();

  const fits = (center: Vector3, radius: number, kinds?: ObstacleKind[]) =>
    obstacles.every(
      (o) => (kinds && !kinds.includes(o.kind)) || o.center.distanceTo(center) > o.radius + radius,
    );

  const add = (kind: ObstacleKind, matrix: Matrix4, radius: number, scale: number, centerOffset = 0.5) => {
    const center = new Vector3(0, centerOffset, 0).applyMatrix4(matrix);
    obstacles.push({ kind, matrix, center, radius, scale });
  };
  const big: ObstacleKind[] = ['arch', 'spire', 'hoodoo', 'island', 'halo', 'lighthouse', 'windmill'];

  // Natural bridges spanning the Great Rift canyon.
  for (let i = 0; i < 5; i++) {
    const along = RIFT.arcStart + 0.3 + i * ((RIFT.arcEnd - RIFT.arcStart - 0.6) / 4);
    const [e1, e2] = [new Vector3(...RIFT.e1), new Vector3(...RIFT.e2)];
    const dir = e1.multiplyScalar(Math.cos(along)).add(e2.multiplyScalar(Math.sin(along))).normalize();
    // Shift onto the wiggling centreline.
    const { across } = riftCoordinates(dir.x, dir.y, dir.z);
    dir.addScaledVector(new Vector3(...RIFT.normal), -Math.sin(across)).normalize();
    const tangentAlong = new Vector3(...RIFT.normal).cross(dir).normalize();
    // Arch spans across the canyon: its local X must point across (along the rift normal).
    const q = new Quaternion().setFromUnitVectors(UP, dir);
    const localZ = new Vector3(0, 0, 1).applyQuaternion(q);
    const spin = Math.atan2(
      new Vector3().crossVectors(localZ, tangentAlong).dot(dir),
      localZ.dot(tangentAlong),
    );
    const scale = 34;
    const base = 46;
    const matrix = makeMatrix(dir, base, spin, scale);
    add('arch', matrix, scale * 1.1, scale);
  }

  const place = (
    kind: ObstacleKind,
    count: number,
    opts: {
      scale: [number, number];
      minH: number;
      maxH: number;
      maxSlope?: number;
      footprint: number;
      radius: number;
      floatAlt?: [number, number];
      near?: Vector3[];
      nearSpread?: number;
      tilt?: number;
      attempts?: number;
      spacing?: ObstacleKind[];
      centerOffset?: number;
    },
  ) => {
    let placed = 0;
    const attempts = opts.attempts ?? count * 40;
    for (let n = 0; n < attempts && placed < count; n++) {
      let dir: Vector3;
      if (opts.near) {
        const c = opts.near[Math.floor(random() * opts.near.length)]!;
        const spread = opts.nearSpread ?? 0.08;
        dir = offsetDirection(c, range(-spread, spread), range(-spread, spread));
      } else dir = randomDirection(random);
      const h = terrainHeight(dir.x, dir.y, dir.z);
      if (h < opts.minH || h > opts.maxH) continue;
      if (opts.maxSlope !== undefined && slope(dir) > opts.maxSlope) continue;
      const { across, along } = riftCoordinates(dir.x, dir.y, dir.z);
      const inRift = Math.abs(across) < 0.07 && along > RIFT.arcStart - 0.1 && along < RIFT.arcEnd + 0.1;
      if (inRift && kind !== 'cloud') continue;
      const scale = range(opts.scale[0], opts.scale[1]);
      const altitude = opts.floatAlt
        ? Math.max(0, h) + range(opts.floatAlt[0], opts.floatAlt[1])
        : lowestGround(dir, opts.footprint * scale) - 1.5;
      const tilt = opts.tilt ? range(-opts.tilt, opts.tilt) : 0;
      const matrix = makeMatrix(dir, altitude, random() * Math.PI * 2, scale, tilt);
      const center = new Vector3(0, opts.centerOffset ?? 0.5, 0).applyMatrix4(matrix);
      const radius = opts.radius * scale;
      if (!fits(center, radius, opts.spacing ?? big)) continue;
      add(kind, matrix, radius, scale, opts.centerOffset ?? 0.5);
      placed++;
    }
  };

  place('arch', 16, { scale: [18, 26], minH: 3, maxH: 40, maxSlope: 0.5, footprint: 1, radius: 1.2 });
  const spireFields = Array.from({ length: 9 }, () => {
    for (;;) {
      const d = randomDirection(random);
      if (terrainHeight(d.x, d.y, d.z) > 2) return d;
    }
  });
  place('spire', 60, {
    scale: [45, 105],
    minH: 1,
    maxH: 60,
    footprint: 0.1,
    radius: 0.22,
    near: spireFields,
    nearSpread: 0.07,
    tilt: 0.12,
  });
  place('hoodoo', 22, { scale: [32, 52], minH: 3, maxH: 45, maxSlope: 0.6, footprint: 0.2, radius: 0.6, centerOffset: 0.8 });
  place('halo', 10, { scale: [20, 30], minH: -40, maxH: 50, footprint: 0, radius: 1.1, floatAlt: [42, 72], centerOffset: 0 });
  place('island', 12, { scale: [16, 28], minH: -60, maxH: 30, footprint: 0, radius: 1.1, floatAlt: [80, 140], centerOffset: 0 });
  place('lighthouse', 9, { scale: [26, 32], minH: 1, maxH: 5, maxSlope: 0.4, footprint: 0.15, radius: 0.3 });
  place('windmill', 12, { scale: [20, 26], minH: 4, maxH: 26, maxSlope: 0.25, footprint: 0.15, radius: 0.6 });
  place('cloud', 70, { scale: [14, 30], minH: -100, maxH: 200, footprint: 0, radius: 1, floatAlt: [105, 175], spacing: ['cloud'], centerOffset: 0 });

  // Forests: denser where a low-frequency mask says so.
  place('tree', 650, { scale: [6, 11], minH: 2, maxH: 26, maxSlope: 0.5, footprint: 0.2, radius: 0.35, attempts: 12000, spacing: [...big, 'tree', 'pine'] });
  place('pine', 650, { scale: [8, 14], minH: 14, maxH: 55, maxSlope: 0.9, footprint: 0.2, radius: 0.25, attempts: 12000, spacing: [...big, 'tree', 'pine'] });

  // Spatial hash of world-space collision spheres.
  const cell = 40;
  // Numeric cell keys (no string per lookup); cells span ±64 × 40 m, far past every obstacle.
  const SPAN = 128;
  const keyOf = (gx: number, gy: number, gz: number) =>
    Math.abs(gx) >= SPAN / 2 || Math.abs(gy) >= SPAN / 2 || Math.abs(gz) >= SPAN / 2
      ? -1
      : ((gx + SPAN / 2) * SPAN + gy + SPAN / 2) * SPAN + gz + SPAN / 2;
  const grid = new Map<number, number[]>();
  const spheres: number[] = [];
  const v = new Vector3();
  for (const o of obstacles) {
    const s = o.matrix.getMaxScaleOnAxis();
    for (const [x, y, z, r] of COLLIDERS[o.kind]) {
      v.set(x, y, z).applyMatrix4(o.matrix);
      const index = spheres.length / 4;
      spheres.push(v.x, v.y, v.z, r * s);
      const rr = r * s + 3;
      for (let gx = Math.floor((v.x - rr) / cell); gx <= Math.floor((v.x + rr) / cell); gx++)
        for (let gy = Math.floor((v.y - rr) / cell); gy <= Math.floor((v.y + rr) / cell); gy++)
          for (let gz = Math.floor((v.z - rr) / cell); gz <= Math.floor((v.z + rr) / cell); gz++) {
            const key = keyOf(gx, gy, gz);
            const list = grid.get(key);
            if (list) list.push(index);
            else grid.set(key, [index]);
          }
    }
  }
  const data = new Float32Array(spheres);

  return {
    obstacles,
    colliderCount: data.length / 4,
    hits(p, r) {
      const list = grid.get(keyOf(Math.floor(p.x / cell), Math.floor(p.y / cell), Math.floor(p.z / cell)));
      if (!list) return false;
      for (const i of list) {
        const dx = p.x - data[i * 4]!;
        const dy = p.y - data[i * 4 + 1]!;
        const dz = p.z - data[i * 4 + 2]!;
        const rr = r + data[i * 4 + 3]!;
        if (dx * dx + dy * dy + dz * dz < rr * rr) return true;
      }
      return false;
    },
  };
}