Crate tile_net [−] [src]

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²⁴ 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.

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 None. 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) {
    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 {
      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>) -> 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 consistently
              // 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) {
      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>) -> 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);  // 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) {
    if resolved {
      println!["Able to move"];
    } else {
      println!["Unable to move"];
    }
  }

  fn resolve<'a, I>(&mut self, mut set: TileSet<'a, usize, I>) -> 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
    }
  }
}

See the examples directory for an example where we use presolve and postsolve to find out if our object can jump or not.

Structs

Line	Describe a line by its start and end `Vector` respectively
Points	A vertex iterator.
SuperCover	Iterator for traversing from one point on the line to the end point
TileNet	`TileNet` is the main class in this library
TileSet	Tile iterator returning tiles from the `tile_net::TileNet`.
TileView	Tile iterator for a rectangular view of the `tile_net::TileNet`.
Vector	Describe a point in 2-space

Traits

Collable

Trait for dynamic objects so they can easily check collisions with the TileMap