src/building.rs 13.6 K · 409 lines · raw · history

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