// The world model on top of the height field: where water goes, and what that
// implies for everything else.
//
// A height field alone is scenery. What makes it read as a world is that the
// terrain decides the water, the water decides the moisture, and moisture plus
// slope and elevation decide what lives where. Each layer here is derived from
// the one above it, so a rerolled world stays internally consistent: rivers run
// downhill into the basins, forests thicken along them, and cliffs stay bare.

import { GRID } from './world.js';

const idx = (x, y) => y * GRID + x;
const inside = (x, y) => x >= 0 && x < GRID && y >= 0 && y < GRID;

/**
 * Droplet erosion. Each drop walks downhill, picking up sediment on steep ground
 * and dropping it where the slope eases, which is what cuts valleys instead of
 * just adding more noise. The flow it leaves behind is the river network.
 */
export function erode(height, rng, drops = 12000) {
    const flow = new Float32Array(GRID * GRID);
    const capacity = 3.2, deposition = 0.28, erosion = 0.42, evaporation = 0.02;

    for (let d = 0; d < drops; d++) {
        let x = rng() * (GRID - 1);
        let y = rng() * (GRID - 1);
        let vx = 0, vy = 0, water = 1, sediment = 0;

        for (let step = 0; step < 64; step++) {
            const gx = Math.floor(x), gy = Math.floor(y);
            if (!inside(gx + 1, gy + 1) || !inside(gx - 1, gy - 1)) break;

            // bilinear gradient
            const fx = x - gx, fy = y - gy;
            const h00 = height[idx(gx, gy)], h10 = height[idx(gx + 1, gy)];
            const h01 = height[idx(gx, gy + 1)], h11 = height[idx(gx + 1, gy + 1)];
            const gradX = (h10 - h00) * (1 - fy) + (h11 - h01) * fy;
            const gradY = (h01 - h00) * (1 - fx) + (h11 - h10) * fx;

            vx = vx * 0.82 - gradX;
            vy = vy * 0.82 - gradY;
            const len = Math.hypot(vx, vy);
            if (len < 1e-4) break;
            vx /= len; vy /= len;

            const hOld = h00 * (1 - fx) * (1 - fy) + h10 * fx * (1 - fy) +
                         h01 * (1 - fx) * fy + h11 * fx * fy;
            x += vx; y += vy;
            if (!inside(Math.floor(x), Math.floor(y))) break;

            const hNew = height[idx(Math.floor(x), Math.floor(y))];
            const drop = hOld - hNew;
            flow[idx(Math.floor(x), Math.floor(y))] += water;

            const cap = Math.max(0, drop) * water * capacity;
            if (sediment > cap || drop < 0) {
                // uphill or over capacity: lay sediment down, filling the hollow
                const give = drop < 0 ? Math.min(sediment, -drop) : (sediment - cap) * deposition;
                height[idx(gx, gy)] += give;
                sediment -= give;
            } else {
                const take = Math.min((cap - sediment) * erosion, Math.max(0, drop));
                height[idx(gx, gy)] -= take;
                sediment += take;
            }

            water *= (1 - evaporation);
            if (water < 0.02) break;
        }
    }
    return flow;
}

/**
 * Drainage area per cell (D8): every cell sheds one unit of rain into its
 * steepest downhill neighbour, processed from the highest ground down so each
 * cell already holds everything upstream of it by the time it drains.
 *
 * Droplet paths alone do not make a river network — with one drop per few cells
 * the traces never converge. Drainage area does, and it is what actually decides
 * where a stream becomes a river: the network is dendritic because the terrain is.
 */
/**
 * Priority-Flood depression filling. Water is poured in from the borders and
 * raised only as much as it must be, so every cell ends up with a downhill path
 * to the edge — and wherever the filled surface sits above the ground, that is a
 * lake, obtained for free.
 *
 * Without this, drainage is meaningless here: erosion leaves thousands of small
 * pits, each one swallowing its catchment, so accumulation never grows past a
 * couple of hundred cells and no river ever forms.
 */
export function fillDepressions(height) {
    const n = GRID * GRID;
    const filled = Float32Array.from(height);
    const closed = new Uint8Array(n);

    // binary heap keyed on height
    const hp = [];
    const push = (i) => {
        hp.push(i);
        let c = hp.length - 1;
        while (c > 0) {
            const p = (c - 1) >> 1;
            if (filled[hp[p]] <= filled[hp[c]]) break;
            [hp[p], hp[c]] = [hp[c], hp[p]];
            c = p;
        }
    };
    const pop = () => {
        const top = hp[0], last = hp.pop();
        if (hp.length) {
            hp[0] = last;
            let p = 0;
            for (;;) {
                const l = p * 2 + 1, r = l + 1;
                let s = p;
                if (l < hp.length && filled[hp[l]] < filled[hp[s]]) s = l;
                if (r < hp.length && filled[hp[r]] < filled[hp[s]]) s = r;
                if (s === p) break;
                [hp[p], hp[s]] = [hp[s], hp[p]];
                p = s;
            }
        }
        return top;
    };

    for (let x = 0; x < GRID; x++) {
        for (const y of [0, GRID - 1]) { const i = idx(x, y); closed[i] = 1; push(i); }
    }
    for (let y = 1; y < GRID - 1; y++) {
        for (const x of [0, GRID - 1]) { const i = idx(x, y); closed[i] = 1; push(i); }
    }

    while (hp.length) {
        const i = pop();
        const x = i % GRID, y = (i / GRID) | 0;
        for (let dy = -1; dy <= 1; dy++) {
            for (let dx = -1; dx <= 1; dx++) {
                if (!dx && !dy) continue;
                const nx = x + dx, ny = y + dy;
                if (!inside(nx, ny)) continue;
                const j = idx(nx, ny);
                if (closed[j]) continue;
                closed[j] = 1;
                // raise just enough to drain, with a hair of slope so D8 has a direction
                filled[j] = Math.max(filled[j], filled[i] + 1e-4);
                push(j);
            }
        }
    }
    return filled;
}

