team04_server/board/
routing.rs

1use super::{Board, BoardSize, Coord, Directions, TileType, xy};
2
3use crate::config::BoardConfig;
4use crate::log;
5
6use std::sync::Arc;
7
8impl Board {
9    /// Get the directions for the shortest path from `source` to `target`.
10    /// Returns None if any of the coordinates are out of bounds or on a rock tile, if source and
11    /// target overlap. May wait for route calculation to finish.
12    pub async fn get_dirs(&self, source: Coord, target: Coord) -> Option<Directions> {
13        if source == target {
14            return None;
15        }
16
17        let source_tile = if let Some(t) = self.get(source) {
18            t
19        } else {
20            return None;
21        };
22        let target_tile = if let Some(t) = self.get(target) {
23            t
24        } else {
25            return None;
26        };
27
28        if source_tile == TileType::Rock || target_tile == TileType::Rock {
29            return None;
30        }
31
32        if let Some(r) = &*self.routing.borrow() {
33            Some(r[target.x + self.width * target.y][source.x + self.width * source.y])
34        } else {
35            self.routing_note.notified().await;
36            Some(
37                self.routing.borrow().as_ref().unwrap()[target.x + self.width * target.y]
38                    [source.x + self.width * source.y],
39            )
40        }
41    }
42}
43
44/// Precalculates all possible shortest paths. Needs to be called sometime before any game is
45/// processed.
46pub fn calculate_routing(bc: Arc<BoardConfig>) {
47    tokio::task::spawn_blocking(move || {
48        let time_at_start = tokio::time::Instant::now();
49
50        let routes =
51            calculate_routing_internal(bc.board.get_size(), |pos| match bc.board.get(pos) {
52                None => true,
53                Some(TileType::Rock) => true,
54                Some(_) => false,
55            });
56
57        log::debug!("Finished calculating routes, {:?} elapsed", time_at_start.elapsed(); &log::pfx());
58
59        if let Err(e) = bc.board.routing_sender.send(Some(routes)) {
60            log::error!("Failed to send routing: {}", e; &log::pfx());
61        }
62        bc.board.routing_note.notify_one();
63    });
64}
65
66fn calculate_routing_internal(
67    size: BoardSize,
68    blocked: impl Fn(Coord) -> bool,
69) -> Vec<Vec<Directions>> {
70    let mut dirs = Vec::with_capacity(size.width * size.height);
71    for y in 0..size.height {
72        for x in 0..size.width {
73            let start = Coord { x, y };
74            dirs.push({
75                let mut dirs = vec![0; size.width * size.height];
76                let mut dists = vec![u16::MAX; size.width * size.height];
77                dists[start.y * size.width + start.x] = 0;
78                let mut min = std::collections::VecDeque::from(vec![start]);
79                loop {
80                    if let Some(current) = min.pop_front() {
81                        let dist = 1 + dists[current.y * size.width + current.x];
82                        for (neighbor, dir) in [
83                            // down neighbor goes up
84                            (current.y + 1 < size.height)
85                                .then(|| (xy(current.x, current.y + 1), 0b0001)),
86                            // left neighbor goes right
87                            (current.x > 0).then(|| (xy(current.x - 1, current.y), 0b0010)),
88                            // up neighbor goes down
89                            (current.y > 0).then(|| (xy(current.x, current.y - 1), 0b0100)),
90                            // right neighbor goes left
91                            (current.x + 1 < size.width)
92                                .then(|| (xy(current.x + 1, current.y), 0b1000)),
93                        ]
94                        .into_iter()
95                        .flatten()
96                        .filter(|c| !blocked(c.0))
97                        {
98                            let neighbor_index = neighbor.y * size.width + neighbor.x;
99                            if dists[neighbor_index] > dist {
100                                dists[neighbor_index] = dist;
101                                dirs[neighbor_index] = 0;
102                                min.push_back(neighbor);
103                            }
104                            if dists[neighbor_index] == dist {
105                                dirs[neighbor_index] |= dir;
106                            }
107                        }
108                    } else {
109                        break;
110                    }
111                }
112                dirs.into_iter()
113                    .zip(dists)
114                    .map(|(dir, dist)| Directions(dir, dist))
115                    .collect()
116            });
117        }
118    }
119    dirs
120}
121
122#[cfg(test)]
123mod test {
124    use super::*;
125    use crate::board::Direction;
126    use TileType::*;
127
128    #[tokio::test]
129    async fn routing_large_and_sparse() {
130        let mut tiles = vec![TileType::Grass; 50 * 50];
131        for y in 0..50 {
132            if y != 25 {
133                tiles[25 + y * 50] = TileType::Rock;
134            }
135        }
136        let boardcfg = Arc::new(BoardConfig {
137            board: Board::new(tiles, 50, 50).unwrap(),
138            min_players: 0,
139            max_players: 0,
140        });
141        calculate_routing(boardcfg.clone());
142        check_routing(&boardcfg.board).await;
143    }
144
145    #[tokio::test]
146    async fn routing_smol_and_tight() {
147        let boardcfg = Arc::new(BoardConfig {
148            board: Board::new_from_arrays([
149                [
150                    Grass, Grass, Grass, Grass, Grass, Grass, Grass, Grass, Grass,
151                ],
152                [Rock, Grass, Rock, Grass, Rock, Grass, Rock, Rock, Grass],
153                [Rock, Rock, Rock, Grass, Rock, Grass, Rock, Rock, Rock],
154            ])
155            .unwrap(),
156            min_players: 0,
157            max_players: 0,
158        });
159        calculate_routing(boardcfg.clone());
160        check_routing(&boardcfg.board).await;
161    }
162
163    fn randomcoord(board: &Board) -> Coord {
164        let bs = board.get_size();
165        loop {
166            let attempt = xy(
167                rand::random_range(0..bs.width),
168                rand::random_range(0..bs.height),
169            );
170            if board.get(attempt).unwrap() != TileType::Rock {
171                break attempt;
172            }
173        }
174    }
175
176    async fn check_routing(board: &Board) {
177        let bs = board.get_size();
178        'target_loop: for target in std::iter::from_fn(|| Some(randomcoord(board))).take(10) {
179            let mut pos = randomcoord(board);
180            let mut steps = 0usize;
181            let mut expected_steps = None;
182            log::debug!("New target: {:?}", target; &log::pfx());
183
184            while steps < 150 {
185                if pos == target {
186                    if let Some(e) = expected_steps {
187                        assert_eq!(e as usize, steps, "Unexpected number of steps");
188                    }
189                    continue 'target_loop; // Success :)
190                }
191
192                let dirs = board.get_dirs(pos, target).await.unwrap();
193                let dir = dirs.random();
194                if expected_steps == None {
195                    expected_steps = Some(dirs.dist());
196                }
197                log::debug!("At {:?} Going {:?} To {:?} Dist {}", pos, dir, target, dirs.dist(); &log::pfx());
198                let newpos = match dir {
199                    Direction::North => (pos.x as isize, pos.y as isize - 1),
200                    Direction::South => (pos.x as isize, pos.y as isize + 1),
201                    Direction::East => (pos.x as isize + 1, pos.y as isize),
202                    Direction::West => (pos.x as isize - 1, pos.y as isize),
203                };
204                if newpos.0 < 0
205                    || newpos.0 >= bs.width as isize
206                    || newpos.1 < 0
207                    || newpos.1 >= bs.height as isize
208                {
209                    panic!("Walked off of board");
210                }
211                pos = xy(newpos.0 as usize, newpos.1 as usize);
212                if board.get(pos).unwrap() == TileType::Rock {
213                    panic!("Walked into rock");
214                }
215                steps += 1;
216            }
217            panic!("Did not reach target in < 150 steps");
218        }
219    }
220}