ez-roguelike/carpet/src/vis.rs

use crate::{Board, Coord};

// This includes an implementation of the visibility algorithm
// described at
// https://journal.stuffwithstuff.com/2015/09/07/what-the-hero-sees/

/// The algorithm as described uses a number from 0 to 8 for
/// this. This is rarely used and doesn't get us much safety, but it
/// felt better to me to have it be a proper enum.
#[derive(Debug, Copy, Clone)]
enum Octant {
    NE,
    EN,
    ES,
    SE,
    SW,
    WS,
    WN,
    NW,
}

const ALL_OCTANTS: &[Octant] = &[
    Octant::NE,
    Octant::EN,
    Octant::ES,
    Octant::SE,
    Octant::SW,
    Octant::WS,
    Octant::WN,
    Octant::NW,
];

impl Octant {
    fn translate(&self, column: usize, row: usize) -> (isize, isize) {
        let x = column as isize;
        let y = row as isize;
        match &self {
            Octant::NE => (x, -y),
            Octant::EN => (y, -x),
            Octant::ES => (y, x),
            Octant::SE => (x, y),
            Octant::SW => (-x, y),
            Octant::WS => (-y, x),
            Octant::WN => (-y, -x),
            Octant::NW => (-x, -y),
        }
    }
}

/// A shadow represents a single occluded section along an octant. We
/// maintain the invariant that both `start` and `end` in the
/// inclusive range `[0.0, 1.0]` and also that `start < end`.
#[derive(Debug, PartialEq, Clone, Copy)]
struct Shadow {
    start: f32,
    end: f32,
}

impl Shadow {
    fn new(a: f32, b: f32) -> Shadow {
        let start = a.min(b);
        let end = a.max(b);
        Shadow { start, end }
    }

    fn project_from(row: usize, col: usize) -> Shadow {
        let row = row as f32;
        let col = col as f32;
        let top_left = col / (row + 2.0);
        let bottom_right = (col + 1.0) / (row + 1.0);
        Shadow::new(top_left, bottom_right)
    }

    fn contains(&self, other: &Shadow) -> bool {
        self.start <= other.start && self.end >= other.end
    }
}

#[derive(Debug, PartialEq)]
struct ShadowLine {
    shadows: Vec<Shadow>,
}

impl ShadowLine {
    fn in_shadow(&self, other: &Shadow) -> bool {
        self.shadows.iter().any(|sh| sh.contains(other))
    }

    fn is_full_shadow(&self) -> bool {
        self.shadows.len() == 1 && self.shadows[0].start.eq(&0.0) && self.shadows[0].end.eq(&1.0)
    }

    fn add(&mut self, other: Shadow) {
        let index = self
            .shadows
            .iter()
            .position(|sh| sh.start >= other.start)
            .unwrap_or(self.shadows.len());

        // find whether there's an overlapping previous and next
        // shadow segment

        // we gotta check here because `index` is unsigned; if we just
        // subtracted and `index` was 0 then we'd get a panic.
        let previous = if index == 0 {
            None
        } else {
            self.shadows
                .get(index - 1)
                .filter(|sh| sh.end > other.start)
        };
        let next = self.shadows.get(index).filter(|sh| sh.start < other.end);

        match (previous, next) {
            // 1 2 3 4 5 6 7      1 2 3 4 5 6 7
            // [prev] [next]  =>  [prev.......]
            //    [other]
            //
            // two overlapping segments: join them together,
            // specifically extending the previous one and deleting
            // the second
            (Some(_), Some(n)) => {
                self.shadows[index - 1].end = n.end;
                self.shadows.remove(index);
            }
            // 1 2 3 4 5 6 7 8 9      1 2 3 4 5 6 7 8 9
            // [prev]     [next]  =>  [prev]  [next...]
            //         [other]
            //
            // just overlapping a later segment: pull the later
            // segment's start point earlier
            (None, Some(_)) => {
                self.shadows[index].start = other.start;
            }
            // 1 2 3 4 5 6 7 8 9      1 2 3 4 5 6 7 8 9
            // [prev]     [next]  =>  [prev...]  [next]
            //   [other]
            //
            // just overlapping an earlier segment: pull the earlier
            // segment's end point later
            (Some(_), None) => {
                self.shadows[index - 1].end = other.end;
            }
            // 1 2 3 4 5 6 7 8    1 2 3 4 5 6 7 8
            // [p]         [n] => [p] [other] [n]
            //     [other]
            // no overlapping segments: just add this one in between
            (None, None) => {
                self.shadows.insert(index, other);
            }
        }
    }
}

