1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
//! Field of view by symmetric shadowcasting, after Albert Ford's write-up at
//! <https://www.albertford.com/shadowcasting/>.
//!
//! Symmetric means that if you can see a floor cell, someone standing there
//! can see you. Monsters wake when they come into view, so this keeps
//! ambushes fair: nothing notices you that you couldn't have seen first.
use super::{Map, Pos};
/// The cells visible from one spot.
pub struct Fov {
width: i32,
visible: Vec<bool>,
}
impl Fov {
pub fn contains(&self, p: Pos) -> bool {
p.x >= 0
&& p.y >= 0
&& p.x < self.width
&& self.visible.get((p.y * self.width + p.x) as usize).copied().unwrap_or(false)
}
}
/// Everything visible from `origin` within `radius` cells. Walls are visible
/// (that's how you see a room's shape); cells behind them aren't.
pub fn compute(map: &Map, origin: Pos, radius: i32) -> Fov {
let mut fov = Fov { width: map.width, visible: vec![false; (map.width * map.height) as usize] };
let mut reveal = |p: Pos| {
if map.contains(p) {
fov.visible[map.index(p)] = true;
}
};
reveal(origin);
for quadrant in Quadrant::ALL {
let mut rows = vec![Row { depth: 1, start: Slope::new(-1, 1), end: Slope::new(1, 1) }];
while let Some(mut row) = rows.pop() {
if row.depth > radius {
continue;
}
let mut prev_blocked = None;
for col in row.min_col()..=row.max_col() {
let p = quadrant.cell(origin, row.depth, col);
let blocked = map.tile(p).blocks_sight();
let in_radius = col * col + row.depth * row.depth <= radius * radius + radius;
if in_radius && (blocked || row.is_symmetric(col)) {
reveal(p);
}
if prev_blocked == Some(true) && !blocked {
row.start = Slope::left_edge(row.depth, col);
}
if prev_blocked == Some(false) && blocked {
let mut next = row.next();
next.end = Slope::left_edge(row.depth, col);
rows.push(next);
}
prev_blocked = Some(blocked);
}
if prev_blocked == Some(false) {
rows.push(row.next());
}
}
}
fov
}
#[derive(Clone, Copy)]
enum Quadrant {
North,
East,
South,
West,
}
impl Quadrant {
const ALL: [Quadrant; 4] = [Quadrant::North, Quadrant::East, Quadrant::South, Quadrant::West];
/// The cell `depth` rows out from `origin` and `col` columns across.
fn cell(self, origin: Pos, depth: i32, col: i32) -> Pos {
match self {
Quadrant::North => origin.offset(col, -depth),
Quadrant::South => origin.offset(col, depth),
Quadrant::East => origin.offset(depth, col),
Quadrant::West => origin.offset(-depth, col),
}
}
}
/// An exact fraction, so shadows land on the same cells every time.
#[derive(Clone, Copy)]
struct Slope {
num: i32,
/// Always positive.
den: i32,
}
impl Slope {
const fn new(num: i32, den: i32) -> Slope {
Slope { num, den }
}
/// The slope through the left edge of the cell at (`depth`, `col`).
const fn left_edge(depth: i32, col: i32) -> Slope {
Slope::new(2 * col - 1, 2 * depth)
}
}
#[derive(Clone, Copy)]
struct Row {
depth: i32,
start: Slope,
end: Slope,
}
impl Row {
/// `depth * start`, rounded with ties going up.
fn min_col(&self) -> i32 {
(2 * self.depth * self.start.num + self.start.den).div_euclid(2 * self.start.den)
}
/// `depth * end`, rounded with ties going down.
fn max_col(&self) -> i32 {
-(self.end.den - 2 * self.depth * self.end.num).div_euclid(2 * self.end.den)
}
/// Whether the centre of the cell at `col` is inside this row's slopes.
fn is_symmetric(&self, col: i32) -> bool {
col * self.start.den >= self.depth * self.start.num
&& col * self.end.den <= self.depth * self.end.num
}
fn next(&self) -> Row {
Row { depth: self.depth + 1, ..*self }
}
}
#[cfg(test)]
mod tests {
use rand::RngExt;
use super::*;
use crate::dungeon::Tile;
use crate::seed;
fn map_from(rows: &[&str]) -> (Map, Pos) {
let mut map = Map::new(rows[0].len() as i32, rows.len() as i32, Tile::Floor);
let mut at = Pos::new(0, 0);
for (y, row) in rows.iter().enumerate() {
for (x, c) in row.chars().enumerate() {
let p = Pos::new(x as i32, y as i32);
match c {
'#' => map.set(p, Tile::Wall),
'@' => at = p,
_ => {}
}
}
}
(map, at)
}
#[test]
fn walls_cast_shadows() {
let (map, at) = map_from(&[
"#########", //
"#.......#", "#...@...#", "#..###..#", "#.......#", "#########",
]);
let fov = compute(&map, at, 10);
assert!(fov.contains(Pos::new(1, 1)), "open floor is visible");
assert!(fov.contains(Pos::new(4, 3)), "the wall itself is visible");
assert!(!fov.contains(Pos::new(4, 4)), "the cell right behind the wall is hidden");
assert!(fov.contains(Pos::new(1, 3)), "cells beside the wall stay visible");
}
#[test]
fn radius_limits_sight() {
let (map, _) = map_from(&[&".".repeat(30)]);
let fov = compute(&map, Pos::new(0, 0), 5);
assert!(fov.contains(Pos::new(5, 0)));
assert!(!fov.contains(Pos::new(6, 0)));
}
/// The property the module promises: seeing is mutual between floor cells.
#[test]
fn sight_is_symmetric() {
let mut rng = seed::rng(4);
for _ in 0..20 {
let mut map = Map::new(24, 16, Tile::Floor);
for p in map.positions().collect::<Vec<_>>() {
if rng.random_bool(0.25) {
map.set(p, Tile::Wall);
}
}
let floors: Vec<Pos> =
map.positions().filter(|&p| map.tile(p) == Tile::Floor).collect();
let views: Vec<Fov> = floors.iter().map(|&p| compute(&map, p, 8)).collect();
for (i, &a) in floors.iter().enumerate() {
for (j, &b) in floors.iter().enumerate() {
assert_eq!(
views[i].contains(b),
views[j].contains(a),
"{a:?} and {b:?} disagree about seeing each other"
);
}
}
}
}
}
|
