use std::collections::VecDeque;

use bevy::prelude::*;

use crate::{
    noise::Noise,
    world::{Terrain, WorldMap},
};

pub const WORLD_SIZE: UVec2 = UVec2::new(256, 256);
pub const DEFAULT_SEED: u32 = 1;

const ELEVATION_SCALE: f32 = 1.0 / 48.0;
const FERTILITY_SCALE: f32 = 1.0 / 16.0;
const DEEP_WATER_SHARE: f32 = 0.10;
const SHALLOW_WATER_SHARE: f32 = 0.06;
const SAND_SHARE: f32 = 0.04;
const STONE_SHARE: f32 = 0.14;
const SOIL_SHARE: f32 = 0.20;

pub struct WorldGenPlugin;

impl Plugin for WorldGenPlugin {
    fn build(&self, app: &mut App) {
        app.insert_resource(WorldSeed(DEFAULT_SEED))
            .insert_resource(generate(WORLD_SIZE, DEFAULT_SEED))
            .add_message::<WorldGenerated>()
            .add_systems(Startup, |mut generated: MessageWriter<WorldGenerated>| {
                generated.write(WorldGenerated);
            })
            .add_systems(Update, regenerate_on_key);
    }
}

#[derive(Resource, Debug, Clone, Copy, PartialEq)]
pub struct WorldSeed(pub u32);

#[derive(Message, Debug, Clone, Copy)]
pub struct WorldGenerated;

fn regenerate_on_key(
    keys: Res<ButtonInput<KeyCode>>,
    mut seed: ResMut<WorldSeed>,
    mut map: ResMut<WorldMap>,
    mut generated: MessageWriter<WorldGenerated>,
) {
    if keys.just_pressed(KeyCode::KeyR) {
        seed.0 = seed.0.wrapping_add(1);
        *map = generate(map.size, seed.0);
        generated.write(WorldGenerated);
    }
}

pub fn generate(size: UVec2, seed: u32) -> WorldMap {
    let elevation_noise = Noise::new(seed);
    let fertility_noise = Noise::new(seed.wrapping_add(0x1000));
    let mut map = WorldMap::filled(size, Terrain::Grass);
    let positions: Vec<UVec2> = map.positions().collect();
    let elevation: Vec<f32> = positions
        .iter()
        .map(|p| elevation_noise.fbm(p.as_vec2() * ELEVATION_SCALE, 5))
        .collect();
    let fertility: Vec<f32> = positions
        .iter()
        .map(|p| fertility_noise.fbm(p.as_vec2() * FERTILITY_SCALE, 3))
        .collect();

    let deep = quantile(&elevation, DEEP_WATER_SHARE);
    let shallow = quantile(&elevation, DEEP_WATER_SHARE + SHALLOW_WATER_SHARE);
    let sand = quantile(
        &elevation,
        DEEP_WATER_SHARE + SHALLOW_WATER_SHARE + SAND_SHARE,
    );
    let stone = quantile(&elevation, 1.0 - STONE_SHARE);
    let soil = quantile(&fertility, 1.0 - SOIL_SHARE);

    for ((&pos, &e), &f) in positions.iter().zip(&elevation).zip(&fertility) {
        let terrain = if e < deep {
            Terrain::DeepWater
        } else if e < shallow {
            Terrain::ShallowWater
        } else if e < sand {
            Terrain::Sand
        } else if e >= stone {
            Terrain::Stone
        } else if f >= soil {
            Terrain::Soil
        } else {
            Terrain::Grass
        };
        map.set(pos, terrain);
    }
    map
}

pub fn quantile(values: &[f32], share: f32) -> f32 {
    let mut sorted = values.to_vec();
    sorted.sort_by(f32::total_cmp);
    let i = ((sorted.len() as f32 * share) as usize).min(sorted.len() - 1);
    sorted[i]
}

pub fn largest_region(map: &WorldMap) -> Vec<UVec2> {
    let mut seen = vec![false; map.size.element_product() as usize];
    let index = |p: UVec2| (p.y * map.size.x + p.x) as usize;
    let mut best = Vec::new();
    for start in map.positions() {
        if seen[index(start)] || map.move_cost(start.as_ivec2()).is_none() {
            continue;
        }
        let region = flood(map, start, |p| {
            let fresh = !seen[index(p)];
            seen[index(p)] = true;
            fresh
        });
        if region.len() > best.len() {
            best = region;
        }
    }
    best
}

