amaze 0.4.1

A maze generator
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

use crate::grid_coord_2d::{GetCoordinateBounds2D, GridCoord2D, LinearizeCoords2D};
use crate::wall4_grid::Wall4Grid;
use std::ops::Index;

#[derive(Debug, Clone, Eq, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct AdjacencyList {
    pub width: usize,
    pub height: usize,
    pub neighbors: Vec<Vec<GridCoord2D>>,
}

impl AdjacencyList {
    pub fn neighbors(&self, coord: GridCoord2D) -> &[GridCoord2D] {
        &self.neighbors[self.linearize_coords(coord)]
    }

    pub fn get_neighbors(&self, coord: GridCoord2D) -> Option<&[GridCoord2D]> {
        if coord.x >= self.width || coord.y >= self.height {
            return None;
        }
        Some(self.neighbors(coord))
    }
}

impl GetCoordinateBounds2D for AdjacencyList {
    #[inline]
    fn width(&self) -> usize {
        self.width
    }

    #[inline]
    fn height(&self) -> usize {
        self.height
    }
}

impl Index<GridCoord2D> for AdjacencyList {
    type Output = [GridCoord2D];

    fn index(&self, index: GridCoord2D) -> &Self::Output {
        self.neighbors(index)
    }
}

impl From<&Wall4Grid> for AdjacencyList {
    fn from(value: &Wall4Grid) -> Self {
        let mut neighbors = vec![Vec::with_capacity(4); value.width() * value.height()];

        for cell in value.coords() {
            neighbors[value.linearize_coords(cell)] = value.open_neighbors(cell).collect();
        }

        Self {
            width: value.width(),
            height: value.height(),
            neighbors,
        }
    }
}

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

    #[test]
    fn adjacency_matches_grid_open_neighbors() {
        let maze = RecursiveBacktracker4::new_from_seed(7).generate(8, 8);
        let adjacency = AdjacencyList::from(&maze);

        for coord in maze.coords() {
            assert_eq!(
                adjacency.neighbors(coord),
                maze.open_neighbors(coord).collect::<Vec<_>>()
            );
        }
    }

    #[test]
    fn get_neighbors_returns_none_out_of_bounds() {
        let maze = RecursiveBacktracker4::new_from_seed(7).generate(8, 8);
        let adjacency = AdjacencyList::from(&maze);

        assert!(
            adjacency
                .get_neighbors(GridCoord2D::new(adjacency.width, 0))
                .is_none()
        );
        assert!(
            adjacency
                .get_neighbors(GridCoord2D::new(0, adjacency.height))
                .is_none()
        );
    }

    #[test]
    fn index_trait_matches_neighbors_method() {
        let maze = RecursiveBacktracker4::new_from_seed(7).generate(8, 8);
        let adjacency = AdjacencyList::from(&maze);

        for coord in maze.coords() {
            assert_eq!(&adjacency[coord], adjacency.neighbors(coord));
        }
    }

    #[test]
    fn neighbor_symmetry() {
        let maze = RecursiveBacktracker4::new_from_seed(7).generate(8, 8);
        let adjacency = AdjacencyList::from(&maze);

        for coord in maze.coords() {
            for neighbor in adjacency.neighbors(coord) {
                assert!(adjacency.neighbors(*neighbor).contains(&coord));
            }
        }
    }

    #[test]
    fn empty_grid_produces_empty_adjacency() {
        let maze = RecursiveBacktracker4::new_from_seed(7).generate(0, 0);
        let adjacency = AdjacencyList::from(&maze);

        assert_eq!(adjacency.width, 0);
        assert_eq!(adjacency.height, 0);
        assert!(adjacency.neighbors.is_empty());
    }
}