pub struct Viewshed<T> {
    pub vis: Board<bool>,
    blocking: Box<fn(&T) -> bool>,
    pub range: Option<usize>,
}

impl<T> Viewshed<T> {
    pub fn create(original: &Board<T>, blocking: fn(&T) -> bool) -> Viewshed<T> {
        let vis = Board::new_from(original.width(), original.height(), |_, _| false);
        let blocking = Box::new(blocking);
        let range = None;
        Viewshed {
            vis,
            blocking,
            range,
        }
    }

    pub fn visibility(&self, coord: impl Into<Coord>) -> bool {
        self.vis[coord.into()]
    }

    pub fn calculate_from(&mut self, board: &Board<T>, coord: Coord) {
        for (_, _, elem) in self.vis.iter_mut() {
            *elem = false;
        }

        self.vis[coord] = true;
        for octant in ALL_OCTANTS {
            self.refresh_octant(*octant, board, coord);
        }
    }

    fn refresh_octant(&mut self, octant: Octant, board: &Board<T>, coord: Coord) {
        let mut line = ShadowLine {
            shadows: Vec::new(),
        };
        let mut full_shadow = false;

        for row in 1.. {
            let pos = coord + octant.translate(row, 0);

            if !board.contains(pos) {
                break;
            }

            for col in 0..=row {
                let pos = coord + octant.translate(row, col);

                if !board.contains(pos) {
                    break;
                }

                if full_shadow {
                    self.vis[pos] = false;
                    continue;
                }

                let projection = Shadow::project_from(row, col);
                let visible = !line.in_shadow(&projection);
                self.vis[pos] = visible;

                if visible {
                    let out_of_range = if let Some(r) = self.range {
                        ((row.pow(2) + col.pow(2)) as f32).sqrt() >= r as f32
                    } else {
                        false
                    };
                    if out_of_range || (self.blocking)(&board[pos]) {
                        line.add(projection);
                        full_shadow = line.is_full_shadow();
                    }
                }
            }
        }
    }
}

#[cfg(test)]
mod test {
    use crate::{Board, Coord, Viewshed};

    macro_rules! board_from_vec {
        ($w:expr, $h:expr; [$($vec:tt)*]) => {
            {
                let w = $w;
                let h = $h;
                let v = vec![$($vec)*];
                assert!(v.len() == w * h);
                Board::new_from(w, h, |x, y| {
                    v.get(x + y * w).unwrap().clone()
                })
            }
        }
    }

    const V: bool = true;
    const U: bool = false;

    fn assert_same_vis(p: Coord, exp: &Board<bool>, actual: &Board<bool>) {
        if exp != actual {
            panic!(
                "Expected:\n{}\n========\nActual:\n{}\n",
                to_vis(p, exp),
                to_vis(p, actual)
            );
        }
    }

    #[test]
    fn add_shadow_line() {
        let mut line = super::ShadowLine {
            shadows: Vec::new(),
        };

        assert_eq!(line.shadows.len(), 0);

        line.add(super::Shadow::new(0.0, 0.6));
        assert_eq!(line.shadows.len(), 1);
        assert_eq!(line.shadows[0], super::Shadow::new(0.0, 0.6));

        line.add(super::Shadow::new(0.4, 1.0));
        assert_eq!(line.shadows.len(), 1);
        assert_eq!(line.shadows[0], super::Shadow::new(0.0, 1.0));
    }

