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 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
44pub 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 (current.y + 1 < size.height)
85 .then(|| (xy(current.x, current.y + 1), 0b0001)),
86 (current.x > 0).then(|| (xy(current.x - 1, current.y), 0b0010)),
88 (current.y > 0).then(|| (xy(current.x, current.y - 1), 0b0100)),
90 (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; }
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}