vimp_engine_core/nav/
spatial.rs

1use std::collections::HashMap;
2
3use serde::{Deserialize, Serialize};
4
5/// Пространственная сетка для быстрого поиска соседей
6/// (порт src/server/modules/bots/SpatialManager.js).
7#[derive(Clone, Serialize, Deserialize)]
8pub struct SpatialGrid {
9    cell_size: f32,
10    grid: HashMap<(i32, i32), Vec<SpatialEntity>>,
11}
12
13#[derive(Clone, Copy, Serialize, Deserialize)]
14pub struct SpatialEntity {
15    pub game_id: u32,
16    pub team_id: u8,
17    pub x: f32,
18    pub y: f32,
19}
20
21impl SpatialGrid {
22    pub fn new(cell_size: f32) -> Self {
23        Self {
24            cell_size,
25            grid: HashMap::new(),
26        }
27    }
28
29    pub fn clear(&mut self) {
30        self.grid.clear();
31    }
32
33    pub fn cell_size(&self) -> f32 {
34        self.cell_size
35    }
36
37    /// Заполненность ячеек `[(cx, cy, count)]` для отладочного дампа, в
38    /// детерминированном порядке (HashMap отдаёт свой).
39    pub fn cell_counts(&self) -> Vec<(i32, i32, usize)> {
40        let mut cells: Vec<(i32, i32, usize)> = self
41            .grid
42            .iter()
43            .map(|((cx, cy), entities)| (*cx, *cy, entities.len()))
44            .collect();
45
46        cells.sort_by_key(|(cx, cy, _)| (*cx, *cy));
47
48        cells
49    }
50
51    fn cell_key(&self, x: f32, y: f32) -> (i32, i32) {
52        (
53            (x / self.cell_size).floor() as i32,
54            (y / self.cell_size).floor() as i32,
55        )
56    }
57
58    pub fn insert(&mut self, entity: SpatialEntity) {
59        let key = self.cell_key(entity.x, entity.y);
60
61        self.grid.entry(key).or_default().push(entity);
62    }
63
64    /// Все сущности в ячейке позиции и 8 соседних.
65    pub fn query_nearby(&self, x: f32, y: f32) -> Vec<SpatialEntity> {
66        let (center_cx, center_cy) = self.cell_key(x, y);
67        let mut candidates = Vec::new();
68
69        for cy in (center_cy - 1)..=(center_cy + 1) {
70            for cx in (center_cx - 1)..=(center_cx + 1) {
71                if let Some(cell) = self.grid.get(&(cx, cy)) {
72                    candidates.extend_from_slice(cell);
73                }
74            }
75        }
76
77        candidates
78    }
79}
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84
85    #[test]
86    fn query_returns_neighbours_only() {
87        let mut grid = SpatialGrid::new(100.0);
88
89        grid.insert(SpatialEntity {
90            game_id: 1,
91            team_id: 1,
92            x: 50.0,
93            y: 50.0,
94        });
95        grid.insert(SpatialEntity {
96            game_id: 2,
97            team_id: 2,
98            x: 150.0,
99            y: 50.0,
100        });
101        grid.insert(SpatialEntity {
102            game_id: 3,
103            team_id: 2,
104            x: 950.0,
105            y: 950.0,
106        });
107
108        let found = grid.query_nearby(60.0, 60.0);
109        let ids: Vec<u32> = found.iter().map(|e| e.game_id).collect();
110
111        assert!(ids.contains(&1));
112        assert!(ids.contains(&2));
113        assert!(!ids.contains(&3));
114    }
115}
vimp_engine_core/nav/spatial.rs

vimp_engine_core/nav/
spatial.rs
