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

jagua_rs/collision_detection/quadtree/
qt_node.rs
