team04_server/board/
caniseeu.rs

1//! An algorithm to determine if the line of sight between two
2//! coordinates on a board is blocked or not.
3//!
4//! # Usage
5//!
6//! Use [Board::is_line_of_sight_blocked](super::Board::is_line_of_sight_blocked).
7//!
8//! # Details
9//!
10//! Assumes that (0, 0) is the bottom left corner,
11//! and (x, y) is `x` units to the right and `y` units up.
12//! NOTE: In the network standard, (y, x) is (usually?) used instead of (x, y).
13
14use super::{BoardSize, Coord};
15
16pub fn is_line_of_sight_blocked(
17    from: Coord,
18    to: Coord,
19    size: BoardSize,
20    is_rock: impl Fn(Coord) -> bool,
21) -> bool {
22    if from.x <= to.x && from.y <= to.y {
23        // going right and up
24        is_line_of_sight_blocked_right_up(from, to, is_rock)
25    } else if from.x >= to.x && from.y >= to.y {
26        // going left and down, swap `to` with `from`
27        is_line_of_sight_blocked_right_up(to, from, is_rock)
28    } else if from.x <= to.x && from.y >= to.y {
29        // going right and down,
30        // mirror `y` coordinates and grid.
31        // this will put us in one of the two cases above.
32        is_line_of_sight_blocked_right_up(
33            Coord {
34                x: from.x,
35                y: size.height - 1 - from.y,
36            },
37            Coord {
38                x: to.x,
39                y: size.height - 1 - to.y,
40            },
41            |coord| {
42                is_rock(Coord {
43                    x: coord.x,
44                    y: size.height - 1 - coord.y,
45                })
46            },
47        )
48    } else if from.x >= to.x && from.y <= to.y {
49        // going left and up,
50        // mirror `x` coordinates and grid.
51        // this will put us in one of the two cases above.
52        is_line_of_sight_blocked_right_up(
53            Coord {
54                x: size.width - 1 - from.x,
55                y: from.y,
56            },
57            Coord {
58                x: size.width - 1 - to.x,
59                y: to.y,
60            },
61            |coord| {
62                is_rock(Coord {
63                    x: size.width - 1 - coord.x,
64                    y: coord.y,
65                })
66            },
67        )
68    } else {
69        unreachable!()
70    }
71}
72
73fn is_line_of_sight_blocked_right_up(
74    from: Coord,
75    to: Coord,
76    is_rock: impl Fn(Coord) -> bool,
77) -> bool {
78    assert!(from.x <= to.x);
79    assert!(from.y <= to.y);
80    let to = Coord {
81        x: to.x - from.x,
82        y: to.y - from.y,
83    };
84    if to.y <= to.x {
85        // going up at most as much as right
86        is_line_of_sight_blocked_right_slightly_up(to, |coord| {
87            is_rock(Coord {
88                x: coord.x + from.x,
89                y: coord.y + from.y,
90            })
91        })
92    } else {
93        // going up more than right, swap x and y
94        is_line_of_sight_blocked_right_slightly_up(Coord { x: to.y, y: to.x }, |coord| {
95            is_rock(Coord {
96                x: coord.y + from.x,
97                y: coord.x + from.y,
98            })
99        })
100    }
101}
102
103/// Works for line of sights from (0, 0) to (to.x, to.y), where to.y <= to.x (angles between 0 and 45°).
104/// Assumes (0, 0) and (to.x, to.y) are non-rock tiles.
105fn is_line_of_sight_blocked_right_slightly_up(to: Coord, is_rock: impl Fn(Coord) -> bool) -> bool {
106    assert!(to.y <= to.x);
107    for x in 1..=to.x {
108        // convert to half-tile units
109        let ht_x = 2 * x - 1;
110        // now, calculate y = x * to.y / to.x
111        // + to.x is required to add a half-tile offset: (v + to.x) / (2 * to.x)) = v / (2 * to.x) + 1/2
112        let y_temp = ht_x * to.y + to.x;
113        let y_div = 2 * to.x;
114        let y_rem: usize = y_temp % y_div;
115        let y = y_temp / y_div;
116        if y_rem > 0 {
117            // y is inexact, meaning the line of sight crosses
118            // the edge of (x, y), but not a corner.
119            if is_rock(Coord { x, y }) || is_rock(Coord { x: x - 1, y }) {
120                return true;
121            }
122        } else {
123            // y is exact, meaning the line of sight
124            // exactly crosses the lower corner of y.
125            // If either y or y-1 is a rock, the line of sight is blocked.
126            if (is_rock(Coord { x, y }) || (y > 0 && is_rock(Coord { x, y: y - 1 })))
127                || (is_rock(Coord { x: x - 1, y })
128                    || (y > 0 && is_rock(Coord { x: x - 1, y: y - 1 })))
129            {
130                return true;
131            }
132        }
133    }
134    // no rock found, so the line of sight is not blocked
135    false
136}