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}