collide_tree/
lib.rs

1//! Collide Tree
2//! ============
3//!
4//! The following Test Shows the naive method, and the tree method will get the same results.
5//!
6//! ```rust
7//! use collide_tree::test_util::create_range_list;
8//! use collide_tree::*;
9//! use collide_tree::boxes::*;
10//! use std::cmp::Ordering;
11//!
12//!
13//! let list = create_range_list(1000);
14//!
15//! // NAIVE collision detection
16//! let mut l_col = Vec::new();
17//! for a in 0..(list.len() - 1) {
18//!     for b in (a + 1)..list.len() {
19//!         if list[a].bounds().hits(&list[b].bounds()) {
20//!             l_col.push((a, b));
21//!         }
22//!     }
23//! }
24//! // COLLIDE_TREE collision detection
25//! // The tree is largely expected to be created and filled every frame.
26//! let mut tree = CollideTree::new(Bounds::new(0., 0., 1000., 1000.));
27//!
28//! let mut t_col: Vec<(usize, usize)> = Vec::new();
29//! for a in &list {
30//!     //Collisions are detected as you add items to the tree
31//!     //The closure is called on every collision
32//!     tree.add_item(a.clone(), &mut |a, b| t_col.push((a.id, b.id)));
33//! }
34//!
35//! // Sort so results match on order
36//! t_col.sort_by(|(a1, a2), (b1, b2)| match a1.cmp(b1) {
37//!     Ordering::Equal => a2.cmp(b2),
38//!     v => v,
39//! });
40//!
41//! assert_eq!(l_col.len(), t_col.len());
42//! assert_eq!(l_col, t_col);
43//! ```
44
45use std::fmt::Debug;
46use std::ops::*;
47
48pub mod boxes;
49#[cfg(test)]
50mod test;
51pub mod test_util;
52
53pub trait BoundBox: Sized + Clone {
54    ///Split the box in half somehow, normally this should vary in direction
55    fn split(&self) -> (Self, Self);
56    ///Test if one box collides with another.
57    fn hits(&self, b: &Self) -> bool;
58}
59
60pub trait Located {
61    type Box: BoundBox;
62    fn bounds(&self) -> Self::Box;
63}
64
65pub struct CollideTree<L: Located + Debug> {
66    bound: L::Box,
67    top: Vec<L>,
68    children: Option<Box<(CollideTree<L>, CollideTree<L>)>>,
69}
70
71impl<L: Located + Debug> CollideTree<L> {
72    pub fn new(bound: L::Box) -> Self {
73        CollideTree {
74            bound,
75            top: Vec::new(),
76            children: None,
77        }
78    }
79    pub fn add_item<F: FnMut(&L, &L)>(&mut self, item: L, f: &mut F) {
80        self.grow_children();
81
82        let ib = item.bounds();
83        for t in &self.top {
84            if t.bounds().hits(&ib) {
85                f(&t, &item);
86            }
87        }
88        match &mut self.children {
89            Some(b) => {
90                let (l, r) = b.deref_mut();
91                match (l.bound.hits(&ib), r.bound.hits(&ib)) {
92                    (true, false) => l.add_item(item, f),
93                    (false, true) => r.add_item(item, f),
94                    _ => {
95                        l.check_hits(&item, f);
96                        r.check_hits(&item, f);
97                        self.top.push(item);
98                    }
99                }
100            }
101            None => self.top.push(item),
102        }
103    }
104    pub fn check_hits<F: FnMut(&L, &L)>(&self, item: &L, f: &mut F) {
105        let ib = item.bounds();
106        for t in &self.top {
107            if t.bounds().hits(&ib) {
108                f(&t, &item);
109            }
110        }
111        if let Some(b) = &self.children {
112            let (l, r) = b.deref();
113            if l.bound.hits(&ib) {
114                l.check_hits(item, f);
115            }
116            if r.bound.hits(&ib) {
117                r.check_hits(item, f);
118            }
119        }
120    }
121
122    pub fn grow_children(&mut self) {
123        if let Some(_) = self.children {
124            return;
125        }
126        if self.top.len() < 8 {
127            return;
128        }
129        let (l, r) = self.bound.split();
130
131        let (mut l, mut r) = (Self::new(l), Self::new(r));
132        let mut newtop = Vec::new();
133        std::mem::swap(&mut newtop, &mut self.top);
134        for v in newtop {
135            let ib = v.bounds();
136            match (l.bound.hits(&ib), r.bound.hits(&ib)) {
137                (true, false) => l.top.push(v),
138                (false, true) => r.top.push(v),
139                _ => self.top.push(v),
140            }
141        }
142        self.children = Some(Box::new((l, r)));
143    }
144
145    pub fn for_each_collision<F: FnMut(&L, &L)>(&self, f: &mut F) {
146        if self.top.len() > 0 {
147            for a in 0..self.top.len() - 1 {
148                for b in (a + 1)..self.top.len() {
149                    if self.top[a].bounds().hits(&self.top[b].bounds()) {
150                        f(&self.top[a], &self.top[b])
151                    }
152                }
153            }
154        }
155
156        if let Some(b) = &self.children {
157            let (l, r) = b.deref();
158            for a in &self.top {
159                l.check_hits(a, f);
160                r.check_hits(a, f);
161            }
162            l.for_each_collision(f);
163            r.for_each_collision(f);
164        }
165    }
166}
167
168#[cfg(test)]
169mod tests {
170    #[test]
171    fn it_works() {
172        assert_eq!(2 + 2, 4);
173    }
174}
collide_tree/lib.rs

collide_tree/
lib.rs
