jagua_rs/collision_detection/quadtree/qt_hazard.rs
1use crate::collision_detection::hazards::HazardEntity;
2use crate::collision_detection::hazards::{HazKey, Hazard};
3use crate::collision_detection::quadtree::qt_partial_hazard::QTHazPartial;
4use crate::geometry::geo_enums::{GeoPosition, GeoRelation};
5use crate::geometry::geo_traits::CollidesWith;
6use crate::geometry::primitives::Rect;
7use crate::util::assertions;
8use slotmap::SlotMap;
9use std::array;
10
11/// Representation of a [`Hazard`] in a [`QTNode`](crate::collision_detection::quadtree::QTNode)
12#[derive(Clone, Debug)]
13pub struct QTHazard {
14 /// The bounding box of the quadtree node
15 pub qt_bbox: Rect,
16 /// The key of the hazard in the hazard map in [`CDEngine`](crate::collision_detection::cd_engine::CDEngine)
17 pub hkey: HazKey,
18 /// Entity inducing the hazard
19 pub entity: HazardEntity,
20 /// How the hazard is present in the node
21 pub presence: QTHazPresence,
22}
23
24/// Presence of a [`Hazard`] in a [`QTNode`](crate::collision_detection::quadtree::QTNode)
25#[derive(Clone, Debug)]
26pub enum QTHazPresence {
27 /// The hazard is entirely absent from the node
28 None,
29 /// The hazard is only partially present in the node
30 Partial(QTHazPartial),
31 /// The hazard is present in the entire node.
32 Entire,
33}
34impl QTHazard {
35 /// Converts a [`Hazard`] into a [`QTHazard`], assuming it is for the root of the quadtree.
36 #[must_use]
37 pub fn from_root(qt_root_bbox: Rect, haz: &Hazard, hkey: HazKey) -> Self {
38 Self {
39 qt_bbox: qt_root_bbox,
40 hkey,
41 entity: haz.entity,
42 presence: QTHazPresence::Partial(QTHazPartial::from_entire_shape(&haz.shape)),
43 }
44 }
45
46 /// Returns the resulting `QTHazards` after constricting to the provided quadrants.
47 /// The quadrants should be ordered according to the [Cartesian system](https://en.wikipedia.org/wiki/Quadrant_(plane_geometry))
48 /// and should all be inside the bounds from which `self` was created.
49 #[must_use]
50 pub fn constrict(&self, quadrants: [Rect; 4], haz_map: &SlotMap<HazKey, Hazard>) -> [Self; 4] {
51 debug_assert!(
52 quadrants
53 .iter()
54 .all(|q| self.qt_bbox.relation_to(*q) == GeoRelation::Surrounding)
55 );
56 debug_assert!(assertions::quadrants_have_valid_layout(&quadrants));
57
58 match &self.presence {
59 QTHazPresence::None => unreachable!("Hazard presence cannot be None in a QTHazard"),
60 QTHazPresence::Entire => array::from_fn(|_| self.clone()), // The hazard is entirely present in all quadrants
61 QTHazPresence::Partial(partial_haz) => {
62 //If the hazard is partially present, we need to check which type of presence each quadrant has
63
64 let haz_shape = &haz_map[self.hkey].shape;
65
66 //Check if one of the quadrants entirely contains the hazard
67 let enclosed_hazard_quadrant = quadrants
68 .iter()
69 .map(|q| haz_shape.bbox.relation_to(*q))
70 .position(|r| r == GeoRelation::Enclosed);
71
72 if let Some(quad_index) = enclosed_hazard_quadrant {
73 //The hazard is entirely enclosed within one quadrant,
74 //For this quadrant the QTHazard is equivalent to the original hazard, the rest are None
75 array::from_fn(|i| {
76 let presence = if i == quad_index {
77 self.presence.clone()
78 } else {
79 QTHazPresence::None
80 };
81 Self {
82 qt_bbox: quadrants[i],
83 presence,
84 hkey: self.hkey,
85 entity: self.entity,
86 }
87 })
88 } else {
89 //The hazard is active in multiple quadrants
90
91 // First lets find the quadrants where edges of the partial hazard are colliding with the quadrants.
92 // These will also be partially present hazards.
93 let mut constricted_hazards = quadrants.map(|q| {
94 //For every quadrant, collect the edges that are colliding with it
95 let mut colliding_edges = None;
96 for edge in &partial_haz.edges {
97 if q.collides_with(edge) {
98 colliding_edges.get_or_insert_with(Vec::new).push(*edge);
99 }
100 }
101 //If there are relevant edges, create a new QTHazard for this quadrant which is partially present
102 colliding_edges.map(|edges| QTHazard {
103 qt_bbox: q,
104 presence: QTHazPresence::Partial(QTHazPartial::from_parent(
105 partial_haz,
106 edges,
107 )),
108 hkey: self.hkey,
109 entity: self.entity,
110 })
111 });
112
113 debug_assert!(constricted_hazards.iter().filter(|h| h.is_some()).count() > 0);
114
115 //At this point, we have resolved all quadrants that have edges colliding with them (i.e. `Partial` presence).
116 //What remain are the quadrants without any intersecting edges.
117 //These can either have the hazard `Entire` or `None` presence
118 for i in 0..4 {
119 let quadrant = quadrants[i];
120 if constricted_hazards[i].is_none() {
121 //One important observation is that `Entire` and `None` present hazards will always be separated by a node with `Partial` presence.
122 //If a neighbor is already resolved to `Entire` or `None`, this quadrant will have the same presence.
123 //This saves quite a bit of containment checks.
124
125 let neighbor_presences = Rect::QUADRANT_NEIGHBOR_LAYOUT[i]
126 .map(|idx| constricted_hazards[idx].as_ref().map(|h| &h.presence));
127
128 let none_neighbor = neighbor_presences
129 .iter()
130 .flatten()
131 .any(|p| matches!(p, QTHazPresence::None));
132 let entire_neighbor = neighbor_presences
133 .iter()
134 .flatten()
135 .any(|p| matches!(p, QTHazPresence::Entire));
136
137 let presence = match (none_neighbor, entire_neighbor) {
138 (true, true) => unreachable!(
139 "No unresolved quadrant should not have both None and Entire neighbors, this indicates a bug in the quadtree construction logic."
140 ),
141 (true, false) => QTHazPresence::None,
142 (false, true) => QTHazPresence::Entire,
143 (false, false) => {
144 let colliding = haz_shape.collides_with(&quadrant.centroid());
145 match self.entity.scope() {
146 GeoPosition::Interior if colliding => QTHazPresence::Entire,
147 GeoPosition::Exterior if !colliding => {
148 QTHazPresence::Entire
149 }
150 _ => QTHazPresence::None,
151 }
152 }
153 };
154
155 constricted_hazards[i] = Some(QTHazard {
156 qt_bbox: quadrant,
157 presence,
158 hkey: self.hkey,
159 entity: self.entity,
160 });
161 }
162 }
163
164 constricted_hazards
165 .map(|h| h.expect("all constricted hazards should be resolved"))
166 }
167 }
168 }
169 }
170
171 #[must_use]
172 pub fn n_edges(&self) -> usize {
173 match &self.presence {
174 QTHazPresence::None | QTHazPresence::Entire => 0,
175 QTHazPresence::Partial(partial_haz) => partial_haz.n_edges(),
176 }
177 }
178}