17 stable releases
Uses old Rust 2015
2.0.5 | May 14, 2023 |
---|---|
2.0.4 | Nov 21, 2016 |
1.3.3 | Nov 17, 2016 |
1.2.3 | Oct 15, 2016 |
#106 in Simulation
47 downloads per month
Used in tilenet_ren
42KB
693 lines
TileNet
This library provides simple tile-based collision detection with custom collision resolution. It also provides some helper methods to make it easier to use.
Documentation
Please run cargo doc --open
to view the documentation.
lib.rs
:
TileNet
holds integer aligned tiles for broad phase continuous collision detection.
The purpose of TileNet
is to have a solid, tile-based, continuous, simple collision
library for aspiring game programmers.
How it works
The library is built on the DDA Supercover algorithm, which is an extension of Bresenham's algorithm. For each moving vertex it creates a line. Each line's overlapping tiles are reported. Your dynamic object decides how it should move. It may adjust speed, and retry the collision. It may also accept and move.
Limitations
The library will experience problems with huge coordinates. This is because adding a small increment to a floating point above 2^24 may not register at all. Precision becomes worse as you approach 2^24. The technical reason is that a 32-bit float has 24 bits in its mantissa. You do not need to worry about floating point errors, as the library ensures consistency by checking end-points.
Examples - Setting Up
We start out by including tile net into our program and creating an empty net
extern crate tile_net;
use tile_net::*;
fn main() {
let net: TileNet<usize> = TileNet::new(10, 10);
println!["{:?}", net];
}
This creates a TileNet
that contains usize
as its elements.
All tiles are initialized to Default
of usize
.
You can now edit various tiles:
extern crate tile_net;
use tile_net::*;
fn main() {
let mut net: TileNet<usize> = TileNet::new(10, 10);
net.set(&1, (9, 0));
println!["{:?}", net];
}
There are several helper functions so you can easily draw something interesting
extern crate tile_net;
use tile_net::*;
fn main() {
let mut net: TileNet<usize> = TileNet::new(10, 10);
net.set_row(&1, 0);
net.set_row(&1, 9);
net.set_col(&1, 0);
net.set_col(&1, 9);
net.set_box(&1, (3, 3), (5, 7));
println!["{:?}", net];
}
You can use any element in TileNet
as long as it has the following traits:
extern crate tile_net;
use tile_net::*;
#[derive(Clone, Debug, Default)]
struct Example(i32);
fn main() {
let mut net: TileNet<Example> = TileNet::new(10, 10); // Requires Default trait
net.set_row(&Example(1), 0); // Requires Clone trait
net.set_row(&Example(2), 9);
net.set_col(&Example(3), 0);
net.set_col(&Example(4), 9);
net.set_box(&Example(5), (3, 3), (5, 7));
println!["{:?}", net]; // Requires Debug trait
}
Collision Detection
TileNet
is not used for drawing tiles to a grid, its main focus is continuous, tile-vertex
collision detection.
Continuous collision detection (CCD) prevents objects tunneling through other objects in a
frame. This happens
when we only check the beginning and end points of an object's movement. This library
interpolates on each
tile. So every intermediate tile is checked. Let's see an example.
extern crate tile_net;
use tile_net::*;
fn main() {
let mut net: TileNet<usize> = TileNet::new(10, 10);
net.set_row(&1, 0);
net.set_row(&2, 9);
net.set_col(&3, 0);
net.set_col(&4, 9);
net.set_box(&5, (3, 3), (5, 7));
println!["{:?}", net];
// We create a new object with speed (100, 100) and check where our collision points will be!
let mut collider = MyObject::new();
let supercover = collider.tiles(); // This is the supercover of the current movement
// in the grid, it just returns integer points of every tile that collider touches
let tiles = net.collide_set(supercover);
if collider.resolve(tiles, &mut ()) {
println!["Able to move"];
} else {
println!["Unable to move"];
}
}
#[derive(Debug)]
struct MyObject {
pts: Vec<(f32, f32)>,
pos: Vector,
mov: Vector,
}
impl MyObject {
fn new() -> MyObject {
MyObject {
// These are the points in object-space
pts: vec![(0.0, 0.0), (1.0, 0.0), (0.0, 1.0), (1.0, 1.0)],
// The current position of the object
pos: Vector(1.1, 1.1),
// The movement vector
mov: Vector(100.0, 100.0),
}
}
}
impl Collable<usize, ()> for MyObject {
// This function returns the vertices of the object
// The points are used by the collision engine to create a set of
// lines from the beginning to the end of the frame.
fn points<'a>(&'a self) -> Points<'a> {
Points::new(self.pos, &self.pts)
}
// The physics engine uses this function in conjunction with points to compute
// the lines - and thus - tiles it will iterate over during a collision test.
fn queued(&self) -> Vector {
self.mov
}
// Here is where your magic happens!
// You will be given a TileSet, which contains all tiles which your object
// collides between the current frame jump.
// The tiles given are in nearest-order, so the first tiles you get from the
// iterator are always the ones you will collide with first.
fn resolve<'a, I>(&mut self, mut set: TileSet<'a, usize, I>, _state: &mut ()) -> bool
where I: Iterator<Item = (i32, i32)>
{
if set.all(|x| *x == 0) { // If there is no collision (we only collide with non-zero tiles)
self.pos = self.pos + self.mov;
self.mov = Vector(0.0, 0.0);
true
} else if self.mov.norm2sq() > 1e-6 { // There was collision, but our speed isn't tiny
self.mov.scale(0.9);
false
} else { // This may happen if we generate a world where we're stuck in a tile,
// normally this will never happen, this library can preserve consistency
// perfectly.
true
}
}
}
What you can do with resolve
is to run it in a loop. After scaling down the movement vector
sufficiently in resolve
, you may end up with a TileSet
that does not cause collision.
This is how we can almost perfectly find the position.
You may employ other methods inside resolve. Whatever suits your needs.
Here is the example again but this time we resolve the collision using a loop
extern crate tile_net;
use tile_net::*;
fn main() {
let mut net: TileNet<usize> = TileNet::new(10, 10);
net.set_row(&1, 0);
net.set_row(&2, 9);
net.set_col(&3, 0);
net.set_col(&4, 9);
net.set_box(&5, (3, 3), (5, 7));
println!["{:?}", net];
// Movement vector is (100, 100), which is way outside the box
let mut collider = MyObject::new();
loop {
let supercover = collider.tiles();
let tiles = net.collide_set(supercover);
if collider.resolve(tiles, &mut ()) {
println!["Able to move"];
break;
} else {
println!["Unable to move"];
}
}
// We are interested in the final position!
println!["{:?}", collider];
}
#[derive(Debug)]
struct MyObject {
pts: Vec<(f32, f32)>,
pos: Vector,
mov: Vector,
}
impl MyObject {
fn new() -> MyObject {
MyObject {
pts: vec![(0.0, 0.0), (1.0, 0.0), (0.0, 1.0), (1.0, 1.0)],
pos: Vector(1.1, 1.1),
mov: Vector(100.0, 100.0),
}
}
}
impl Collable<usize, ()> for MyObject {
// This function returns the vertices of the object
// The points are used by the collision engine to create a set of
// lines from the beginning to the end of the frame.
fn points<'a>(&'a self) -> Points<'a> {
Points::new(self.pos, &self.pts)
}
// The physics engine uses this function in conjunction with points to compute
// the lines - and thus - tiles it will iterate over during a collision test.
fn queued(&self) -> Vector {
self.mov
}
// Here is where your magic happens!
// You will be given a TileSet, which contains all tiles which your object
// collides between the current frame jump.
// The tiles given are in nearest-order, so the first tiles you get from the
// iterator are always the ones you will collide with first.
fn resolve<'a, I>(&mut self, mut set: TileSet<'a, usize, I>, _state: &mut ()) -> bool
where I: Iterator<Item = (i32, i32)>
{
if set.all(|x| *x == 0) { // If there is no collision (we only collide with non-zero tiles)
self.pos = self.pos + self.mov;
self.mov = Vector(0.0, 0.0);
true // Means we resolved correctly
} else if self.mov.norm2sq() > 1e-6 { // There was collision, but our speed isn't tiny
self.mov.scale(0.9);
false // Means we did not resolve collision
} else {
true
}
}
}
You can try to use more nuanced methods instead of scaling down and checking again. One method may be to check the first collision point and scale down to the distance thereof. Everything is iterator based.
TileView
For drawing you may want to avoid sending huge grids to the GPU, so we use a view from the grid.
extern crate tile_net;
use tile_net::*;
fn main() {
let mut net: TileNet<usize> = TileNet::new(10, 10);
net.set_row(&1, 0);
net.set_row(&2, 9);
net.set_col(&3, 0);
net.set_col(&4, 9);
net.set_box(&5, (3, 3), (5, 7));
println!["{:?}", net];
// This creates a box with x from 0 to 4 and y from 3 to 6
// Note that the last elements are not included (so for x: 0, 1, 2, 3, but not 4)
for element in net.view_box((0, 4, 3, 6)) {
let (value, col, row) = element;
// Draw here!
println!["{}-{} = {}", row, col, value];
}
// This just prints every single element in the net
for element in net.view_all() {
let (value, col, row) = element;
// Draw here!
println!["{}-{} = {}", row, col, value];
}
// Looks from (0, 1) to (6, 5). This takes care of negative indices that may be created.
// The first argument represents the center. The second argument is the span around that
// center.
for element in net.view_center((3, 3), (4, 2)) {
let (value, col, row) = element;
// Draw here!
println!["{}-{} = {}", row, col, value];
}
// Same as `view_center` but allows floats for the first pair.
// Makes sure that the left-most bound will always be 0.
for element in net.view_center_f32((3.0, 3.0), (4, 2)) {
let (value, col, row) = element;
// Draw here!
println!["{}-{} = {}", row, col, value];
}
}
Ergonomics
Instead of using a manual loop, you can use the built-in solve
. Which calls presolve
,
runs a loop around resolve
, and then calls postsolve
with bools denoting whether a
solution was found and at least a single collision was encountered.
extern crate tile_net;
use tile_net::*;
fn main() {
let mut net: TileNet<usize> = TileNet::new(10, 10);
net.set_row(&1, 0);
net.set_row(&2, 9);
net.set_col(&3, 0);
net.set_col(&4, 9);
net.set_box(&5, (3, 3), (5, 7));
println!["{:?}", net];
let mut collider = MyObject::new();
collider.solve(&net, &mut ()); // Much simpler than the loop!
println!["{:?}", collider];
}
#[derive(Debug)]
struct MyObject {
pts: Vec<(f32, f32)>,
pos: Vector,
mov: Vector,
}
impl MyObject {
fn new() -> MyObject {
MyObject {
pts: vec![(0.0, 0.0), (1.0, 0.0), (0.0, 1.0), (1.0, 1.0)],
pos: Vector(1.1, 1.1),
mov: Vector(100.0, 100.0),
}
}
}
impl Collable<usize, ()> for MyObject {
fn points<'a>(&'a self) -> Points<'a> {
Points::new(self.pos, &self.pts)
}
fn queued(&self) -> Vector {
self.mov
}
fn postsolve(&mut self, _collided_once: bool, resolved: bool, _state: &mut ()) {
if resolved {
println!["Able to move"];
} else {
println!["Unable to move"];
}
}
fn resolve<'a, I>(&mut self, mut set: TileSet<'a, usize, I>, _state: &mut ()) -> bool
where I: Iterator<Item = (i32, i32)>
{
if set.all(|x| *x == 0) { // If there is no collision (we only collide with non-zero tiles)
self.pos = self.pos + self.mov;
self.mov = Vector(0.0, 0.0);
true // Means we resolved correctly
} else if self.mov.norm2sq() > 1e-6 { // There was collision, but our speed isn't tiny
self.mov.scale(0.9);
false // Means we did not resolve collision
} else {
true
}
}
}
State
You may have seen the state
variables in presolve
, solve
, and postsolve
.
You can put arbitrary information in this variable. It allows you to communicate between
the three stages and outside of the solve
call.
State is appropriate whenever there exists a property that is not supposed to be part of
the Collable
that you are implementing. In addition to making your Collable
cleaner,
you also avoid redundant information stored in your objects.
See the examples directory for an example where we use presolve and postsolve to find out if our object can jump or not.