src/paths.rs 9 K · 280 lines · raw · history

1 use bevy::prelude::*;
2
3 use crate::{
4 building::{Blueprints, BuildKind},
5 colonist::Colonist,
6 sim::{SimSystems, SimTick, TICKS_PER_HOUR},
7 structures::Structure,
8 world::{Terrain, TileChanged, TilePos, WorldMap},
9 zones::Zones,
10 };
11
12 pub struct PathsPlugin;
13
14 impl Plugin for PathsPlugin {
15 fn build(&self, app: &mut App) {
16 app.add_systems(
17 FixedUpdate,
18 (
19 plan_paving.in_set(SimSystems::Decide),
20 update_paths.in_set(SimSystems::Act),
21 ),
22 );
23 }
24 }
25
26 pub const PATH_WEAR: f32 = 8.0;
27 pub const PAVE_WEAR: f32 = 20.0;
28 pub const BUSY_WEAR: f32 = PAVE_WEAR;
29
30 pub fn busy_path(map: &WorldMap, tile: IVec2) -> bool {
31 matches!(map.get(tile), Some(Terrain::Paved | Terrain::Bridge)) || map.wear(tile) >= BUSY_WEAR
32 }
33
34 pub const BRIDGE_WEAR: f32 = PATH_WEAR;
35 pub const BRIDGE_BATCH: usize = 6;
36
37 pub fn bridging_candidates(map: &WorldMap, blueprints: &Blueprints) -> Vec<UVec2> {
38 let pending = blueprints
39 .0
40 .values()
41 .filter(|k| **k == BuildKind::Bridge)
42 .count();
43 let reachable_from_land = |p: UVec2| {
44 [IVec2::X, IVec2::NEG_X, IVec2::Y, IVec2::NEG_Y]
45 .iter()
46 .any(|d| map.move_cost(p.as_ivec2() + *d).is_some())
47 };
48 let mut busiest: Vec<UVec2> = map
49 .worn_tiles()
50 .into_iter()
51 .filter(|&p| {
52 map.get(p.as_ivec2()).is_some_and(|t| t.is_water())
53 && map.wear(p.as_ivec2()) >= BRIDGE_WEAR
54 && blueprints.get(p).is_none()
55 && reachable_from_land(p)
56 })
57 .collect();
58 busiest.sort_by(|a, b| {
59 map.wear(b.as_ivec2())
60 .total_cmp(&map.wear(a.as_ivec2()))
61 .then((a.y, a.x).cmp(&(b.y, b.x)))
62 });
63 busiest.truncate(BRIDGE_BATCH.saturating_sub(pending));
64 busiest
65 }
66 pub const REGROW_WEAR: f32 = 1.0;
67 pub const WEAR_KEPT_PER_HOUR: f32 = 0.98;
68 pub const PAVE_BATCH: usize = 8;
69 const UPDATE_INTERVAL_TICKS: u64 = TICKS_PER_HOUR;
70
71 pub fn wears_into_path(terrain: Terrain) -> bool {
72 matches!(terrain, Terrain::Grass | Terrain::Soil | Terrain::Sand)
73 }
74
75 pub fn evolve(map: &mut WorldMap, zones: &Zones, mut on_change: impl FnMut(UVec2)) {
76 for pos in map.worn_tiles() {
77 let p = pos.as_ivec2();
78 let wear = map.wear(p) * WEAR_KEPT_PER_HOUR;
79 map.set_wear(pos, wear);
80 let Some(terrain) = map.get(p) else {
81 continue;
82 };
83 let becomes = if wears_into_path(terrain)
84 && wear >= PATH_WEAR
85 && map.plant(p).is_none()
86 && !zones.is_farm(pos)
87 {
88 Terrain::Path
89 } else if terrain == Terrain::Path && wear < REGROW_WEAR {
90 Terrain::Grass
91 } else {
92 continue;
93 };
94 map.set(pos, becomes);
95 on_change(pos);
96 }
97 }
98
99 fn update_paths(
100 tick: Res<SimTick>,
101 zones: Res<Zones>,
102 mut map: ResMut<WorldMap>,
103 mut changed: MessageWriter<TileChanged>,
104 ) {
105 if !tick.0.is_multiple_of(UPDATE_INTERVAL_TICKS) {
106 return;
107 }
108 evolve(&mut map, &zones, |pos| {
109 changed.write(TileChanged(pos));
110 });
111 }
112
113 pub fn paving_candidates(
114 map: &WorldMap,
115 blueprints: &Blueprints,
116 occupied: &[UVec2],
117 ) -> Vec<UVec2> {
118 let pending = blueprints
119 .0
120 .values()
121 .filter(|k| **k == BuildKind::Pave)
122 .count();
123 let mut busiest: Vec<UVec2> = map
124 .worn_tiles()
125 .into_iter()
126 .filter(|&p| {
127 map.get(p.as_ivec2()) == Some(Terrain::Path)
128 && map.wear(p.as_ivec2()) >= PAVE_WEAR
129 && blueprints.get(p).is_none()
130 && !occupied.contains(&p)
131 })
132 .collect();
133 busiest.sort_by(|a, b| {
134 map.wear(b.as_ivec2())
135 .total_cmp(&map.wear(a.as_ivec2()))
136 .then((a.y, a.x).cmp(&(b.y, b.x)))
137 });
138 busiest.truncate(PAVE_BATCH.saturating_sub(pending));
139 busiest
140 }
141
142 fn plan_paving(
143 tick: Res<SimTick>,
144 map: Res<WorldMap>,
145 structures: Query<&TilePos, (With<Structure>, Without<Colonist>)>,
146 mut blueprints: ResMut<Blueprints>,
147 ) {
148 if !tick.0.is_multiple_of(UPDATE_INTERVAL_TICKS) {
149 return;
150 }
151 let occupied: Vec<UVec2> = structures.iter().map(|p| p.0).collect();
152 for tile in paving_candidates(&map, &blueprints, &occupied) {
153 blueprints.0.insert(tile, BuildKind::Pave);
154 }
155 for tile in bridging_candidates(&map, &blueprints) {
156 blueprints.0.insert(tile, BuildKind::Bridge);
157 }
158 }
159
160 #[cfg(test)]
161 mod tests {
162 use super::*;
163
164 fn worn(terrain: Terrain, wear: f32) -> WorldMap {
165 let mut map = WorldMap::filled(UVec2::splat(3), terrain);
166 map.set_wear(UVec2::ONE, wear);
167 map
168 }
169
170 #[test]
171 fn busy_ground_wears_into_a_path() {
172 let mut map = worn(Terrain::Grass, PATH_WEAR * 2.0);
173 let mut changes = 0;
174 evolve(&mut map, &Zones::default(), |_| changes += 1);
175 assert_eq!(map.get(IVec2::ONE), Some(Terrain::Path));
176 assert_eq!(map.get(IVec2::ZERO), Some(Terrain::Grass));
177 assert_eq!(changes, 1);
178 }
179
180 #[test]
181 fn farms_plants_and_rock_floors_keep_their_ground() {
182 let mut farm_map = worn(Terrain::Soil, PATH_WEAR * 2.0);
183 let mut zones = Zones::default();
184 zones.add_farm_tiles(&farm_map, [UVec2::ONE]);
185 evolve(&mut farm_map, &zones, |_| {});
186 assert_eq!(farm_map.get(IVec2::ONE), Some(Terrain::Soil));
187
188 let mut bush_map = worn(Terrain::Grass, PATH_WEAR * 2.0);
189 bush_map.set_plant(UVec2::ONE, Some(crate::world::Plant::BerryBush));
190 evolve(&mut bush_map, &Zones::default(), |_| {});
191 assert_eq!(bush_map.get(IVec2::ONE), Some(Terrain::Grass));
192
193 let mut gravel = worn(Terrain::Gravel, PATH_WEAR * 2.0);
194 evolve(&mut gravel, &Zones::default(), |_| {});
195 assert_eq!(gravel.get(IVec2::ONE), Some(Terrain::Gravel));
196 }
197
198 #[test]
199 fn unused_paths_grow_back() {
200 let mut map = worn(Terrain::Path, 0.5);
201 evolve(&mut map, &Zones::default(), |_| {});
202 assert_eq!(map.get(IVec2::ONE), Some(Terrain::Grass));
203 }
204
205 // Only worn tiles are visited each hour (a full-map pass every game hour dominated frame time
206 // at high speeds), so faded wear must drop out of the worn set and stray paths must still
207 // regrow before that happens.
208 #[test]
209 fn faded_paths_regrow_and_leave_the_worn_set() {
210 let mut map = worn(Terrain::Path, PATH_WEAR);
211 for _ in 0..500 {
212 evolve(&mut map, &Zones::default(), |_| {});
213 }
214 assert_eq!(map.get(IVec2::ONE), Some(Terrain::Grass));
215 assert!(map.worn_tiles().is_empty());
216 }
217
218 #[test]
219 fn wear_fades_over_time() {
220 let mut map = worn(Terrain::Grass, 10.0);
221 evolve(&mut map, &Zones::default(), |_| {});
222 assert!(map.wear(IVec2::ONE) < 10.0);
223 }
224
225 #[test]
226 fn the_busiest_paths_are_paved_first_in_batches() {
227 let mut map = WorldMap::filled(UVec2::new(20, 1), Terrain::Path);
228 for x in 0..20 {
229 map.set_wear(UVec2::new(x, 0), PAVE_WEAR + x as f32);
230 }
231 let mut blueprints = Blueprints::default();
232 blueprints.0.insert(UVec2::new(19, 0), BuildKind::Pave);
233 let picked = paving_candidates(&map, &blueprints, &[UVec2::new(18, 0)]);
234 assert_eq!(picked.len(), PAVE_BATCH - 1);
235 assert_eq!(picked[0], UVec2::new(17, 0));
236 assert!(!picked.contains(&UVec2::new(18, 0)));
237 }
238
239 fn lake_map() -> WorldMap {
240 let mut map = WorldMap::filled(UVec2::new(40, 30), Terrain::Grass);
241 for y in 0..25 {
242 for x in 18..22 {
243 map.set(UVec2::new(x, y), Terrain::DeepWater);
244 }
245 }
246 map
247 }
248
249 // A lake forces a long walk around; colonists notice the much shorter route a bridge would
250 // give and put demand on its water tiles, then bridge them from the shore outwards.
251 #[test]
252 fn detours_around_water_lead_to_bridges() {
253 let mut map = lake_map();
254 let (from, to) = (UVec2::new(10, 5), UVec2::new(30, 5));
255 let route = crate::pathfinding::find_path(&map, from, to).unwrap();
256 let bridged = crate::pathfinding::find_bridged_path(&map, from, to, 4000).unwrap();
257 assert!(bridged.len() * 2 < route.len());
258 for _ in 0..BRIDGE_WEAR as usize {
259 crate::jobs::note_detour(&mut map, from, to, Some(&route));
260 }
261 let blueprints = Blueprints::default();
262 let plan = bridging_candidates(&map, &blueprints);
263 assert!(!plan.is_empty());
264 assert!(plan.iter().all(|t| t.x == 18 || t.x == 21), "{plan:?}");
265 assert!(plan.iter().all(|t| (3..=7).contains(&t.y)), "{plan:?}");
266 }
267
268 #[test]
269 fn short_or_straight_walks_put_no_demand_on_water() {
270 let mut map = lake_map();
271 let route = crate::pathfinding::find_path(&map, UVec2::new(10, 28), UVec2::new(30, 28));
272 crate::jobs::note_detour(
273 &mut map,
274 UVec2::new(10, 28),
275 UVec2::new(30, 28),
276 route.as_deref(),
277 );
278 assert!(map.worn_tiles().is_empty());
279 }
280 }