From 8012f86b052f550fe6644ec33a2713f381fc4347 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Tomas=20Wenstr=C3=B6m?= Date: Sun, 7 Feb 2021 16:40:58 +0100 Subject: [PATCH] Added a supercover line algorithm for better collision detection --- src/common/geometry.rs | 118 ++++++++++++++++++++++++++++++++++++++++++++++++- src/common/mod.rs | 1 + src/core/level/mod.rs | 61 +++++++++++++++++-------- src/teststate.rs | 51 ++++++++++++++++++++- 4 files changed, 209 insertions(+), 22 deletions(-) diff --git a/src/common/geometry.rs b/src/common/geometry.rs index 455e600..5a115fd 100644 --- a/src/common/geometry.rs +++ b/src/common/geometry.rs @@ -220,7 +220,7 @@ macro_rules! dimen { }; } -#[derive(Debug, Default)] +#[derive(Debug, Default, Copy, Clone, PartialEq)] pub struct Dimension { pub width: T, pub height: T, @@ -242,6 +242,95 @@ impl From<(T, T)> for Dimension { } } +impl From> for (T, T) { + fn from(item: Dimension) -> Self { + (item.width, item.height) + } +} + +//////////////////////////////////////////////////////////////////////////////// + +#[allow(dead_code)] +pub fn supercover_line_int(p1: Point, p2: Point) -> Vec> { + let d = p2 - p1; + let n = point!(d.x.abs(), d.y.abs()); + let step = point!( + if d.x > 0 { 1 } else { -1 }, + if d.y > 0 { 1 } else { -1 } + ); + + let mut p = p1.clone(); + let mut points = vec!(point!(p.x as isize, p.y as isize)); + let mut i = point!(0, 0); + while i.x < n.x || i.y < n.y { + let decision = (1 + 2 * i.x) * n.y - (1 + 2 * i.y) * n.x; + if decision == 0 { // next step is diagonal + p.x += step.x; + p.y += step.y; + i.x += 1; + i.y += 1; + } else if decision < 0 { // next step is horizontal + p.x += step.x; + i.x += 1; + } else { // next step is vertical + p.y += step.y; + i.y += 1; + } + points.push(point!(p.x as isize, p.y as isize)); + } + + points +} + +/// Calculates all points a line crosses, unlike Bresenham's line algorithm. +/// There might be room for a lot of improvement here. +pub fn supercover_line(mut p1: Point, mut p2: Point) -> Vec> { + let mut delta = p2 - p1; + if (delta.x.abs() > delta.y.abs() && delta.x.is_sign_negative()) || (delta.x.abs() <= delta.y.abs() && delta.y.is_sign_negative()) { + std::mem::swap(&mut p1, &mut p2); + delta = -delta; + } + + let mut last = point!(p1.x as isize, p1.y as isize); + let mut coords: Vec> = vec!(); + coords.push(last); + + if delta.x.abs() > delta.y.abs() { + let k = delta.y / delta.x; + let m = p1.y as f64 - p1.x as f64 * k; + for x in (p1.x as isize + 1)..=(p2.x as isize) { + let y = (k * x as f64 + m).floor(); + let next = point!(x as isize - 1, y as isize); + if next != last { + coords.push(next); + } + let next = point!(x as isize, y as isize); + coords.push(next); + last = next; + } + } else { + let k = delta.x / delta.y; + let m = p1.x as f64 - p1.y as f64 * k; + for y in (p1.y as isize + 1)..=(p2.y as isize) { + let x = (k * y as f64 + m).floor(); + let next = point!(x as isize, y as isize - 1); + if next != last { + coords.push(next); + } + let next = point!(x as isize, y as isize); + coords.push(next); + last = next; + } + } + + let next = point!(p2.x as isize, p2.y as isize); + if next != last { + coords.push(next); + } + + coords +} + ////////// TESTS /////////////////////////////////////////////////////////////// #[cfg(test)] @@ -333,4 +422,31 @@ mod tests { panic!(); } } + + #[test] + fn some_coordinates_on_line() { + // horizontally up + let coords = supercover_line(point!(0.0, 0.0), point!(3.3, 2.2)); + assert_eq!(coords.as_slice(), &[point!(0, 0), point!(1, 0), point!(1, 1), point!(2, 1), point!(2, 2), point!(3, 2)]); + + // horizontally down + let coords = supercover_line(point!(0.0, 5.0), point!(3.3, 2.2)); + assert_eq!(coords.as_slice(), &[point!(0, 5), point!(0, 4), point!(1, 4), point!(1, 3), point!(2, 3), point!(2, 2), point!(3, 2)]); + + // vertically right + let coords = supercover_line(point!(0.0, 0.0), point!(2.2, 3.3)); + assert_eq!(coords.as_slice(), &[point!(0, 0), point!(0, 1), point!(1, 1), point!(1, 2), point!(2, 2), point!(2, 3)]); + + // vertically left + let coords = supercover_line(point!(5.0, 0.0), point!(3.0, 3.0)); + assert_eq!(coords.as_slice(), &[point!(5, 0), point!(4, 0), point!(4, 1), point!(3, 1), point!(3, 2), point!(3, 3)]); + + // negative + let coords = supercover_line(point!(0.0, 0.0), point!(-3.0, -2.0)); + assert_eq!(coords.as_slice(), &[point!(-3, -2), point!(-2, -2), point!(-2, -1), point!(-1, -1), point!(-1, 0), point!(0, 0)]); + + // + let coords = supercover_line(point!(0.0, 0.0), point!(2.3, 1.1)); + assert_eq!(coords.as_slice(), &[point!(0, 0), point!(1, 0), point!(2, 0), point!(2, 1)]); + } } diff --git a/src/common/mod.rs b/src/common/mod.rs index 505860d..675d973 100644 --- a/src/common/mod.rs +++ b/src/common/mod.rs @@ -5,6 +5,7 @@ pub use common::geometry::{ Radians, Degrees, Intersection, + supercover_line, }; mod time; diff --git a/src/core/level/mod.rs b/src/core/level/mod.rs index 2a90739..488cae1 100644 --- a/src/core/level/mod.rs +++ b/src/core/level/mod.rs @@ -1,4 +1,4 @@ -use common::{Point, Dimension, Intersection}; +use common::{Point, Dimension, Intersection, supercover_line}; use core::render::Renderer; use sprites::SpriteManager; use std::rc::Rc; @@ -36,23 +36,21 @@ impl Level { let size = dimen!(lvlsize.width / 20, lvlsize.height / 20); // TODO: make sure all walls fit within the grid bounds let cs = point!(lvlsize.width / size.width, lvlsize.height / size.height); //let cs = point!(cell_size.width as f64, cell_size.height as f64); - let mut grid = vec!(vec!(vec!(); size.height); size.width); + let mut grid = Grid { + cells: vec!(vec!(vec!(); size.height); size.width), + size, + cell_size: dimen!(cs.x, cs.y), + }; for wall in walls { for edge in &wall.edges { - // TODO: include cells that this edge overlaps - for p in &[edge.p1, edge.p2] { - let p = point!(p.x as usize, p.y as usize) / cs; - grid[0.max(p.x as usize).min(size.width - 1)][0.max(p.y as usize).min(size.height - 1)].push(Rc::clone(edge)); + for c in grid.grid_coordinates_on_line(edge.p1, edge.p2) { + grid.cells[c.x][c.y].push(Rc::clone(edge)); } } } - Grid { - size, - cell_size: dimen!(cs.x, cs.y), - cells: grid, - } + grid } pub fn render(&mut self, renderer: &mut Renderer, _sprites: &SpriteManager) { @@ -77,6 +75,8 @@ impl Level { for x in 0..self.wall_grid.size.width { for y in 0..self.wall_grid.size.height { if !self.wall_grid.cells[x][y].is_empty() { + let num = self.wall_grid.cells[x][y].len(); + renderer.canvas().set_draw_color((0, 32*num as u8, 0)); renderer.canvas().fill_rect(sdl2::rect::Rect::new( x as i32 * size.width as i32, y as i32 * size.height as i32, @@ -98,14 +98,16 @@ impl Level { } pub fn intersect_walls(&self, p1: Point, p2: Point) -> IntersectResult { - let c = point!(p2.x as isize / self.wall_grid.cell_size.width as isize, p2.y as isize / self.wall_grid.cell_size.height as isize); - if let Some(walls) = self.wall_grid.at(c) { - for w in walls { - if let Intersection::Point(p) = Intersection::lines(p1, p2, w.p1, w.p2) { - let wall = Wall { - edge: Rc::clone(&w), - }; - return IntersectResult::Intersection(wall, p) + for c in self.wall_grid.grid_coordinates_on_line(p1, p2) { + if let walls = &self.wall_grid.cells[c.x][c.y] { + for w in walls { + if let Intersection::Point(p) = Intersection::lines(p1, p2, w.p1, w.p2) { + let wall = Wall { + region: &self.walls[w.region], + edge: Rc::clone(&w), + }; + return IntersectResult::Intersection(wall, p) + } } } } @@ -138,6 +140,27 @@ impl Grid { None } } + + pub fn to_grid_coordinate(&self, c: C) -> Option> + where C: Into<(isize, isize)> + { + let c = c.into(); + if c.0 >= 0 && c.0 < self.size.width as isize && c.1 >= 0 && c.1 < self.size.height as isize { + Some(point!(c.0 as usize, c.1 as usize)) + } else { + None + } + } + + /// Returns a list of grid coordinates that a line in world coordinates passes through. + pub fn grid_coordinates_on_line(&self, p1: Point, p2: Point) -> Vec> { + let scale = (self.cell_size.width as f64, self.cell_size.height as f64); + supercover_line(p1 / scale, p2 / scale) + .iter() + .map(|c| self.to_grid_coordinate(*c)) + .flatten() + .collect() + } } ////////// WALL REGION ///////////////////////////////////////////////////////// diff --git a/src/teststate.rs b/src/teststate.rs index 2f8f240..0a66d82 100644 --- a/src/teststate.rs +++ b/src/teststate.rs @@ -1,20 +1,23 @@ -use common::{Point, Intersection}; +use common::{Dimension, Point, Intersection}; use core::app::{AppState, StateChange}; use core::controller::ControllerManager; +use core::level::Grid; use core::render::Renderer; -use point; // defined in common, but loaded from main... +use {point, dimen}; use sdl2::event::Event; use sprites::SpriteManager; use time::{Duration, Instant}; pub struct TestState { start: Instant, + mouse: Point, } impl TestState { pub fn new() -> TestState { TestState { start: Instant::now(), + mouse: point!(0, 0), } } @@ -67,12 +70,56 @@ impl AppState for TestState { let y2 = ((self.start.elapsed().as_seconds_f64() + std::f64::consts::FRAC_PI_4).sin() * 60.0) as i32; self.draw_intersecting_lines(renderer, (100 + x, 100 + y), (150 + x, 150 + y), (100 + x2, 150 + y2), (150 + x2, 100 + y2)); self.draw_intersecting_lines(renderer, (250 + x, 85 + y), (250 + x, 165 + y), (210 + x2, 125 + y2), (290 + x2, 125 + y2)); + + let grid = Grid { + size: dimen!(10, 10), + cell_size: dimen!(30, 30), + cells: vec!(vec!(false; 10); 10), + }; + + let offset = point!(200, 200); + let size = grid.cell_size; + for x in 0..grid.size.width { + for y in 0..grid.size.height { + let col = (32 + 32 * ((x + y) % 2)) as u8; + renderer.canvas().set_draw_color((col, col, col)); + renderer.canvas().fill_rect(sdl2::rect::Rect::new( + offset.x + x as i32 * size.width as i32, + offset.y + y as i32 * size.height as i32, + size.width as u32, + size.height as u32)).unwrap(); + } + } + + let offsetf = point!(offset.x as f64, offset.y as f64); +// let p1 = point!(23.0, 16.0); + let p1 = point!(300.0 / 2.0, 300.0 / 2.0); + let p2 = { + //let p = point!(78.0*3.0, 54.0*3.0); + let p = self.mouse - offset; + point!(p.x as f64, p.y as f64) + }; + for p in grid.grid_coordinates_on_line(p1, p2) { + renderer.canvas().set_draw_color((0, 96, 0)); + renderer.canvas().fill_rect(sdl2::rect::Rect::new( + offset.x + p.x as i32 * size.width as i32, + offset.y + p.y as i32 * size.height as i32, + size.width as u32, + size.height as u32)).unwrap(); + } + let p1 = p1 + offsetf; + let p2 = self.mouse;//p2 + offsetf; + renderer.draw_line((p1.x as i32, p1.y as i32), (p2.x as i32, p2.y as i32), (255, 255, 0)); } fn leave(&mut self) { } fn handle_event(&mut self, _event: Event) -> Option { + match _event { + Event::MouseMotion { x, y, .. } => self.mouse = point!(x, y), + _ => {} + } None } } -- 2.11.0