In a race to hit the deadline for the melonJS 0.9.7 release later this month, I decided to spend my free time tonight working on the new collision detection again. I was able to make to another 25% faster (!) but at the cost of losing sub-pixel velocities. :( The good news is it should be possible to work around the issue and support sub-pixel velocities again while retaining the nice optimization that made it faster.
It all has to do with how often objects are checked for collisions. If the object is not moving, don't run collision checks on it! Sounds simple enough! But what happens when the object is moving by less than one pixel per frame? It's not going to generate any new collisions every frame at such a low velocity, so the collision checks also should not run each frame.
There's some trouble predicting when a slow-moving object might generate a collision, though. First, because the object's position is only updated after collision detection has run, and a collision response has been calculated. The collision response is what gets added to the object's position, not the "requested" velocity. So if the collision detection isn't run because the object is moving too slow, and its position isn't updated because collision detection didn't run, how do we know when it's time to actually update the position?
I suppose an illustration would be helpful, but please bear with me for a moment. Let's say an object has a velocity along the X-axis set to 0.2. That means, every frame, the object will move 1/5 of a pixel to the right. In other words, it will move exactly one pixel right after every 5 frames. So it only makes sense to check collision detection on this slow moving object every 5 frames, after it has had a chance to move one full pixel. That's where the chicken-and-egg problem comes in; collision detection has to run in order to update the position. And the position must be updated in order to do collision detection!
I'm currently experimenting with a way to record a sum of all "requested" velocities over time when the absolute velocities are less than 1. Ideally I would then use the velocity sum to decide whether the object has gained enough momentum to move at least one pixel, and therefore has moved enough to consider performing collision detection. It isn't working yet, but that's the idea!
One caveat for doing this is that sub-pixel velocities are treated as "zero" within the collision detection system, so they also need to be treated the same outside of it. melonJS games currently assume that objects are not moving only when the velocity is zero, but this won't be the case for long ... IN THE NAME OF SPEED!
A lot of the optimizations I've done with collision detection have been little attempts like this to "bail early" before getting to the heavy operations involving iterations. And there are a few more that I am aware of which should make it a bit faster still! These speed improvements are great, but the accuracy of the new code still leaves a lot to be desired. (There are silly bugs like jumping against a wall applying an incorrect response vector.) All in due time...
Tomorrow, I'll get back to the game, and I'll probably spend nearly the entire day on it. So we'll see where that takes us! See you then!