fn flood(map: &WorldMap, start: UVec2, mut visit: impl FnMut(UVec2) -> bool) -> Vec<UVec2> {
    let mut region = Vec::new();
    let mut queue = VecDeque::from([start]);
    visit(start);
    while let Some(pos) = queue.pop_front() {
        region.push(pos);
        for step in [IVec2::X, IVec2::NEG_X, IVec2::Y, IVec2::NEG_Y] {
            let next = pos.as_ivec2() + step;
            if map.move_cost(next).is_some() && visit(next.as_uvec2()) {
                queue.push_back(next.as_uvec2());
            }
        }
    }
    region
}

pub fn spawn_tiles(map: &WorldMap, count: usize) -> Vec<UVec2> {
    let center = map.size.as_vec2() / 2.0;
    let Some(&origin) = largest_region(map).iter().min_by(|a, b| {
        a.as_vec2()
            .distance_squared(center)
            .total_cmp(&b.as_vec2().distance_squared(center))
    }) else {
        return Vec::new();
    };
    let mut seen = std::collections::HashSet::new();
    flood(map, origin, |p| seen.insert(p))
        .into_iter()
        .step_by(2)
        .take(count)
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::pathfinding::find_path;

    const SIZE: UVec2 = UVec2::new(96, 64);

    fn share(map: &WorldMap, terrain: Terrain) -> f32 {
        let n = map
            .positions()
            .filter(|p| map.get(p.as_ivec2()) == Some(terrain))
            .count();
        n as f32 / map.size.element_product() as f32
    }

    #[test]
    fn same_seed_generates_same_world() {
        let (a, b, c) = (generate(SIZE, 7), generate(SIZE, 7), generate(SIZE, 8));
        let tiles = |m: &WorldMap| {
            m.positions()
                .map(|p| m.get(p.as_ivec2()))
                .collect::<Vec<_>>()
        };
        assert_eq!(tiles(&a), tiles(&b));
        assert_ne!(tiles(&a), tiles(&c));
    }

    // Elevation thresholds come from quantiles rather than fixed values, so every seed gets the
    // same terrain mix instead of occasionally being all ocean or all mountain.
    #[test]
    fn terrain_shares_are_stable_across_seeds() {
        for seed in 0..5 {
            let map = generate(SIZE, seed);
            assert!((share(&map, Terrain::DeepWater) - DEEP_WATER_SHARE).abs() < 0.02);
            assert!((share(&map, Terrain::Stone) - STONE_SHARE).abs() < 0.02);
            for terrain in Terrain::ALL {
                assert!(share(&map, terrain) > 0.0, "seed {seed} lacks {terrain:?}");
            }
        }
    }

    #[test]
    fn quantile_picks_value_at_share() {
        let values: Vec<f32> = (0..10).rev().map(|v| v as f32).collect();
        assert_eq!(quantile(&values, 0.0), 0.0);
        assert_eq!(quantile(&values, 0.3), 3.0);
        assert_eq!(quantile(&values, 1.0), 9.0);
    }

    #[test]
    fn largest_region_picks_biggest_walkable_area() {
        let mut map = WorldMap::filled(UVec2::new(6, 3), Terrain::Grass);
        for y in 0..3 {
            map.set(UVec2::new(2, y), Terrain::Stone);
        }
        let region = largest_region(&map);
        assert_eq!(region.len(), 9);
        assert!(region.iter().all(|p| p.x > 2));
    }

    // Colonists must start somewhere they can all reach each other and most of the map,
    // not on a small island cut off by deep water or stone.
    #[test]
    fn spawn_tiles_are_distinct_walkable_and_mutually_reachable() {
        for seed in 0..5 {
            let map = generate(SIZE, seed);
            let tiles = spawn_tiles(&map, 3);
            assert_eq!(tiles.len(), 3);
            let region = largest_region(&map);
            for t in &tiles {
                assert!(region.contains(t));
                assert!(find_path(&map, tiles[0], *t).is_some());
            }
            let mut unique = tiles.clone();
            unique.dedup();
            assert_eq!(unique.len(), 3);
        }
    }
}