jagua_rs/collision_detection/quadtree/
qt_node.rs

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

jagua_rs/collision_detection/quadtree/
qt_node.rs
