terrain_forge/algorithms/
bsp.rs

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

terrain_forge/algorithms/
bsp.rs
