Back to Index

AABB Collision Handling

The problem I will be talking about is AABB (Axis-Aligned Bounding Boxes) collision handling, specifically used to support entity-to-level collisions in a 3d game. This is the kind of algorithm that Minecraft uses for its collisions. Collision handling has been giving me headaches for years now. It was my demise in a Ludum Dare once. More recently, I've spent the last 72 hours of my life bashing my head against this problem before I reached a solution that met my criteria.

These criteria were:

  1. 3D AABBs (it is simple to adapt most implementations to any number of dimensions but there are some nuances);
  2. Seamless collisions between AABBs (without jittering or jumps in position);
  3. Wall sliding;
  4. No restrictions on the speed of AABBs (this means mitigating tunnelling);
  5. No restrictions on the size of AABBs (this means supporting scenarios in which an entity is larger than the AABBs of the level);
  6. Tolerance to seams between AABBs (this is important for wall sliding);

Introduction

My journey began with me realizing there isn't only one way of doing collision detection. You can do it fast and simple but there will be restrictions and flaws.

The KISS way of doing it has been very well explained by S�bastien B�nard in this great tutorial. It's simple and it works for most games, especially when you are time restricted (like in a Ludum Dare). It has its flaws though: it only works if the entity is smaller than the level's grid and it sometimes jumps in corners.

But I wanted more.


Tunnelling and Swept AABB

I won't explain this in great detail because BrendanL.K already did a great job explaining it in his article. Just keep in mind that the code he shows DOES NOT WORK. Trying to get it to work covered the first 24 hours of my epic. It served as a good starting point though.

Finally I've ended up implementing another method of swept AABB, described by Kenton Hamaluik in his article Swept AABB Collision Detection Using the Minkowski Difference .


My implementation

After I got swept collisions working I battled several problems one at a time: Sticking to walls, sticking to seams and not working when there were collisions with multiple AABBs. I'll be showing my code in Javascript but it should be relatively easy to port to other languages.

Swept AABB

First comes the implementation of the Swept AABB using the Minkowski's difference. This function takes two AABBs, defined by their closest point to the origin and size along each axis, and their relative speed (assuming B is stationary).

Collision.sweepAABB = function(ax,ay,az,ahx,ahy,ahz,  bx,by,bz,bhx,bhy,bhz, dx,dy,dz) {
    var mx,my,mz, mhx,mhy,mhz;

    mx = bx - (ax + ahx);
    my = by - (ay + ahy);
    mz = bz - (az + ahz);
    mhx = ahx + bhx;
    mhy = ahy + bhy;
    mhz = ahz + bhz;

    var h = 1, s, nx=0,ny=0,nz=0;
    // X min
    s = Collision.lineToPlane(0,0,0, dx,dy,dz, mx,my,mz, -1,0,0);
    if (s >= 0 && dx > 0 && s < h && Util.between(s*dy,my,my+mhy) && Util.between(s*dz,mz,mz+mhz)) 
        {h = s; nx = -1; ny = 0; nz = 0;} 
	
    // X max
    s = Collision.lineToPlane(0,0,0, dx,dy,dz, mx+mhx,my,mz, 1,0,0);
    if (s >= 0 && dx < 0 && s < h && Util.between(s*dy,my,my+mhy) && Util.between(s*dz,mz,mz+mhz))
        {h = s; nx =  1; ny = 0; nz = 0;}
	
    // Y min
    s = Collision.lineToPlane(0,0,0, dx,dy,dz, mx,my,mz, 0,-1,0);
    if (s >= 0 && dy > 0 && s < h && Util.between(s*dx,mx,mx+mhx) && Util.between(s*dz,mz,mz+mhz))
        {h = s; nx = 0; ny = -1; nz = 0;} 
	
    // Y max
    s = Collision.lineToPlane(0,0,0, dx,dy,dz, mx,my+mhy,mz, 0,1,0);
    if (s >= 0 && dy < 0 && s < h && Util.between(s*dx,mx,mx+mhx) && Util.between(s*dz,mz,mz+mhz))
        {h = s; nx = 0; ny =  1; nz = 0;}  
	
    // Z min
    s = Collision.lineToPlane(0,0,0, dx,dy,dz, mx,my,mz, 0,0,-1);
    if (s >= 0 && dz > 0 && s < h && Util.between(s*dx,mx,mx+mhx) && Util.between(s*dy,my,my+mhy))
        {h = s; nx = 0; ny = 0; nz = -1;} 
	
    // Z max
    s = Collision.lineToPlane(0,0,0, dx,dy,dz, mx,my,mz+mhz, 0,0,1);
    if (s >= 0 && dz < 0 && s < h && Util.between(s*dx,mx,mx+mhx) && Util.between(s*dy,my,my+mhy))
        {h = s; nx = 0; ny = 0; nz =  1;}

    return {h:h, nx:nx, ny:ny, nz:nz};
}		
			

