shuyi_ui/grid/
steer.rs

1//! A unit's path as the cursor steers it: the player draws a route by
2//! moving the cursor, and the path follows. A grid skin draws it
3//! ([`MapScene::path`](super::MapScene::path)).
4
5use crate::prelude::*;
6use shuyi_core::Pos;
7
8/// The path after the cursor moves to `to`. `path` runs from the unit's
9/// tile (never empty); `valid` says whether a path is legal (the game's
10/// rules: the unit's move points, who stands where), and `cheapest` gives
11/// the cheapest path to a tile, or `None` if the unit can't reach it
12/// (`shuyi_core::Reach::path_to`).
13///
14/// - `to` already on the path: the path is cut back to it.
15/// - `to` next to the path's end and the longer path is legal: `to` is
16///   appended, so the player can steer a route.
17/// - Otherwise the cheapest path to `to`, or the path unchanged if `to`
18///   can't be reached.
19pub fn steer(
20    path: &[Pos],
21    to: Pos,
22    cheapest: impl FnOnce(Pos) -> Option<Vec<Pos>>,
23    valid: impl Fn(&[Pos]) -> bool,
24) -> Vec<Pos> {
25    if let Some(i) = path.iter().position(|&p| p == to) {
26        return path[..=i].to_vec();
27    }
28    if path.last().is_some_and(|&end| Pos::manhattan(end, to) == 1) {
29        let mut longer = path.to_vec();
30        longer.push(to);
31        if valid(&longer) {
32            return longer;
33        }
34    }
35    cheapest(to).unwrap_or_else(|| path.to_vec())
36}
37
38#[cfg(test)]
39mod tests {
40    use proptest::prelude::*;
41    use shuyi_core::{Reach, reachable};
42
43    use super::*;
44
45    fn p(x: i32, y: i32) -> Pos {
46        Pos::new(x, y)
47    }
48
49    /// A 10 × 8 field where each step costs 1 but a wall at column 4,
50    /// rows 0 to 5, and the unit at (2, 3) with 5 move points.
51    fn field() -> Reach {
52        reachable(10, 8, p(2, 3), 5, |pos| {
53            (pos.x != 4 || pos.y > 5).then_some(1)
54        })
55    }
56
57    /// Whether `path` is a walk the unit can make: from its tile, a step
58    /// at a time, within reach, within its move points.
59    fn legal(reach: &Reach, path: &[Pos]) -> bool {
60        let steps = path.windows(2).all(|w| Pos::manhattan(w[0], w[1]) == 1);
61        let budget = usize::try_from(reach.budget()).unwrap_or(usize::MAX);
62        path.first() == Some(&reach.origin())
63            && steps
64            && path.iter().all(|&q| reach.contains(q))
65            && path.len() <= budget + 1
66    }
67
68    /// `path` steered to each of `cursor` in turn.
69    fn steered(reach: &Reach, cursor: &[Pos]) -> Vec<Pos> {
70        let mut path = vec![reach.origin()];
71        for &to in cursor {
72            path = steer(&path, to, |to| reach.path_to(to), |q| legal(reach, q));
73        }
74        path
75    }
76
77    #[test]
78    fn steering_appends_cuts_back_and_falls_back_to_the_cheapest_path() {
79        let reach = field();
80        let unit = p(2, 3);
81        // Down, right, up, up: a detour the cheapest path wouldn't take.
82        let walk = [p(2, 4), p(3, 4), p(3, 3), p(3, 2)];
83        assert_eq!(
84            steered(&reach, &walk),
85            [unit, p(2, 4), p(3, 4), p(3, 3), p(3, 2)]
86        );
87        // Back onto the path: cut back to that tile.
88        let mut back = walk.to_vec();
89        back.push(p(3, 4));
90        assert_eq!(steered(&reach, &back), [unit, p(2, 4), p(3, 4)]);
91        // Back onto the unit: just its tile.
92        back.push(p(2, 4));
93        back.push(unit);
94        assert_eq!(steered(&reach, &back), [unit]);
95        // Too long to go on (5 move points): the cheapest path instead.
96        let far = [p(2, 2), p(2, 1), p(1, 1), p(0, 1), p(0, 2), p(0, 3)];
97        let cheapest = reach.path_to(p(0, 3)).unwrap();
98        assert_eq!(cheapest.len(), 3);
99        assert_eq!(steered(&reach, &far), cheapest);
100        // Out of reach (behind the wall): the path stays as it was.
101        assert_eq!(steered(&reach, &[p(3, 3), p(5, 3)]), [unit, p(3, 3)]);
102        // A tile next to the path's end but not legal to add, though
103        // reachable another way: the cheapest path to it.
104        let blocked = steer(&[unit, p(3, 3)], p(3, 2), |to| reach.path_to(to), |_| false);
105        assert_eq!(blocked, reach.path_to(p(3, 2)).unwrap());
106        // Not next to the end: never appended, even when legal.
107        let jump = steer(&[unit], p(2, 5), |_| None, |_| true);
108        assert_eq!(jump, [unit]);
109    }
110
111    proptest! {
112        /// Whatever the cursor does, the path stays legal, and it ends on
113        /// the cursor whenever the cursor is on a tile the unit can reach.
114        #[test]
115        fn steered_paths_are_legal_and_follow_the_cursor(
116            moves in prop::collection::vec(0..4usize, 0..40),
117        ) {
118            let reach = field();
119            let mut cursor = reach.origin();
120            let mut path = vec![cursor];
121            for m in moves {
122                let (dx, dy) = [(1, 0), (-1, 0), (0, 1), (0, -1)][m];
123                cursor = p((cursor.x + dx).clamp(0, 9), (cursor.y + dy).clamp(0, 7));
124                path = steer(&path, cursor, |to| reach.path_to(to), |q| legal(&reach, q));
125                prop_assert!(legal(&reach, &path), "{:?}", path);
126                if reach.contains(cursor) {
127                    prop_assert_eq!(path.last(), Some(&cursor));
128                }
129            }
130        }
131    }
132}
shuyi_ui/grid/steer.rs

shuyi_ui/grid/
steer.rs
