use std::{cmp::Reverse, collections::BinaryHeap};

use bevy::prelude::*;

use crate::world::WorldMap;

const STRAIGHT: u32 = 10;
const DIAGONAL: u32 = 14;
const MIN_TERRAIN_COST: u32 = 100;

const NEIGHBORS: [IVec2; 8] = [
    IVec2::new(1, 0),
    IVec2::new(-1, 0),
    IVec2::new(0, 1),
    IVec2::new(0, -1),
    IVec2::new(1, 1),
    IVec2::new(1, -1),
    IVec2::new(-1, 1),
    IVec2::new(-1, -1),
];

pub fn find_path(map: &WorldMap, start: UVec2, goal: UVec2) -> Option<Vec<UVec2>> {
    let start = start.as_ivec2();
    let goal = goal.as_ivec2();
    map.move_cost(start)?;
    map.move_cost(goal)?;
    if start == goal {
        return Some(vec![]);
    }

    let width = map.size.x as usize;
    let index = |p: IVec2| p.y as usize * width + p.x as usize;
    let tiles = map.size.element_product() as usize;
    let mut cost_so_far = vec![u32::MAX; tiles];
    let mut came_from = vec![None::<IVec2>; tiles];
    let mut open = BinaryHeap::new();

    cost_so_far[index(start)] = 0;
    open.push(Reverse((heuristic(start, goal), start.x, start.y)));

    while let Some(Reverse((_, x, y))) = open.pop() {
        let current = IVec2::new(x, y);
        if current == goal {
            return Some(reconstruct(&came_from, index, start, goal));
        }
        let current_cost = cost_so_far[index(current)];
        for step in NEIGHBORS {
            let next = current + step;
            let Some(terrain_cost) = map.move_cost(next) else {
                continue;
            };
            let diagonal = step.x != 0 && step.y != 0;
            if diagonal
                && (map.move_cost(current + IVec2::new(step.x, 0)).is_none()
                    || map.move_cost(current + IVec2::new(0, step.y)).is_none())
            {
                continue;
            }
            let base = if diagonal { DIAGONAL } else { STRAIGHT };
            let new_cost = current_cost + base * terrain_cost;
            if new_cost < cost_so_far[index(next)] {
                cost_so_far[index(next)] = new_cost;
                came_from[index(next)] = Some(current);
                open.push(Reverse((new_cost + heuristic(next, goal), next.x, next.y)));
            }
        }
    }
    None
}

fn heuristic(a: IVec2, b: IVec2) -> u32 {
    let d = (a - b).abs();
    let (min, max) = (d.x.min(d.y) as u32, d.x.max(d.y) as u32);
    (DIAGONAL * min + STRAIGHT * (max - min)) * MIN_TERRAIN_COST
}

fn reconstruct(
    came_from: &[Option<IVec2>],
    index: impl Fn(IVec2) -> usize,
    start: IVec2,
    goal: IVec2,
) -> Vec<UVec2> {
    let mut path = vec![goal.as_uvec2()];
    let mut current = goal;
    while let Some(prev) = came_from[index(current)] {
        if prev == start {
            break;
        }
        path.push(prev.as_uvec2());
        current = prev;
    }
    path.reverse();
    path
}

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

    fn map_from(rows: &[&str]) -> WorldMap {
        let size = UVec2::new(rows[0].len() as u32, rows.len() as u32);
        let mut map = WorldMap::filled(size, Terrain::Grass);
        for (row, line) in rows.iter().enumerate() {
            let y = size.y - 1 - row as u32;
            for (x, c) in line.chars().enumerate() {
                let terrain = match c {
                    '#' => Terrain::Stone,
                    '~' => Terrain::ShallowWater,
                    _ => Terrain::Grass,
                };
                map.set(UVec2::new(x as u32, y), terrain);
            }
        }
        map
    }

    fn is_connected(start: UVec2, path: &[UVec2]) -> bool {
        std::iter::once(start)
            .chain(path.iter().copied())
            .collect::<Vec<_>>()
            .windows(2)
            .all(|w| (w[0].as_ivec2() - w[1].as_ivec2()).abs().max_element() == 1)
    }

    #[test]
    fn path_excludes_start_and_ends_at_goal() {
        let map = map_from(&["....."]);
        let path = find_path(&map, UVec2::new(0, 0), UVec2::new(4, 0)).unwrap();
        assert_eq!(
            path,
            vec![UVec2::new(1, 0), UVec2::new(2, 0), UVec2::new(3, 0), UVec2::new(4, 0)]
        );
    }

    #[test]
    fn path_to_self_is_empty() {
        let map = map_from(&["..."]);
        assert_eq!(find_path(&map, UVec2::ZERO, UVec2::ZERO), Some(vec![]));
    }

    #[test]
    fn path_goes_around_walls() {
        let map = map_from(&[
            ".....", //
            ".###.",
            ".#.#.",
            "...#.",
        ]);
        let start = UVec2::new(2, 1);
        let goal = UVec2::new(4, 0);
        let path = find_path(&map, start, goal).unwrap();
        assert!(is_connected(start, &path));
        assert_eq!(path.last(), Some(&goal));
        assert!(path.iter().all(|p| map.move_cost(p.as_ivec2()).is_some()));
    }

    #[test]
    fn unreachable_or_impassable_goal_has_no_path() {
        let map = map_from(&[
            "..#..", //
            "..#..",
        ]);
        assert_eq!(find_path(&map, UVec2::new(0, 0), UVec2::new(4, 0)), None);
        assert_eq!(find_path(&map, UVec2::new(0, 0), UVec2::new(2, 0)), None);
    }

    // Colonists move in straight lines between tile centers, so a diagonal step between two
    // blocked orthogonal neighbours would visually clip through the corners of walls.
    #[test]
    fn diagonal_steps_never_cut_wall_corners() {
        let map = map_from(&[
            "#.", //
            ".#",
        ]);
        assert_eq!(find_path(&map, UVec2::new(0, 0), UVec2::new(1, 1)), None);
        let map = map_from(&[
            "..", //
            "#.",
        ]);
        let path = find_path(&map, UVec2::new(0, 1), UVec2::new(1, 0)).unwrap();
        assert_eq!(path, vec![UVec2::new(1, 1), UVec2::new(1, 0)]);
    }

    #[test]
    fn prefers_detour_over_slow_terrain() {
        let map = map_from(&[
            ".....", //
            "..~..",
        ]);
        let path = find_path(&map, UVec2::new(0, 0), UVec2::new(4, 0)).unwrap();
        assert!(!path.contains(&UVec2::new(2, 0)));
    }

    #[test]
    fn crosses_slow_terrain_when_it_is_the_only_way() {
        let map = map_from(&["..~.."]);
        let path = find_path(&map, UVec2::new(0, 0), UVec2::new(4, 0)).unwrap();
        assert!(path.contains(&UVec2::new(2, 0)));
    }

    #[test]
    fn finds_paths_across_a_generated_world() {
        let map = crate::worldgen::generate(crate::worldgen::WORLD_SIZE, 1);
        let region = crate::worldgen::largest_region(&map);
        let (start, goal) = (region[0], region[region.len() - 1]);
        let path = find_path(&map, start, goal).unwrap();
        assert!(is_connected(start, &path));
        assert_eq!(path.last(), Some(&goal));
    }
}