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:
- Fast moving object may pass through obstacles
- Object may miss a corner during perframe-perpixel collision checks
- Collision response is precise and accurate
Goals of this collision algorithm are:
- To accommodate variable velocities while the object is approaching the tile
- Solve collision so that object is just touching tile
- Not miss any corners
- Solve collision with fast moving objects
Before I begin, there are some points that should be made clear:
- 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
- We are simply using the tilemap to quickly retrieve which rectangles we want to run the collision algorithm against.
- No native collision functions (hitTestObject, hitTestPoint) are used
- 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.
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)