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    fn cell_key(&self, x: f32, y: f32) -> (i32, i32) {
34        (
35            (x / self.cell_size).floor() as i32,
36            (y / self.cell_size).floor() as i32,
37        )
38    }
39
40    pub fn insert(&mut self, entity: SpatialEntity) {
41        let key = self.cell_key(entity.x, entity.y);
42
43        self.grid.entry(key).or_default().push(entity);
44    }
45
46    /// Все сущности в ячейке позиции и 8 соседних.
47    pub fn query_nearby(&self, x: f32, y: f32) -> Vec<SpatialEntity> {
48        let (center_cx, center_cy) = self.cell_key(x, y);
49        let mut candidates = Vec::new();
50
51        for cy in (center_cy - 1)..=(center_cy + 1) {
52            for cx in (center_cx - 1)..=(center_cx + 1) {
53                if let Some(cell) = self.grid.get(&(cx, cy)) {
54                    candidates.extend_from_slice(cell);
55                }
56            }
57        }
58
59        candidates
60    }
61}
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    #[test]
68    fn query_returns_neighbours_only() {
69        let mut grid = SpatialGrid::new(100.0);
70
71        grid.insert(SpatialEntity {
72            game_id: 1,
73            team_id: 1,
74            x: 50.0,
75            y: 50.0,
76        });
77        grid.insert(SpatialEntity {
78            game_id: 2,
79            team_id: 2,
80            x: 150.0,
81            y: 50.0,
82        });
83        grid.insert(SpatialEntity {
84            game_id: 3,
85            team_id: 2,
86            x: 950.0,
87            y: 950.0,
88        });
89
90        let found = grid.query_nearby(60.0, 60.0);
91        let ids: Vec<u32> = found.iter().map(|e| e.game_id).collect();
92
93        assert!(ids.contains(&1));
94        assert!(ids.contains(&2));
95        assert!(!ids.contains(&3));
96    }
97}
vimp_engine_core/nav/spatial.rs

vimp_engine_core/nav/
spatial.rs
