bump_rs/
lib.rs

1use std::collections::{HashMap, HashSet};
2use generational_arena::{Arena, Index};
3use nalgebra::Vector2;
4
5#[derive(Copy, Clone)]
6pub enum CollisionResponse{
7    Touch,
8    Cross,
9    Slide,
10    Bounce,
11}
12impl CollisionResponse{
13    pub fn response<T>(self, world: &World<T>, collision: &Collision, collisions: Vec<Collision>, item: Index, rect: Rectangle, mut goal: Vec2f, filter: impl Fn(Index) -> bool, collider: impl Fn(Index, &T, &RectCollision) -> Option<CollisionResponse>) -> (Vec2f, Vec<Collision>){
14        match self{
15            CollisionResponse::Touch => {
16                (collision.info.touch, Vec::new())
17            }
18            CollisionResponse::Cross => {
19                //original uses another world.project, maybe this causes invalid behaviour?
20                (goal, collisions)
21            }
22            CollisionResponse::Slide => {
23                if collision.info.movement.magnitude_squared() != 0.{
24                    if collision.info.normal.x != 0.{
25                        goal.x = collision.info.touch.x;
26                    } else {
27                        goal.y = collision.info.touch.y;
28                    }
29                }
30                (goal, world.project(item, Rectangle{
31                    position: collision.info.touch,
32                    size: rect.size,
33                }, goal, filter, collider))
34            }
35            CollisionResponse::Bounce => {
36                goal = if collision.info.movement.magnitude_squared() != 0.{
37                    let mut bn = goal - collision.info.touch;
38                    if collision.info.normal.x == 0.{
39                        bn.y *= -1.;
40                    } else {
41                        bn.x *= -1.;
42                    }
43                    collision.info.touch + bn
44                } else {
45                    collision.info.touch
46                };
47                (goal, world.project(item, Rectangle{
48                    position: collision.info.touch,
49                    size: rect.size,
50                }, goal, filter, collider))
51            }
52        }
53    }
54}
55fn nearest_number(x: f64, a: f64, b: f64) -> f64{
56    if (a-x).abs() < (b-x).abs() {a} else {b}
57}
58const DELTA: f64 = 1e-10;
59pub type Vec2f = Vector2<f64>;
60#[derive(Copy, Clone)]
61pub struct Rectangle{
62    pub position: Vec2f,
63    pub size: Vec2f,
64}
65impl Rectangle{
66    pub fn end(self) -> Vec2f{
67        self.position + self.size
68    }
69    fn nearest_corner(self, point: Vec2f) -> Vec2f{
70        Vec2f::new(nearest_number(point.x, self.position.x, self.end().x), nearest_number(point.y, self.position.y, self.end().y))
71    }
72    fn mink_diff(self, other: Rectangle) -> Rectangle{
73        Rectangle{
74            position: Vec2f::new(other.position.x-self.position.x-self.size.x, other.position.y-self.position.y-self.size.y),
75            size: Vec2f::new(self.size.x + other.size.x, self.size.y + other.size.y)
76        }
77    }
78    pub fn contains_point(self, point: Vec2f) -> bool{
79        point.x - self.position.x > DELTA && point.y - self.position.y > DELTA &&
80            self.end().x - point.x > DELTA && self.end().y - point.y > DELTA
81    }
82    pub fn intersects(self, other: Rectangle) -> bool{
83        self.position.x < other.end().x && other.position.x < self.end().x &&
84        self.position.y < other.end().y && other.position.y < self.end().y
85    }
86    fn squared_distance(self, other: Rectangle) -> f64{
87        Vec2f::new(
88            self.position.x - other.position.x + (self.size.x-other.size.x)/2.,
89            self.position.y - other.position.y + (self.size.y-other.size.y)/2.,
90        ).magnitude_squared()
91    }
92    fn segment_intersection_indices(self, p1: Vec2f, p2: Vec2f, mut ti1: f64, mut ti2: f64) -> Option<(f64, f64,Vec2f,Vec2f)>{
93        let (dx,dy) = (p2.x-p1.x, p2.y-p1.y);
94        let mut n1 = Vec2f::new(0., 0.);
95        let mut n2 = Vec2f::new(0., 0.);
96        for (n,p,q) in [
97            (Vec2f::new(-1.,0.),-dx, p1.x-self.position.x),
98            (Vec2f::new(1.,0.),dx, self.end().x - p1.x),
99            (Vec2f::new(0., -1.),-dy, p1.y-self.position.y),
100            (Vec2f::new(0., 1.),dy, self.end().y - p1.y),
101        ]{
102            if p == 0. {
103                if q <= 0. {return None;}
104            } else {
105                let r = q / p;
106                if p < 0.{
107                    if r > ti2 {return None;}
108                    else if r > ti1 {
109                        ti1 = r;
110                        n1 = n;
111                    }
112                } else {
113                    if r < ti1 {return None;}
114                    else if r < ti2 {
115                        ti2 = r;
116                        n2 = n;
117                    }
118                }
119            }
120        }
121        Some((ti1, ti2, n1, n2))
122    }
123    pub fn detect_collision(self, other: Rectangle, goal: Vec2f) -> Option<RectCollision>{
124        let d = Vec2f::new(goal.x - self.position.x, goal.y - self.position.y);
125        let diff_rect = self.mink_diff(other);
126        let overlaps;
127        let ti;
128        let n;
129        let t;
130        if diff_rect.contains_point(Vec2f::new(0.0, 0.0)){
131            let corner = diff_rect.nearest_corner(Vec2f::new(0.0, 0.0));
132            let (wi, hi) = (self.size.x.min(corner.x.abs()), self.size.y.min(corner.y.abs()));
133            ti = -wi * hi;
134            overlaps = true;
135            if d.magnitude_squared() == 0. {
136                let mut p = diff_rect.nearest_corner(Vec2f::new(0., 0.));
137                if p.x.abs() < p.y.abs() {
138                    p.y = 0.;
139                } else {
140                    p.x = 0.;
141                }
142                n = Vec2f::new(p.x.signum(), p.y.signum());
143                t = Vec2f::new(self.position.x + p.x, self.position.y + p.y);
144            } else {
145                if let Some((ti1, _, n2, _)) = diff_rect.segment_intersection_indices(Vec2f::new(0., 0.), d, -f64::INFINITY, 1.){
146                    n = n2;
147                    t = Vec2f::new(self.position.x + d.x * ti1, self.position.y + d.y * ti1);
148                } else {
149                    return None;
150                }
151            }
152        } else {
153            if let Some((ti1, ti2, n1, _)) = diff_rect.segment_intersection_indices(Vec2f::new(0., 0.), d, -f64::INFINITY, f64::INFINITY) {
154                if ti1 < 1. && (ti1-ti2).abs() >= DELTA && (0. < ti1 + DELTA || 0. == ti1 && ti2 > 0.){
155                    ti = ti1;
156                    n = n1;
157                    overlaps = false;
158                    t = Vec2f::new(self.position.x + d.x * ti, self.position.y + d.y * ti);
159                } else {
160                    return None;
161                }
162            } else {
163                return None;
164            }
165        }
166        Some(RectCollision{
167            overlaps,
168            ti,
169            movement: d,
170            normal: n,
171            touch: t,
172            item_rect: self,
173            other_rect: other,
174        })
175    }
176}
177#[derive(Copy, Clone)]
178pub struct RectCollision{
179    pub overlaps: bool,
180    pub ti: f64,
181    pub movement: Vec2f,
182    pub normal: Vec2f,
183    pub touch: Vec2f,
184    pub item_rect: Rectangle,
185    pub other_rect: Rectangle,
186}
187#[derive(Copy, Clone)]
188pub struct Collision{
189    pub info: RectCollision,
190    pub item: ItemId,
191    pub other: ItemId,
192    pub response_type: CollisionResponse,
193}
194pub struct World<T>{
195    items: Arena<WorldItem<T>>,
196    cells: HashMap<CellIndex, Vec<Index>>,
197    grid: CellGrid,
198}
199impl<T> World<T>{
200    pub fn new() -> Self{
201        Self::with_cell_size(64.)
202    }
203    pub fn with_cell_size(cell_size: f64) -> Self{
204        World{
205            items: Arena::new(),
206            cells: HashMap::new(),
207            grid: CellGrid{
208                cell_size,
209            },
210        }
211    }
212    pub fn get_item(&self, item: ItemId) -> Option<&T>{
213        self.items.get(item.0).map(|i|&i.data)
214    }
215    pub fn get_rect(&self, item: ItemId) -> Option<Rectangle>{
216        self.items.get(item.0).map(|i|i.rect)
217    }
218    pub fn get_item_mut(&mut self, item: ItemId) -> Option<&mut T>{
219        self.items.get_mut(item.0).map(|i|&mut i.data)
220    }
221    pub fn contains(&self, item: ItemId) -> bool{
222        self.items.contains(item.0)
223    }
224    pub fn query_rect(&self, rect: Rectangle) -> Vec<ItemId> {
225        let mut query = HashSet::new();
226        for cell_index in self.grid.cell_rect(rect).into_iter() {
227            if let Some(cell) = self.cells.get(&cell_index) {
228                for other in cell {
229                    if rect.intersects(self.get_rect(ItemId(*other)).unwrap()){
230                        query.insert(ItemId(*other));
231                    }
232                }
233            }
234        }
235        query.into_iter().collect()
236    }
237    pub fn query_point(&self, point: Vec2f) -> Vec<ItemId>{
238        let mut query = Vec::new();
239        if let Some(cell) = self.cells.get(&self.grid.to_cell(point)){
240            for other in cell {
241                if self.get_rect(ItemId(*other)).unwrap().contains_point(point) {
242                    query.push(ItemId(*other));
243                }
244            }
245        }
246        query
247    }
248    pub fn query_line_segment(&self, start: Vec2f, end: Vec2f) -> Vec<LineSegmentQuery>{
249        let mut query = Vec::new();
250        let mut visited = HashSet::new();
251        let d = end - start;
252        self.grid.traverse(start, end, |cell_index|{
253            if let Some(cell) = self.cells.get(&cell_index){
254                for other in cell {
255                    if visited.insert(*other) {
256                        let rect = self.get_rect(ItemId(*other)).unwrap();
257                        if let Some((ti1, ti2, _, _)) = rect.segment_intersection_indices(start, end, 0., 1.){
258                            if (0. < ti1 && ti1 < 1.) || (0. < ti2 && ti2 < 1.){
259                                let (tii0, tii1, _, _) = rect.segment_intersection_indices(start, end, -f64::INFINITY, f64::INFINITY).unwrap();
260                                query.push((LineSegmentQuery{
261                                    item: ItemId(*other),
262                                    ti1,
263                                    ti2,
264                                    p1: start + d * ti1,
265                                    p2: start + d * ti2,
266                                }, tii0.min(tii1)));
267                            }
268                        }
269                    }
270                }
271            }
272        });
273        query.sort_by(|q1, q2|q1.1.total_cmp(&q2.1));
274        query.into_iter().map(|q|q.0).collect()
275    }
276    pub fn add(&mut self, item: T, rect: Rectangle) -> ItemId{
277        let index = self.items.insert(WorldItem{
278            data: item,
279            rect,
280        });
281        for cell in self.grid.cell_rect(rect).into_iter(){
282            self.add_item_to_cell(cell, index);
283        }
284        ItemId(index)
285    }
286    pub fn remove(&mut self, index: ItemId) -> Option<(T, Rectangle)>{
287        match self.items.remove(index.0){
288            Some(world_item) => {
289                for cell in self.grid.cell_rect(world_item.rect).into_iter(){
290                    self.remove_item_from_cell(cell, index.0);
291                }
292                Some((world_item.data, world_item.rect))
293            }
294            None => None,
295        }
296    }
297    pub fn update(&mut self, index: ItemId, new_rect: Rectangle) -> Option<Rectangle>{
298        let old_rect = self.get_rect(index)?;
299        let new_rect_cells = self.grid.cell_rect(new_rect);
300        let old_rect_cells = self.grid.cell_rect(old_rect);
301        if new_rect_cells != old_rect_cells{
302            //todo: unoptimal
303            let new_cells = new_rect_cells.into_iter().collect::<HashSet<_>>();
304            let old_cells = old_rect_cells.into_iter().collect::<HashSet<_>>();
305            for add_cells in new_cells.difference(&old_cells){
306                self.add_item_to_cell(*add_cells, index.0);
307            }
308            for remove_cells in old_cells.difference(&new_cells){
309                self.remove_item_from_cell(*remove_cells, index.0);
310            }
311        }
312        self.items.get_mut(index.0).unwrap().rect = new_rect;
313        Some(old_rect)
314    }
315    pub fn update_position(&mut self, index: ItemId, new_position: Vec2f) -> Option<Vec2f>{
316        self.update(index, Rectangle{
317            position: new_position,
318            size: self.get_rect(index).unwrap().size,
319        }).map(|rect|rect.position)
320    }
321    pub fn check(&self, index: ItemId, mut goal: Vec2f, collider: impl Fn(ItemId, &T, &RectCollision) -> Option<CollisionResponse>) -> Option<(Vec2f, Vec<Collision>)>{
322        let mut visited = HashSet::new();
323        let rect = self.get_rect(index)?;
324        let mut collisions = Vec::new();
325        let mut projected_collisions = self.project(index.0, rect, goal, |index|!visited.contains(&index), |item, data, info|collider(ItemId(item), data, info));
326        while projected_collisions.len() > 0{
327            let collision = projected_collisions.remove(0);
328            collisions.push(collision);
329            visited.insert(collision.other.0);
330            (goal, projected_collisions) = collision.response_type.response(self, &collision, projected_collisions, index.0, rect, goal, |index|!visited.contains(&index), |item, data, info|collider(ItemId(item), data, info));
331        }
332        Some((goal, collisions))
333    }
334    pub fn move_item(&mut self, index: ItemId, goal: Vec2f, collider: impl Fn(ItemId, &T, &RectCollision) -> Option<CollisionResponse>) -> Option<(Vec2f, Vec<Collision>)>{
335        let checked = self.check(index, goal, collider)?;
336        self.update(index, Rectangle{
337            position: checked.0,
338            size: self.get_rect(index).unwrap().size,
339        });
340        Some(checked)
341    }
342    fn add_item_to_cell(&mut self, cell: CellIndex, item: Index) {
343        self.cells.entry(cell).or_insert_with(Vec::new).push(item);
344    }
345    fn remove_item_from_cell(&mut self, cell: CellIndex, item: Index){
346        let remove = if let Some(cell) = self.cells.get_mut(&cell){
347            let index = cell.iter().position(|&x| x == item).expect("item not found");
348            cell.remove(index);
349            cell.is_empty()
350        } else {
351            panic!("Tried to remove item from cell that does not exist");
352        };
353        if remove {
354            self.cells.remove(&cell);
355        }
356    }
357    fn project(&self, item: Index, rect: Rectangle, goal: Vec2f, filter: impl Fn(Index) -> bool, collider: impl Fn(Index, &T, &RectCollision) -> Option<CollisionResponse>) -> Vec<Collision>{
358        let mut collisions = Vec::new();
359        let mut visited = HashSet::new();
360        visited.insert(item);
361        let cr = self.grid.cell_rect(Rectangle{
362            position: Vec2f::new(goal.x.min(rect.position.x), goal.y.min(rect.position.y)),
363            size: Vec2f::new((goal.x+rect.size.x).max(rect.end().x), (goal.y+rect.size.y).max(rect.end().y)),
364        });
365        for cell_index in cr.into_iter(){
366            if let Some(cell) = self.cells.get(&cell_index){
367                for other in cell{
368                    if visited.insert(*other) && filter(*other){
369                        let other_rect = self.items.get(*other).unwrap().rect;
370                        if let Some(collision) = rect.detect_collision(other_rect, goal) {
371                            let response = collider(*other, self.get_item(ItemId(*other)).unwrap(), &collision);
372                            if let Some(response) = response {
373                                collisions.push(Collision {
374                                    info: collision,
375                                    item: ItemId(item),
376                                    other: ItemId(*other),
377                                    response_type: response,
378                                })
379                            }
380                        }
381                    }
382                }
383            }
384        }
385        collisions.sort_by(|a, b| {
386            if a.info.ti == b.info.ti{
387                let ad = a.info.item_rect.squared_distance(a.info.other_rect);
388                let bd = a.info.item_rect.squared_distance(b.info.other_rect);
389                ad.total_cmp(&bd)
390            } else {
391                a.info.ti.total_cmp(&b.info.ti)
392            }
393        });
394        collisions
395    }
396}
397#[derive(Copy, Clone)]
398pub struct LineSegmentQuery{
399    pub item: ItemId,
400    pub ti1: f64,
401    pub ti2: f64,
402    pub p1: Vec2f,
403    pub p2: Vec2f,
404}
405#[derive(Copy, Clone, Hash, Eq, PartialEq)]
406pub struct ItemId(Index);
407#[derive(Copy, Clone)]
408struct CellGrid{
409    cell_size: f64,
410}
411impl CellGrid{
412    fn to_cell(self, pos: Vec2f) -> CellIndex{
413        CellIndex{
414            x: (pos.x / self.cell_size).floor() as i32,
415            y: (pos.y / self.cell_size).floor() as i32,
416        }
417    }
418    fn traverse_init_step(self, ct: f64, t1: f64, t2: f64) -> (i32, f64, f64){
419        let v = t2 - t1;
420        if v > 0. {
421            (1, self.cell_size / v, ((ct + v + 1.) * self.cell_size - t1) / v)
422        } else if v < 0. {
423            (-1, -self.cell_size / v, ((ct + v) * self.cell_size - t1) / v)
424        } else {
425            (0, f64::INFINITY, f64::INFINITY)
426        }
427    }
428    fn traverse(self, p1: Vec2f, p2: Vec2f, mut f: impl FnMut(CellIndex)){
429        let mut c1 = self.to_cell(p1);
430        let c2 = self.to_cell(p2);
431        let (step_x, dx, mut tx) = self.traverse_init_step(c1.x as f64, p1.x, p2.x);
432        let (step_y, dy, mut ty) = self.traverse_init_step(c1.y as f64, p1.y, p2.y);
433        f(c1);
434        while (c1.x-c2.x).abs() + (c1.y-c2.y).abs() > 1{
435            if tx < ty{
436                tx += dx;
437                c1.x += step_x;
438            } else {
439                if tx == ty{
440                    f(CellIndex{x: c1.x + step_x, y: c1.y});
441                }
442                ty += dy;
443                c1.y += step_y;
444            }
445            f(c1);
446        }
447        if c1 != c2 {
448            f(c2);
449        }
450    }
451    fn cell_rect(self, rect: Rectangle) -> CellRectangle{
452        let c = self.to_cell(rect.position);
453        let s = CellIndex{x: (rect.end().x/self.cell_size).ceil() as i32, y: (rect.end().y/self.cell_size).ceil() as i32};
454        CellRectangle{
455            position: c,
456            size: CellIndex{x: s.x-c.x, y: s.y-c.y},
457        }
458    }
459}
460#[derive(Copy, Clone, PartialEq, Eq, Hash)]
461struct CellIndex{
462    x: i32,
463    y: i32,
464}
465#[derive(Copy, Clone, PartialEq)]
466struct CellRectangle{
467    position: CellIndex,
468    size: CellIndex,
469}
470impl IntoIterator for CellRectangle{
471    type Item = CellIndex;
472    type IntoIter = CellRectangleIter;
473    fn into_iter(self) -> Self::IntoIter {
474        CellRectangleIter{
475            rect: self,
476            x: self.position.x,
477            y: self.position.y,
478        }
479    }
480}
481struct CellRectangleIter{
482    rect: CellRectangle,
483    x: i32,
484    y: i32,
485}
486impl Iterator for CellRectangleIter{
487    type Item = CellIndex;
488    fn next(&mut self) -> Option<CellIndex> {
489        if self.y >= self.rect.end().y{
490            return None;
491        }
492        let return_value = CellIndex{x: self.x, y: self.y};
493        self.x += 1;
494        if self.x >= self.rect.end().x{
495            self.x = self.rect.position.x;
496            self.y += 1;
497        }
498        Some(return_value)
499    }
500}
501impl CellRectangle{
502    fn end(self) -> CellIndex{
503        CellIndex{
504            x: self.position.x + self.size.x,
505            y: self.position.y + self.size.y,
506        }
507    }
508}
509struct WorldItem<T>{
510    data: T,
511    rect: Rectangle,
512}
bump_rs/lib.rs

bump_rs/
lib.rs
