veloren_common/
region.rs

1use crate::comp::{Pos, Presence, Vel};
2use common_base::span;
3use hashbrown::{DefaultHashBuilder, HashSet};
4use indexmap::IndexMap;
5use specs::{BitSet, Entities, Join, LendJoin, ReadStorage, hibitset::BitSetLike};
6use vek::*;
7
8pub enum Event {
9    // Contains the key of the region the entity moved to
10    // TODO: We only actually use the info from this when the entity moves to another region and
11    // isn't deleted, but we still generate and process these events in the case where the entity
12    // was deleted.
13    Left(u32, Option<Vec2<i32>>),
14    // Contains the key of the region the entity came from
15    Entered(u32, Option<Vec2<i32>>),
16}
17
18/// Region consisting of a bitset of entities within it
19#[derive(Default)]
20pub struct Region {
21    // Use specs bitset for simplicity (and joinability)
22    bitset: BitSet,
23    // Indices of neighboring regions
24    neighbors: [Option<usize>; 8],
25    // TODO consider SmallVec for these
26    // Entities that left or entered this region
27    events: Vec<Event>,
28}
29impl Region {
30    /// Checks if the region contains no entities and no events
31    fn removable(&self) -> bool { self.bitset.is_empty() && self.events.is_empty() }
32
33    fn add(&mut self, id: u32, from: Option<Vec2<i32>>) {
34        self.bitset.add(id);
35        self.events.push(Event::Entered(id, from));
36    }
37
38    fn remove(&mut self, id: u32, to: Option<Vec2<i32>>) {
39        self.bitset.remove(id);
40        self.events.push(Event::Left(id, to));
41    }
42
43    pub fn events(&self) -> &[Event] { &self.events }
44
45    pub fn entities(&self) -> &BitSet { &self.bitset }
46}
47
48/// How far can an entity roam outside its region before it is switched over to
49/// the neighboring one In units of blocks (i.e. world pos)
50/// Used to prevent rapid switching of entities between regions
51pub const TETHER_LENGTH: u32 = 16;
52/// Bitshift between region and world pos, i.e. log2(REGION_SIZE)
53const REGION_LOG2: u8 = 9;
54/// Region Size in blocks
55pub const REGION_SIZE: u32 = 1 << REGION_LOG2;
56/// Offsets to iterate though neighbors
57/// Counter-clockwise order
58const NEIGHBOR_OFFSETS: [Vec2<i32>; 8] = [
59    Vec2::new(0, 1),
60    Vec2::new(-1, 1),
61    Vec2::new(-1, 0),
62    Vec2::new(-1, -1),
63    Vec2::new(0, -1),
64    Vec2::new(1, -1),
65    Vec2::new(1, 0),
66    Vec2::new(1, 1),
67];
68
69#[derive(Default)]
70// TODO generic region size (16x16 for now)
71// TODO compare to sweep and prune approach
72/// A region system that tracks where entities are.
73///
74/// Note, this structure is primarily intended for tracking which entities need
75/// to be synchronized to which clients (and as part of that what entities are
76/// already synchronized). If an entity is marked to not be synchronized to
77/// other clients it may not appear here.
78pub struct RegionMap {
79    // Tree?
80    // Sorted Vec? (binary search lookup)
81    // Sort into multiple vecs (say 32) using lower bits of morton code, then binary search via
82    // upper bits? <-- sounds very promising to me (might not be super good though?)
83    regions: IndexMap<Vec2<i32>, Region, DefaultHashBuilder>,
84    // If an entity isn't here it needs to be added to a region
85    tracked_entities: BitSet,
86    // Re-useable vecs
87    // (src, entity, pos)
88    entities_to_move: Vec<(usize, u32, Vec3<i32>)>,
89    // (region, entity)
90    entities_to_remove: Vec<(usize, u32)>,
91    // Track the current tick, used to enable not checking everything every tick
92    // rate is dependent on the rate the caller calls region_manager.tick()
93    tick: u64,
94}
95impl RegionMap {
96    pub fn new() -> Self { Self::default() }
97
98    // TODO maintain within a system?
99    // TODO special case large entities
100    pub fn tick(
101        &mut self,
102        pos: ReadStorage<Pos>,
103        vel: ReadStorage<Vel>,
104        presence: ReadStorage<Presence>,
105        entities: Entities,
106    ) {
107        span!(_guard, "tick", "Region::tick");
108        self.tick += 1;
109        // Clear events within each region
110        self.regions.values_mut().for_each(|region| {
111            region.events.clear();
112        });
113
114        // Add any untracked entities
115        for (pos, id) in (&pos, &entities, presence.maybe(), !&self.tracked_entities)
116            .join()
117            .filter(|(_, _, presence, _)| presence.is_none_or(|p| p.kind.sync_me()))
118            .map(|(pos, e, _, _)| (pos, e.id()))
119            .collect::<Vec<_>>()
120        {
121            // Add entity
122            self.tracked_entities.add(id);
123            self.add_entity(id, pos.0.map(|e| e as i32), None);
124        }
125
126        let mut regions_to_remove = Vec::new();
127
128        let RegionMap {
129            entities_to_move,
130            entities_to_remove,
131            regions,
132            ..
133        } = self;
134        regions
135            .iter()
136            .enumerate()
137            .for_each(|(i, (&current_region, region_data))| {
138                for (maybe_pos, _maybe_vel, maybe_presence, id) in (
139                    pos.maybe(),
140                    vel.maybe(),
141                    presence.maybe(),
142                    &region_data.bitset,
143                )
144                    .join()
145                {
146                    let should_sync = maybe_presence.is_none_or(|p| p.kind.sync_me());
147                    match maybe_pos {
148                        // Switch regions for entities which need switching
149                        // TODO don't check every tick (use velocity) (and use id to stagger)
150                        // Starting parameters at v = 0 check every 100 ticks
151                        // tether_length^2 / vel^2  (with a max of every tick)
152                        Some(pos) if should_sync => {
153                            let pos = pos.0.map(|e| e as i32);
154                            let key = Self::pos_key(pos);
155                            // Consider switching
156                            // Calculate distance outside border
157                            if key != current_region
158                                && (Vec2::<i32>::from(pos) - Self::key_pos(current_region))
159                                    .map(|e| e.unsigned_abs())
160                                    .reduce_max()
161                                    > TETHER_LENGTH
162                            {
163                                // Switch
164                                entities_to_move.push((i, id, pos));
165                            }
166                        },
167                        // Remove any non-existant entities (or just ones that lost their position
168                        // component) TODO: distribute this between ticks
169                        None | Some(_) => {
170                            // TODO: shouldn't there be a way to extract the bitset of entities with
171                            // positions directly from specs? Yes, with `.mask()` on the component
172                            // storage.
173                            entities_to_remove.push((i, id));
174                        },
175                    }
176                }
177
178                // Remove region if it is empty
179                // TODO: distribute this between ticks
180                if region_data.removable() {
181                    regions_to_remove.push(current_region);
182                }
183            });
184
185        // Mutate
186        // Note entity moving is outside the whole loop so that the same entity is not
187        // checked twice (this may be fine though...)
188        while let Some((i, id, pos)) = self.entities_to_move.pop() {
189            let (prev_key, region) = self.regions.get_index_mut(i).map(|(k, v)| (*k, v)).unwrap();
190            region.remove(id, Some(Self::pos_key(pos)));
191
192            self.add_entity(id, pos, Some(prev_key));
193        }
194        for (i, id) in self.entities_to_remove.drain(..) {
195            self.regions
196                .get_index_mut(i)
197                .map(|(_, v)| v)
198                .unwrap()
199                .remove(id, None);
200            self.tracked_entities.remove(id);
201        }
202        for key in regions_to_remove.into_iter() {
203            // Check that the region is still removable
204            if self.regions.get(&key).unwrap().removable() {
205                // Note we have to use key's here since the index can change when others are
206                // removed
207                self.remove(key);
208            }
209        }
210    }
211
212    /// Must be called immediately after succesfully deleting an entity from the
213    /// ecs (i.e. when deleting the entity did not generate a WrongGeneration
214    /// error).
215    pub fn entity_deleted(&mut self, entity: specs::Entity) {
216        self.tracked_entities.remove(entity.id());
217    }
218
219    fn add_entity(&mut self, id: u32, pos: Vec3<i32>, from: Option<Vec2<i32>>) {
220        let key = Self::pos_key(pos);
221        if let Some(region) = self.regions.get_mut(&key) {
222            region.add(id, from);
223            return;
224        }
225
226        let index = self.insert(key);
227        self.regions
228            .get_index_mut(index)
229            .map(|(_, v)| v)
230            .unwrap()
231            .add(id, None);
232    }
233
234    fn pos_key<P: Into<Vec2<i32>>>(pos: P) -> Vec2<i32> { pos.into().map(|e| e >> REGION_LOG2) }
235
236    pub fn key_pos(key: Vec2<i32>) -> Vec2<i32> { key.map(|e| e << REGION_LOG2) }
237
238    /// Finds the region where a given entity is located using a given position
239    /// to speed up the search
240    pub fn find_region(&self, entity: specs::Entity, pos: Vec3<f32>) -> Option<Vec2<i32>> {
241        let id = entity.id();
242        // Compute key for most likely region
243        let key = Self::pos_key(pos.map(|e| e as i32));
244        // Get region
245        if let Some(region) = self.regions.get(&key) {
246            if region.entities().contains(id) {
247                return Some(key);
248            } else {
249                // Check neighbors
250                for idx in region.neighbors.iter().flatten() {
251                    let (key, region) = self.regions.get_index(*idx).unwrap();
252                    if region.entities().contains(id) {
253                        return Some(*key);
254                    }
255                }
256            }
257        } else if !self.tracked_entities.contains(id) {
258            return None;
259        } else {
260            // Check neighbors
261            for o in &NEIGHBOR_OFFSETS {
262                let key = key + o;
263                if let Some(region) = self.regions.get(&key) {
264                    if region.entities().contains(id) {
265                        return Some(key);
266                    }
267                }
268            }
269        }
270
271        // Scan though all regions
272        for (key, region) in self.iter() {
273            if region.entities().contains(id) {
274                return Some(key);
275            }
276        }
277
278        None
279    }
280
281    /// Checks if this entity is located in the `RegionMap`.
282    pub fn in_region_map(&self, entity: specs::Entity) -> bool {
283        self.tracked_entities.contains(entity.id())
284    }
285
286    fn key_index(&self, key: Vec2<i32>) -> Option<usize> {
287        self.regions.get_full(&key).map(|(i, _, _)| i)
288    }
289
290    /// Adds a new region
291    /// Returns the index of the region in the index map
292    fn insert(&mut self, key: Vec2<i32>) -> usize {
293        let (index, old_region) = self.regions.insert_full(key, Region::default());
294        if old_region.is_some() {
295            panic!("Inserted a region that already exists!!!(this should never need to occur");
296        }
297        // Add neighbors and add to neighbors
298        let mut neighbors = [None; 8];
299        for i in 0..8 {
300            if let Some((idx, _, region)) = self.regions.get_full_mut(&(key + NEIGHBOR_OFFSETS[i]))
301            {
302                // Add neighbor to the new region
303                neighbors[i] = Some(idx);
304                // Add new region to neighbor
305                region.neighbors[(i + 4) % 8] = Some(index);
306            }
307        }
308        self.regions
309            .get_index_mut(index)
310            .map(|(_, v)| v)
311            .unwrap()
312            .neighbors = neighbors;
313
314        index
315    }
316
317    /// Remove a region using its key
318    fn remove(&mut self, key: Vec2<i32>) {
319        if let Some(index) = self.key_index(key) {
320            self.remove_index(index);
321        }
322    }
323
324    /// Add a region using its key
325    fn remove_index(&mut self, index: usize) {
326        // Remap neighbor indices for neighbors of the region that will be moved from
327        // the end of the index map
328        if index != self.regions.len() - 1 {
329            let moved_neighbors = self
330                .regions
331                .get_index(self.regions.len() - 1)
332                .map(|(_, v)| v)
333                .unwrap()
334                .neighbors;
335            for (i, possible_idx) in moved_neighbors.iter().enumerate() {
336                if let Some(idx) = possible_idx {
337                    self.regions
338                        .get_index_mut(*idx)
339                        .map(|(_, v)| v)
340                        .unwrap()
341                        .neighbors[(i + 4) % 8] = Some(index);
342                }
343            }
344        }
345        if let Some(region) = self
346            .regions
347            .swap_remove_index(index)
348            .map(|(_, region)| region)
349        {
350            if !region.bitset.is_empty() {
351                panic!("Removed region containing entities");
352            }
353            // Remove from neighbors
354            for i in 0..8 {
355                if let Some(idx) = region.neighbors[i] {
356                    self.regions
357                        .get_index_mut(idx)
358                        .map(|(_, v)| v)
359                        .unwrap()
360                        .neighbors[(i + 4) % 8] = None;
361                }
362            }
363        }
364    }
365
366    /// Returns a region given a key
367    pub fn get(&self, key: Vec2<i32>) -> Option<&Region> { self.regions.get(&key) }
368
369    /// Returns an iterator of (Position, Region)
370    pub fn iter(&self) -> impl Iterator<Item = (Vec2<i32>, &Region)> {
371        self.regions.iter().map(|(key, r)| (*key, r))
372    }
373}
374
375/// Note vd is in blocks in this case
376pub fn region_in_vd(key: Vec2<i32>, pos: Vec3<f32>, vd: f32) -> bool {
377    let vd_extended = vd + TETHER_LENGTH as f32 * 2.0f32.sqrt();
378
379    let min_region_pos = RegionMap::key_pos(key).map(|e| e as f32);
380    // Should be diff to closest point on the square (which can be in the middle of
381    // an edge)
382    let diff = (min_region_pos - Vec2::from(pos)).map(|e| {
383        if e < 0.0 {
384            (e + REGION_SIZE as f32).min(0.0)
385        } else {
386            e
387        }
388    });
389
390    diff.magnitude_squared() < vd_extended.powi(2)
391}
392
393// Note vd is in blocks in this case
394pub fn regions_in_vd(pos: Vec3<f32>, vd: f32) -> HashSet<Vec2<i32>> {
395    let mut set = HashSet::new();
396
397    let pos_xy = Vec2::<f32>::from(pos);
398    let vd_extended = vd + TETHER_LENGTH as f32 * 2.0f32.sqrt();
399
400    let max = RegionMap::pos_key(pos_xy.map(|e| (e + vd_extended) as i32));
401    let min = RegionMap::pos_key(pos_xy.map(|e| (e - vd_extended) as i32));
402
403    for x in min.x..max.x + 1 {
404        for y in min.y..max.y + 1 {
405            let key = Vec2::new(x, y);
406
407            if region_in_vd(key, pos, vd) {
408                set.insert(key);
409            }
410        }
411    }
412
413    set
414}
415// Iterator designed for use in collision systems
416// Iterates through all regions yielding them along with half of their neighbors
417// ..................
418
419/*fn interleave_i32_with_zeros(mut x: i32) -> i64 {
420    x = (x ^ (x << 16)) & 0x0000ffff0000ffff;
421    x = (x ^ (x << 8)) & 0x00ff00ff00ff00ff;
422    x = (x ^ (x << 4)) & 0x0f0f0f0f0f0f0f0f;
423    x = (x ^ (x << 2)) & 0x3333333333333333;
424    x = (x ^ (x << 1)) & 0x5555555555555555;
425    x
426}
427
428fn morton_code(pos: Vec2<i32>) -> i64 {
429    interleave_i32_with_zeros(pos.x) | (interleave_i32_with_zeros(pos.y) << 1)
430}*/
veloren_common/region.rs

veloren_common/
region.rs