export function drainage(height) {
    const n = GRID * GRID;
    const acc = new Float32Array(n).fill(1);
    const order = Array.from({ length: n }, (_, i) => i)
        .sort((a, b) => height[b] - height[a]);
    const sinks = [];

    for (const i of order) {
        const x = i % GRID, y = (i / GRID) | 0;
        let best = -1, bestDrop = 0;
        for (let dy = -1; dy <= 1; dy++) {
            for (let dx = -1; dx <= 1; dx++) {
                if (!dx && !dy) continue;
                const nx = x + dx, ny = y + dy;
                if (!inside(nx, ny)) continue;
                const j = idx(nx, ny);
                const drop = (height[i] - height[j]) / Math.hypot(dx, dy);
                if (drop > bestDrop) { bestDrop = drop; best = j; }
            }
        }
        if (best >= 0) acc[best] += acc[i];
        else sinks.push(i);
    }
    return { acc, sinks };
}

/**
 * Standing and running water. Rivers come from drainage area; seas and lakes
 * are simply everything below the water line. Returns the water depth per cell
 * (0 where dry) and the surface height to render.
 */
export function hydrology(height, flow, seaLevel, filled) {
    const surface = new Float32Array(GRID * GRID);
    const depth = new Float32Array(GRID * GRID);

    // A stream becomes visible once it drains enough ground — the same rule a map
    // uses. 0.4% of the grid is roughly a first-order stream at this resolution.
    const riverThreshold = GRID * GRID * 0.004;
    let maxFlow = riverThreshold;
    for (let i = 0; i < flow.length; i++) maxFlow = Math.max(maxFlow, flow[i]);

    for (let y = 0; y < GRID; y++) {
        for (let x = 0; x < GRID; x++) {
            const i = idx(x, y);
            const h = height[i];

            if (seaLevel > -900 && h < seaLevel) {
                surface[i] = seaLevel;
                depth[i] = seaLevel - h;
                continue;
            }
            // A filled depression is a lake — but only a real one. The fill raises
            // cells by a hair as it propagates outward, and treating those as water
            // hangs sheets of it down every cliff, so a lake has to be deep enough
            // to be a lake.
            if (filled && filled[i] - h > 0.4) {
                surface[i] = filled[i];
                depth[i] = filled[i] - h;
                continue;
            }
            if (flow[i] <= riverThreshold) continue;

            // Water only stays where the ground can hold it. Drops run down steep
            // faces and leave flow behind them, but painting a surface there gives
            // sheets of water clinging to cliffs — so the channel has to be flat
            // enough, and the steeper it is the more flow it takes to qualify.
            const dx = height[idx(Math.min(GRID - 1, x + 1), y)] - height[idx(Math.max(0, x - 1), y)];
            const dy = height[idx(x, Math.min(GRID - 1, y + 1))] - height[idx(x, Math.max(0, y - 1))];
            const grade = Math.hypot(dx, dy) / 2;                 // metres per cell
            const maxGrade = 0.7;
            if (grade > maxGrade) continue;

            const strength = Math.min(1, (flow[i] - riverThreshold) / (maxFlow - riverThreshold + 1e-6));
            if (strength < (grade / maxGrade) * 0.35) continue;

            const d = 0.12 + strength * 0.45 * (1 - grade / maxGrade * 0.6);
            surface[i] = h + d;
            depth[i] = d;
        }
    }
    return { surface, depth };
}

/**
 * Distance to the nearest water, in cells, by two-pass chamfer transform — cheap
 * and accurate enough to drive vegetation. Everything is thirsty; how thirsty is
 * what separates a riverbank from a dune field.
 */
