mazeir/map/orthogonal/
depth_first.rs

1//! Cell bit flags:
2//!
3//! | flag | description |
4//! |:-----|:------------|
5//! | 0 | visited |
6//! | 1-3 | last direction |
7use super::{Orthogonal, Direction2D};
8
9use rand::Rng;
10use rand::seq::SliceRandom;
11
12use crate::algorithm::DepthFirst;
13
14const FLAG: u8 = 0b1000_0000;
15const LAST_DIRECTION_MASK: u8 = 0b0111_0000;
16const LAST_DIRECTION_MASK_INVERSE: u8 = 0b1000_1111;
17const LAST_DIRECTION_NONE: u8 = 0b0000_0000;
18const LAST_DIRECTION_LEFT: u8 = 0b0001_0000;
19const LAST_DIRECTION_RIGHT: u8 = 0b0010_0000;
20const LAST_DIRECTION_UP: u8 = 0b0011_0000;
21const LAST_DIRECTION_DOWN: u8 = 0b00100_0000;
22
23
24impl Orthogonal {
25    #[inline]
26    fn add_walls_to_vec_with_flag(&mut self, x: usize, y: usize, vec: &mut Vec<Direction2D>) {
27        if x != 0 && *self.get_mut(x - 1, y) & FLAG == 0 { vec.push(Direction2D::Left); }
28        if x != self.width - 1 && *self.get_mut(x + 1, y) & FLAG == 0 { vec.push(Direction2D::Right); }
29        if y != 0 && *self.get_mut(x, y - 1) & FLAG == 0 { vec.push(Direction2D::Up); }
30        if y != self.height - 1 && *self.get_mut(x, y + 1) & FLAG == 0 { vec.push(Direction2D::Down); }
31    }
32}
33
34
35impl DepthFirst for Orthogonal {
36    fn depth_first_with_rng<R: Rng + ?Sized>(&mut self, rng: &mut R) {
37        if self.width == 0 || self.height == 0 { return; }
38        let mut rng = rng;
39        let start_point = self.center_point();
40        let (mut x, mut y) = (start_point.0, start_point.1);
41        self.set(x, y, FLAG);
42        let mut walls = Vec::with_capacity(4);
43        loop {
44            walls.clear();
45            self.add_walls_to_vec_with_flag(x, y, &mut walls);
46            let wall = walls.choose(&mut rng);
47            match wall {
48                Some(wall) => {
49                    self.break_wall(x, y, wall);
50                    match wall {
51                        Direction2D::Left => {
52                            x -= 1;
53                            self.map[y * self.width + x] &= LAST_DIRECTION_MASK_INVERSE;
54                            self.map[y * self.width + x] |= LAST_DIRECTION_RIGHT;
55                        }
56                        Direction2D::Right => {
57                            x += 1;
58                            self.map[y * self.width + x] &= LAST_DIRECTION_MASK_INVERSE;
59                            self.map[y * self.width + x] |= LAST_DIRECTION_LEFT;
60                        }
61                        Direction2D::Up => {
62                            y -= 1;
63                            self.map[y * self.width + x] &= LAST_DIRECTION_MASK_INVERSE;
64                            self.map[y * self.width + x] |= LAST_DIRECTION_DOWN;
65                        }
66                        Direction2D::Down => {
67                            y += 1;
68                            self.map[y * self.width + x] &= LAST_DIRECTION_MASK_INVERSE;
69                            self.map[y * self.width + x] |= LAST_DIRECTION_UP;
70                        }
71                    }
72                    self.map[y * self.width + x] |= FLAG;
73                }
74                None => {
75                    let point_value = self.get_mut(x, y);
76                    match *point_value & LAST_DIRECTION_MASK {
77                        LAST_DIRECTION_LEFT => { x -= 1; }
78                        LAST_DIRECTION_RIGHT => { x += 1; }
79                        LAST_DIRECTION_UP => { y -= 1; }
80                        LAST_DIRECTION_DOWN => { y += 1; }
81                        LAST_DIRECTION_NONE => { break; }
82                        _ => {}//不会发生
83                    }
84                }
85            }
86        }
87    }
88}
mazeir/map/orthogonal/depth_first.rs

mazeir/map/orthogonal/
depth_first.rs
