jagua_rs/collision_detection/quadtree/
qt_node.rs

1use crate::collision_detection::hazards::collector::HazardCollector;
2use crate::collision_detection::hazards::filter::HazardFilter;
3use crate::collision_detection::hazards::{HazKey, Hazard, HazardEntity};
4use crate::collision_detection::quadtree::QTHazPresence;
5use crate::collision_detection::quadtree::QTHazard;
6use crate::collision_detection::quadtree::qt_hazard_vec::QTHazardVec;
7use crate::collision_detection::quadtree::qt_traits::QTQueryable;
8use crate::geometry::geo_traits::CollidesWith;
9use crate::geometry::primitives::Rect;
10use slotmap::SlotMap;
11
12/// Quadtree node
13#[derive(Clone, Debug)]
14pub struct QTNode {
15    /// The level of the node in the tree, 0 being the bottom-most level
16    pub level: u8,
17    /// The bounding box of the node
18    pub bbox: Rect,
19    /// The children of the node, if any
20    pub children: Option<Box<[QTNode; 4]>>,
21    /// The hazards present in the node
22    pub hazards: QTHazardVec,
23    /// Stop traversing the quadtree and perform collision detection immediately when the total number of edges in a node falls below this number
24    pub cd_threshold: u8,
25}
26
27impl QTNode {
28    pub fn new(level: u8, bbox: Rect, cd_threshold: u8) -> Self {
29        QTNode {
30            level,
31            bbox,
32            children: None,
33            hazards: QTHazardVec::new(),
34            cd_threshold,
35        }
36    }
37
38    pub fn register_hazard(&mut self, new_qt_haz: QTHazard, haz_map: &SlotMap<HazKey, Hazard>) {
39        let constrict_and_register_to_children =
40            |qt_hazard: &QTHazard, children: &mut Box<[QTNode; 4]>| {
41                // Constrict the hazard to the bounding boxes of the children
42                let child_bboxes = children.each_ref().map(|c| c.bbox);
43                let child_hazards = qt_hazard.constrict(child_bboxes, haz_map);
44
45                // Register the hazards to the children if present
46                child_hazards
47                    .into_iter()
48                    .enumerate()
49                    .for_each(|(i, child_haz)| {
50                        match child_haz.presence {
51                            QTHazPresence::None => (), // No need to register if the hazard is not present
52                            QTHazPresence::Partial(_) | QTHazPresence::Entire => {
53                                children[i].register_hazard(child_haz, haz_map);
54                            }
55                        }
56                    });
57            };
58
59        //Check if we have to expand the node (generate children)
60        if self.children.is_none()
61            && self.level > 0
62            && matches!(new_qt_haz.presence, QTHazPresence::Partial(_))
63        {
64            // Generate a child for every quadrant
65            let children = self
66                .bbox
67                .quadrants()
68                .map(|quad| QTNode::new(self.level - 1, quad, self.cd_threshold));
69            self.children = Some(Box::new(children));
70
71            // Register all previous hazards to them
72            for qt_hazard in self.hazards.iter() {
73                constrict_and_register_to_children(qt_hazard, self.children.as_mut().unwrap());
74            }
75        }
76        if let Some(children) = self.children.as_mut() {
77            // If there are children, register the hazard to them
78            constrict_and_register_to_children(&new_qt_haz, children);
79        }
80        self.hazards.add(new_qt_haz);
81    }
82
83    pub fn deregister_hazard(&mut self, hkey: HazKey) {
84        let modified = self.hazards.remove(hkey).is_some();
85
86        if modified {
87            if self.hazards.no_partial_hazards() {
88                // Drop the children if there are no partially present hazards left
89                self.children = None;
90            } else if let Some(children) = self.children.as_mut() {
91                children.iter_mut().for_each(|c| c.deregister_hazard(hkey));
92            }
93        }
94    }
95
96    /// Used to detect collisions in a binary fashion: either there is a collision or there isn't.
97    /// Returns `None` if no collision between the entity and any hazard is detected,
98    /// otherwise the first encountered hazard that collides with the entity is returned.
99    pub fn collides<T: QTQueryable>(
100        &self,
101        entity: &T,
102        filter: &impl HazardFilter,
103    ) -> Option<&HazardEntity> {
104        match self.hazards.strongest(filter) {
105            None => None,
106            Some(strongest_hazard) => match strongest_hazard.presence {
107                QTHazPresence::None => None,
108                QTHazPresence::Entire => Some(&strongest_hazard.entity),
109                QTHazPresence::Partial(_) => {
110                    // Condition to perform collision detection now or pass it to children:
111                    match &self.children {
112                        Some(children) => {
113                            //Check if any of the children collide with the entity
114                            let quadrants = [0, 1, 2, 3].map(|idx| &children[idx].bbox);
115                            let colliding_quadrants =
116                                entity.collides_with_quadrants(&self.bbox, quadrants);
117
118                            colliding_quadrants
119                                .iter()
120                                .enumerate()
121                                .filter(|(_, collides)| **collides)
122                                .map(|idx| children[idx.0].collides(entity, filter))
123                                .find(|x| x.is_some())
124                                .flatten()
125                        }
126                        None => {
127                            //Check if any of the partially present (and active) hazards collide with the entity
128                            let mut relevant_hazards = self
129                                .hazards
130                                .iter()
131                                .filter(|hz| !filter.is_irrelevant(hz.hkey));
132
133                            relevant_hazards
134                                .find(|hz| match &hz.presence {
135                                    QTHazPresence::None => false,
136                                    QTHazPresence::Entire => {
137                                        unreachable!("should have been handled above")
138                                    }
139                                    QTHazPresence::Partial(p_haz) => p_haz.collides_with(entity),
140                                })
141                                .map(|hz| &hz.entity)
142                        }
143                    }
144                }
145            },
146        }
147    }
148
149    /// Gathers all hazards that collide with the entity and reports them to the `collector`.
150    /// All hazards already present in the `collector` are ignored.
151    pub fn collect_collisions<T: QTQueryable>(
152        &self,
153        entity: &T,
154        collector: &mut impl HazardCollector,
155    ) {
156        // Condition to perform collision detection now or pass it to children:
157        let perform_cd_now = self.hazards.n_active_edges() <= self.cd_threshold as usize;
158
159        match (self.children.as_ref(), perform_cd_now) {
160            (Some(children), false) => {
161                // Collect collisions from all children that collide with the entity
162                let quadrants = [0, 1, 2, 3].map(|idx| &children[idx].bbox);
163                let colliding_quadrants = entity.collides_with_quadrants(&self.bbox, quadrants);
164
165                colliding_quadrants
166                    .iter()
167                    .enumerate()
168                    .filter(|(_, collides)| **collides)
169                    .map(|(i, _)| &children[i])
170                    .for_each(|child| {
171                        child.collect_collisions(entity, collector);
172                    });
173            }
174            _ => {
175                //Check the hazards now
176                for hz in self.hazards.iter() {
177                    if !collector.contains_key(hz.hkey) {
178                        match &hz.presence {
179                            QTHazPresence::None => (),
180                            QTHazPresence::Entire => collector.insert(hz.hkey, hz.entity),
181                            QTHazPresence::Partial(p_haz) => {
182                                if p_haz.collides_with(entity) {
183                                    collector.insert(hz.hkey, hz.entity);
184                                }
185                            }
186                        }
187                    }
188                }
189            }
190        }
191    }
192}
jagua_rs/collision_detection/quadtree/qt_node.rs

jagua_rs/collision_detection/quadtree/
qt_node.rs
