Back in 2008 I wrote my first Silverlight game, in Silverlight 1.16 Beta. However, the game was never published because it had bad collision detection bugs. I spend a lot of time trying to fix this, but I didn’t succeed. Later I got an idea how to approach the ball to ball collision theme in a different way, but highly unmotivated, I started writing other games. Which is somehow a pity, because I think Bolas is a fun game.
Anyhow, I picked up the challenge now about two years later, introducing the collision detection scheme I was thinking of. First, let’s start with the research I’ve done until now.
I translated a Flash implementation of ball to ball collision from Flash action script found in this article. This script detects a collision and handles it. A known problem with this algorithm is that at some point, the balls will clutter together. If you have balls with different radii, this problem will occur sooner than when all the balls have the same radius. As I use different radii for Bolas, the problem occurred to me very quickly.
Another article from Gamasutra gave an algorithm plus code, to do a more accurate collision detection and handling. I implemented this, but at hot spot moments, it still failed. The reason for failure was that my algorithm did not consider multiple collisions within one frame. I tried to solve this, however my approach was simply bad, because I did not understand the problem.
However, I did understand one thing. If I have a series of touching balls in a straight line, and I bounce a moving ball against it, within the same line, the ball at the other end should move, while the others remain stationary. My algorithm could not handle this situation. Why? Because my approach was frame-to-frame oriented. My error was that things happening within a frame were unordered.
How is that? Well, a game-loop is typically based on frames, i.e. moments in time when the screen of your monitor is painted. In a game-loop, you reorder your visuals for the next frame to be painted. So if you calculate and handle all detected collisions for the next frame, you are missing information. Because handling one collision in a frame, could cause another collision within the same frame. So if you have three balls, A, B and C, a collision handling between A and B, could cause a new collision between B and C. If not handled correctly, this will cause errors in your collision detection and handling.
My new approach in calculating the next frame is to play whatever happens between the previous and the next frame. So:
1) If collisions are detected at X% of the frame time, then:
2) The balls are moved with X% of their speed;
3) The collisions are handled;
4) Run collision detection for the current and remaining (100-X)% of the frame
5) If step 4 resulted in collisions, then goto step 1 for new collision detections;
6) Else, move the balls for the remaining frame time
Because of step 4, a collision handling at frame time X, may cause new collisions for this same frame time X, which will be handled in the next iteration (the “goto 1” in step 5). Note, the above algorithm is more difficult to implement than described! A line of balls situation, described above, must be handled with a ball speed threshold. Suppose the speed of a ball becomes lower than a certain value, then the speed must become zero, to break infinite loops.
I haven’t figured everything yet, but let’s start with the simplest implementation. Moving balls which don’t lose speed, and which only bounce against the borders of the screen. It looks simple, but it was hard enough. A collision to one border is registered as one collision. Things happening within one frame are handled in order of time. This is not the ordinary bounce against borders and reverse the x or y parameter of the speed vector. Each border is a collision and handled accordingly.
Subscribe