//! Field of view by symmetric shadowcasting, after Albert Ford's write-up at
//! <https://www.albertford.com/shadowcasting/>.
//!
//! Symmetric means that if you can see a floor cell, someone standing there
//! can see you. Monsters wake when they come into view, so this keeps
//! ambushes fair: nothing notices you that you couldn't have seen first.

use super::{Map, Pos};

/// The cells visible from one spot.
pub struct Fov {
    width: i32,
    visible: Vec<bool>,
}

impl Fov {
    pub fn contains(&self, p: Pos) -> bool {
        p.x >= 0
            && p.y >= 0
            && p.x < self.width
            && self.visible.get((p.y * self.width + p.x) as usize).copied().unwrap_or(false)
    }
}

/// Everything visible from `origin` within `radius` cells. Walls are visible
/// (that's how you see a room's shape); cells behind them aren't.
pub fn compute(map: &Map, origin: Pos, radius: i32) -> Fov {
    let mut fov = Fov { width: map.width, visible: vec![false; (map.width * map.height) as usize] };
    let mut reveal = |p: Pos| {
        if map.contains(p) {
            fov.visible[map.index(p)] = true;
        }
    };
    reveal(origin);
    for quadrant in Quadrant::ALL {
        let mut rows = vec![Row { depth: 1, start: Slope::new(-1, 1), end: Slope::new(1, 1) }];
        while let Some(mut row) = rows.pop() {
            if row.depth > radius {
                continue;
            }
            let mut prev_blocked = None;
            for col in row.min_col()..=row.max_col() {
                let p = quadrant.cell(origin, row.depth, col);
                let blocked = map.tile(p).blocks_sight();
                let in_radius = col * col + row.depth * row.depth <= radius * radius + radius;
                if in_radius && (blocked || row.is_symmetric(col)) {
                    reveal(p);
                }
                if prev_blocked == Some(true) && !blocked {
                    row.start = Slope::left_edge(row.depth, col);
                }
                if prev_blocked == Some(false) && blocked {
                    let mut next = row.next();
                    next.end = Slope::left_edge(row.depth, col);
                    rows.push(next);
                }
                prev_blocked = Some(blocked);
            }
            if prev_blocked == Some(false) {
                rows.push(row.next());
            }
        }
    }
    fov
}

#[derive(Clone, Copy)]
enum Quadrant {
    North,
    East,
    South,
    West,
}

impl Quadrant {
    const ALL: [Quadrant; 4] = [Quadrant::North, Quadrant::East, Quadrant::South, Quadrant::West];

    /// The cell `depth` rows out from `origin` and `col` columns across.
    fn cell(self, origin: Pos, depth: i32, col: i32) -> Pos {
        match self {
            Quadrant::North => origin.offset(col, -depth),
            Quadrant::South => origin.offset(col, depth),
            Quadrant::East => origin.offset(depth, col),
            Quadrant::West => origin.offset(-depth, col),
        }
    }
}

/// An exact fraction, so shadows land on the same cells every time.
#[derive(Clone, Copy)]
struct Slope {
    num: i32,
    /// Always positive.
    den: i32,
}

impl Slope {
    const fn new(num: i32, den: i32) -> Slope {
        Slope { num, den }
    }

    /// The slope through the left edge of the cell at (`depth`, `col`).
    const fn left_edge(depth: i32, col: i32) -> Slope {
        Slope::new(2 * col - 1, 2 * depth)
    }
}

#[derive(Clone, Copy)]
struct Row {
    depth: i32,
    start: Slope,
    end: Slope,
}

impl Row {
    /// `depth * start`, rounded with ties going up.
    fn min_col(&self) -> i32 {
        (2 * self.depth * self.start.num + self.start.den).div_euclid(2 * self.start.den)
    }

    /// `depth * end`, rounded with ties going down.
    fn max_col(&self) -> i32 {
        -(self.end.den - 2 * self.depth * self.end.num).div_euclid(2 * self.end.den)
    }

    /// Whether the centre of the cell at `col` is inside this row's slopes.
    fn is_symmetric(&self, col: i32) -> bool {
        col * self.start.den >= self.depth * self.start.num
            && col * self.end.den <= self.depth * self.end.num
    }

    fn next(&self) -> Row {
        Row { depth: self.depth + 1, ..*self }
    }
}

#[cfg(test)]
mod tests {
    use rand::RngExt;

    use super::*;
    use crate::dungeon::Tile;
    use crate::seed;

    fn map_from(rows: &[&str]) -> (Map, Pos) {
        let mut map = Map::new(rows[0].len() as i32, rows.len() as i32, Tile::Floor);
        let mut at = Pos::new(0, 0);
        for (y, row) in rows.iter().enumerate() {
            for (x, c) in row.chars().enumerate() {
                let p = Pos::new(x as i32, y as i32);
                match c {
                    '#' => map.set(p, Tile::Wall),
                    '@' => at = p,
                    _ => {}
                }
            }
        }
        (map, at)
    }

    #[test]
    fn walls_cast_shadows() {
        let (map, at) = map_from(&[
            "#########", //
            "#.......#", "#...@...#", "#..###..#", "#.......#", "#########",
        ]);
        let fov = compute(&map, at, 10);
        assert!(fov.contains(Pos::new(1, 1)), "open floor is visible");
        assert!(fov.contains(Pos::new(4, 3)), "the wall itself is visible");
        assert!(!fov.contains(Pos::new(4, 4)), "the cell right behind the wall is hidden");
        assert!(fov.contains(Pos::new(1, 3)), "cells beside the wall stay visible");
    }

    #[test]
    fn radius_limits_sight() {
        let (map, _) = map_from(&[&".".repeat(30)]);
        let fov = compute(&map, Pos::new(0, 0), 5);
        assert!(fov.contains(Pos::new(5, 0)));
        assert!(!fov.contains(Pos::new(6, 0)));
    }

    /// The property the module promises: seeing is mutual between floor cells.
    #[test]
    fn sight_is_symmetric() {
        let mut rng = seed::rng(4);
        for _ in 0..20 {
            let mut map = Map::new(24, 16, Tile::Floor);
            for p in map.positions().collect::<Vec<_>>() {
                if rng.random_bool(0.25) {
                    map.set(p, Tile::Wall);
                }
            }
            let floors: Vec<Pos> =
                map.positions().filter(|&p| map.tile(p) == Tile::Floor).collect();
            let views: Vec<Fov> = floors.iter().map(|&p| compute(&map, p, 8)).collect();
            for (i, &a) in floors.iter().enumerate() {
                for (j, &b) in floors.iter().enumerate() {
                    assert_eq!(
                        views[i].contains(b),
                        views[j].contains(a),
                        "{a:?} and {b:?} disagree about seeing each other"
                    );
                }
            }
        }
    }
}