team04_server/board/
mod.rs

1//! Representation of the board specified by the board config and used in-game,
2//! as well as associated functions and data structures.
3//! See: [Board]
4pub mod caniseeu;
5
6pub mod routing;
7
8use serde::{Deserialize, Serialize};
9use std::hash::Hash;
10
11use crate::log;
12
13/// The "Field Type" enum from the spec.
14#[derive(Deserialize, Serialize, Debug, PartialEq, Eq, Hash, Clone, Copy)]
15#[serde(rename_all = "SCREAMING_SNAKE_CASE")]
16pub enum TileType {
17    Rock,
18    Grass,
19    Force,
20    MedicCenter,
21    Lava,
22}
23
24/// A direction on the board
25#[derive(Debug, PartialEq, Eq, Clone, Copy)]
26pub enum Direction {
27    /// Up, y gets smaller
28    North,
29    /// Down, y gets bigger
30    South,
31    /// Right, x gets bigger
32    East,
33    /// Left, y gets bigger
34    West,
35}
36
37/// A Set of Directions.
38///
39/// Internally represented by a bitfield, where the bits correspond as follows:
40/// - 0: North
41/// - 1: East
42/// - 2: South
43/// - 3: West
44///
45/// Also includes the distance to the target.
46#[derive(Debug, Clone, Copy, Eq, PartialEq)]
47pub struct Directions(u8, u16);
48
49impl Directions {
50    /// Choose a random direction
51    pub fn random(&self) -> Direction {
52        let mut choices = Vec::with_capacity(4);
53        if self.0 & 0b0001 != 0 {
54            choices.push(Direction::North);
55        }
56        if self.0 & 0b0010 != 0 {
57            choices.push(Direction::East);
58        }
59        if self.0 & 0b0100 != 0 {
60            choices.push(Direction::South);
61        }
62        if self.0 & 0b1000 != 0 {
63            choices.push(Direction::West);
64        }
65        choices[rand::random_range(0..choices.len())]
66    }
67
68    /// The distance from the source to the target
69    pub fn dist(&self) -> u16 {
70        self.1
71    }
72}
73
74/// Representation of the board specified by the board config and used in-game.
75///
76/// A [Board] is a rectangular grid of [Tiles](TileType)
77/// with integer [Coordinates](Coord).
78///
79/// # Mirroring
80///
81/// Boards are mirrored on the x and the y axis (effectively mirrored on the center point).
82/// Because of this, only half of the board has to be stored. When a tile on the other half
83/// should be read, the coordinates are simply mirrored:
84///
85/// ```text
86///  A B|C D
87/// _E_F|G_H_
88///  H G|F E
89///  D C|B A
90/// ```
91///
92/// # Board Coordinates
93///
94/// The top half of the board is indexed in Left-to-Right (x)
95/// and Top-to-Bottom (y) order:
96///
97/// ```
98/// A: x=0 y=0
99/// B: x=1 y=0
100/// E: x=0 y=1
101/// ```
102///
103/// The bottom half continues this scheme:
104///
105/// ```
106/// H: x=0 y=2
107/// G: x=1 y=2
108/// D: x=0 y=3
109/// ```
110///
111/// Note: The top half is the one from which Player 1 sees the game,
112/// the bottom half is the one from which Player 2 sees the game.
113#[derive(Debug)]
114pub struct Board {
115    /// The tiles of one half of the board, in order
116    /// `(0,0)`, `(0,width-1)`, `(1,0)`, ...
117    tiles: Vec<TileType>,
118    /// Width of the entire board
119    width: usize,
120    /// Height of half the board
121    height: usize,
122
123    /// For each tile, this stores the directions to take for the shortest path for
124    /// any other tile.
125    ///
126    /// Structure: Source tile < Target tile
127    /// Full board coordinates are used.
128    routing: tokio::sync::watch::Receiver<Option<Vec<Vec<Directions>>>>,
129    routing_sender: tokio::sync::watch::Sender<Option<Vec<Vec<Directions>>>>,
130    routing_note: tokio::sync::Notify,
131}
132
133/// A coordinate on a board.
134/// Contains `x` and `y` components and can be constructed using [xy].
135#[derive(Clone, Copy, Debug, PartialEq, Eq)]
136pub struct Coord {
137    pub x: usize,
138    pub y: usize,
139}
140/// Quick way to construct a coordinate without having to use the lengthy `Coord { x: _, y: _ }` struct syntax.
141pub fn xy(x: usize, y: usize) -> Coord {
142    Coord { x, y }
143}
144
145impl Coord {
146    /// Calculates the 1-metric/taxicab distance between two points
147    pub fn cab_dist(self, other: Coord) -> usize {
148        self.x.abs_diff(other.x) + self.y.abs_diff(other.y)
149    }
150}
151/// Contains a board's width and height.
152#[derive(Clone, Copy, Debug, PartialEq, Eq)]
153pub struct BoardSize {
154    pub width: usize,
155    pub height: usize,
156}
157
158impl Board {
159    /// Creates a new `Board` from a list of tiles.
160    ///
161    /// `tiles` must contain the **top** half of the board, in row-major order,
162    /// with the halves width and height defined by the parameters of the same name.
163    ///
164    /// This means that `[A,B,C,D,E,F]` with `width=3, height=2` represents the board
165    ///
166    /// ```text
167    /// A,B,C
168    /// D,E,F
169    /// F,E,D
170    /// C,B,A
171    /// ```
172    ///
173    /// The Board will be validated, that is, it will be checked whether it
174    /// complies to the following rules:
175    /// - `tiles` must have the correct length
176    /// - There must be at least 8 grass tiles per board half
177    /// - The entire board must be strictly connected: Every non-rock tile must
178    ///   be reachable from every other non-rock tile.
179    ///
180    /// This function returns [Err] when the board does not fulfill any of the
181    /// above conditions.
182    pub fn new(tiles: Vec<TileType>, width: usize, height: usize) -> Result<Self, BoardError> {
183        if tiles.len() != width * height {
184            return Err(BoardError::InvalidLength);
185        }
186
187        let board = Self::new_unchecked(tiles, width, height);
188        board.validate()?;
189        Ok(board)
190    }
191    /// See the docs on [new](Self::new) for input format of `tiles`.
192    /// This function does not do any of the checks [new](Self::new) does,
193    /// and may result in invalid state.
194    /// It is only intended for test cases
195    /// which specifically don't care about some of the conditions [new](Self::new)
196    /// guarantees.
197    fn new_unchecked(tiles: Vec<TileType>, width: usize, height: usize) -> Self {
198        let routing_sender = tokio::sync::watch::Sender::new(None);
199        Self {
200            tiles,
201            width,
202            height,
203            routing: routing_sender.subscribe(),
204            routing_sender,
205            routing_note: tokio::sync::Notify::new(),
206        }
207    }
208    /// Removes the possibility of an [InvalidLength](BoardError::InvalidLength) error
209    /// by using arrays of known sizes.
210    /// Input is expected to be an array of rows `0` to `height-1`,
211    /// where each row contains the tiles `0` to `width-1` of that row.
212    ///
213    /// You may also want to read the docs on [new](Self::new)
214    /// for possible errors this function can return.
215    pub fn new_from_arrays<const WIDTH: usize, const HEIGHT: usize>(
216        tiles: [[TileType; WIDTH]; HEIGHT],
217    ) -> Result<Self, BoardError> {
218        Self::new(tiles.into_iter().flatten().collect(), WIDTH, HEIGHT)
219    }
220    /// See the docs on [new_from_arrays](Self::new_from_arrays) and [new_unchecked](Self::new_unchecked).
221    fn new_from_arrays_unchecked<const WIDTH: usize, const HEIGHT: usize>(
222        tiles: [[TileType; WIDTH]; HEIGHT],
223    ) -> Self {
224        Self::new_unchecked(tiles.into_iter().flatten().collect(), WIDTH, HEIGHT)
225    }
226
227    /// Returns the tile at position `pos`, or [None] if `pos` is out of bounds.
228    ///
229    /// Supports getting tiles from anywhere on the full board, meaning that
230    /// this function will return `Some(_)` if and only if \
231    /// `pos.x < self.get_size().width && pos.y < self.get_size().height`.
232    pub fn get(&self, pos: Coord) -> Option<TileType> {
233        if pos.x >= self.width || pos.y >= 2 * self.height {
234            None
235        } else if pos.y >= self.height {
236            // Enemy's half, rotate
237            // if requesting the largest `y` value, `2 * self.height - 1`,
238            // should actually read from `y=0`. If requesting less, read from `y>0`.
239            let y = 2 * self.height - 1 - pos.y;
240            // if requesting the largest `x` value, `self.width - 1`,
241            // should actually read from `x=0`. If requesting less, read from `x>0`.
242            let x = self.width - 1 - pos.x;
243            Some(self.tiles[x + y * self.width])
244        } else {
245            // top half (player 1's half), can be
246            // directly accessed with the given coordinates.
247            Some(self.tiles[pos.x + pos.y * self.width])
248        }
249    }
250
251    /// Returns the size of the full board.
252    ///
253    /// `height` will always be an even number, because the full board
254    /// is two half boards, both of which have the same height.
255    ///
256    /// You may want to see the documentation of [Board](Self#mirroring).
257    pub fn get_size(&self) -> BoardSize {
258        BoardSize {
259            width: self.width,
260            height: 2 * self.height,
261        }
262    }
263
264    /// Iterates through the rows of the top half of this board.
265    ///
266    /// Iteration order is `(0,0)` to `(0,1)` to `(0,width-1)` to `(1,0)` to `(1,1)` and so on,
267    /// stopping when half the board has been traversed (`0 <= y < self.get_size().height/2`).
268    ///
269    /// A 4x4 board would be traversed in the following order:
270    ///
271    /// ```text
272    /// 0123
273    /// 4567
274    /// ----
275    /// ----
276    /// ```
277    ///
278    /// See also: [iter_second_half_mirrored](Self::iter_second_half_mirrored) and [iter_second_half_continuing](Self::iter_second_half_continuing)
279    pub fn iter_half(&self) -> impl Iterator<Item = (Coord, TileType)> {
280        (0..self.height)
281            .flat_map(|y| (0..self.width).map(move |x| xy(x, y)))
282            .map(|coord| (coord, self.get(coord).expect("we hope xdd")))
283    }
284    /// Iterates through the rows of the **bottom** half of this board,
285    /// returning the same tiles as [iter_half](Self::iter_half) in the same order, just with different coordinates.
286    ///
287    /// Iteration order is `(height-1,width-1)` to `(height-1,0)`, ..., `(h,width-1)` to `(h,0)`.
288    /// where `h` is `self.get_size().height/2`, or the height of a half-board.
289    ///
290    /// A 4x4 board would be traversed in the following order:
291    ///
292    /// ```text
293    /// ----
294    /// ----
295    /// 7654
296    /// 3210
297    /// ```
298    ///
299    /// See also: [iter_half](Self::iter_half) and [iter_second_half_continuing](Self::iter_second_half_continuing)
300    pub fn iter_second_half_mirrored(&self) -> impl Iterator<Item = (Coord, TileType)> {
301        (self.height..2 * self.height)
302            .rev()
303            .flat_map(|y| (0..self.width).rev().map(move |x| xy(x, y)))
304            .map(|coord| (coord, self.get(coord).expect("we hope xdd")))
305    }
306    /// Iterates through the rows of the **bottom** half of this board, continuing in the same coordinate order as [iter_half](Self::iter_half).
307    ///
308    /// Iteration order is `(h,0)` to `(h,1)` to `(h,width-1)` to `(h+1,0)` to `(h+1,1)` and so on,
309    /// where `h` is `self.get_size().height/2`, or the height of a half-board.
310    ///
311    /// A 4x4 board would be traversed in the following order:
312    ///
313    /// ```text
314    /// ----
315    /// ----
316    /// 0123
317    /// 4567
318    /// ```
319    ///
320    /// See also: [iter_half](Self::iter_half) and [iter_second_half_mirrored](Self::iter_second_half_mirrored)
321    pub fn iter_second_half_continuing(&self) -> impl Iterator<Item = (Coord, TileType)> {
322        (self.height..2 * self.height)
323            .flat_map(|y| (0..self.width).map(move |x| xy(x, y)))
324            .map(|coord| (coord, self.get(coord).expect("we hope xdd")))
325    }
326
327    pub fn is_line_of_sight_blocked(&self, from: Coord, to: Coord) -> bool {
328        let BoardSize { width, height } = self.get_size();
329        if from.x >= width || from.y >= height || to.x >= width || to.y >= height {
330            log::warning!("coordinate out of bounds for is_line_of_sight_blocked"; &log::pfx());
331            return false;
332        }
333        caniseeu::is_line_of_sight_blocked(from, to, self.get_size(), |coord| {
334            self.get(coord).is_none_or(|tt| tt == TileType::Rock)
335        })
336    }
337
338    fn validate(&self) -> Result<(), BoardError> {
339        if self
340            .tiles
341            .iter()
342            .filter(|&tile| *tile == TileType::Grass)
343            .count()
344            < 8
345        {
346            return Err(BoardError::NotEnoughGrass);
347        }
348
349        // Check connectivity by doing a flood fill
350        let size = self.get_size();
351        let mut visited = vec![false; size.width * size.height];
352        let mut flood_stack = Vec::<Coord>::new();
353
354        // Mark first non-rock field as visited. visited describes a full map,
355        // while tiles describes a half map, so we need to convert to full map
356        // coordinates by adding half of the board
357        let first_field = self
358            .iter_half()
359            .find(|(_, tile)| *tile != TileType::Rock)
360            .unwrap()
361            .0;
362        flood_stack.push(first_field);
363
364        while let Some(test) = flood_stack.pop() {
365            if visited.get(test.x + test.y * size.width) == Some(&true) {
366                continue;
367            }
368
369            if self.get(test).unwrap_or(TileType::Rock) != TileType::Rock {
370                visited[test.x + test.y * size.width] = true;
371
372                flood_stack.push(xy(test.x + 1, test.y));
373                flood_stack.push(xy(test.x, test.y + 1));
374                if test.x > 0 {
375                    flood_stack.push(xy(test.x - 1, test.y));
376                }
377                if test.y > 0 {
378                    flood_stack.push(xy(test.x, test.y - 1));
379                }
380            }
381        }
382
383        if let Some(coord) = visited.iter().enumerate().find_map(|(idx, &visited)| {
384            if !visited {
385                let coord = xy(idx % size.width, idx / size.width);
386                (self.get(coord).unwrap() != TileType::Rock).then_some(coord)
387            } else {
388                None
389            }
390        }) {
391            return Err(BoardError::DisconnectedBoard(coord));
392        }
393
394        Ok(())
395    }
396}
397
398impl PartialEq for Board {
399    fn eq(&self, other: &Self) -> bool {
400        (&self.tiles, &self.width, &self.height) == (&other.tiles, &other.width, &other.height)
401    }
402}
403
404impl Serialize for Board {
405    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
406    where
407        S: serde::Serializer,
408    {
409        let mut board = Vec::new();
410        for n in 0..self.height {
411            board.push(&self.tiles[self.width * n..self.width * (n + 1)]);
412        }
413        board.serialize(serializer)
414    }
415}
416
417#[derive(Debug, PartialEq)]
418pub enum BoardError {
419    InvalidLength,
420    NotEnoughGrass,
421    DisconnectedBoard(Coord),
422}
423
424impl std::fmt::Display for BoardError {
425    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
426        match self {
427            Self::InvalidLength => write!(f, "The 'tiles' vector has invalid length"),
428            Self::NotEnoughGrass => write!(f, "There are not at least 8 grass tiles"),
429            Self::DisconnectedBoard(coord) => {
430                write!(f, "There is an unreachable tile at {coord}")
431            }
432        }
433    }
434}
435
436impl std::error::Error for BoardError {}
437
438#[cfg(test)]
439mod test {
440    use super::*;
441    use TileType::*;
442
443    #[test]
444    fn get_with_coord() {
445        let board = Board::new_from_arrays_unchecked([
446            [Grass, Rock, Force],
447            [Force, Lava, MedicCenter],
448            [Rock, Force, Grass],
449        ]);
450        // top half
451        assert_eq!(Grass, board.get(Coord { x: 0, y: 0 }).unwrap());
452        assert_eq!(Rock, board.get(Coord { x: 1, y: 0 }).unwrap());
453        assert_eq!(Force, board.get(Coord { x: 2, y: 0 }).unwrap());
454        assert_eq!(Force, board.get(Coord { x: 0, y: 1 }).unwrap());
455        assert_eq!(Lava, board.get(Coord { x: 1, y: 1 }).unwrap());
456        assert_eq!(MedicCenter, board.get(Coord { x: 2, y: 1 }).unwrap());
457        assert_eq!(Rock, board.get(Coord { x: 0, y: 2 }).unwrap());
458        assert_eq!(Force, board.get(Coord { x: 1, y: 2 }).unwrap());
459        assert_eq!(Grass, board.get(Coord { x: 2, y: 2 }).unwrap());
460        // bottom half
461        assert_eq!(Grass, board.get(Coord { x: 2, y: 5 }).unwrap());
462        assert_eq!(Rock, board.get(Coord { x: 1, y: 5 }).unwrap());
463        assert_eq!(Force, board.get(Coord { x: 0, y: 5 }).unwrap());
464        assert_eq!(Force, board.get(Coord { x: 2, y: 4 }).unwrap());
465        assert_eq!(Lava, board.get(Coord { x: 1, y: 4 }).unwrap());
466        assert_eq!(MedicCenter, board.get(Coord { x: 0, y: 4 }).unwrap());
467        assert_eq!(Rock, board.get(Coord { x: 2, y: 3 }).unwrap());
468        assert_eq!(Force, board.get(Coord { x: 1, y: 3 }).unwrap());
469        assert_eq!(Grass, board.get(Coord { x: 0, y: 3 }).unwrap());
470    }
471
472    #[test]
473    fn iters() {
474        let board =
475            Board::new_from_arrays_unchecked([[Rock, Grass, Force], [MedicCenter, Lava, Grass]]);
476        assert_eq!(
477            board.iter_half().collect::<Vec<_>>(),
478            vec![
479                (xy(0, 0), Rock),
480                (xy(1, 0), Grass),
481                (xy(2, 0), Force),
482                (xy(0, 1), MedicCenter),
483                (xy(1, 1), Lava),
484                (xy(2, 1), Grass)
485            ]
486        );
487        assert_eq!(
488            board.iter_second_half_continuing().collect::<Vec<_>>(),
489            vec![
490                (xy(0, 2), Grass),
491                (xy(1, 2), Lava),
492                (xy(2, 2), MedicCenter),
493                (xy(0, 3), Force),
494                (xy(1, 3), Grass),
495                (xy(2, 3), Rock)
496            ]
497        );
498        assert_eq!(
499            board.iter_second_half_mirrored().collect::<Vec<_>>(),
500            vec![
501                (xy(2, 3), Rock),
502                (xy(1, 3), Grass),
503                (xy(0, 3), Force),
504                (xy(2, 2), MedicCenter),
505                (xy(1, 2), Lava),
506                (xy(0, 2), Grass)
507            ]
508        );
509    }
510
511    #[test]
512    fn valid_board() {
513        Board::new_from_arrays([
514            [Grass, Grass, Rock, Grass],
515            [Rock, Grass, Lava, MedicCenter],
516            [Rock, Rock, Rock, Force],
517            [Grass, Grass, Grass, Grass],
518        ])
519        .unwrap();
520    }
521
522    #[test]
523    fn invalid_size() {
524        let test_board = vec![Grass, Grass, Grass, Grass, Grass, Grass, Grass, Grass];
525        assert_eq!(
526            Board::new(test_board.clone(), 3, 2),
527            Err(BoardError::InvalidLength)
528        );
529        assert_eq!(
530            Board::new(test_board.clone(), 4, 3),
531            Err(BoardError::InvalidLength)
532        );
533    }
534
535    #[test]
536    fn cannot_touch_grass() {
537        assert_eq!(
538            Board::new_from_arrays([
539                [Lava, Lava, Lava, Lava],
540                [Lava, MedicCenter, Grass, Rock],
541                [Lava, Grass, Grass, Lava],
542                [Lava, Lava, Lava, Lava],
543            ]),
544            Err(BoardError::NotEnoughGrass)
545        );
546    }
547
548    #[test]
549    fn disconnected_board() {
550        match Board::new_from_arrays([
551            [Force, Grass, Grass, Force],
552            [Grass, Lava, Lava, Grass],
553            [Grass, Grass, Grass, Grass],
554            [Rock, Rock, Rock, Grass],
555        ]) {
556            // We do not check the coordinates, because these are calculated with
557            // best effort only, not really meant to be stable and just a hint
558            // for debugging board configs.
559            Err(BoardError::DisconnectedBoard(_)) => {}
560            a => panic!(
561                "Expected Err(BoardError::DisconnectedBoard), but got {:?}",
562                a
563            ),
564        }
565    }
566
567    #[test]
568    fn caniknowificanseeu() {
569        let board = Board::new_from_arrays([
570            [Grass, Grass, Grass, Grass],
571            [Grass, Grass, Grass, Grass],
572            [Rock, Rock, Grass, Grass],
573            [Grass, Grass, Grass, Grass],
574            [Grass, Grass, Grass, Grass],
575        ])
576        .unwrap();
577        // line of sight not blocked
578        assert!(!board.is_line_of_sight_blocked(xy(0, 0), xy(3, 0)));
579        assert!(!board.is_line_of_sight_blocked(xy(1, 0), xy(2, 2)));
580        // line of sight blocked
581        assert!(board.is_line_of_sight_blocked(xy(1, 0), xy(2, 3)));
582        assert!(board.is_line_of_sight_blocked(xy(0, 0), xy(0, 3)));
583    }
584}
585
586impl std::fmt::Display for Coord {
587    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
588        write!(f, "yx({},{})", self.y, self.x)
589    }
590}