terrain_forge/spatial/
distance.rs

1//! Distance transform algorithms for spatial analysis
2
3use crate::{Cell, Grid};
4use std::collections::VecDeque;
5
6/// Distance metrics for spatial calculations
7#[derive(Debug, Clone, Copy, PartialEq, Eq)]
8pub enum DistanceMetric {
9    /// Euclidean distance (straight line)
10    Euclidean,
11    /// Manhattan distance (taxicab)
12    Manhattan,
13    /// Chebyshev distance (chessboard)
14    Chebyshev,
15}
16
17/// Distance transform result
18#[derive(Debug, Clone)]
19pub struct DistanceTransform {
20    distances: Vec<f32>,
21    width: usize,
22    height: usize,
23}
24
25impl DistanceTransform {
26    pub fn new(width: usize, height: usize) -> Self {
27        Self {
28            distances: vec![f32::INFINITY; width * height],
29            width,
30            height,
31        }
32    }
33
34    pub fn get(&self, x: usize, y: usize) -> f32 {
35        self.distances[y * self.width + x]
36    }
37
38    pub fn set(&mut self, x: usize, y: usize, distance: f32) {
39        self.distances[y * self.width + x] = distance;
40    }
41
42    pub fn width(&self) -> usize {
43        self.width
44    }
45    pub fn height(&self) -> usize {
46        self.height
47    }
48}
49
50/// Generate distance field from passable cells
51pub fn distance_field<C: Cell>(grid: &Grid<C>, metric: DistanceMetric) -> DistanceTransform {
52    let mut transform = DistanceTransform::new(grid.width(), grid.height());
53    let mut queue = VecDeque::new();
54
55    // Initialize with passable cells as distance 0
56    for y in 0..grid.height() {
57        for x in 0..grid.width() {
58            if let Some(cell) = grid.get(x as i32, y as i32) {
59                if cell.is_passable() {
60                    transform.set(x, y, 0.0);
61                    queue.push_back((x, y));
62                }
63            }
64        }
65    }
66
67    // Propagate distances
68    while let Some((x, y)) = queue.pop_front() {
69        let current_dist = transform.get(x, y);
70
71        for (dx, dy) in neighbors(metric) {
72            let nx = x as i32 + dx;
73            let ny = y as i32 + dy;
74
75            if nx >= 0 && ny >= 0 && (nx as usize) < grid.width() && (ny as usize) < grid.height() {
76                let nx = nx as usize;
77                let ny = ny as usize;
78
79                let step_dist = match metric {
80                    DistanceMetric::Euclidean => ((dx * dx + dy * dy) as f32).sqrt(),
81                    DistanceMetric::Manhattan => (dx.abs() + dy.abs()) as f32,
82                    DistanceMetric::Chebyshev => dx.abs().max(dy.abs()) as f32,
83                };
84
85                let new_dist = current_dist + step_dist;
86                if new_dist < transform.get(nx, ny) {
87                    transform.set(nx, ny, new_dist);
88                    queue.push_back((nx, ny));
89                }
90            }
91        }
92    }
93
94    transform
95}
96
97fn neighbors(metric: DistanceMetric) -> &'static [(i32, i32)] {
98    match metric {
99        DistanceMetric::Manhattan => &[(-1, 0), (1, 0), (0, -1), (0, 1)],
100        DistanceMetric::Euclidean | DistanceMetric::Chebyshev => &[
101            (-1, -1),
102            (-1, 0),
103            (-1, 1),
104            (0, -1),
105            (0, 1),
106            (1, -1),
107            (1, 0),
108            (1, 1),
109        ],
110    }
111}
terrain_forge/spatial/distance.rs

terrain_forge/spatial/
distance.rs
