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/

/// In many roguelikes, there are three possible visibility states:
/// completely unseen (represented as undrawn black squares), actively
/// visible (represented as brightly-drawn squares with visible
/// monsters), and discovered-but-currently-occluded (represented as
/// dim squares without drawn monsters).
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum Visibility {
    /// The square is in view of the current POV
    Visible,
    /// The square has been viewed before but is not currently visible
    Seen,
    /// The square has not been viewed before
    Unseen,
}

/// 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(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(start: f32, end: f32) -> Shadow {
        Shadow { start, end }
    }

    fn project_from(coord: Coord) -> Shadow {
        let Coord { x, y } = coord;
        let top_left = y as f32 / (x as f32 + 2.0);
        let bottom_right = (y as f32 + 1.0) / (x as f32 + 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 = {
            let mut index = 0;
            for (i, shadow) in self.shadows.iter().enumerate() {
                if shadow.start >= other.start {
                    index = i;
                    break;
                }
            }
            index
        };

        // 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) {
            // two overlapping segments: join them together
            (Some(_), Some(n)) => {
                self.shadows[index - 1].end = n.end;
                self.shadows.remove(index);
            }
            // just one overlapping segment: extend the segment in the
            // appropriate direction
            (None, Some(_)) => {
                self.shadows[index].end = other.end;
            }
            (Some(_), None) => {
                self.shadows[index - 1].start = other.start;
            }
            // no overlapping segments: add this one
            (None, None) => {
                self.shadows.insert(index, other);
            }
        }
    }
}

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

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(), |_, _| {
            Visibility::Unseen
        });
        let blocking = Box::new(blocking);
        Viewshed { vis, blocking }
    }

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

    pub fn calculate_from(&mut self, board: &Board<T>, coord: Coord) {
        self.set_visibility(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.set_visibility(pos, false);
                    continue;
                }

                let projection = Shadow::project_from(Coord::new(row, col));
                let visible = !line.in_shadow(&projection);
                self.set_visibility(pos, visible);

                if visible && (self.blocking)(&board[pos]) {
                    line.add(projection);
                    full_shadow = line.is_full_shadow();
                }
            }
        }
    }

    fn set_visibility(&mut self, coord: Coord, visible: bool) {
        if visible {
            self.vis[coord] = Visibility::Visible;
        } else if self.vis[coord] == Visibility::Unseen {
            self.vis[coord] = Visibility::Unseen
        } else {
            self.vis[coord] = Visibility::Seen
        }
    }
}

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

    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: Visibility = Visibility::Visible;
    const U: Visibility = Visibility::Unseen;
    const S: Visibility = Visibility::Seen;

    #[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));
    }

    fn to_vis(vis: &super::Board<super::Visibility>) -> String {
        let mut buf = String::new();
        for x in 0..vis.width() {
            for y in 0..vis.height() {
                buf.push(match vis[(x, y)] {
                    V => '.',
                    S => '#',
                    U => ' ',
                })
            }
            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);
        v.calculate_from(&b, Coord::new(2, 2));
        let exp: Board<Visibility> = 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_eq!(to_vis(&v.vis), to_vis(&exp));
    }

    #[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);
        v.calculate_from(&b, Coord::new(2, 2));
        let exp: Board<Visibility> = 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_eq!(v.vis, exp);

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