wde_terrain_navigation/navgrid/
graph.rs

1//! Colony network: which placed buildings are linked to which, and the bases they form.
2//!
3//! Two buildings are linked when anchors of the same kind meet (tunnels through `AnchorIn`,
4//! paths through `AnchorOut`). A group of linked buildings with exactly one control room is a
5//! base; a group with several control rooms is a conflicting base. Buildings in a group without
6//! control room, or in a conflicting base, are not working.
7
8use std::collections::{HashMap, HashSet, VecDeque};
9
10use bevy::prelude::*;
11use wde_terrain_grid::{core::grid::TILE_SIZE, prelude::*};
12
13/// Placement role of the building that defines a base.
14pub const CONTROL_ROOM_ROLE: &str = "control_room";
15
16/// Link from an anchor of a building to the anchor of a neighbor.
17#[derive(Clone, Debug)]
18pub struct NavNeighbor {
19    pub entity: Entity,
20    pub kind: LinkKind,
21    /// Anchor of this building.
22    pub anchor: String,
23    /// Anchor of the neighbor.
24    pub neighbor_anchor: String,
25    /// World XZ position of the link.
26    pub position: Vec2
27}
28
29/// A placed building in the colony network.
30#[derive(Clone, Debug)]
31pub struct NavBuilding {
32    pub label: String,
33    /// World XZ center.
34    pub center: Vec2,
35    /// World XZ rectangle covered by the footprint (min, max).
36    pub rect: (Vec2, Vec2),
37    pub is_control_room: bool,
38    /// Tunnel or path piece.
39    pub is_network: bool,
40    /// Number of tunnel (`AnchorIn`) anchors the building can be linked through.
41    pub tunnel_anchors: usize,
42    /// Number of path (`AnchorOut`) anchors the building can be linked through.
43    pub path_anchors: usize,
44    pub neighbors: Vec<NavNeighbor>,
45    /// Index in [`NavGrid::bases`], if linked to a control room.
46    pub base: Option<usize>
47}
48
49/// Linked buildings sharing at least one control room.
50#[derive(Clone, Debug, Default)]
51pub struct NavBase {
52    /// Exactly one for a working base.
53    pub control_rooms: Vec<Entity>,
54    /// Every building of the base, control rooms included.
55    pub buildings: Vec<Entity>
56}
57impl NavBase {
58    /// Whether the base has a single control room, i.e. its buildings work.
59    pub fn is_valid(&self) -> bool {
60        self.control_rooms.len() == 1
61    }
62}
63
64/// Colony network of all placed buildings, rebuilt when a building is placed or removed.
65#[derive(Resource, Default, Debug)]
66pub struct NavGrid {
67    pub buildings: HashMap<Entity, NavBuilding>,
68    pub bases: Vec<NavBase>,
69    /// Groups of linked buildings without any control room: they do not work.
70    pub unconnected: Vec<Vec<Entity>>
71}
72impl NavGrid {
73    /// Whether the building belongs to a base with a single control room.
74    pub fn is_working(&self, entity: Entity) -> bool {
75        self.buildings
76            .get(&entity)
77            .and_then(|b| b.base)
78            .is_some_and(|base| self.bases[base].is_valid())
79    }
80
81    /// Every building not linked to any control room.
82    pub fn unconnected_buildings(&self) -> impl Iterator<Item = Entity> + '_ {
83        self.unconnected.iter().flatten().copied()
84    }
85
86    /// Human readable description of every problem preventing buildings from working.
87    pub fn problems(&self) -> Vec<String> {
88        let mut problems = Vec::new();
89        for (index, base) in self.bases.iter().enumerate() {
90            if base.is_valid() {
91                continue;
92            }
93            let rooms: Vec<String> = base
94                .control_rooms
95                .iter()
96                .map(|e| fmt_pos(self.buildings[e].center))
97                .collect();
98            problems.push(format!(
99                "Base #{} has {} control rooms (at {}). Only one is allowed per base, so its {} \
100                 buildings do not work: disconnect or remove the extra control rooms.",
101                index + 1,
102                base.control_rooms.len(),
103                rooms.join(", "),
104                base.buildings.len()
105            ));
106        }
107        for group in &self.unconnected {
108            let first = &self.buildings[&group[0]];
109            if group.len() == 1 && first.tunnel_anchors + first.path_anchors == 0 {
110                problems.push(format!(
111                    "{} at {} has no connection point, so it can never join a base.",
112                    first.label,
113                    fmt_pos(first.center)
114                ));
115                continue;
116            }
117            let buildings: Vec<&NavBuilding> = group.iter().map(|e| &self.buildings[e]).collect();
118            let center = buildings.iter().map(|b| b.center).sum::<Vec2>() / buildings.len() as f32;
119            let them = if group.len() == 1 { "it" } else { "them" };
120            let hint = match buildings.iter().any(|b| b.tunnel_anchors > 0) {
121                true => format!("Link {them} with tunnels to a control room."),
122                false => format!("Link {them} with paths to an airlock leading to a control room.")
123            };
124            problems.push(format!(
125                "{} not linked to any control room around {}, not working: {}. {}",
126                match group.len() {
127                    1 => "1 building is".to_string(),
128                    n => format!("{n} buildings are")
129                },
130                fmt_pos(center),
131                summarize(&buildings),
132                hint
133            ));
134
135            // Common mistake: a path or tunnel passing along a building without ending on it
136            for entity in group {
137                let building = &self.buildings[entity];
138                if building.is_network {
139                    continue;
140                }
141                let alongside = self.buildings.iter().find(|(other, b)| {
142                    b.is_network
143                        && touches(building.rect, b.rect)
144                        && !building.neighbors.iter().any(|n| n.entity == **other)
145                });
146                if let Some((_, piece)) = alongside {
147                    problems.push(format!(
148                        "A {} runs alongside {} at {} without ending on it: lines only connect \
149                         where they end against a building side.",
150                        piece.label.to_lowercase(),
151                        building.label,
152                        fmt_pos(building.center)
153                    ));
154                }
155            }
156        }
157        problems
158    }
159
160    fn build(placed: &[(Entity, &GridEntity)]) -> Self {
161        let mut buildings = HashMap::new();
162        for (i, (entity, grid_entity)) in placed.iter().enumerate() {
163            let entry = grid_entity.entry();
164            let others = placed
165                .iter()
166                .enumerate()
167                .filter(|(j, _)| *j != i)
168                .map(|(_, (_, g))| *g);
169            let neighbors = anchor_links(grid_entity, others)
170                .into_iter()
171                .map(|link| {
172                    // `link.other` indexes the others, i.e. skips this building
173                    let other = if link.other < i {
174                        link.other
175                    } else {
176                        link.other + 1
177                    };
178                    NavNeighbor {
179                        entity: placed[other].0,
180                        kind: link.kind,
181                        anchor: link.anchor,
182                        neighbor_anchor: link.other_anchor,
183                        position: link.position
184                    }
185                })
186                .collect();
187            buildings.insert(
188                *entity,
189                NavBuilding {
190                    label: entry.label.clone(),
191                    center: grid_entity.center(),
192                    rect: footprint_rect(grid_entity),
193                    is_control_room: entry.role.as_deref() == Some(CONTROL_ROOM_ROLE),
194                    is_network: entry.network.is_some(),
195                    tunnel_anchors: entry.anchors_in.len(),
196                    path_anchors: entry.anchors_out.len(),
197                    neighbors,
198                    base: None
199                }
200            );
201        }
202
203        // Group linked buildings, in placement order for stable base numbers
204        let mut grid = NavGrid {
205            buildings,
206            ..Default::default()
207        };
208        let mut visited = HashSet::new();
209        for (start, _) in placed {
210            if !visited.insert(*start) {
211                continue;
212            }
213            let mut group = Vec::new();
214            let mut queue = VecDeque::from([*start]);
215            while let Some(entity) = queue.pop_front() {
216                group.push(entity);
217                for neighbor in &grid.buildings[&entity].neighbors {
218                    if visited.insert(neighbor.entity) {
219                        queue.push_back(neighbor.entity);
220                    }
221                }
222            }
223            let control_rooms: Vec<Entity> = group
224                .iter()
225                .copied()
226                .filter(|e| grid.buildings[e].is_control_room)
227                .collect();
228            if control_rooms.is_empty() {
229                grid.unconnected.push(group);
230                continue;
231            }
232            let base = grid.bases.len();
233            for entity in &group {
234                grid.buildings.get_mut(entity).unwrap().base = Some(base);
235            }
236            grid.bases.push(NavBase {
237                control_rooms,
238                buildings: group
239            });
240        }
241        grid
242    }
243}
244
245/// World XZ rectangle covered by a placed building.
246fn footprint_rect(grid_entity: &GridEntity) -> (Vec2, Vec2) {
247    // `bbox` holds the centers of two opposite footprint tiles
248    let (a, b) = grid_entity.bbox();
249    let half = Vec2::splat(TILE_SIZE / 2.0);
250    (a.min(b) - half, a.max(b) + half)
251}
252
253/// Whether two rectangles share part of an edge (touching, not overlapping).
254fn touches(a: (Vec2, Vec2), b: (Vec2, Vec2)) -> bool {
255    let overlap = a.1.min(b.1) - a.0.max(b.0);
256    let eps = 0.05;
257    (overlap.x.abs() < eps && overlap.y > eps) || (overlap.y.abs() < eps && overlap.x > eps)
258}
259
260/// Formats a world XZ position.
261pub fn fmt_pos(pos: Vec2) -> String {
262    format!("({:.0}, {:.0})", pos.x, pos.y)
263}
264
265/// "2 × Tunnel Straight, Dome Small" style summary of building labels.
266fn summarize(buildings: &[&NavBuilding]) -> String {
267    let mut counts: Vec<(&str, usize)> = Vec::new();
268    for b in buildings {
269        match counts.iter_mut().find(|(label, _)| *label == b.label) {
270            Some((_, n)) => *n += 1,
271            None => counts.push((&b.label, 1))
272        }
273    }
274    counts
275        .iter()
276        .map(|(label, n)| match n {
277            1 => label.to_string(),
278            n => format!("{n} × {label}")
279        })
280        .collect::<Vec<_>>()
281        .join(", ")
282}
283
284/// Rebuilds the [`NavGrid`] when the connections of a building change (placed, removed or a
285/// neighbor changed).
286pub(crate) fn rebuild_nav_grid(
287    changed: Query<(), Changed<BuildingConnections>>,
288    mut removed: RemovedComponents<BuildingConnections>,
289    placed: Query<(Entity, &GridEntity), With<BuildingConnections>>,
290    mut nav_grid: ResMut<NavGrid>
291) {
292    if changed.is_empty() && removed.read().count() == 0 {
293        return;
294    }
295    let mut placed: Vec<(Entity, &GridEntity)> = placed.iter().collect();
296    placed.sort_by_key(|(e, _)| *e);
297    *nav_grid = NavGrid::build(&placed);
298}
wde_terrain_navigation/navgrid/graph.rs

wde_terrain_navigation/navgrid/
graph.rs
