The shot involves two phases. Computation and execution. The computation phase calculates the shot to completion, but does not display any activity. The execution phase plays back the shot that has been calculated.
All computation is done in the virtual time domain, where balls have constant velocities. Shot computation begins with the cue stick striking the cue ball and progresses through virtual time until all balls have stopped moving. Throughout the computation each ball has a state given by whether or not it is on the table, and if so, its position at a reference time and its velocity. This state gives the ball's position at any time between its last collision and it's next collision by a simple linear equasion in the virtual time domain, where a collision is any event which alters a ball's velocity. A ball can collide with:
In addition, when a ball stops, this is considered a collision. This occurs when a ball reaches a minimum real speed.
Throughout the computation phase, a queue of collisions is maintained. These collisions are not only ones which will occur in the shot, but collisions which could occur in the shot. More precisely, the collisions in the queue include those that would occur if the balls were to continue on their current path. This includes: all the collisions that would occur between balls if the balls were to continue on their current path, and for all moving balls, the first collision they would have with an immovable object (anything other than a ball). The earliest collision in the queue is guaranteed to happen in the shot. The algorithm proceeds by pulling the earliest collision from the cue, recomputing the new velocitie(s) of the colliding ball(s) and recomputing the possible collisions for the balls whose velocities have changed. Recomputing collisions includes removing collisions from the queue that will no longer happen and adding the ones that might.
A few short cuts can be taken to avoid waisted computation for collisions that will never occur. One is that minimum-time collisions between balls may be used. These signify that 2 balls are guaranteed not to collide before a certain time. The idea is that these minimum collision times are much quicker to compute that the exact collision times. If either of the balls is redirected before a minimum time collision occurs, the exact collision will never need to be computed and computation time has been saved. When a minimum-time collision is popped from the queue, no ball states are changed, but the exact collision for these balls is computed. The minimum collision time is computed by computing the collision time of the enclosing squares of the balls.
The execution phase is given a chronological list of collisions which do occur in the shot from the computation phase. The execution loop looks like:
Set cue ball in motion
while there is another moving ball (A ball is considered to be moving until it is drawn at rest.)
Compute the virtual time of the current real time
Execute any collisions that occur up to this time (by pulling new ball states from the chronological collision list)
Redraw ball
If it was drawn stopped, remove it from the set of moving balls
Note: Since that balls are not all redrawn at the same time, they can be drawn overlapped and drawing glitches can occur, but they will be rare and not very noticable.
Spin physics is added as an afterthought. This takes us beyond the physics assumptions presented earlier. It requires a significant amount of additional computation and memory, as ball movement (in the virtual time domain) becomes non-linear for balls that are not rolling. We keep track of spin for each ball as a 3 dimensional left-handed spin vector. Spin is applied to balls by various surface forces: cue, felt, rails, balls. One approach would be to use non-linear equations for ball paths. Computing collision times for non-linear ball paths is too difficult/expensive, and the non-linear equations are not mathmatically obvious (5th order if all rotational forces are in the nomal plain to the ball velociy, and I don't know what otherwise). So instead, we still handle ball movement with our linear model, however spinning balls will recompute their velocities, spin, and collision times frequently. To fit this into our computation model, when computing collisions for spinning balls we add a ACCELERATE collision into our collision queue whose time is a very small time duration from now. This is all in the virtual time domain. Note that acceleration due to spin is a real-time effect, so virtual to real translations are done. For spin, the virtual-to-real-time translation translates to viscous friction due to the ball spin.
Spin modes:
The physics:
Take the spin physics quiz.
Debug progress verbosity levels: