export const GENERATOR_VERSION = "value-fbm-v1";
export type TerrainParams = {
  seed: number;
  size: number;
  frequency: number;
  octaves: number;
  water: number;
  mountain: number;
};
export type Grid = {
  size: number;
  heights: Float64Array;
  blocked: Uint8Array;
  start: number;
  goal: number;
};
export type SearchResult = {
  path: number[];
  visited: number[];
  steps: number | null;
  expanded: number;
  found: boolean;
};
export type Algorithm = "astar" | "bfs";

function lattice(x: number, y: number, seed: number) {
  let h = (Math.imul(x, 374761393) ^ Math.imul(y, 668265263) ^ seed) >>> 0;
  h = Math.imul(h ^ (h >>> 13), 1274126177);
  return ((h ^ (h >>> 16)) >>> 0) / 4294967296;
}
function noise(x: number, y: number, seed: number) {
  const ix = Math.floor(x),
    iy = Math.floor(y);
  const fx = x - ix,
    fy = y - iy;
  const u = fx * fx * (3 - 2 * fx),
    v = fy * fy * (3 - 2 * fy);
  const a = lattice(ix, iy, seed),
    b = lattice(ix + 1, iy, seed);
  const c = lattice(ix, iy + 1, seed),
    d = lattice(ix + 1, iy + 1, seed);
  return (a + (b - a) * u) * (1 - v) + (c + (d - c) * u) * v;
}
export function generateTerrain(params: TerrainParams): Grid {
  const { seed, size, frequency, octaves, water, mountain } = params;
  if (
    !Number.isInteger(seed) ||
    seed < 0 ||
    seed > 0xffffffff ||
    !Number.isInteger(size) ||
    size < 3 ||
    size > 128 ||
    !Number.isFinite(frequency) ||
    frequency <= 0 ||
    frequency > 1 ||
    !Number.isInteger(octaves) ||
    octaves < 1 ||
    octaves > 8 ||
    !Number.isFinite(water) ||
    !Number.isFinite(mountain) ||
    water < 0 ||
    mountain > 1 ||
    water >= mountain
  )
    throw new RangeError("Invalid terrain parameters");
  const heights = new Float64Array(size * size),
    blocked = new Uint8Array(size * size);
  for (let y = 0; y < size; y++)
    for (let x = 0; x < size; x++) {
      let sum = 0,
        norm = 0,
        amplitude = 1,
        scale = frequency;
      for (let octave = 0; octave < octaves; octave++) {
        sum +=
          noise(
            (x + 27) * scale,
            (y + 13) * scale,
            (seed + octave * 1013) >>> 0,
          ) * amplitude;
        norm += amplitude;
        amplitude *= 0.5;
        scale *= 2;
      }
      const index = y * size + x;
      heights[index] = sum / norm;
      blocked[index] =
        heights[index] < water || heights[index] > mountain ? 1 : 0;
    }
  const start = (size - 2) * size + 1,
    goal = size + size - 2;
  blocked[start] = blocked[goal] = 0;
  return { size, heights, blocked, start, goal };
}
export function neighbors(id: number, size: number) {
  const x = id % size,
    y = Math.floor(id / size),
    result: number[] = [];
  if (x > 0) result.push(id - 1);
  if (x < size - 1) result.push(id + 1);
  if (y > 0) result.push(id - size);
  if (y < size - 1) result.push(id + size);
  return result;
}
type Entry = { id: number; f: number; g: number };
class MinHeap {
  items: Entry[] = [];
  better(a: Entry, b: Entry) {
    return (
      a.f < b.f || (a.f === b.f && (a.g > b.g || (a.g === b.g && a.id < b.id)))
    );
  }
  push(value: Entry) {
    const a = this.items;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.better(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop() {
    const a = this.items,
      result = a[0],
      last = a.pop()!;
    if (a.length) {
      a[0] = last;
      let i = 0;
      while (true) {
        let best = i;
        const l = i * 2 + 1,
          r = l + 1;
        if (l < a.length && this.better(a[l], a[best])) best = l;
        if (r < a.length && this.better(a[r], a[best])) best = r;
        if (best === i) break;
        [a[i], a[best]] = [a[best], a[i]];
        i = best;
      }
    }
    return result;
  }
}
/** Both algorithms solve the SAME four-connected graph with unit edge costs.
 * A* uses consistent Manhattan distance and a binary heap. Heights are visual only. */
export function search(grid: Grid, algorithm: Algorithm): SearchResult {
  const { size, blocked, start, goal } = grid,
    total = size * size;
  if (
    !Number.isInteger(size) ||
    size < 1 ||
    blocked.length !== total ||
    !Number.isInteger(start) ||
    !Number.isInteger(goal) ||
    start < 0 ||
    goal < 0 ||
    start >= total ||
    goal >= total ||
    !["astar", "bfs"].includes(algorithm)
  )
    throw new RangeError("Invalid search input");
  const empty = {
    path: [],
    visited: [],
    steps: null,
    expanded: 0,
    found: false,
  };
  if (blocked[start] || blocked[goal]) return empty;
  const parent = new Int32Array(total).fill(-1),
    costs = new Float64Array(total).fill(Infinity);
  const closed = new Uint8Array(total),
    visited: number[] = [],
    queue = new Uint32Array(total),
    heap = new MinHeap();
  let head = 0,
    tail = 0;
  const heuristic = (id: number) =>
    Math.abs((id % size) - (goal % size)) +
    Math.abs(Math.floor(id / size) - Math.floor(goal / size));
  costs[start] = 0;
  if (algorithm === "bfs") queue[tail++] = start;
  else heap.push({ id: start, f: heuristic(start), g: 0 });
  while (algorithm === "bfs" ? head < tail : heap.items.length > 0) {
    const id = algorithm === "bfs" ? queue[head++] : heap.pop().id;
    if (closed[id]) continue;
    closed[id] = 1;
    visited.push(id);
    if (id === goal) {
      const path = [goal];
      while (path[path.length - 1] !== start)
        path.push(parent[path[path.length - 1]]);
      path.reverse();
      return {
        path,
        visited,
        steps: path.length - 1,
        expanded: visited.length,
        found: true,
      };
    }
    for (const next of neighbors(id, size)) {
      if (blocked[next] || closed[next]) continue;
      const cost = costs[id] + 1;
      if (cost >= costs[next]) continue;
      costs[next] = cost;
      parent[next] = id;
      if (algorithm === "bfs") queue[tail++] = next;
      else heap.push({ id: next, g: cost, f: cost + heuristic(next) });
    }
  }
  return {
    path: [],
    visited,
    steps: null,
    expanded: visited.length,
    found: false,
  };
}