Here I present the design for a perfect algorithm, handling ball to ball collisions. You would never guess that this algorithm could be so hard to create. Believe me, it is.
Bolas is the first game I ever developed in Silverlight, but it was never finished because I could not get the collision detection right. The big difference between Bolas and a billiards ball game is that the player ball may gain speed continuously, while at a billiards ball game, the player ball only gets speed when it is hit by the cue. Allow for spring forces between balls, the environment gets even more complex. To fix Bolas, I needed a perfect ball to ball collision detection and handling algorithm. Less than perfect would uncover game errors quite quickly.
Here is the result:
The demo video shows three tests. The first test is a complex situation with many balls and a bar with rounded corners. The second test is three red balls lined up, being hit by a blue ball. The third test is a blue ball in the corner, being hit by a red ball, with a slightly less angle than 45 degrees. All tests are performed very well.
The research
First I tried Emanuele Feronato’s ball to ball Flash script, and rewrote it for Silverlight. It seemed like a good algorithm, but sometimes balls cluttered together and never parted again. This happened more often when the balls had different radii, while it happened less when all balls had the same radius.
Second I tried an algorithm from Gamasutra, for collision detection, while I kept the “manage_bounce” function from Emanuelle’s script for collision handling. Everything was not quite right yet. Sometimes balls jumped over to the other side of the ball they collided with. This scheme was based on the fact that every collision would generate a correction. Suddenly, a ball to border collision and a ball to bar collision needed corrections as well. In Bolas, the player could push a ball into the corner, out of the screen. Then I tried second passes, or even a continues loop while not all collisions were solved yet.
It all did not work.
A typical game-loop is frame based. If a frame is seen as a timeline, then most collisions will happen on the line, not at the ends. That’s the easy part.
A little harder, multiple collisions can happen within one frame. Instead of just handling them all, in an undefined order, you should handle these collisions in the timely order in which they occur.
Now, the hardest part is this: a collision between balls A and B, may cause a new collision between balls B and C, within the same frame. This new collision between B and C, may replace an earlier detected collision between ball C and another object. Are you with me? Suppose ball C is moving towards the border and it will collide, but now ball A hits ball B, and B will hit ball C at the same or later time, changing the direction of C, such that C won’t hit the border anymore. The new collision between B and C, just replaced an earlier detected collision between ball C and the border.
To comply with these requirements, the following algorithm should be implemented:
1. Remaining frametime is 100%
2. Detect collisions, if nothing is detected, goto 5
3. Move balls to the first moment of collision and bounce the balls. Decrease remaining frametime with the collision-moment.
4. If you still have remaining frametime, goto 2, else goto 5
5. Move the balls for the remaining frametime – the end part of the frame
Also note the ball to bar / corner collision. This article gives a good algorithm between ball and point corner collision. For a bar with rounded corners, detect a ball-to-ball collision, but handle it like a ball-to-point collision at the point where the collision takes place.
The above algorithm was tweaked to get satisfactory results. The video shows that there are no glitches.
Also another point of interest, when the simulation is ran twice, the balls move the same way in both runs. In Silverlight, the time between two frames may be different. This is compensated in the ball’s movement. The video proves that the scheme is stable, that the fluctuation of FPS does not affect the simulation at all. Therefore, here we have a perfect ball to ball collision detection algorithm.
Next is using this algorithm in a game.
Subscribe