AABB Sweep Test tutorial

An AABB sweep test algorithm is best used for a tile game because most of the entities are Axis Aligned Bounding Boxes.

It is necessary to use a sweep test algorithm for your tile game because of the following reasons:

1. Fast moving object may pass through obstacles
2. Object may miss a corner during perframe-perpixel collision checks
3. Collision response is precise and accurate

Goals of this collision algorithm are:

1. To accommodate variable velocities while the object is approaching the tile
2. Solve collision so that object is just touching tile
3. Not miss any corners
4. Solve collision with fast moving objects

Before I begin, there are some points that should be made clear:

1. Many online tutorials use the method of getting an tile number of surrounding tiles from an array using indexes retrieved from a calculation based on the characters current position. It will not work in this case because we need to support number 2 of the goals above
2. We are simply using the tilemap to quickly retrieve which rectangles we want to run the collision algorithm against.
3. No native collision functions (hitTestObject, hitTestPoint) are used
4. Code provided is probably un-optimized pseudo code

We start of by writing a function that can solve a 1 to 1 collision between 2 AABBs. Then we will get to the tilemap. The function takes 3 paremeters:

previousRect, currentRect, tileRect

currentRect corresponds to the position and size of the current state of the object.
previousRect corresponds to the position in the last frame
tileRect corresponds the position and size of the tile

we first want to find out how far the object has to travel to just overlap on both axes. This is a signed value. Picture 1 shows the values we are looking for.

To find those values, we need to combine the information of both the positions of the object, and the direction that its travelling in

sweptshapebound = newrect union oldrect
velocity = newrect.xy - oldrect.xy

if velocity.x > 0
  distanceX = tile.left - oldRect.right 
else 
  distanceX = tile.right - oldRect.left

(repeat for y axis) 

the right and left values in the code above should be calculated using min and max functions. In our (me and truefire’s game) we have a class that inlines math functions like these to make it really fast.

Moving on: The reason for calculating these values is that we are going to use them to calculate the exact time the overlap on each axis occurred. When I say time, I don’t mean in terms of how many frames; rather, what fraction of a frame. The reason is, in the computer world, there is no real motion. When you add 2 to the x value of an object, the object in a sense tele-ported 2 pixels to the right.

However, we as software engineers know that the object traveled a full path all the way; There is just no information regarding the specifics within that fraction of a frame, such as whether the object’s speed fluctuated during that time period, or the object’s path was curved.

When calculating with math though, we can just assume that the object moved straight toward the location with uniform speed. This way, given the information that the object travels 5 pixels a frame, we can find out that it took 3/5 frames to travel 3 pixels.

With that understanding, we go back the the collision problem. The penetration depth value we just calculated is a fraction of the velocity. Now you should be able to see where I am heading. Using this information we can calculate how much time it took to overlap in each of the axes. And by time, I mean numbers like 0.878787 frames.

timeY = (distanceX/velocity.x)
timeY = (distanceY/velocity.y)

No absolute value; the negative values give us a chance to see if an axis already has an overlap.

We know, according to the Separation Axis Theorem that the shapes only collide when both axes are overlapping. What we want to do is find the last axis the overlaps. Only when the last axis is satisfied with an overlap does a collision occur.

actualtime = max(timeX,timeY)
(more time = later)

with the collision time solved, we can basically move the object backwards along its velocity by the amount of time.

position-=(1-actualtime)*velocity

You might think that there is a problem with this method:
The object might not have collided with the tile, might not even be close.

The answer is that we will be using the bounds of the swept shape to find out which tiles we are running the collision test with. All tiles that are put through this function should be overlapping with the bounds of the swept shape.

That brings the next question: There is still a possibility that the shape has not collided with the tile. In picture 2, it shows just that situation.

I had only discovered this problem recently, and our collision system still registered a collision and response even in this situation. The bug was so small to notice, the game still ran fine, but I wanted it to be as perfect as possible.

The answer to this problem is to make sure the the axis hasn’t left or passed the overlap before the second axis even becomes overlapped. We do this by finding the the time it took for the shape to leave the intersection.

if velocity.x > 0
  disjointTimeX = tile.right - oldRect.left
else
  disjointTimeX = tile.left - oldRect.right

The actual disjoint time is the earliest axis that stops overlapping

actualDisjointTime = min(disjointTimeX,disjointTimeY)

The actual collision occurs when both axes overlap before the first one disjoints:

collided = actualTime>actualDisjointTime?false:true

So, we should only move the object back along its velocity if this condition is met.

Finally this check is important:

if (timeX < 0 && timeY < 0) || (timeX > 1 || timeY > 1)
  collided = false

This is because moving away after a resolved collision returns both negative values, and both times greater than 1 means a the object has not reached the tile
In the next part I’ll talk about how to implement this function in an environment with multiple tile collisions.

(to be continued, I have to sleep, pictures coming tommorrow)

