How to pre-calculate the trajectories in a billiard (pool) game?

Question

Most collision detection algorithm in billiard uses a naive approch, where the balls' positions are incremented and then checked for collisions. This method dosen't work well when the speed are really high because we might "skip" collisions.

I have been searching for a way to pre-calculate the trajectories of the balls in a billiard game. Once the trajectories are know, I can animate the balls until they stop moving. And I don't have to worry about the speed, because the collisions are mathematically detected and resolved.

Do you know if anyone has done that? I don't want to reinvent the wheel. Thank you.

Answer 1

Start with quadtrees and make your sampling interval smaller. If your billiard balls are moving so fast that they pass through other balls, however, you're modeling the game incorrectly. Have you ever played a game of billiards where the balls ACTUALLY moved that fast?

Alternatively

Between your time steps, model the ball's previous position and current position as a 2-Dimensional cylinder. If any two cylinders collide, make the time step smaller and try again. In this fashion, you get very quick general calculations, and you can still handle super high velocities.

Answer 2

The easy way is to just use the "naive" approach with a very fine step size, but don't actually animate the balls yet.

Answer 3

One solution that I've implemented for something similar is to use variable time steps.

The implementation goes something like this: you have a time-parameterized method to determine ball position (at current time T plus variable time V); the default is to specify a V of 1.0. In your calculation of updated position, you can perform collision detection; the natural artifact of collision detection is a fractional indicator of when a collision occurs. If this occurs, reset your positions for the current iteration, and resubmit all the moves with the fractional V, then iterate over the amount 1.0 - V.

This works surprisingly well, and has the benefit of being a relatively simple implementation. One point of concern is that you need enough CPU power to be able to calculate moves potentially many times during a "natural" time slice (i.e., one display frame, etc.). However, since this type of calculation is pretty easy for modern processors, that shouldn't be a problem.

Answer 4

I did something similar many years ago and described the motion of the balls with position as a function of time. Using this method I was able to find the exact time of intersection for any two balls. Each ball kept a priority queue with the smallest intersection time at the head of the queue, and the queues would be adjusted when a collision occurred. This worked very well and was pretty easy for the first pass, which had no accelleration to the balls. Later (with some harder math) I was also able to extend it to work with friction added.

The main drawback to this method is that the calculations tend to happen all at once, then nothing for a while, instead of being able to do a little bit of work each frame. This means that your framerate will not be stable. It didn't cause any noticeable glitches on the hardware I was running 8 or so years ago. Even on the break, or strange more or less impossible cases like several balls exactly touching and moving in the same direction when they hit the wall the would be a dip in framerate, but not anything noticeable.