    #[test]
    fn add_shadow_line_after() {
        let mut line = super::ShadowLine {
            shadows: Vec::new(),
        };

        assert_eq!(line.shadows.len(), 0);

        line.add(super::Shadow::new(0.0, 0.1));
        assert_eq!(line.shadows.len(), 1);
        assert_eq!(line.shadows[0], super::Shadow::new(0.0, 0.1));

        line.add(super::Shadow::new(0.9, 1.0));
        assert_eq!(line.shadows.len(), 2);
        assert_eq!(line.shadows[0], super::Shadow::new(0.0, 0.1));
        assert_eq!(line.shadows[1], super::Shadow::new(0.9, 1.0));
    }

    #[test]
    fn add_shadow_line_before() {
        let mut line = super::ShadowLine {
            shadows: Vec::new(),
        };

        assert_eq!(line.shadows.len(), 0);

        line.add(super::Shadow::new(0.9, 1.0));
        assert_eq!(line.shadows.len(), 1);
        assert_eq!(line.shadows[0], super::Shadow::new(0.9, 1.0));

        line.add(super::Shadow::new(0.0, 0.1));
        assert_eq!(line.shadows.len(), 2);
        assert_eq!(line.shadows[0], super::Shadow::new(0.0, 0.1));
        assert_eq!(line.shadows[1], super::Shadow::new(0.9, 1.0));
    }

    #[test]
    fn add_shadow_line_several() {
        let mut line = super::ShadowLine {
            shadows: Vec::new(),
        };

        assert_eq!(line.shadows.len(), 0);

        line.add(super::Shadow::new(0.5, 0.8));
        assert_eq!(line.shadows.len(), 1);

        line.add(super::Shadow::new(0.0, 0.667));
        assert_eq!(line.shadows.len(), 1);

        line.add(super::Shadow::new(0.6, 1.0));
        assert_eq!(line.shadows.len(), 1);
    }

    fn to_vis(p: Coord, vis: &super::Board<bool>) -> String {
        let mut buf = String::new();
        for y in 0..vis.height() {
            for x in 0..vis.width() {
                if p.x == x && p.y == y {
                    buf.push('@')
                } else {
                    buf.push(match vis[(x, y)] {
                        true => '#',
                        false => '.',
                    })
                }
            }
            buf.push('\n')
        }
        buf
    }

    #[test]
    fn simple_room_visibility() {
        let b: Board<isize> = board_from_vec![
            5,5;
            [
                0, 0, 0, 0, 0,
                0, 1, 1, 1, 0,
                0, 1, 0, 1, 0,
                0, 1, 1, 1, 0,
                0, 0, 0, 0, 0,
            ]
        ];
        let mut v = Viewshed::create(&b, |n| *n == 1);
        let p = Coord::new(2, 2);
        v.calculate_from(&b, p);
        let exp: Board<bool> = board_from_vec![
            5,5;
            [
                U, U, U, U, U,
                U, V, V, V, U,
                U, V, V, V, U,
                U, V, V, V, U,
                U, U, U, U, U,
            ]
        ];
        assert_same_vis(p, &exp, &v.vis);
    }

    #[test]
    fn big_room_visibility() {
        let b: Board<isize> = board_from_vec![
            7,7;
            [
                0, 0, 0, 0, 0, 0, 0,
                0, 1, 1, 1, 1, 1, 0,
                0, 1, 0, 0, 0, 1, 0,
                0, 1, 0, 0, 0, 1, 0,
                0, 1, 0, 0, 0, 1, 0,
                0, 1, 1, 1, 1, 1, 0,
                0, 0, 0, 0, 0, 0, 0,
            ]
        ];
        let mut v = Viewshed::create(&b, |n| *n == 1);
        let p = Coord::new(3, 3);
        v.calculate_from(&b, p);
        let exp: Board<bool> = board_from_vec![
            7,7;
            [
                U, U, U, U, U, U, U,
                U, V, V, V, V, V, U,
                U, V, V, V, V, V, U,
                U, V, V, V, V, V, U,
                U, V, V, V, V, V, U,
                U, V, V, V, V, V, U,
                U, U, U, U, U, U, U,
            ]
        ];
        assert_same_vis(p, &exp, &v.vis);
    }

