With a full weekend of coding, I was finally able to make good progress on my collision detection and resolution.
Last week, I began to implement the AABB Sweep Test. This is a continuous collision detection algorithm that solves the ‘bullet through paper’ problem, in which a fast moving object will pass through another object undetected. This issue arises if your collision detection algorithm fails to check a sufficient set of positions between in start and end position for each time step. The AABB Sweep Test uses the Separating Axis Theorem which states that there exists an axis on which the projection of the objects do not overlap. Therefore, all we have to do is track the earliest times of collision and disjointing for each axis. If all axes collide before any axis becomes disjoint, then a collision occurs. Not only that, but we know exactly when and on which axis the collision occurred. The following video demonstrates the Sweep Test at work, causing blocks to flash red if they detect a new collision caused by the player (overlaps are not colored red for demonstration purposes):
With collision detection completed, I was able to move onto collision resolution. My current solution is not perfect, but I certainly feel that I am on the right track. In short, I am following this structure:
Adjust entities according to input and velocities For all entities i For all entities j from i + 1 If i is colliding with j, add to contacts For all contacts c For all c's entities a If c's time is == a's earliest time Add force to a's forces Add impulse to a's impulses For all entities i Add force aggregate to i's position Add impulse aggregate to i's velocity
The basic idea here is that the collision resolution will calculate two things: force and impulse. Force is the vector required to remove the object from its collision, and impulse is the resulting velocity after the collision. I have to be careful about how and when I apply these values. If I were to apply the force as soon as it was calculated, than the proceeding force calculations for this time step would be incorrect. Similarly, if I were to apply the impulse before all collisions were resolved, I could easily cause undetected collisions. The end result is demonstrated in this short video:
There is still some collision work to be done and bugs to be fixed, but with any luck I should be able to add some more realistic physics and controls. Look for that and more next week.