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