banished_path/
pathfind.rs

1//! Path finding over the map's cells: the walkable regions and the A* pathfinder.
2//!
3//! - [`regions`] gives every walkable cell the number of its connected region. A request between
4//!   two regions fails at once, without a search.
5//! - [`Pathfinder`] is the A* search, with a cost for each cell type ([`mode_costs`]).
6//! - [`request`] checks a request as the original does, then searches.
7//! - [`nearest_neighbour`] finds the allowed cell next to a cell that is nearest to a target.
8//!
9//! The original solves paths on a worker thread, and a walker polls for the result. The port
10//! solves a path when it is requested; the walker still reads the result on its next update, so
11//! the timing is the same.
12//!
13//! See [Citizens](https://tanepiper.github.io/unbanished/topics/citizens) for how citizens use it.
14
15// Original: regions FUN_1400a1950 / FUN_1400a1640 (map cell +0x26); the path manager at map
16// +0x68 (FUN_1400abcc0), whose worker thread runs queued commands (FUN_1400ab900: 0 walk mask,
17// 1 per-type cost, 4 search options, 5 find path); A* FUN_14001d760 / FUN_14001d9a0; request
18// validation FUN_1400a2480; per-mover cost tables FUN_1400a3a20; nearest neighbour FUN_1400a21c0.
19// See docs/CITIZEN-AI.md.
20
21use std::cmp::Reverse;
22use std::collections::{BTreeSet, VecDeque};
23
24use banished_terrain::CellType;
25
26/// Cell types a walker may enter (0–4, 9–11).
27pub const WALKABLE: u32 = 0xe1f;
28/// Water and blocking types (5–8): requests touching them skip the region check.
29pub const WATER: u32 = 0x1e0;
30/// Longest path a search returns.
31///
32/// Original: `FUN_14001d760`.
33pub const MAX_PATH: usize = 0x4000;
34
35/// The bit of a cell type in a type mask such as [`WALKABLE`].
36pub fn bit(t: CellType) -> u32 {
37    1u32 << (t.0 & 0x1f)
38}
39
40/// Whether a walker may enter a cell of this type (the test [`regions`] labels by).
41pub fn walkable(t: CellType) -> bool {
42    bit(t) & WALKABLE != 0
43}
44
45/// Label connected walkable cells in scan order, starting at 1 (0 = none).
46///
47/// Original: `FUN_1400a1950`.
48pub fn regions(size: usize, types: &[CellType]) -> Vec<u16> {
49    let mut region = vec![0u16; types.len()];
50    let mut id: u16 = 1;
51    for i in 0..types.len() {
52        if bit(types[i]) & WALKABLE != 0 && region[i] == 0 {
53            fill(size, types, &mut region, i, id);
54            id = id.wrapping_add(1);
55        }
56    }
57    region
58}
59
60/// `FUN_1400a1640`: FIFO scanline fill. A run is widened by one cell for the rows above and
61/// below only when that cell is strictly inside the row (`row_start < left - 1`,
62/// `right + 1 < row_end`), so runs touch diagonal neighbours except at the map edge.
63fn fill(size: usize, types: &[CellType], region: &mut [u16], start: usize, id: u16) {
64    let n = size as i32;
65    let walk = |c: i32| bit(types[c as usize]) & WALKABLE != 0;
66    let mut queue = VecDeque::from([start as i32]);
67    while let Some(c) = queue.pop_front() {
68        let row = c / n;
69        let (row_start, row_end) = (n * row, (row + 1) * n - 1);
70        if region[c as usize] != 0 || !walk(c) {
71            continue;
72        }
73        let mut left = c;
74        while left - 1 >= row_start && walk(left - 1) {
75            left -= 1;
76        }
77        let mut right = c;
78        while right + 1 <= row_end && walk(right + 1) {
79            right += 1;
80        }
81        for k in left..=right {
82            region[k as usize] = id;
83        }
84        if row_start < left - 1 {
85            left -= 1;
86        }
87        if right + 1 < row_end {
88            right += 1;
89        }
90        for (ok, step) in [(row > 0, -n), (row < n - 1, n)] {
91            if !ok {
92                continue;
93            }
94            for u in left..=right {
95                let k = u + step;
96                if region[k as usize] == 0 && walk(k) {
97                    queue.push_back(k);
98                }
99            }
100        }
101    }
102}
103
104// +0x470
105/// Per-type cost tables a mover selects (MoveTo) and whether the search may step diagonally.
106///
107/// Original: `FUN_1400a3a20`.
108pub fn mode_costs(mode: u32) -> Option<(&'static [(u8, i32)], bool)> {
109    const CITIZEN: [(u8, i32); 11] = [
110        (0, 3),
111        (1, 3),
112        (2, 4),
113        (3, 8),
114        (4, 16),
115        (5, 16),
116        (6, 16),
117        (7, 16),
118        (8, 16),
119        (9, 3),
120        (10, 4),
121    ];
122    const MODE1: [(u8, i32); 11] = [
123        (0, 16),
124        (1, 16),
125        (2, 4),
126        (3, 4),
127        (4, 16),
128        (5, 16),
129        (6, 16),
130        (7, 4),
131        (8, 4),
132        (9, 4),
133        (10, 4),
134    ];
135    const UNIFORM: [(u8, i32); 11] = [
136        (0, 1),
137        (1, 1),
138        (2, 1),
139        (3, 1),
140        (4, 1),
141        (5, 1),
142        (6, 1),
143        (7, 1),
144        (8, 1),
145        (9, 1),
146        (10, 1),
147    ];
148    const MODE3: [(u8, i32); 11] = [
149        (0, 10),
150        (1, 10),
151        (2, 10),
152        (3, 10),
153        (4, 10),
154        (5, 10),
155        (6, 10),
156        (7, 5),
157        (8, 1),
158        (9, 5),
159        (10, 10),
160    ];
161    match mode {
162        0 => Some((&CITIZEN, true)),
163        1 => Some((&MODE1, true)),
164        2 => Some((&UNIFORM, false)),
165        3 => Some((&MODE3, true)),
166        _ => None,
167    }
168}
169
170#[derive(Clone, Copy, Default)]
171struct Node {
172    parent: i32,
173    /// `+0x0c` / `+0x10`: equal to the search id while open / closed.
174    open: i32,
175    closed: i32,
176    g: i32,
177    /// Open-set key while open: `(f, counter)`.
178    key: (i32, i32),
179}
180
181// The path manager is at map +0x68, its grid at +0x78.
182/// The pathfinder: the map's cells, the cost of each cell type, and the state of the A* search.
183///
184/// Original: `FUN_1400abcc0` (the path manager).
185pub struct Pathfinder {
186    size: i32,
187    /// Path grid bytes: cell type `& 0x7f`, `0x80` blocked (commands 2 and 3).
188    cells: Vec<u8>,
189    /// `+0x50`: cost per type (command 1).
190    costs: [i32; 32],
191    // +0xd0
192    /// Allowed types (command 0).
193    pub mask: u32,
194    /// `+0xd4..+0xd6` (command 4): diagonal steps, Manhattan heuristic, honour blocked bit.
195    diagonal: bool,
196    manhattan: bool,
197    check_blocked: bool,
198    search: i32,
199    counter: i32,
200    nodes: Vec<Node>,
201    open: BTreeSet<((i32, Reverse<i32>), i32)>,
202}
203
204impl Pathfinder {
205    /// Built from the map with diagonal steps on.
206    ///
207    /// Original: `FUN_1400a3d90`.
208    pub fn new(size: usize, types: &[CellType]) -> Pathfinder {
209        Pathfinder {
210            size: size as i32,
211            cells: types.iter().map(|t| t.0 & 0x7f).collect(),
212            costs: [1; 32],
213            mask: 0,
214            diagonal: true,
215            manhattan: false,
216            check_blocked: false,
217            search: 0,
218            counter: 0,
219            nodes: vec![Node::default(); types.len()],
220            open: BTreeSet::new(),
221        }
222    }
223
224    /// Command 2: a cell's type changed.
225    pub fn set_type(&mut self, cell: usize, t: CellType) {
226        self.cells[cell] = self.cells[cell] & 0x80 | t.0 & 0x7f;
227    }
228
229    /// Command 3.
230    pub fn set_blocked(&mut self, cell: usize, blocked: bool) {
231        self.cells[cell] = self.cells[cell] & 0x7f | if blocked { 0x80 } else { 0 };
232    }
233
234    /// Select a mover's cost table and diagonal option.
235    ///
236    /// Original: `FUN_1400a3a20`.
237    pub fn set_mode(&mut self, mode: u32) {
238        if let Some((costs, diagonal)) = mode_costs(mode) {
239            for &(t, c) in costs {
240                self.costs[t as usize] = c;
241            }
242            self.diagonal = diagonal;
243            self.manhattan = false;
244            self.check_blocked = false;
245        }
246    }
247
248    /// `FUN_1400ab390`: neighbour `dir` of `cell`, if inside, unblocked and allowed.
249    fn neighbour(&self, cell: i32, dir: usize) -> Option<i32> {
250        let n = self.size;
251        let (mut x, mut y) = (cell % n, cell / n);
252        match dir {
253            0 => x += 1,
254            1 => x -= 1,
255            2 => y += 1,
256            3 => y -= 1,
257            4 => (x, y) = (x + 1, y + 1),
258            5 => (x, y) = (x + 1, y - 1),
259            6 => (x, y) = (x - 1, y - 1),
260            _ => (x, y) = (x - 1, y + 1),
261        }
262        if x < 0 || x >= n || y < 0 || y >= n {
263            return None;
264        }
265        let k = n * y + x;
266        let byte = self.cells[k as usize];
267        if self.check_blocked && byte & 0x80 != 0 {
268            return None;
269        }
270        (self.mask >> (byte & 0x1f) & 1 != 0).then_some(k)
271    }
272
273    /// `FUN_1400ab500`.
274    fn heuristic(&self, a: i32, b: i32) -> i32 {
275        let n = self.size;
276        let dx = (a % n - b % n).abs();
277        let dy = (a / n - b / n).abs();
278        if self.diagonal {
279            (dy + dx) * 10 - 6 * dx.min(dy)
280        } else if self.manhattan {
281            (dy + dx) * 10
282        } else {
283            dy.max(dx) * 10
284        }
285    }
286
287    /// `FUN_14001dc80`: open (or reopen) `cell` with a new parent and cost.
288    fn push(&mut self, cell: i32, parent: i32, g: i32, f: i32) {
289        let node = self.nodes[cell as usize];
290        if node.open == self.search {
291            self.open.remove(&((node.key.0, Reverse(node.key.1)), cell));
292        }
293        let counter = self.counter;
294        self.counter += 1;
295        let node = &mut self.nodes[cell as usize];
296        node.closed = node.closed.wrapping_sub(1);
297        node.parent = parent;
298        node.open = self.search;
299        node.g = g;
300        node.key = (f, counter);
301        self.open.insert(((f, Reverse(counter)), cell));
302    }
303
304    /// `FUN_14001d9a0`: A* from `from` to `to`. The open set orders by `f`, then by the most
305    /// recent insertion (the AVL comparator at `FUN_14001ddb0`).
306    fn solve(&mut self, from: i32, to: i32) -> bool {
307        self.open.clear();
308        self.counter = 0;
309        let h = self.heuristic(from, to);
310        self.push(from, -1, 0, h);
311        let n = self.size;
312        while let Some(&first) = self.open.first() {
313            let cur = first.1;
314            if cur == to {
315                return true;
316            }
317            self.open.remove(&first);
318            let search = self.search;
319            let node = &mut self.nodes[cur as usize];
320            node.open = node.open.wrapping_sub(1);
321            node.closed = search;
322            let g_cur = node.g;
323            for dir in 0..if self.diagonal { 8 } else { 4 } {
324                let Some(nb) = self.neighbour(cur, dir) else {
325                    continue;
326                };
327                let straight = (cur % n - nb % n).abs() + (cur / n - nb / n).abs() == 1;
328                let cost = self.costs[(self.cells[nb as usize] & 0x7f) as usize & 31]
329                    * if straight { 10 } else { 14 };
330                let g = g_cur + cost;
331                let node = &mut self.nodes[nb as usize];
332                if node.closed == search {
333                    if node.g <= g {
334                        continue;
335                    }
336                    node.closed = node.closed.wrapping_sub(1);
337                }
338                if node.open != search || g < node.g {
339                    let f = self.heuristic(nb, to) + g;
340                    self.push(nb, cur, g, f);
341                }
342            }
343        }
344        false
345    }
346
347    /// The cells of a road from one cell to another: every cell type costs 1, there are no
348    /// diagonal steps, and blocked cells and cells outside `mask` are avoided. `blocked` marks the
349    /// cells that have an occupant.
350    ///
351    /// Original: `FUN_1400a22d0`; its search options `FUN_1400abd80(0, manhattan, 1)`.
352    pub fn find_road(
353        &mut self,
354        from: i32,
355        to: i32,
356        mask: u32,
357        manhattan: bool,
358        blocked: &[bool],
359    ) -> Option<Vec<i32>> {
360        let saved = (
361            self.costs,
362            self.diagonal,
363            self.manhattan,
364            self.check_blocked,
365            self.mask,
366        );
367        self.costs = [1; 32];
368        self.diagonal = false;
369        self.manhattan = manhattan;
370        self.check_blocked = true;
371        self.mask = mask;
372        let old: Vec<u8> = self.cells.clone();
373        for (c, &b) in self.cells.iter_mut().zip(blocked) {
374            if b {
375                *c |= 0x80;
376            }
377        }
378        let path = self.find(from, to);
379        self.cells = old;
380        (
381            self.costs,
382            self.diagonal,
383            self.manhattan,
384            self.check_blocked,
385            self.mask,
386        ) = saved;
387        path
388    }
389
390    /// Run `search` and put the costs, diagonal, heuristic, blocked check and mask back.
391    pub fn keeping_state<T>(&mut self, search: impl FnOnce(&mut Self) -> T) -> T {
392        let saved = (
393            self.costs,
394            self.diagonal,
395            self.manhattan,
396            self.check_blocked,
397            self.mask,
398        );
399        let out = search(self);
400        (
401            self.costs,
402            self.diagonal,
403            self.manhattan,
404            self.check_blocked,
405            self.mask,
406        ) = saved;
407        out
408    }
409
410    /// The cells from `from` to `to` inclusive, or `None`.
411    ///
412    /// Original: `FUN_14001d760`.
413    pub fn find(&mut self, from: i32, to: i32) -> Option<Vec<i32>> {
414        self.search = self.search.wrapping_add(1);
415        if !self.solve(from, to) {
416            return None;
417        }
418        let mut path = Vec::new();
419        let mut c = to;
420        while c != -1 {
421            path.push(c);
422            c = self.nodes[c as usize].parent;
423        }
424        path.reverse();
425        path.truncate(MAX_PATH);
426        Some(path)
427    }
428}
429
430/// Validate a request (both end types join the mask; without water types both ends must share a
431/// non-zero region), set the mask and search.
432///
433/// Original: `FUN_1400a2480`.
434pub fn request(
435    finder: &mut Pathfinder,
436    types: &[CellType],
437    region: &[u16],
438    flags: u32,
439    from: i32,
440    to: i32,
441) -> Option<Vec<i32>> {
442    let (a, b) = (bit(types[from as usize]), bit(types[to as usize]));
443    let mut flags = flags | a | b;
444    if flags & WATER == 0 {
445        let (ra, rb) = (region[from as usize], region[to as usize]);
446        if ra == 0 || rb == 0 || ra != rb {
447            return None;
448        }
449    }
450    if flags & 0x180 != 0 {
451        flags |= 0x180;
452    }
453    finder.mask = flags;
454    finder.find(from, to)
455}
456
457/// Of the 8 cells around `cell` whose type is in `mask`, the one nearest (squared cell distance) to
458/// `toward`; the first found wins ties (x outer, y inner).
459///
460/// Original: `FUN_1400a21c0`.
461pub fn nearest_neighbour(
462    size: usize,
463    types: &[CellType],
464    cell: i32,
465    toward: i32,
466    mask: u32,
467) -> Option<i32> {
468    let n = size as i32;
469    let (cx, cy) = (cell % n, cell / n);
470    let mut best: Option<(i32, i32)> = None;
471    for dx in -1..=1 {
472        for dy in -1..=1 {
473            let (x, y) = (cx + dx, cy + dy);
474            if (dx == 0 && dy == 0) || x < 0 || y < 0 || x >= n || y >= n {
475                continue;
476            }
477            let k = n * y + x;
478            if mask & bit(types[k as usize]) == 0 {
479                continue;
480            }
481            let (ex, ey) = (k / n - toward / n, k % n - toward % n);
482            let d = ex * ex + ey * ey;
483            if best.is_none_or(|(_, bd)| d < bd) {
484                best = Some((k, d));
485            }
486        }
487    }
488    best.map(|(k, _)| k)
489}
490
491#[cfg(test)]
492mod tests {
493    use super::*;
494
495    fn grid(rows: &[&str]) -> (usize, Vec<CellType>) {
496        // Rows are given top (high y) first; '.' ground, '#' water, '=' road.
497        let n = rows.len();
498        let mut t = vec![CellType(2); n * n];
499        for (r, row) in rows.iter().enumerate() {
500            let y = n - 1 - r;
501            for (x, ch) in row.chars().enumerate() {
502                t[y * n + x] = match ch {
503                    '#' => CellType(8),
504                    '=' => CellType(1),
505                    _ => CellType(2),
506                };
507            }
508        }
509        (n, t)
510    }
511
512    #[test]
513    fn regions_split_by_water() {
514        let (n, t) = grid(&["..#..", "..#..", "..#..", "..#..", "..#.."]);
515        let r = regions(n, &t);
516        assert_eq!(r[0], 1);
517        assert_eq!(r[3], 2);
518        assert_eq!(r[2], 0);
519    }
520
521    #[test]
522    fn path_goes_around_water_and_prefers_roads() {
523        let (n, t) = grid(&[".....", ".###.", ".....", ".....", "....."]);
524        let r = regions(n, &t);
525        let mut pf = Pathfinder::new(n, &t);
526        pf.set_mode(0);
527        let from = (3 * n) as i32; // (0, 3)
528        let to = (3 * n + 4) as i32; // (4, 3), across the water row
529        let p = request(&mut pf, &t, &r, WALKABLE, from, to).unwrap();
530        assert_eq!(*p.first().unwrap(), from);
531        assert_eq!(*p.last().unwrap(), to);
532        assert!(p.iter().all(|&c| t[c as usize] != CellType(8)));
533        // Unreachable across a full water column.
534        let (n, t) = grid(&["..#..", "..#..", "..#..", "..#..", "..#.."]);
535        let r = regions(n, &t);
536        let mut pf = Pathfinder::new(n, &t);
537        pf.set_mode(0);
538        assert!(request(&mut pf, &t, &r, WALKABLE, 0, 4).is_none());
539    }
540}
banished_path/pathfind.rs

banished_path/
pathfind.rs