    #[test]
    fn corridor_visibility() {
        let b: Board<isize> = board_from_vec![
            13,7;
            [
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0,
                0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0,
                0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
                0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0,
                0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
            ]
        ];
        let mut v = Viewshed::create(&b, |n| *n == 1);
        let p = Coord::new(3, 3);
        v.calculate_from(&b, p);
        let exp: Board<bool> = board_from_vec![
            13,7;
            [
                U, U, U, U, U, U, U, U, U, U, U, U, U,
                U, V, V, V, V, V, U, U, U, U, U, U, U,
                U, V, V, V, V, V, V, V, V, V, V, V, U,
                U, V, V, V, V, V, V, V, V, V, V, V, U,
                U, V, V, V, V, V, V, V, V, V, V, V, U,
                U, V, V, V, V, V, U, U, U, U, U, U, U,
                U, U, U, U, U, U, U, U, U, U, U, U, U,
            ]
        ];
        assert_same_vis(p, &exp, &v.vis);
    }

    #[test]
    fn last_room_visible() {
        let b: Board<isize> = board_from_vec![
            7,5;
            [
                0, 0, 0, 0, 0, 0, 0,
                0, 1, 1, 1, 1, 1, 0,
                0, 1, 0, 1, 0, 1, 0,
                0, 1, 1, 1, 1, 1, 0,
                0, 0, 0, 0, 0, 0, 0,
            ]
        ];

        let mut v = Viewshed::create(&b, |n| *n == 1);
        let p = Coord::new(2, 2);
        v.calculate_from(&b, p);
        let exp: Board<bool> = board_from_vec![
            7,5;
            [
                U, U, U, U, U, U, U,
                U, V, V, V, U, U, U,
                U, V, V, V, U, U, U,
                U, V, V, V, U, U, U,
                U, U, U, U, U, U, U,
            ]
        ];
        assert_same_vis(p, &exp, &v.vis);

        let p = Coord::new(4, 2);
        v.calculate_from(&b, p);
        let exp: Board<bool> = board_from_vec![
            7,5;
            [
                U, U, U, U, U, U, U,
                U, U, U, V, V, V, U,
                U, U, U, V, V, V, U,
                U, U, U, V, V, V, U,
                U, U, U, U, U, U, U,
            ]
        ];
        assert_same_vis(p, &exp, &v.vis);
    }

    #[test]
    fn long_room_visible() {
        let b: Board<isize> = board_from_vec![
            9,7;
            [
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 1, 1, 1, 1, 1, 1, 1, 0,
                0, 1, 0, 0, 0, 0, 0, 1, 0,
                0, 1, 0, 0, 0, 0, 0, 1, 0,
                0, 1, 0, 0, 0, 0, 0, 1, 0,
                0, 1, 1, 1, 1, 1, 1, 1, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0,
            ]
        ];

        let mut v = Viewshed::create(&b, |n| *n == 1);
        let p = Coord::new(2, 2);
        v.calculate_from(&b, p);
        let exp: Board<bool> = board_from_vec![
            9,7;
            [
                U, U, U, U, U, U, U, U, U,
                U, V, V, V, V, V, V, V, U,
                U, V, V, V, V, V, V, V, U,
                U, V, V, V, V, V, V, V, U,
                U, V, V, V, V, V, V, V, U,
                U, V, V, V, V, V, V, V, U,
                U, U, U, U, U, U, U, U, U,
            ]
        ];
        assert_same_vis(p, &exp, &v.vis);
    }
}