axioval_engine/
walkability.rs

1//! Source-neutral walkable-region topology and service contracts.
2use crate::{LengthInterval, ServiceRegistry, ServiceRegistryError};
3use axioval_ir::{Evidence, ObjectId};
4use std::{
5    collections::{BTreeMap, BTreeSet, VecDeque},
6    sync::Arc,
7};
8use thiserror::Error;
9#[derive(Clone, Debug, Error, PartialEq)]
10pub enum WalkabilityError {
11    #[error("minimum width must be finite and positive")]
12    InvalidMinimumWidth,
13    #[error("walkability region identifier is blank")]
14    InvalidRegionId,
15    #[error("passage joins a region to itself")]
16    SelfPassage,
17    #[error("passage evidence is not exact and reviewable")]
18    InexactPassage,
19    #[error("walkability evidence is incomplete")]
20    IncompleteEvidence,
21    #[error("duplicate walkability region")]
22    DuplicateRegion,
23    #[error("passage names an unknown region")]
24    UnknownRegion,
25    #[error("duplicate walkable passage")]
26    DuplicatePassage,
27    #[error("region maps an object outside the request universe")]
28    UnexpectedMappedObject,
29    #[error("portal passage violates the request portal policy")]
30    ForbiddenPortalPassage,
31    #[error("walkability object is not mapped to a region")]
32    ObjectUnavailable,
33    #[error("backend returned another request")]
34    ResponseRequestMismatch,
35}
36#[derive(Clone, Debug, PartialEq)]
37pub struct WalkabilityRequest {
38    surfaces: Vec<ObjectId>,
39    entrances: Vec<ObjectId>,
40    obstacles: Vec<ObjectId>,
41    minimum_width: f64,
42    elevation_band: Option<LengthInterval>,
43    traverse_verified_portals: bool,
44    include_motion_envelopes: bool,
45}
46impl WalkabilityRequest {
47    pub fn try_new(
48        mut surfaces: Vec<ObjectId>,
49        mut entrances: Vec<ObjectId>,
50        mut obstacles: Vec<ObjectId>,
51        minimum_width: f64,
52        elevation_band: Option<LengthInterval>,
53        traverse_verified_portals: bool,
54        include_motion_envelopes: bool,
55    ) -> Result<Self, WalkabilityError> {
56        if !minimum_width.is_finite() || minimum_width <= 0.0 {
57            return Err(WalkabilityError::InvalidMinimumWidth);
58        }
59        surfaces.sort();
60        surfaces.dedup();
61        entrances.sort();
62        entrances.dedup();
63        obstacles.sort();
64        obstacles.dedup();
65        Ok(Self {
66            surfaces,
67            entrances,
68            obstacles,
69            minimum_width,
70            elevation_band,
71            traverse_verified_portals,
72            include_motion_envelopes,
73        })
74    }
75    pub fn surfaces(&self) -> &[ObjectId] {
76        &self.surfaces
77    }
78    pub fn entrances(&self) -> &[ObjectId] {
79        &self.entrances
80    }
81    pub fn obstacles(&self) -> &[ObjectId] {
82        &self.obstacles
83    }
84    pub fn minimum_width_metres(&self) -> f64 {
85        self.minimum_width
86    }
87    pub fn elevation_band(&self) -> Option<LengthInterval> {
88        self.elevation_band
89    }
90    pub fn traverses_verified_portals(&self) -> bool {
91        self.traverse_verified_portals
92    }
93    pub fn includes_motion_envelopes(&self) -> bool {
94        self.include_motion_envelopes
95    }
96}
97#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
98pub struct WalkabilityRegionId(String);
99impl WalkabilityRegionId {
100    pub fn new(value: impl Into<String>) -> Result<Self, WalkabilityError> {
101        let value = value.into();
102        if value.trim().is_empty() {
103            Err(WalkabilityError::InvalidRegionId)
104        } else {
105            Ok(Self(value))
106        }
107    }
108    pub fn as_str(&self) -> &str {
109        &self.0
110    }
111}
112#[derive(Clone, Debug, PartialEq)]
113pub struct WalkabilityRegion {
114    id: WalkabilityRegionId,
115    objects: Vec<ObjectId>,
116}
117impl WalkabilityRegion {
118    pub fn new(id: WalkabilityRegionId, mut objects: Vec<ObjectId>) -> Self {
119        objects.sort();
120        objects.dedup();
121        Self { id, objects }
122    }
123    pub fn id(&self) -> &WalkabilityRegionId {
124        &self.id
125    }
126    pub fn objects(&self) -> &[ObjectId] {
127        &self.objects
128    }
129}
130#[derive(Clone, Debug, PartialEq)]
131pub struct VerifiedWalkablePassage {
132    a: WalkabilityRegionId,
133    b: WalkabilityRegionId,
134    portal: Option<ObjectId>,
135    clear_width: LengthInterval,
136    evidence: Evidence,
137}
138impl VerifiedWalkablePassage {
139    pub fn try_new(
140        mut a: WalkabilityRegionId,
141        mut b: WalkabilityRegionId,
142        portal: Option<ObjectId>,
143        clear_width: LengthInterval,
144        evidence: Evidence,
145    ) -> Result<Self, WalkabilityError> {
146        if a == b {
147            return Err(WalkabilityError::SelfPassage);
148        }
149        if !evidence.exact || evidence.locator.trim().is_empty() {
150            return Err(WalkabilityError::InexactPassage);
151        }
152        if b < a {
153            std::mem::swap(&mut a, &mut b);
154        }
155        Ok(Self {
156            a,
157            b,
158            portal,
159            clear_width,
160            evidence,
161        })
162    }
163    pub fn endpoints(&self) -> (&WalkabilityRegionId, &WalkabilityRegionId) {
164        (&self.a, &self.b)
165    }
166    pub fn portal(&self) -> Option<&ObjectId> {
167        self.portal.as_ref()
168    }
169    pub fn clear_width(&self) -> LengthInterval {
170        self.clear_width
171    }
172    pub fn evidence(&self) -> &Evidence {
173        &self.evidence
174    }
175}
176#[derive(Clone, Debug, PartialEq)]
177pub struct WalkabilitySnapshot {
178    request: WalkabilityRequest,
179    regions: Vec<WalkabilityRegion>,
180    passages: Vec<VerifiedWalkablePassage>,
181    object_regions: BTreeMap<ObjectId, Vec<WalkabilityRegionId>>,
182    evidence: Evidence,
183}
184impl WalkabilitySnapshot {
185    pub fn try_new(
186        request: WalkabilityRequest,
187        mut regions: Vec<WalkabilityRegion>,
188        mut passages: Vec<VerifiedWalkablePassage>,
189        evidence: Evidence,
190    ) -> Result<Self, WalkabilityError> {
191        if !evidence.exact || evidence.locator.trim().is_empty() {
192            return Err(WalkabilityError::IncompleteEvidence);
193        }
194        regions.sort_by(|a, b| a.id.cmp(&b.id));
195        if regions.windows(2).any(|w| w[0].id == w[1].id) {
196            return Err(WalkabilityError::DuplicateRegion);
197        }
198        let ids: BTreeSet<_> = regions.iter().map(|r| r.id.clone()).collect();
199        if passages
200            .iter()
201            .any(|p| !ids.contains(&p.a) || !ids.contains(&p.b))
202        {
203            return Err(WalkabilityError::UnknownRegion);
204        }
205        let universe: BTreeSet<_> = request
206            .surfaces()
207            .iter()
208            .chain(request.entrances())
209            .chain(request.obstacles())
210            .cloned()
211            .collect();
212        if regions
213            .iter()
214            .flat_map(|region| region.objects.iter())
215            .any(|object| !universe.contains(object))
216        {
217            return Err(WalkabilityError::UnexpectedMappedObject);
218        }
219        if passages.iter().any(|passage| {
220            passage.portal.as_ref().is_some_and(|portal| {
221                !request.traverse_verified_portals
222                    || request.entrances.binary_search(portal).is_err()
223            })
224        }) {
225            return Err(WalkabilityError::ForbiddenPortalPassage);
226        }
227        passages.sort_by(|a, b| (&a.a, &a.b, &a.portal).cmp(&(&b.a, &b.b, &b.portal)));
228        if passages.windows(2).any(|window| {
229            (&window[0].a, &window[0].b, &window[0].portal)
230                == (&window[1].a, &window[1].b, &window[1].portal)
231        }) {
232            return Err(WalkabilityError::DuplicatePassage);
233        }
234        let mut object_regions: BTreeMap<ObjectId, Vec<WalkabilityRegionId>> = BTreeMap::new();
235        for region in &regions {
236            for object in &region.objects {
237                object_regions
238                    .entry(object.clone())
239                    .or_default()
240                    .push(region.id.clone());
241            }
242        }
243        for mapped in object_regions.values_mut() {
244            mapped.sort();
245            mapped.dedup();
246        }
247        Ok(Self {
248            request,
249            regions,
250            passages,
251            object_regions,
252            evidence,
253        })
254    }
255    pub fn request(&self) -> &WalkabilityRequest {
256        &self.request
257    }
258    pub fn regions(&self) -> &[WalkabilityRegion] {
259        &self.regions
260    }
261    pub fn passages(&self) -> &[VerifiedWalkablePassage] {
262        &self.passages
263    }
264    pub fn evidence(&self) -> &Evidence {
265        &self.evidence
266    }
267    pub fn route_between(
268        &self,
269        from: &ObjectId,
270        to: &ObjectId,
271    ) -> Result<WalkabilityRouteOutcome, WalkabilityError> {
272        let starts = self
273            .object_regions
274            .get(from)
275            .ok_or(WalkabilityError::ObjectUnavailable)?;
276        let goals = self
277            .object_regions
278            .get(to)
279            .ok_or(WalkabilityError::ObjectUnavailable)?;
280        if let Some(path) = self.path(starts, goals, false) {
281            return Ok(WalkabilityRouteOutcome::Reachable(path));
282        }
283        if self.path(starts, goals, true).is_some() {
284            Ok(WalkabilityRouteOutcome::Indeterminate)
285        } else {
286            Ok(WalkabilityRouteOutcome::Unreachable)
287        }
288    }
289    fn path(
290        &self,
291        starts: &[WalkabilityRegionId],
292        goals: &[WalkabilityRegionId],
293        possible: bool,
294    ) -> Option<Vec<WalkabilityRegionId>> {
295        let mut graph: BTreeMap<WalkabilityRegionId, Vec<WalkabilityRegionId>> = BTreeMap::new();
296        for edge in &self.passages {
297            let usable = if possible {
298                edge.clear_width.upper_metres() >= self.request.minimum_width
299            } else {
300                edge.clear_width.lower_metres() >= self.request.minimum_width
301            };
302            if usable {
303                graph
304                    .entry(edge.a.clone())
305                    .or_default()
306                    .push(edge.b.clone());
307                graph
308                    .entry(edge.b.clone())
309                    .or_default()
310                    .push(edge.a.clone());
311            }
312        }
313        for neighbors in graph.values_mut() {
314            neighbors.sort();
315            neighbors.dedup();
316        }
317        let goal_set: BTreeSet<_> = goals.iter().cloned().collect();
318        let mut queue = VecDeque::new();
319        let mut parent: BTreeMap<WalkabilityRegionId, Option<WalkabilityRegionId>> =
320            BTreeMap::new();
321        for start in starts {
322            if parent.insert(start.clone(), None).is_none() {
323                queue.push_back(start.clone());
324            }
325        }
326        while let Some(node) = queue.pop_front() {
327            if goal_set.contains(&node) {
328                let mut path = vec![node.clone()];
329                let mut cursor = node;
330                while let Some(Some(prev)) = parent.get(&cursor) {
331                    path.push(prev.clone());
332                    cursor = prev.clone();
333                }
334                path.reverse();
335                return Some(path);
336            }
337            for next in graph.get(&node).into_iter().flatten() {
338                if !parent.contains_key(next) {
339                    parent.insert(next.clone(), Some(node.clone()));
340                    queue.push_back(next.clone());
341                }
342            }
343        }
344        None
345    }
346}
347#[derive(Clone, Debug, PartialEq)]
348pub enum WalkabilityRouteOutcome {
349    Reachable(Vec<WalkabilityRegionId>),
350    Unreachable,
351    Indeterminate,
352}
353pub trait WalkabilityService: Send + Sync {
354    fn snapshot(
355        &self,
356        request: &WalkabilityRequest,
357    ) -> Result<WalkabilitySnapshot, WalkabilityError>;
358}
359#[derive(Clone)]
360pub struct WalkabilityServiceHandle(Arc<dyn WalkabilityService>);
361impl WalkabilityServiceHandle {
362    pub fn new(service: Arc<dyn WalkabilityService>) -> Self {
363        Self(service)
364    }
365    pub fn snapshot(
366        &self,
367        request: &WalkabilityRequest,
368    ) -> Result<WalkabilitySnapshot, WalkabilityError> {
369        let snapshot = self.0.snapshot(request)?;
370        if snapshot.request() != request {
371            return Err(WalkabilityError::ResponseRequestMismatch);
372        }
373        Ok(snapshot)
374    }
375    pub fn register(self, services: &mut ServiceRegistry) -> Result<(), ServiceRegistryError> {
376        services.register(self)
377    }
378}
axioval_engine/walkability.rs

axioval_engine/
walkability.rs