export function moisture(depth) {
    const INF = 1e6;
    const dist = new Float32Array(GRID * GRID).fill(INF);
    for (let i = 0; i < depth.length; i++) if (depth[i] > 0) dist[i] = 0;

    for (let y = 0; y < GRID; y++) {
        for (let x = 0; x < GRID; x++) {
            let d = dist[idx(x, y)];
            if (inside(x - 1, y)) d = Math.min(d, dist[idx(x - 1, y)] + 1);
            if (inside(x, y - 1)) d = Math.min(d, dist[idx(x, y - 1)] + 1);
            if (inside(x - 1, y - 1)) d = Math.min(d, dist[idx(x - 1, y - 1)] + 1.414);
            dist[idx(x, y)] = d;
        }
    }
    for (let y = GRID - 1; y >= 0; y--) {
        for (let x = GRID - 1; x >= 0; x--) {
            let d = dist[idx(x, y)];
            if (inside(x + 1, y)) d = Math.min(d, dist[idx(x + 1, y)] + 1);
            if (inside(x, y + 1)) d = Math.min(d, dist[idx(x, y + 1)] + 1);
            if (inside(x + 1, y + 1)) d = Math.min(d, dist[idx(x + 1, y + 1)] + 1.414);
            dist[idx(x, y)] = d;
        }
    }

    // 0..1, saturating about 25 cells out
    const m = new Float32Array(GRID * GRID);
    for (let i = 0; i < m.length; i++) m[i] = Math.max(0, 1 - dist[i] / 25);
    return m;
}

/**
 * Where a creature can live. Habitats are expressed the way a field guide would:
 * water or land, how steep, how high, how wet — never "region 3", so the same
 * table works on any world the generator produces.
 */
export const HABITAT = {
    water:     { water: [0.6, 99], slope: [0, 9], height: [-99, 99], moist: [0, 1] },
    shallows:  { water: [0.05, 1.2], slope: [0, 0.5], height: [-99, 99], moist: [0.5, 1] },
    riverbank: { water: [0, 0.02], slope: [0, 0.45], height: [0, 99], moist: [0.55, 1] },
    plain:     { water: [0, 0.02], slope: [0, 0.35], height: [1, 99], moist: [0.1, 0.8] },
    forest:    { water: [0, 0.02], slope: [0, 0.6], height: [2, 99], moist: [0.35, 1] },
    arid:      { water: [0, 0.02], slope: [0, 0.5], height: [1, 99], moist: [0, 0.25] },
    highland:  { water: [0, 0.02], slope: [0.2, 1.2], height: [14, 99], moist: [0, 1] },
    cliff:     { water: [0, 0.02], slope: [0.7, 9], height: [6, 99], moist: [0, 1] },
};

function fits(rule, ctx) {
    return ctx.water >= rule.water[0] && ctx.water <= rule.water[1] &&
           ctx.slope >= rule.slope[0] && ctx.slope <= rule.slope[1] &&
           ctx.height >= rule.height[0] && ctx.height <= rule.height[1] &&
           ctx.moist >= rule.moist[0] && ctx.moist <= rule.moist[1];
}

/**
 * Populate the world. `species` is a list of {id, habitat, weight, scale, herd},
 * so the caller supplies its own cast — dinosaurs, livestock, anything — and the
 * rules here decide where each one belongs. Herd animals are placed in clusters
 * because a lone sauropod on an empty plain does not read as a living world.
 */
export function populate(world, species, rng, opts = {}) {
    const { height, seaLevel } = world;
    const { depth, } = world.water;
    const moist = world.moisture;
    const step = (opts.worldSize || 200) / (GRID - 1);
    const budget = opts.budget || 120;

    const placed = [];
    const total = species.reduce((a, s) => a + (s.weight || 1), 0);

    for (const sp of species) {
        const want = Math.max(1, Math.round(budget * (sp.weight || 1) / total));
        const rule = HABITAT[sp.habitat] || HABITAT.plain;
        let made = 0, tries = 0;

        while (made < want && tries < want * 220) {
            tries++;
            const gx = Math.floor(rng() * GRID), gy = Math.floor(rng() * GRID);
            const i = idx(gx, gy);
            const h = height[i];
            const dxh = (height[idx(Math.min(GRID - 1, gx + 1), gy)] - height[idx(Math.max(0, gx - 1), gy)]);
            const dyh = (height[idx(gx, Math.min(GRID - 1, gy + 1))] - height[idx(gx, Math.max(0, gy - 1))]);
            const slope = Math.hypot(dxh, dyh) / (step * 2);

            if (!fits(rule, { water: depth[i], slope, height: h, moist: moist[i] })) continue;

            // herd members share a neighbourhood rather than being sprinkled
            const group = sp.herd ? 1 + Math.floor(rng() * sp.herd) : 1;
            for (let g = 0; g < group && made < want; g++) {
                const jx = gx + (g ? Math.round((rng() - 0.5) * 10) : 0);
                const jy = gy + (g ? Math.round((rng() - 0.5) * 10) : 0);
                if (!inside(jx, jy)) continue;
                const j = idx(jx, jy);
                if (!fits(rule, { water: depth[j], slope, height: height[j], moist: moist[j] })) continue;
                placed.push({
                    id: sp.id,
                    x: -(opts.worldSize || 200) / 2 + jx * step,
                    z: -(opts.worldSize || 200) / 2 + jy * step,
                    y: depth[j] > 0.05 ? Math.max(height[j], seaLevel) : height[j],
                    scale: (sp.scale || 1) * (0.85 + rng() * 0.3),
                    rot: rng() * Math.PI * 2,
                });
                made++;
            }
        }
    }
    return placed;
}