terrain_forge/algorithms/
bsp.rs

1use crate::{Algorithm, Grid, Rng, Tile};
2
3#[derive(Debug, Clone)]
4pub struct BspConfig {
5    pub min_room_size: usize,
6    pub max_depth: usize,
7    pub room_padding: usize,
8}
9
10impl Default for BspConfig {
11    fn default() -> Self {
12        Self {
13            min_room_size: 5,
14            max_depth: 4,
15            room_padding: 1,
16        }
17    }
18}
19
20pub struct Bsp {
21    config: BspConfig,
22}
23
24impl Bsp {
25    pub fn new(config: BspConfig) -> Self {
26        Self { config }
27    }
28}
29
30impl Default for Bsp {
31    fn default() -> Self {
32        Self::new(BspConfig::default())
33    }
34}
35
36struct BspNode {
37    x: usize,
38    y: usize,
39    w: usize,
40    h: usize,
41    left: Option<Box<BspNode>>,
42    right: Option<Box<BspNode>>,
43    room: Option<(usize, usize, usize, usize)>,
44}
45
46impl BspNode {
47    fn new(x: usize, y: usize, w: usize, h: usize) -> Self {
48        Self {
49            x,
50            y,
51            w,
52            h,
53            left: None,
54            right: None,
55            room: None,
56        }
57    }
58
59    fn split(&mut self, rng: &mut Rng, min_size: usize, depth: usize, max_depth: usize) {
60        if depth >= max_depth {
61            return;
62        }
63
64        let can_h = self.h >= min_size * 2;
65        let can_v = self.w >= min_size * 2;
66        if !can_h && !can_v {
67            return;
68        }
69
70        let split_h = if can_h && can_v {
71            rng.chance(0.5)
72        } else {
73            can_h
74        };
75
76        if split_h {
77            let split = rng.range_usize(min_size, self.h - min_size + 1);
78            self.left = Some(Box::new(BspNode::new(self.x, self.y, self.w, split)));
79            self.right = Some(Box::new(BspNode::new(
80                self.x,
81                self.y + split,
82                self.w,
83                self.h - split,
84            )));
85        } else {
86            let split = rng.range_usize(min_size, self.w - min_size + 1);
87            self.left = Some(Box::new(BspNode::new(self.x, self.y, split, self.h)));
88            self.right = Some(Box::new(BspNode::new(
89                self.x + split,
90                self.y,
91                self.w - split,
92                self.h,
93            )));
94        }
95
96        if let Some(ref mut l) = self.left {
97            l.split(rng, min_size, depth + 1, max_depth);
98        }
99        if let Some(ref mut r) = self.right {
100            r.split(rng, min_size, depth + 1, max_depth);
101        }
102    }
103
104    fn create_rooms(&mut self, rng: &mut Rng, padding: usize) {
105        if self.left.is_some() || self.right.is_some() {
106            if let Some(ref mut l) = self.left {
107                l.create_rooms(rng, padding);
108            }
109            if let Some(ref mut r) = self.right {
110                r.create_rooms(rng, padding);
111            }
112        } else {
113            let min_w = 3.min(self.w.saturating_sub(padding * 2));
114            let min_h = 3.min(self.h.saturating_sub(padding * 2));
115            if min_w < 3 || min_h < 3 {
116                return;
117            }
118
119            let max_w = self.w.saturating_sub(padding * 2);
120            let max_h = self.h.saturating_sub(padding * 2);
121            let w = rng.range_usize(min_w, max_w + 1);
122            let h = rng.range_usize(min_h, max_h + 1);
123            let x = self.x + padding + rng.range_usize(0, max_w - w + 1);
124            let y = self.y + padding + rng.range_usize(0, max_h - h + 1);
125            self.room = Some((x, y, w, h));
126        }
127    }
128
129    fn get_center(&self) -> Option<(usize, usize)> {
130        if let Some((x, y, w, h)) = self.room {
131            return Some((x + w / 2, y + h / 2));
132        }
133        self.left
134            .as_ref()
135            .and_then(|n| n.get_center())
136            .or_else(|| self.right.as_ref().and_then(|n| n.get_center()))
137    }
138
139    fn carve(&self, grid: &mut Grid<Tile>) {
140        if let Some((x, y, w, h)) = self.room {
141            grid.fill_rect(x as i32, y as i32, w, h, Tile::Floor);
142        }
143        if let (Some(ref left), Some(ref right)) = (&self.left, &self.right) {
144            left.carve(grid);
145            right.carve(grid);
146            if let (Some((lx, ly)), Some((rx, ry))) = (left.get_center(), right.get_center()) {
147                for x in lx.min(rx)..=lx.max(rx) {
148                    grid.set(x as i32, ly as i32, Tile::Floor);
149                }
150                for y in ly.min(ry)..=ly.max(ry) {
151                    grid.set(rx as i32, y as i32, Tile::Floor);
152                }
153            }
154        }
155    }
156}
157
158impl Algorithm<Tile> for Bsp {
159    fn generate(&self, grid: &mut Grid<Tile>, seed: u64) {
160        let mut rng = Rng::new(seed);
161        let mut root = BspNode::new(1, 1, grid.width() - 2, grid.height() - 2);
162        root.split(
163            &mut rng,
164            self.config.min_room_size,
165            0,
166            self.config.max_depth,
167        );
168        root.create_rooms(&mut rng, self.config.room_padding);
169        root.carve(grid);
170    }
171
172    fn name(&self) -> &'static str {
173        "BSP"
174    }
175}
terrain_forge/algorithms/bsp.rs

terrain_forge/algorithms/
bsp.rs
