rpfm_extensions/startpos/cai/
pathfinder.rs

1//---------------------------------------------------------------------------//
2// Copyright (c) 2017-2026 Ismael Gutiérrez González. All rights reserved.
3//
4// This file is part of the Rusted PackFile Manager (RPFM) project,
5// which can be found here: https://github.com/Frodo45127/rpfm.
6//
7// This file is licensed under the MIT license, which can be found here:
8// https://github.com/Frodo45127/rpfm/blob/master/LICENSE.
9//---------------------------------------------------------------------------//
10
11//! The AI's high-level pathfinder graph (`CAI_HIGH_LEVEL_PATHFINDER`, from the map's `hlp_data.esf`), and the
12//! distances between regions the AI derives from it.
13//!
14//! The record is a flat list of leaves: the region count, then for each region its index and its nodes. A node is
15//! its id (area index << 9 | region index), its cell, an unknown U32, its portals and the cost of crossing the node
16//! from each portal to each other one. A portal is the segment it crosses, the cost of crossing it, the node it leads
17//! to, its slot in the node's cost table and two flags. The cost table lists, slot by slot, the cost to every other
18//! slot. The region-to-region tables after the regions are filled in by the game.
19
20use std::cmp::Reverse;
21use std::collections::{BTreeSet, BinaryHeap, HashMap};
22
23use rpfm_lib::error::{RLibError, Result};
24use rpfm_lib::files::esf::{NodeType, RecordNode};
25
26use crate::startpos::esf_nav::leaves;
27
28#[cfg(test)] #[path = "pathfinder_test.rs"] mod pathfinder_test;
29
30//---------------------------------------------------------------------------//
31//                              Types
32//---------------------------------------------------------------------------//
33
34/// The high-level pathfinder graph of a map.
35#[derive(Debug, Clone, PartialEq, Default)]
36pub struct Pathfinder {
37    nodes: Vec<PathNode>,
38}
39
40/// A node of the graph: an area of a region.
41#[derive(Debug, Clone, PartialEq, Default)]
42struct PathNode {
43
44    /// Index of the node's region in the map.
45    region: u32,
46
47    /// Portals to neighbour nodes.
48    portals: Vec<Portal>,
49
50    /// Cost of crossing the node between two portals, by portal slot (see the module docs).
51    crossing_costs: Vec<u32>,
52}
53
54/// A portal from a node to a neighbour one.
55#[derive(Debug, Clone, PartialEq, Default)]
56struct Portal {
57
58    /// Ends of the segment the portal crosses.
59    segment: [u32; 4],
60
61    /// Cost of crossing the portal.
62    cost: u32,
63
64    /// Position of the neighbour node in the graph.
65    target: usize,
66
67    /// Position in the neighbour node of the portal leading back.
68    back: usize,
69
70    /// Slot of the portal in the node's cost table.
71    slot: usize,
72}
73
74//---------------------------------------------------------------------------//
75//                              Implementations
76//---------------------------------------------------------------------------//
77
78impl Pathfinder {
79
80    /// Reads the graph of a `CAI_HIGH_LEVEL_PATHFINDER` record.
81    ///
82    /// # Errors
83    ///
84    /// Returns an error if the record doesn't have the expected leaves.
85    pub fn read(record: &RecordNode) -> Result<Self> {
86        let invalid = || RLibError::CampaignMapDataError("unexpected CAI_HIGH_LEVEL_PATHFINDER layout".to_owned());
87        let group = record.children().first().ok_or_else(invalid)?;
88        let mut values = leaves(group).map(|leaf| match leaf {
89            NodeType::U8(value) => Some(u32::from(*value)),
90            NodeType::U16(value) => Some(u32::from(*value)),
91            NodeType::U32(value) => Some(*value.value()),
92            NodeType::Bool(value) => Some(u32::from(*value.value())),
93            _ => None,
94        });
95        let mut next = || values.next().flatten().ok_or_else(invalid);
96
97        let mut ids = HashMap::new();
98        let mut node_targets = vec![];
99        let mut nodes = vec![];
100        for _ in 0..next()? {
101            let region = next()?;
102            for _ in 0..next()? {
103                ids.insert(next()?, nodes.len());
104                let _cell = (next()?, next()?);
105                let _unknown = next()?;
106
107                let mut portals = vec![];
108                let mut targets = vec![];
109                for _ in 0..next()? {
110                    let segment = [next()?, next()?, next()?, next()?];
111                    let cost = next()?;
112                    targets.push(next()?);
113                    let slot = next()? as usize;
114                    let _flags = (next()?, next()?);
115                    portals.push(Portal { segment, cost, slot, ..Default::default() });
116                }
117                let crossings = portals.len() * portals.len().saturating_sub(1);
118                let crossing_costs = (0..crossings).map(|_| next()).collect::<Result<Vec<_>>>()?;
119                node_targets.push(targets);
120                nodes.push(PathNode { region, portals, crossing_costs });
121            }
122        }
123
124        // Link the portals: each leads to a node, through the portal there that crosses the same segment back.
125        for (position, targets) in node_targets.into_iter().enumerate() {
126            for (portal, target_id) in targets.into_iter().enumerate() {
127                nodes[position].portals[portal].target = *ids.get(&target_id).ok_or_else(invalid)?;
128            }
129        }
130        for position in 0..nodes.len() {
131            for portal in 0..nodes[position].portals.len() {
132                let Portal { segment: [x1, y1, x2, y2], target, .. } = nodes[position].portals[portal];
133                let back = nodes[target].portals.iter()
134                    .position(|other| other.target == position && other.segment == [x2, y2, x1, y1])
135                    .ok_or_else(invalid)?;
136                nodes[position].portals[portal].back = back;
137            }
138        }
139        Ok(Self { nodes })
140    }
141
142    /// Returns the largest cost of a path between two regions, as the game stores it in
143    /// `CAI_INTERFACE_MAX_REGION_DISTANCE`. Regions without a path between them don't count.
144    pub fn max_region_distance(&self) -> u32 {
145        let regions = self.nodes.iter().map(|node| node.region).collect::<BTreeSet<_>>();
146        regions.iter()
147            .flat_map(|&region| {
148                let costs = self.region_costs(region);
149                costs.into_iter().filter(move |(other, _)| *other > region).map(|(_, cost)| cost)
150            })
151            .max()
152            .unwrap_or_default()
153    }
154
155    /// Returns the cost of the cheapest path from a region to every region it reaches.
156    ///
157    /// Paths leave the region through any portal of its nodes, then cross each node from the portal they entered by
158    /// to the one they leave by, paying the crossing cost of the node and of each portal.
159    fn region_costs(&self, region: u32) -> HashMap<u32, u32> {
160        let mut costs = HashMap::<(usize, usize), u32>::new();
161        let mut queue = BinaryHeap::new();
162        let push = |costs: &mut HashMap<(usize, usize), u32>, queue: &mut BinaryHeap<_>, state: (usize, usize), cost: u32| {
163            if costs.get(&state).is_none_or(|known| cost < *known) {
164                costs.insert(state, cost);
165                queue.push(Reverse((cost, state)));
166            }
167        };
168
169        for node in self.nodes.iter().filter(|node| node.region == region) {
170            for portal in &node.portals {
171                push(&mut costs, &mut queue, (portal.target, portal.back), portal.cost);
172            }
173        }
174
175        let mut regions = HashMap::new();
176        while let Some(Reverse((cost, (position, entry)))) = queue.pop() {
177            if costs.get(&(position, entry)).is_some_and(|known| cost > *known) {
178                continue;
179            }
180            let node = &self.nodes[position];
181            regions.entry(node.region).and_modify(|best: &mut u32| *best = (*best).min(cost)).or_insert(cost);
182            for (exit, portal) in node.portals.iter().enumerate().filter(|(exit, _)| *exit != entry) {
183                let total = cost.saturating_add(node.crossing_cost(entry, exit)).saturating_add(portal.cost);
184                push(&mut costs, &mut queue, (portal.target, portal.back), total);
185            }
186        }
187        regions.remove(&region);
188        regions
189    }
190}
191
192impl PathNode {
193
194    /// Returns the cost of crossing the node from a portal to another one.
195    fn crossing_cost(&self, from: usize, to: usize) -> u32 {
196        let (from, to) = (self.portals[from].slot, self.portals[to].slot);
197        let width = self.portals.len() - 1;
198        let column = if to < from { to } else { to - 1 };
199        self.crossing_costs.get(from * width + column).copied().unwrap_or(u32::MAX)
200    }
201}
rpfm_extensions/startpos/cai/pathfinder.rs

rpfm_extensions/startpos/cai/
pathfinder.rs
