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 { min_room_size: 5, max_depth: 4, room_padding: 1 }
13    }
14}
15
16pub struct Bsp {
17    config: BspConfig,
18}
19
20impl Bsp {
21    pub fn new(config: BspConfig) -> Self { Self { config } }
22}
23
24impl Default for Bsp {
25    fn default() -> Self { Self::new(BspConfig::default()) }
26}
27
28struct BspNode {
29    x: usize, y: usize, w: usize, h: usize,
30    left: Option<Box<BspNode>>,
31    right: Option<Box<BspNode>>,
32    room: Option<(usize, usize, usize, usize)>,
33}
34
35impl BspNode {
36    fn new(x: usize, y: usize, w: usize, h: usize) -> Self {
37        Self { x, y, w, h, left: None, right: None, room: None }
38    }
39
40    fn split(&mut self, rng: &mut Rng, min_size: usize, depth: usize, max_depth: usize) {
41        if depth >= max_depth { return; }
42
43        let can_h = self.h >= min_size * 2;
44        let can_v = self.w >= min_size * 2;
45        if !can_h && !can_v { return; }
46
47        let split_h = if can_h && can_v { rng.chance(0.5) } else { can_h };
48
49        if split_h {
50            let split = rng.range_usize(min_size, self.h - min_size + 1);
51            self.left = Some(Box::new(BspNode::new(self.x, self.y, self.w, split)));
52            self.right = Some(Box::new(BspNode::new(self.x, self.y + split, self.w, self.h - split)));
53        } else {
54            let split = rng.range_usize(min_size, self.w - min_size + 1);
55            self.left = Some(Box::new(BspNode::new(self.x, self.y, split, self.h)));
56            self.right = Some(Box::new(BspNode::new(self.x + split, self.y, self.w - split, self.h)));
57        }
58
59        if let Some(ref mut l) = self.left { l.split(rng, min_size, depth + 1, max_depth); }
60        if let Some(ref mut r) = self.right { r.split(rng, min_size, depth + 1, max_depth); }
61    }
62
63    fn create_rooms(&mut self, rng: &mut Rng, padding: usize) {
64        if self.left.is_some() || self.right.is_some() {
65            if let Some(ref mut l) = self.left { l.create_rooms(rng, padding); }
66            if let Some(ref mut r) = self.right { r.create_rooms(rng, padding); }
67        } else {
68            let min_w = 3.min(self.w.saturating_sub(padding * 2));
69            let min_h = 3.min(self.h.saturating_sub(padding * 2));
70            if min_w < 3 || min_h < 3 { return; }
71
72            let max_w = self.w.saturating_sub(padding * 2);
73            let max_h = self.h.saturating_sub(padding * 2);
74            let w = rng.range_usize(min_w, max_w + 1);
75            let h = rng.range_usize(min_h, max_h + 1);
76            let x = self.x + padding + rng.range_usize(0, max_w - w + 1);
77            let y = self.y + padding + rng.range_usize(0, max_h - h + 1);
78            self.room = Some((x, y, w, h));
79        }
80    }
81
82    fn get_center(&self) -> Option<(usize, usize)> {
83        if let Some((x, y, w, h)) = self.room {
84            return Some((x + w / 2, y + h / 2));
85        }
86        self.left.as_ref().and_then(|n| n.get_center())
87            .or_else(|| self.right.as_ref().and_then(|n| n.get_center()))
88    }
89
90    fn carve(&self, grid: &mut Grid<Tile>) {
91        if let Some((x, y, w, h)) = self.room {
92            grid.fill_rect(x as i32, y as i32, w, h, Tile::Floor);
93        }
94        if let (Some(ref left), Some(ref right)) = (&self.left, &self.right) {
95            left.carve(grid);
96            right.carve(grid);
97            if let (Some((lx, ly)), Some((rx, ry))) = (left.get_center(), right.get_center()) {
98                for x in lx.min(rx)..=lx.max(rx) { grid.set(x as i32, ly as i32, Tile::Floor); }
99                for y in ly.min(ry)..=ly.max(ry) { grid.set(rx as i32, y as i32, Tile::Floor); }
100            }
101        }
102    }
103}
104
105impl Algorithm<Tile> for Bsp {
106    fn generate(&self, grid: &mut Grid<Tile>, seed: u64) {
107        let mut rng = Rng::new(seed);
108        let mut root = BspNode::new(1, 1, grid.width() - 2, grid.height() - 2);
109        root.split(&mut rng, self.config.min_room_size, 0, self.config.max_depth);
110        root.create_rooms(&mut rng, self.config.room_padding);
111        root.carve(grid);
112    }
113
114    fn name(&self) -> &'static str { "BSP" }
115}
terrain_forge/algorithms/bsp.rs

terrain_forge/algorithms/
bsp.rs
