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:
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 Sebastien Benard 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 a more flexible approach.
I won't explain this in great detail because BrendanL.K already did a great job explaining it in his article (source for the diagram above). Just keep in mind, though the explanation is sound, the code example he provides 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 .
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.
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
"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; }
"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; }
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; } } }
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