terrain_forge/algorithms/
bsp.rs

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

terrain_forge/algorithms/
bsp.rs
