I’ve been too busy this last week to make any significant progress, so instead I’ll spend this update sharing a few ideas I’ve picked up throughout the week.
There were some infrequent bugs in my collision resolution code that were quickly becoming a pain to test. Originally, I was just setting breakpoints in the problematic path and using the debugger to discover where the issue was originating. This worked well enough while the collision code was still fairly small, but as the code grew it became increasingly difficult to detect the source of the bugs. After some frustrating debugging sessions, I remembered something that could help: Unit tests. For whatever reason I’ve never had the experience of writing unit tests at school or work, so what better way to learn than through a personal project. Coding up a few unit tests quickly uncovered some bugs in my collision detection, and while I’m still working on ironing all these bugs out the tests did a great job of narrowing the search down to the right function.
My next point is the cause of these bugs: floating point numbers. It’s easy to forget that a simple equality comparison between two floating point numbers can fail because of the precision. In order to overcome this discrepancy, I’ve introduced an epsilon value. This value allows me to accept a certain error in my calculations so that even if the values are not exact equal, they are close enough that for the purposes of my game I will consider them equal.
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.