point Number 4: Code provided is probably un-optimized pseudo code

what is pseudo code?

Code that describes the logic but isn’t any language that can compile anywhere.

Pseudo code it pretty much just writing the code in ‘normal’ language

I’m really lazy but I might update sometime today (lol prolly gonna be lazy and not) but here is what it is supposed to achieve.

http://megaswf.com/serve/2400301

click to move the red small square.

oh, and we need this to fix boundary bugs.

if ((timeX < 0 && timeY < 0) || (timeX > 1 || timeY > 1))
		{
			return new CollisionData(false);
		}

Argh cleaning it up later.

Originally posted by qwerberberber:

I’m really lazy but I might update sometime today (lol prolly gonna be lazy and not) but here is what it is supposed to achieve.

http://megaswf.com/serve/2400301

click to move the red small square.

oh, and we need this to fix boundary bugs.

if ((timeX < 0 && timeY < 0) || (timeX > 1 || timeY > 1))
		{
			return new CollisionData(false);
		}

Argh cleaning it up later.

is the swf meant to be undownloadable?
The Example seems to be very precise. I’m attempting to impliment the logic right now. I hope I can get it to work with my for loop. : D

EDIT: The code below does NOT work.
Well, I’m trying.
It would be a lot more helpful if I could see the source though. If you’d permit that.
Good for me though, I’m in territory I haven’t been in yet. I didn’t know about the Math.max & Math.min functions.
The code below so doesn’t work yet.

package 
{
	import flash.display.*;
	import flash.events.*;
	
	public class AABBtest extends MovieClip{
		
			public var sq2:square2 = new square2;
			public var sq1:square1 = new square1;
			public var distanceX1;
			public var distanceY1;
			public var distanceX2;
			public var distanceY2;
			public var timeX;
			public var timeY;
			public var disjointTimeX;
			public var disjointTimeY;
			public var actualTime;
			public var actualDisjointTime;
			public var prevSq1X;
			public var prevSq1Y;
			public var velocityX = 0;
			public var velocityY = 0;
			public var squareX;
			public var squareY;
			public var collided:Boolean;
		
		public function AABBtest() {

			sq1.x = 150;
			sq1.y = 150;
			sq2.x = 300;
			sq2.y = 300;
			stage.addChild(sq1);
			stage.addChild(sq2);
			stage.addEventListener(MouseEvent.CLICK, Move);
			
		}
		
		public function Move(e:MouseEvent){
			moveSquare();
			solveCollision(100,100,100,100);
		}
		
		public function moveSquare(){
			prevSq1X = sq1.x;
			prevSq1Y = sq1.y;
			squareX = mouseX;
			squareY = mouseY;
		}
		
		public function solveCollision(a:int,b:int,c:int,d:int) {
			
			velocityY = squareY - prevSq1Y;
			velocityX = squareX - prevSq1X;
					
				if(velocityX < 0){
					distanceX1 = sq2.x + (sq2.width/2) - prevSq1X;
					distanceX2 = prevSq1X - (sq2.x + (sq2.width/2));
				} else {
					distanceX1 = prevSq1X - (sq2.x + (sq2.width/2));
					distanceX2 = sq2.x + (sq2.width/2) - prevSq1X;
				}
				if(velocityY < 0){
					distanceY1 = sq2.y + (sq2.height/2) - prevSq1Y;
					distanceY2 = prevSq1Y - (sq2.y +(sq2.height/2));
				} else {
					distanceY1 = prevSq1Y - (sq2.y +(sq2.height/2));
					distanceY2 = sq2.y + (sq2.height/2) - prevSq1Y;
				}
			
			timeX = distanceX1/velocityX;
			timeY = distanceY1/velocityY;
			
			actualTime = Math.max(timeX,timeY);		

			disjointTimeX = distanceX2/velocityX;
			disjointTimeY = distanceY2/velocityY;
			
			actualDisjointTime = Math.min(disjointTimeX, disjointTimeY);
			
			if(actualTime < actualDisjointTime){
				sq1.x = sq2.x -(1-actualTime)*velocityX;
				sq1.y = sq2.y -(1-actualTime)*velocityY;
			} else {
				sq1.x = mouseX;
				sq1.y = mouseY;
			}
			
			trace("Time X = " + timeX + ", Time Y = " + timeY + ", actualDisjointTime = " + actualDisjointTime);
		}
	}//---
}//-------

Actually, I’m making some updates to the logic pretty soon, I have found a very awesome way of doing it without absolute values.

Orly?

Interested Alec is Interested.

Originally posted by alecz127:

Orly?

Interested Alec is Interested.

Finally done with homework;

I updated the first diagram, with some changes to the text and code also.

The code below DOES work!!
Finished!
This was a very educational success my good friend qwerberberber.
I’m posting what I came up with below, but I encourage anyone coming across this thread to attempt their own approach as its quite a learning experience. : D

