src/building.rs 13.3 K · 399 lines · raw · history

1 use std::collections::{HashMap, HashSet, VecDeque};
2
3 use bevy::prelude::*;
4
5 use crate::{
6 colonist::Colonist,
7 items::{Item, ItemKind},
8 sim::{SimSystems, SimTick},
9 structures::{Structure, StructureKind},
10 world::{TILE_SIZE, TilePos, WorldMap},
11 worldgen::WorldGenerated,
12 zones::{Zones, can_zone},
13 };
14
15 pub struct BuildingPlugin;
16
17 impl Plugin for BuildingPlugin {
18 fn build(&self, app: &mut App) {
19 app.init_resource::<Blueprints>()
20 .add_systems(
21 Update,
22 (
23 clear_blueprints.run_if(on_message::<WorldGenerated>),
24 draw_blueprints,
25 ),
26 )
27 .add_systems(FixedUpdate, plan_shelter.in_set(SimSystems::Decide));
28 }
29 }
30
31 pub const MAX_ROOM_TILES: usize = 120;
32 const PLAN_INTERVAL_TICKS: u64 = 300;
33 const MAX_ROOM_MARGIN: i32 = 2;
34 const CRAMPED_SIDE_COST: i32 = 3;
35 const WALL_BLUEPRINT_COLOR: Color = Color::srgba(0.5, 0.75, 1.0, 0.8);
36 const DOOR_BLUEPRINT_COLOR: Color = Color::srgba(1.0, 0.8, 0.4, 0.8);
37 const PAVE_BLUEPRINT_COLOR: Color = Color::srgba(0.85, 0.85, 0.85, 0.5);
38 const ROOF_BLUEPRINT_COLOR: Color = Color::srgba(0.8, 0.6, 1.0, 0.35);
39
40 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
41 pub enum BuildKind {
42 Structure(StructureKind),
43 Roof,
44 Pave,
45 }
46
47 impl BuildKind {
48 pub fn cost(self) -> (ItemKind, u32) {
49 match self {
50 BuildKind::Structure(kind) => kind.cost(),
51 BuildKind::Roof => (ItemKind::Wood, 1),
52 BuildKind::Pave => (ItemKind::Stone, 1),
53 }
54 }
55
56 pub fn work(self) -> u32 {
57 match self {
58 BuildKind::Structure(StructureKind::Campfire) => 360,
59 BuildKind::Structure(StructureKind::Torch) => 120,
60 BuildKind::Structure(StructureKind::Bed) => 600,
61 BuildKind::Structure(StructureKind::Wall) => 300,
62 BuildKind::Structure(StructureKind::Door) => 300,
63 BuildKind::Roof => 120,
64 BuildKind::Pave => 120,
65 }
66 }
67
68 pub fn name(self) -> &'static str {
69 match self {
70 BuildKind::Structure(kind) => kind.name(),
71 BuildKind::Roof => "roof",
72 BuildKind::Pave => "paving",
73 }
74 }
75
76 pub fn blocks_tile(self) -> bool {
77 self == BuildKind::Structure(StructureKind::Wall)
78 }
79 }
80
81 #[derive(Resource, Default, Debug, Clone)]
82 pub struct Blueprints(pub HashMap<UVec2, BuildKind>);
83
84 impl Blueprints {
85 pub fn get(&self, tile: UVec2) -> Option<BuildKind> {
86 self.0.get(&tile).copied()
87 }
88
89 pub fn tiles(&self) -> HashSet<UVec2> {
90 self.0.keys().copied().collect()
91 }
92 }
93
94 fn clear_blueprints(mut blueprints: ResMut<Blueprints>) {
95 blueprints.0.clear();
96 }
97
98 pub fn enclosed_room(map: &WorldMap, doors: &HashSet<UVec2>, start: UVec2) -> Option<Vec<UVec2>> {
99 let mut seen = HashSet::from([start]);
100 let mut queue = VecDeque::from([start]);
101 while let Some(tile) = queue.pop_front() {
102 if seen.len() > MAX_ROOM_TILES {
103 return None;
104 }
105 for step in [IVec2::X, IVec2::NEG_X, IVec2::Y, IVec2::NEG_Y] {
106 let next = tile.as_ivec2() + step;
107 if !map.in_bounds(next) {
108 return None;
109 }
110 let next = next.as_uvec2();
111 let barrier = map.is_wall(next.as_ivec2())
112 || doors.contains(&next)
113 || map.get(next.as_ivec2()).is_some_and(|t| t.is_rock());
114 if !barrier && seen.insert(next) {
115 queue.push_back(next);
116 }
117 }
118 }
119 let mut room: Vec<UVec2> = seen.into_iter().collect();
120 room.sort_by_key(|t| (t.y, t.x));
121 Some(room)
122 }
123
124 pub struct ShelterContext<'a> {
125 pub map: &'a WorldMap,
126 pub structures: &'a [(UVec2, StructureKind)],
127 pub items: &'a [UVec2],
128 }
129
130 impl ShelterContext<'_> {
131 fn doors(&self) -> HashSet<UVec2> {
132 self.structures
133 .iter()
134 .filter(|(_, kind)| *kind == StructureKind::Door)
135 .map(|(pos, _)| *pos)
136 .collect()
137 }
138
139 fn wall_buildable(&self, tile: IVec2) -> bool {
140 can_zone(self.map, tile)
141 && self.map.plant(tile).is_none()
142 && !self.items.contains(&tile.as_uvec2())
143 && !self
144 .structures
145 .iter()
146 .any(|(pos, _)| *pos == tile.as_uvec2())
147 }
148
149 fn already_closed(&self, tile: IVec2, doors: &HashSet<UVec2>) -> bool {
150 self.map.is_wall(tile)
151 || doors.contains(&tile.as_uvec2())
152 || self.map.get(tile).is_some_and(|t| t.is_rock())
153 }
154
155 pub fn plan(&self, beds: &[UVec2], toward: UVec2) -> Option<HashMap<UVec2, BuildKind>> {
156 let doors = self.doors();
157 if let Some(&first) = beds.first()
158 && let Some(room) = enclosed_room(self.map, &doors, first)
159 {
160 let roofs: HashMap<UVec2, BuildKind> = room
161 .into_iter()
162 .filter(|t| !self.map.is_roofed(t.as_ivec2()))
163 .map(|t| (t, BuildKind::Roof))
164 .collect();
165 return (!roofs.is_empty()).then_some(roofs);
166 }
167 let min = beds.iter().copied().reduce(|a, b| a.min(b))?.as_ivec2();
168 let max = beds.iter().copied().reduce(|a, b| a.max(b))?.as_ivec2();
169 let margins = 0..=MAX_ROOM_MARGIN;
170 let shapes = margins.clone().flat_map(|l| {
171 let margins = margins.clone();
172 margins.clone().flat_map(move |r| {
173 let margins = margins.clone();
174 margins
175 .clone()
176 .flat_map(move |d| margins.clone().map(move |u| IVec4::new(l, r, d, u)))
177 })
178 });
179 shapes
180 .filter_map(|m| {
181 let lo = min - IVec2::new(m.x, m.z) - 1;
182 let hi = max + IVec2::new(m.y, m.w) + 1;
183 let plan = self.walls_around(lo, hi, toward, &doors)?;
184 let cramped = m.to_array().iter().filter(|&&side| side == 0).count() as i32;
185 let cost = plan.len() as i32 + CRAMPED_SIDE_COST * cramped;
186 Some((cost, m.to_array(), plan))
187 })
188 .min_by_key(|(cost, margins, _)| (*cost, *margins))
189 .map(|(_, _, plan)| plan)
190 }
191
192 fn walls_around(
193 &self,
194 lo: IVec2,
195 hi: IVec2,
196 toward: UVec2,
197 doors: &HashSet<UVec2>,
198 ) -> Option<HashMap<UVec2, BuildKind>> {
199 let ring: Vec<IVec2> = (lo.y..=hi.y)
200 .flat_map(|y| (lo.x..=hi.x).map(move |x| IVec2::new(x, y)))
201 .filter(|t| t.x == lo.x || t.x == hi.x || t.y == lo.y || t.y == hi.y)
202 .collect();
203 let mut plan = HashMap::new();
204 for &tile in &ring {
205 if !self.map.in_bounds(tile) {
206 return None;
207 }
208 if self.already_closed(tile, doors) {
209 continue;
210 }
211 if !self.wall_buildable(tile) {
212 return None;
213 }
214 plan.insert(tile.as_uvec2(), BuildKind::Structure(StructureKind::Wall));
215 }
216 let has_door = ring.iter().any(|t| doors.contains(&t.as_uvec2()));
217 if !has_door {
218 let corner = |t: &UVec2| {
219 let t = t.as_ivec2();
220 (t.x == lo.x || t.x == hi.x) && (t.y == lo.y || t.y == hi.y)
221 };
222 let door = plan.keys().filter(|t| !corner(t)).copied().min_by(|a, b| {
223 a.as_vec2()
224 .distance_squared(toward.as_vec2())
225 .total_cmp(&b.as_vec2().distance_squared(toward.as_vec2()))
226 .then((a.y, a.x).cmp(&(b.y, b.x)))
227 })?;
228 plan.insert(door, BuildKind::Structure(StructureKind::Door));
229 }
230 Some(plan)
231 }
232 }
233
234 pub fn plan_shelter(
235 tick: Res<SimTick>,
236 map: Res<WorldMap>,
237 mut zones: ResMut<Zones>,
238 structures: Query<(&TilePos, &Structure), Without<Colonist>>,
239 items: Query<&TilePos, With<Item>>,
240 mut blueprints: ResMut<Blueprints>,
241 ) {
242 let shelter_pending = blueprints.0.values().any(|k| *k != BuildKind::Pave);
243 if !tick.0.is_multiple_of(PLAN_INTERVAL_TICKS) || shelter_pending {
244 return;
245 }
246 let structures: Vec<(UVec2, StructureKind)> =
247 structures.iter().map(|(pos, s)| (pos.0, s.kind)).collect();
248 let beds: Vec<UVec2> = structures
249 .iter()
250 .filter(|(pos, kind)| *kind == StructureKind::Bed && !map.is_roofed(pos.as_ivec2()))
251 .map(|(pos, _)| *pos)
252 .collect();
253 if beds.is_empty() {
254 return;
255 }
256 let items: Vec<UVec2> = items.iter().map(|pos| pos.0).collect();
257 let ctx = ShelterContext {
258 map: &map,
259 structures: &structures,
260 items: &items,
261 };
262 let toward = structures
263 .iter()
264 .find(|(_, kind)| *kind == StructureKind::Campfire)
265 .map(|(pos, _)| *pos)
266 .unwrap_or_else(|| zones.home(beds[0]));
267 if let Some(plan) = ctx.plan(&beds, toward) {
268 for (tile, kind) in &plan {
269 if *kind != BuildKind::Roof {
270 zones.remove_tile(*tile);
271 }
272 }
273 blueprints.0.extend(plan);
274 }
275 }
276
277 fn draw_blueprints(mut gizmos: Gizmos, blueprints: Res<Blueprints>) {
278 for (tile, kind) in &blueprints.0 {
279 let color = match kind {
280 BuildKind::Structure(StructureKind::Door) => DOOR_BLUEPRINT_COLOR,
281 BuildKind::Roof => ROOF_BLUEPRINT_COLOR,
282 BuildKind::Pave => PAVE_BLUEPRINT_COLOR,
283 _ => WALL_BLUEPRINT_COLOR,
284 };
285 gizmos.rect_2d(
286 WorldMap::tile_center(*tile),
287 Vec2::splat(TILE_SIZE * 0.85),
288 color,
289 );
290 }
291 }
292
293 #[cfg(test)]
294 mod tests {
295 use super::*;
296 use crate::world::Terrain;
297
298 fn ctx<'a>(map: &'a WorldMap, structures: &'a [(UVec2, StructureKind)]) -> ShelterContext<'a> {
299 ShelterContext {
300 map,
301 structures,
302 items: &[],
303 }
304 }
305
306 fn count(plan: &HashMap<UVec2, BuildKind>, kind: BuildKind) -> usize {
307 plan.values().filter(|k| **k == kind).count()
308 }
309
310 const WALL: BuildKind = BuildKind::Structure(StructureKind::Wall);
311 const DOOR: BuildKind = BuildKind::Structure(StructureKind::Door);
312
313 #[test]
314 fn shelter_is_a_wall_ring_with_one_door_around_the_beds() {
315 let map = WorldMap::filled(UVec2::splat(20), Terrain::Grass);
316 let beds = [UVec2::new(10, 10), UVec2::new(11, 10)];
317 let plan = ctx(&map, &[]).plan(&beds, UVec2::new(10, 2)).unwrap();
318 assert_eq!(plan.len(), 6 * 5 - 4 * 3);
319 assert_eq!(count(&plan, DOOR), 1);
320 let door = plan.iter().find(|(_, k)| **k == DOOR).unwrap().0;
321 assert_eq!(door.y, 8);
322 }
323
324 // Mountains are free walls: a shelter dug against a cliff only needs walls on the open sides.
325 #[test]
326 fn rock_counts_as_wall() {
327 let mut map = WorldMap::filled(UVec2::splat(20), Terrain::Grass);
328 for y in 0..20 {
329 map.set(UVec2::new(12, y), Terrain::Stone);
330 }
331 let plan = ctx(&map, &[])
332 .plan(&[UVec2::new(10, 10)], UVec2::new(10, 2))
333 .unwrap();
334 assert!(plan.keys().all(|t| t.x != 12));
335 assert_eq!(count(&plan, WALL) + count(&plan, DOOR), 16 - 5);
336 }
337
338 #[test]
339 fn shelters_route_around_unbuildable_tiles() {
340 let mut map = WorldMap::filled(UVec2::splat(20), Terrain::Grass);
341 map.set(UVec2::new(10, 8), Terrain::ShallowWater);
342 let plan = ctx(&map, &[])
343 .plan(&[UVec2::new(10, 10)], UVec2::new(10, 2))
344 .unwrap();
345 assert!(!plan.contains_key(&UVec2::new(10, 8)));
346 assert_eq!(
347 plan.values()
348 .filter(|k| **k == BuildKind::Structure(StructureKind::Door))
349 .count(),
350 1
351 );
352 }
353
354 // Beds often end up right next to the stockpile; walls may take over empty stockpile tiles
355 // (which then stop being storage) instead of the shelter never getting planned at all.
356 #[test]
357 fn walls_may_replace_empty_stockpile_tiles_but_not_stored_items() {
358 let map = WorldMap::filled(UVec2::splat(20), Terrain::Grass);
359 let mut zones = Zones::default();
360 zones.add_stockpile(&map, IVec2::new(12, 5), IVec2::new(15, 15));
361 let items = [UVec2::new(13, 10)];
362 let ctx = ShelterContext {
363 map: &map,
364 structures: &[],
365 items: &items,
366 };
367 let plan = ctx.plan(&[UVec2::new(11, 10)], UVec2::new(5, 10)).unwrap();
368 assert!(plan.keys().any(|t| zones.is_stockpile(*t)));
369 assert!(!plan.contains_key(&UVec2::new(13, 10)));
370 }
371
372 #[test]
373 fn enclosed_rooms_get_roof_blueprints() {
374 let mut map = WorldMap::filled(UVec2::splat(10), Terrain::Grass);
375 for i in 3..=6 {
376 for t in [
377 UVec2::new(i, 3),
378 UVec2::new(i, 6),
379 UVec2::new(3, i),
380 UVec2::new(6, i),
381 ] {
382 map.set_wall(t, true);
383 }
384 }
385 map.set_wall(UVec2::new(4, 3), false);
386 let structures = [(UVec2::new(4, 3), StructureKind::Door)];
387 let plan = ctx(&map, &structures)
388 .plan(&[UVec2::new(4, 4)], UVec2::ZERO)
389 .unwrap();
390 assert_eq!(plan.len(), 4);
391 assert!(plan.values().all(|k| *k == BuildKind::Roof));
392 }
393
394 #[test]
395 fn open_areas_are_not_rooms() {
396 let map = WorldMap::filled(UVec2::splat(30), Terrain::Grass);
397 assert!(enclosed_room(&map, &HashSet::new(), UVec2::new(15, 15)).is_none());
398 }
399 }