jagua_rs/collision_detection/quadtree/
qt_hazard.rs

1use crate::collision_detection::hazards::Hazard;
2use crate::collision_detection::hazards::HazardEntity;
3use crate::collision_detection::quadtree::qt_partial_hazard::{QTHazPartial, RelevantEdges};
4use crate::geometry::geo_enums::{GeoPosition, GeoRelation};
5use crate::geometry::geo_traits::CollidesWith;
6use crate::geometry::primitives::Rect;
7use crate::geometry::primitives::SPolygon;
8use crate::util::assertions;
9use std::sync::Arc;
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    /// Entity inducing the hazard
17    pub entity: HazardEntity,
18    /// How the hazard is present in the node
19    pub presence: QTHazPresence,
20    /// Whether the hazard is active or not
21    pub active: bool,
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_qt_root(qt_root_bbox: Rect, haz: &Hazard) -> Self {
37        Self {
38            qt_bbox: qt_root_bbox,
39            entity: haz.entity,
40            presence: QTHazPresence::Partial(QTHazPartial {
41                shape: haz.shape.clone(),
42                edges: RelevantEdges::All,
43            }),
44            active: haz.active,
45        }
46    }
47
48    /// Returns the resulting QTHazards after constricting to the provided quadrants.
49    /// The quadrants should be ordered according to the [Cartesian system](https://en.wikipedia.org/wiki/Quadrant_(plane_geometry))
50    /// and should all be inside the bounds from which `self` was created.
51    pub fn constrict(&self, quadrants: [Rect; 4]) -> [Self; 4] {
52        debug_assert!(
53            quadrants
54                .iter()
55                .all(|q| self.qt_bbox.relation_to(*q) == GeoRelation::Surrounding)
56        );
57        debug_assert!(assertions::quadrants_have_valid_layout(&quadrants));
58
59        match &self.presence {
60            QTHazPresence::None => unreachable!(),
61            QTHazPresence::Entire => [0, 1, 2, 3].map(|_| self.clone()),
62            QTHazPresence::Partial(partial_haz) => {
63                //If the hazard is partially present, it may produce different hazards for each quadrant
64
65                //check the bbox of the hazard with the bboxes of the quadrants
66                let haz_bbox = partial_haz.shape.bbox;
67
68                //Check if one of the quadrants entirely contains the hazard
69                let enclosed_hazard_quadrant = quadrants
70                    .iter()
71                    .map(|q| haz_bbox.relation_to(*q))
72                    .position(|r| r == GeoRelation::Enclosed);
73
74                if let Some(quad_index) = enclosed_hazard_quadrant {
75                    //The hazard is entirely enclosed within one quadrant,
76                    //For this quadrant the QTHazard is equivalent to the original hazard, the rest are None
77                    [0, 1, 2, 3].map(|i| {
78                        let presence = match i {
79                            i if i == quad_index => QTHazPresence::Partial(partial_haz.clone()),
80                            _ => QTHazPresence::None,
81                        };
82                        Self {
83                            qt_bbox: quadrants[i],
84                            entity: self.entity,
85                            presence,
86                            active: self.active,
87                        }
88                    })
89                } else {
90                    //The hazard is partially active in multiple quadrants, find which ones
91                    let arc_shape = &partial_haz.shape;
92
93                    //For every quadrant, check which of the edges of the hazard are relevant
94                    let mut constricted_hazards = quadrants.map(|q| {
95                        compute_edge_collisions_in_quadrant(q, &partial_haz.edges, arc_shape).map(
96                            |p_haz| {
97                                //The quadrant has collisions with the hazard edges
98                                //For these quadrants we can be sure they will be of Partial presence
99                                QTHazard {
100                                    qt_bbox: q,
101                                    entity: self.entity,
102                                    presence: QTHazPresence::Partial(p_haz),
103                                    active: self.active,
104                                }
105                            },
106                        )
107                    });
108
109                    debug_assert!(constricted_hazards.iter().filter(|h| h.is_some()).count() > 0);
110
111                    //At this point, we know which quadrants have collisions with which edges.
112                    //What remain are the quadrants without any intersecting edges.
113                    //These can either have the hazard entirely present or entirely absent.
114                    for i in 0..4 {
115                        let quadrant = quadrants[i];
116                        if constricted_hazards[i].is_none() {
117                            //Presence of Entire and None type are always separated by a node with Partial presence.
118                            //If a neighbor is already resolved to Entire or None, this quadrant will have the same presence.
119                            let [neighbor_0, neighbor_1] = Rect::QUADRANT_NEIGHBOR_LAYOUT[i];
120                            let presence_n0 = constricted_hazards[neighbor_0]
121                                .as_ref()
122                                .map(|h| &h.presence);
123                            let presence_n1 = constricted_hazards[neighbor_1]
124                                .as_ref()
125                                .map(|h| &h.presence);
126
127                            let presence = match (presence_n0, &presence_n1) {
128                                (Some(QTHazPresence::None), Some(QTHazPresence::Entire))
129                                | (Some(QTHazPresence::Entire), Some(QTHazPresence::None)) => {
130                                    unreachable!(
131                                        "one of the neighbors is Entire, the other is None, this quadrant should be Partial"
132                                    )
133                                }
134                                (Some(QTHazPresence::Entire), _) => QTHazPresence::Entire,
135                                (_, Some(QTHazPresence::Entire)) => QTHazPresence::Entire,
136                                (Some(QTHazPresence::None), _) => QTHazPresence::None,
137                                (_, Some(QTHazPresence::None)) => QTHazPresence::None,
138                                _ => {
139                                    //Neither of its neighbors is resolved, check its position.
140                                    let haz_scope = self.entity.scope();
141                                    //Since partial presence is not possible, checking whether the center of the quadrant collides or not suffices
142                                    let colliding = arc_shape.collides_with(&quadrant.centroid());
143                                    match (haz_scope, colliding) {
144                                        (GeoPosition::Interior, true) => QTHazPresence::Entire,
145                                        (GeoPosition::Exterior, false) => QTHazPresence::Entire,
146                                        _ => QTHazPresence::None,
147                                    }
148                                }
149                            };
150
151                            constricted_hazards[i] = Some(QTHazard {
152                                qt_bbox: quadrant,
153                                entity: self.entity,
154                                presence,
155                                active: self.active,
156                            });
157                        }
158                    }
159
160                    constricted_hazards
161                        .map(|h| h.expect("all constricted hazards should be resolved"))
162                }
163            }
164        }
165    }
166
167    pub fn n_edges(&self) -> usize {
168        match &self.presence {
169            QTHazPresence::None | QTHazPresence::Entire => 0,
170            QTHazPresence::Partial(partial_haz) => partial_haz.n_edges(),
171        }
172    }
173}
174
175fn compute_edge_collisions_in_quadrant(
176    quadrant: Rect,
177    relevant_edges: &RelevantEdges,
178    shape: &Arc<SPolygon>,
179) -> Option<QTHazPartial> {
180    let mut p_haz = None;
181
182    let mut check_edge = |idx| {
183        let edge = shape.edge(idx);
184        if quadrant.collides_with(&edge) {
185            p_haz
186                .get_or_insert(QTHazPartial {
187                    shape: shape.clone(),
188                    edges: RelevantEdges::Some(vec![]),
189                })
190                .register_edge(idx);
191        }
192    };
193
194    match relevant_edges {
195        RelevantEdges::All => {
196            for i in 0..shape.n_vertices() {
197                check_edge(i);
198            }
199        }
200        RelevantEdges::Some(indices) => {
201            for &i in indices {
202                check_edge(i);
203            }
204        }
205    }
206
207    p_haz
208}
jagua_rs/collision_detection/quadtree/qt_hazard.rs

jagua_rs/collision_detection/quadtree/
qt_hazard.rs