Basically it calculates the Miskowski's AABB and checks the closest intersection between it and the velocity vector. This function will return a value between 0 and 1, where 0.5 means "a collision occurred halfway of the AABB's path" and 1 means "there was no collision". Notably, if one of the AABB's is completly inside the other, it will return 1, meaning our AABBs will be "hollow".

It also returns the normal to the surface that was hit. This will be useful when we implement wall sliding

Line to Plane

"Collision.lineToPlane" is, like its name suggests, a function that intersects a line with a plane. It returns at which point of the line the collision happened (0 - it occurred at the line's origin; 1 - it occurred at the tip of its defining vector; Infinity - it's parallel to the plane). This is its implementation:

Collision.lineToPlane = function(px,py,pz, ux,uy,uz,  vx,vy,vz, nx,ny,nz) {
    var NdotU = nx*ux + ny*uy + nz*uz;
    if (NdotU == 0) return Infinity;

    // return n.(v-p) / n.u
    return (nx*(vx-px) + ny*(vy-py) + nz*(vz-pz)) / NdotU;
}
			

Between

"Util.between" is just a function that returns whether a value is inside a given range. In the code above it is used to check if the velocity vector intersection is within a face of the Miskowski's AABB.

Util.between = function(x,a,b) {
    return x >= a && x <= b;
}
			

The collision handler

This is where the real magic happens. This code was made for a world made of voxels but it should work for any configuration of AABBs.

Entity.prototype.levelCollision = function() {
	if (!this.collideWithLevel) return;
	
	//Notice there is a cycle. We may have to run the algorithm several times until the collision is resolved 
	while(true) {
		
		// First we calculate the movement vector for this frame
		// This is the entity's current position minus its last position.
		// The last position is set at the beggining of each frame.
		var dx = this.x - this.px;
		var dy = this.y - this.py;
		var dz = this.z - this.pz;
		
		// These are the bounds of the AABB that may collide with the entity.
		var minXi = Math.floor(Math.min(this.x,this.px)-this.hx/2), maxXi = Math.floor(Math.max(this.x,this.px)+this.hx/2);
		var minYi = Math.floor(Math.min(this.y,this.py)-this.hy/2), maxYi = Math.floor(Math.max(this.y,this.py)+this.hy/2);
		var minZi = Math.floor(Math.min(this.z,this.pz)-this.hz/2), maxZi = Math.floor(Math.max(this.z,this.pz)+this.hz/2);
		
		var r = {h:1, nx:0, ny:0, nz:0};

		// For each voxel that may collide with the entity, find the first that colides with it
		for(var yi = minYi; yi <= maxYi; yi++) {
		for(var zi = minZi; zi <= maxZi; zi++) {
		for(var xi = minXi; xi <= maxXi; xi++) { 
			// Discard non-solid voxels
			if (!Blocks[level.getBlock(xi,yi,zi)].solid) continue;

			// Check swept collision
			var c = Collision.sweepAABB(
				this.px - this.hx/2,this.py - this.hy/2, this.pz - this.hz/2, 
				this.hx,this.hy, this.hz,
				xi,yi,zi, 
				1,1,1,
				dx,dy,dz
			);
			//Check if this collision is closer than the closest so far.
			if (c.h < r.h) r = c;
		}}}
		
		
		// Update the entity's position
		// We move the entity slightly away from the block in order to miss seams.
		var ep = 0.001;
		this.x = this.px + r.h*dx + ep*r.nx;
		this.y = this.py + r.h*dy + ep*r.ny;
		this.z = this.pz + r.h*dz + ep*r.nz;

		// If there was no collision, end the algorithm.
		if (r.h == 1) break;

		// Wall Sliding
		// c = a - (a.b)/(b.b) b
		// c - slide vector (rejection of a over b)
		// b - normal to the block
		// a - remaining speed (= (1-h)*speed)
		var BdotB = r.nx*r.nx + r.ny*r.ny + r.nz*r.nz;
		if (BdotB != 0) {

			// Store the current position for the next iteration
			this.px = this.x;
			this.py = this.y;
			this.pz = this.z;

			// Apply Slide
			var AdotB = (1-r.h)*(dx*r.nx + dy*r.ny + dz*r.nz);
			this.x += (1-r.h)*dx - (AdotB/BdotB)*r.nx;
			this.y += (1-r.h)*dy - (AdotB/BdotB)*r.ny; 
			this.z += (1-r.h)*dz - (AdotB/BdotB)*r.nz;
   
		}
	}
}
		

Closing Words

Thank you for reading my wall of text :) I hope this is useful and that you spend less time thinking about this than I did. In the future I may do another one of these touching topics like moving platforms and ramps. If you find a bug or have any questions don't be afraid of leaving a comment or shooting me an email.


04/08/2016
Luis Eduardo Reis

Back to Index