package {
	import flash.display.*;
	import flash.events.*;
	public class AABBtest extends MovieClip{
			public var sq2:square2 = new square2;
			public var sq1:square1 = new square1;
			public var prevSq1X;
			public var prevSq1Y;
			public var squareX;
			public var squareY;
			public var collided:Boolean;
		public function AABBtest() {
			sq1.x = 150;
			sq1.y = 150;
			sq2.x = 300;
			sq2.y = 300;
			stage.addChild(sq1);
			stage.addChild(sq2);
			stage.addEventListener(MouseEvent.CLICK, Move);
		}
		public function Move(e:MouseEvent){
			moveSquare();
			solveCollision();
		}
		public function moveSquare(){
			prevSq1X = sq1.x;
			prevSq1Y = sq1.y;
			squareX = mouseX;
			squareY = mouseY;
			sq1.x = mouseX;
			sq1.y = mouseY;
		}
		public function solveCollision() {
			var velocityY = squareY - prevSq1Y;
			var velocityX = squareX - prevSq1X;
			var distanceX1;
			var distanceY1;
			var distanceX2;
			var distanceY2;
				if(velocityX < 0){
					distanceX1 = sq2.x + sq2.width - prevSq1X;
					distanceX2 = sq2.x - prevSq1X - sq1.width;
				} else {
					distanceX1 = sq2.x - prevSq1X - sq1.width;
					distanceX2 = sq2.x + sq2.width - prevSq1X;
				}
				if(velocityY < 0){
					distanceY1 = sq2.y + sq2.height - prevSq1Y;
					distanceY2 = sq2.y - prevSq1Y - sq1.height;
				} else {
					distanceY1 = sq2.y - prevSq1Y - sq1.height;
					distanceY2 = sq2.y + sq2.height - prevSq1Y;
				}
			var timeX = distanceX1/velocityX;
			var timeY = distanceY1/velocityY;
			var actualTime = Math.max(timeX,timeY);
			var disjointTimeX = distanceX2/velocityX;
			var disjointTimeY = distanceY2/velocityY;
			var actualDisjointTime = Math.min(disjointTimeX, disjointTimeY);
			if (timeX < 0 && timeY < 0){
				collided = false;
				return;
			}
			if(actualTime < actualDisjointTime){
					sq1.x = mouseX;
					sq1.y = mouseY;
					sq1.x = sq1.x - ((1-actualTime) * velocityX);
					sq1.y = sq1.y - ((1-actualTime) * velocityY);
			}
		}
	}//---
}//-------

Great! Now the goal is to run this collision on multiple tiles and use the earliest time out of those, and only push it back along the axis that the collision happened on (x or y) so that it can slide along walls. This may sound complicated, but ask here if you can’t figure it out.

This was actually really insightful, I’m definitely going to use this for my new game, it runs exponentially faster then my SAT implementation and I’m only using AABB’s for it anways so this worked perfect for what I needed. Thanks!

If anyone wants the function, here’s my implementation of it.

function AABBCollision(oldRect:Rectangle, newRect:Rectangle, tile:Rectangle):Point {
	
	var velocity:Point = new Point(newRect.x - oldRect.x, newRect.y - oldRect.y);
	var time:Point = new Point();
	var disjointTime:Point = new Point();
	var actualDisjointTime:Number, actualTime:Number;
	var separation:Point = new Point(0, 0);
	var distance:Point = new Point();
	var collided:Boolean = false;
	
	if(velocity.x > 0) {
		distance.x = tile.left - oldRect.right;
		disjointTime.x = tile.right - oldRect.left;
	} else {
		distance.x = tile.right - oldRect.left;
		disjointTime.x = tile.left - oldRect.right;
	}
	
	if(velocity.y > 0) {
		distance.y = tile.top - oldRect.bottom;
		disjointTime.y = tile.bottom - oldRect.top;
	} else {
		distance.y = tile.bottom - oldRect.top;
		disjointTime.y = tile.top - oldRect.bottom;
	}
	
	time.x = distance.x/velocity.x;
	time.y = distance.y/velocity.y;
	disjointTime.x = disjointTime.x/velocity.x;
	disjointTime.y = disjointTime.y/velocity.y;
	
	actualTime = Math.max(time.x, time.y);
	actualDisjointTime = Math.min(disjointTime.x, disjointTime.y);
	
	collided = (actualTime>actualDisjointTime)?false:true;
	if((time.x < 0 && time.y < 0) || (time.x > 1 || time.y > 1)) collided = false;
	
	if(collided) {
		separation.x = (1-actualTime)*velocity.x;
		separation.y = (1-actualTime)*velocity.y;
	}
	
	return separation;
}

Lol it seems that I have forgotten to update this tutorial, I’ll add the tilemap implementation information when i get the next chance.

still waiting! :D