steel_core/world/player_index/
area.rs

1//! Spatial data structure for efficient player proximity queries.
2//!
3//! Based on VMP (Very Many Players) implementation pattern:
4//! Maps chunk coordinates to sets of players for O(1) nearby player lookup.
5
6use std::sync::Arc;
7
8use rustc_hash::FxHashSet;
9use steel_utils::ChunkPos;
10
11use crate::{chunk::player_chunk_view::PlayerChunkView, entity::Entity, player::Player};
12
13/// Spatial index for player proximity queries.
14///
15/// Uses packed `ChunkPos` chunk coordinates as keys for efficient hashing.
16/// Thread-safe via `scc::HashMap` for concurrent access.
17///
18/// The map maintains a dual index:
19/// - `chunks`: Maps chunk coords to players whose tracking area includes that chunk
20/// - `player_chunks`: Maps player entity IDs to the set of chunks they're registered in
21///
22/// This enables O(1) lookup of nearby players and O(tracking area) removal.
23///
24/// Entity IDs are used instead of UUIDs because:
25/// - They are globally unique within a server session (vanilla uses a static atomic counter)
26/// - They are smaller (4 bytes vs 16 bytes) and faster to hash
27/// - `PlayerAreaMap` only tracks players during a session, not persisted
28pub struct PlayerAreaMap {
29    /// Maps packed chunk coords (`ChunkPos`) to set of player entity IDs
30    chunks: scc::HashMap<ChunkPos, FxHashSet<i32>>,
31
32    /// Maps player entity ID to its current set of tracked chunks (for efficient removal)
33    player_chunks: scc::HashMap<i32, FxHashSet<ChunkPos>>,
34}
35
36impl Default for PlayerAreaMap {
37    fn default() -> Self {
38        Self::new()
39    }
40}
41
42impl PlayerAreaMap {
43    /// Creates a new player area map.
44    #[must_use]
45    pub fn new() -> Self {
46        Self {
47            chunks: scc::HashMap::new(),
48            player_chunks: scc::HashMap::new(),
49        }
50    }
51
52    /// Registers a player at their current position using their chunk view.
53    pub fn on_player_join(&self, player: &Player, view: &PlayerChunkView) {
54        let entity_id = player.id();
55        let mut player_set = FxHashSet::default();
56
57        view.for_each(|chunk| {
58            player_set.insert(chunk);
59            self.add_to_chunk(chunk, entity_id);
60        });
61
62        let _ = self.player_chunks.insert_sync(entity_id, player_set);
63    }
64
65    /// Removes a player from all tracked chunks.
66    pub fn on_player_leave(&self, player: &Arc<Player>) {
67        self.remove_by_entity_id(player.id());
68    }
69
70    /// Removes a player from all tracked chunks by entity ID.
71    ///
72    /// This is useful when you don't have an `Arc<Player>` reference,
73    /// such as during respawn cleanup.
74    pub fn remove_by_entity_id(&self, entity_id: i32) {
75        if let Some((_, chunks)) = self.player_chunks.remove_sync(&entity_id) {
76            for chunk in chunks {
77                self.remove_from_chunk(chunk, entity_id);
78            }
79        }
80    }
81
82    /// Updates a player's tracked chunks using pre-computed view differences.
83    ///
84    /// Call this after computing the difference via `PlayerChunkView::difference()`.
85    pub fn on_player_view_change(
86        &self,
87        entity_id: i32,
88        added_chunks: &[ChunkPos],
89        removed_chunks: &[ChunkPos],
90    ) {
91        if added_chunks.is_empty() && removed_chunks.is_empty() {
92            return;
93        }
94
95        for &chunk in removed_chunks {
96            self.remove_from_chunk(chunk, entity_id);
97        }
98
99        for &chunk in added_chunks {
100            self.add_to_chunk(chunk, entity_id);
101        }
102
103        // Update the player's chunk set
104        self.player_chunks.update_sync(&entity_id, |_, set| {
105            for &chunk in removed_chunks {
106                set.remove(&chunk);
107            }
108            for &chunk in added_chunks {
109                set.insert(chunk);
110            }
111        });
112    }
113
114    /// Gets all players tracking the given chunk.
115    #[must_use]
116    pub fn get_tracking_players(&self, chunk: ChunkPos) -> Vec<i32> {
117        self.chunks
118            .read_sync(&chunk, |_, set| set.iter().copied().collect())
119            .unwrap_or_default()
120    }
121
122    /// Returns the number of tracked players.
123    #[must_use]
124    pub fn len(&self) -> usize {
125        self.player_chunks.len()
126    }
127
128    /// Returns true if no players are tracked.
129    #[must_use]
130    pub fn is_empty(&self) -> bool {
131        self.player_chunks.is_empty()
132    }
133
134    fn add_to_chunk(&self, chunk: ChunkPos, entity_id: i32) {
135        if self
136            .chunks
137            .update_sync(&chunk, |_, set| {
138                set.insert(entity_id);
139            })
140            .is_none()
141        {
142            let mut set = FxHashSet::default();
143            set.insert(entity_id);
144            let _ = self.chunks.insert_sync(chunk, set);
145        }
146    }
147
148    fn remove_from_chunk(&self, chunk: ChunkPos, entity_id: i32) {
149        let should_remove = self
150            .chunks
151            .update_sync(&chunk, |_, set| {
152                set.remove(&entity_id);
153                set.is_empty()
154            })
155            .unwrap_or(false);
156
157        if should_remove {
158            let _ = self.chunks.remove_if_sync(&chunk, |set| set.is_empty());
159        }
160    }
161}
162
163#[cfg(test)]
164mod tests {
165    use super::*;
166
167    #[test]
168    fn test_add_and_get() {
169        let map = PlayerAreaMap::new();
170        let entity_id = 42;
171        let center = ChunkPos::new(0, 0);
172        let view = PlayerChunkView::new(center, 2);
173
174        // Manually add since we don't have a Player in tests
175        let mut player_set = FxHashSet::default();
176        view.for_each(|chunk| {
177            player_set.insert(chunk);
178            map.add_to_chunk(chunk, entity_id);
179        });
180        let _ = map.player_chunks.insert_sync(entity_id, player_set);
181
182        assert!(map.get_tracking_players(center).contains(&entity_id));
183        assert!(
184            map.get_tracking_players(ChunkPos::new(1, 1))
185                .contains(&entity_id)
186        );
187        // ChunkPos(3,0) should be in view with distance 2 (due to buffer logic)
188        assert!(
189            map.get_tracking_players(ChunkPos::new(3, 0))
190                .contains(&entity_id)
191        );
192        // ChunkPos(5,5) should be outside
193        assert!(
194            !map.get_tracking_players(ChunkPos::new(5, 5))
195                .contains(&entity_id)
196        );
197    }
198
199    #[test]
200    fn test_remove() {
201        let map = PlayerAreaMap::new();
202        let entity_id = 42;
203        let center = ChunkPos::new(0, 0);
204        let view = PlayerChunkView::new(center, 2);
205
206        // Manually add
207        let mut player_set = FxHashSet::default();
208        view.for_each(|chunk| {
209            player_set.insert(chunk);
210            map.add_to_chunk(chunk, entity_id);
211        });
212        let _ = map.player_chunks.insert_sync(entity_id, player_set);
213        assert_eq!(map.len(), 1);
214
215        // Manually remove
216        if let Some((_, chunks)) = map.player_chunks.remove_sync(&entity_id) {
217            for chunk in chunks {
218                map.remove_from_chunk(chunk, entity_id);
219            }
220        }
221        assert_eq!(map.len(), 0);
222        assert!(map.get_tracking_players(center).is_empty());
223    }
224
225    #[test]
226    fn test_view_change() {
227        let map = PlayerAreaMap::new();
228        let entity_id = 42;
229        let old_center = ChunkPos::new(0, 0);
230        let new_center = ChunkPos::new(5, 5);
231        let old_view = PlayerChunkView::new(old_center, 1);
232        let new_view = PlayerChunkView::new(new_center, 1);
233
234        // Manually add
235        let mut player_set = FxHashSet::default();
236        old_view.for_each(|chunk| {
237            player_set.insert(chunk);
238            map.add_to_chunk(chunk, entity_id);
239        });
240        let _ = map.player_chunks.insert_sync(entity_id, player_set);
241        assert!(map.get_tracking_players(old_center).contains(&entity_id));
242
243        // Compute diff using PlayerChunkView::difference
244        let mut diff = (Vec::new(), Vec::new());
245        PlayerChunkView::difference(
246            &old_view,
247            &new_view,
248            |pos, (added, _): &mut (Vec<ChunkPos>, Vec<ChunkPos>)| added.push(pos),
249            |pos, (_, removed): &mut (Vec<ChunkPos>, Vec<ChunkPos>)| removed.push(pos),
250            &mut diff,
251        );
252        let (added, removed) = diff;
253
254        map.on_player_view_change(entity_id, &added, &removed);
255
256        assert!(!map.get_tracking_players(old_center).contains(&entity_id));
257        assert!(map.get_tracking_players(new_center).contains(&entity_id));
258    }
259
260    #[test]
261    fn test_multiple_players() {
262        let map = PlayerAreaMap::new();
263        let entity_id1 = 42;
264        let entity_id2 = 43;
265
266        let view1 = PlayerChunkView::new(ChunkPos::new(0, 0), 2);
267        let view2 = PlayerChunkView::new(ChunkPos::new(1, 1), 2);
268
269        // Manually add both
270        let mut set1 = FxHashSet::default();
271        view1.for_each(|chunk| {
272            set1.insert(chunk);
273            map.add_to_chunk(chunk, entity_id1);
274        });
275        let _ = map.player_chunks.insert_sync(entity_id1, set1);
276
277        let mut set2 = FxHashSet::default();
278        view2.for_each(|chunk| {
279            set2.insert(chunk);
280            map.add_to_chunk(chunk, entity_id2);
281        });
282        let _ = map.player_chunks.insert_sync(entity_id2, set2);
283
284        let players = map.get_tracking_players(ChunkPos::new(0, 0));
285        assert!(players.contains(&entity_id1));
286        assert!(players.contains(&entity_id2));
287        assert_eq!(map.len(), 2);
288    }
289}
steel_core/world/player_index/area.rs

steel_core/world/player_index/
area.rs
