terrain_forge/effects/
spatial.rs

1//! Spatial analysis
2
3use crate::{Grid, Tile};
4use std::collections::VecDeque;
5
6pub fn distance_transform(grid: &Grid<Tile>) -> Vec<Vec<u32>> {
7    let (w, h) = (grid.width(), grid.height());
8    let mut dist = vec![vec![u32::MAX; w]; h];
9    let mut queue = VecDeque::new();
10
11    for y in 0..h {
12        for x in 0..w {
13            if !grid[(x, y)].is_floor() {
14                dist[y][x] = 0;
15                queue.push_back((x, y));
16            }
17        }
18    }
19
20    while let Some((x, y)) = queue.pop_front() {
21        let d = dist[y][x] + 1;
22        for (nx, ny) in neighbors(x, y, w, h) {
23            if dist[ny][nx] > d {
24                dist[ny][nx] = d;
25                queue.push_back((nx, ny));
26            }
27        }
28    }
29    dist
30}
31
32pub fn dijkstra_map(grid: &Grid<Tile>, sources: &[(usize, usize)]) -> Vec<Vec<u32>> {
33    let (w, h) = (grid.width(), grid.height());
34    let mut dist = vec![vec![u32::MAX; w]; h];
35    let mut queue = VecDeque::new();
36
37    for &(x, y) in sources {
38        if x < w && y < h && grid[(x, y)].is_floor() {
39            dist[y][x] = 0;
40            queue.push_back((x, y));
41        }
42    }
43
44    while let Some((x, y)) = queue.pop_front() {
45        let d = dist[y][x] + 1;
46        for (nx, ny) in neighbors(x, y, w, h) {
47            if grid[(nx, ny)].is_floor() && dist[ny][nx] > d {
48                dist[ny][nx] = d;
49                queue.push_back((nx, ny));
50            }
51        }
52    }
53    dist
54}
55
56fn neighbors(x: usize, y: usize, w: usize, h: usize) -> impl Iterator<Item = (usize, usize)> {
57    let mut n = Vec::with_capacity(4);
58    if x > 0 {
59        n.push((x - 1, y));
60    }
61    if x + 1 < w {
62        n.push((x + 1, y));
63    }
64    if y > 0 {
65        n.push((x, y - 1));
66    }
67    if y + 1 < h {
68        n.push((x, y + 1));
69    }
70    n.into_iter()
71}
terrain_forge/effects/spatial.rs

terrain_forge/effects/
spatial.rs
