modeling billiard table

[Dean Ware]

I am trying to construct a model for use in a video game

Basically I have boiled things down to the following situation that needs to
be modelled:



Think of a snooker/pool table (without the pockets) with two balls on it.

The balls bounce around colliding with the sides of the table and each
other. Perfectly elastically for simplicity.

For further simplicity, there is no friction. Maybe they have unit mass.

Basically picture two circles bouncing around inside a rectangle.

My question is:

Given:

1) the dimensions of the rectangle and the circles.

2) the initial velocities of the circles

Is there an equation where I can find the location of the circles at time t?

e.g.

circle_one_centre(x,y) = f(t)

circle_two_centre(x,y) = f(t)

If so, how do i go about finding this equation?

what about the same thing for n circles?

Different shaped tables??

Any ideas?

Thanks for any help

Dean

[Bill97]

"Dean Ware" <no****@nospam.com> wrote in message
news:eX*****************@newsfe2-gui.ntli.net...

I am trying to construct a model for use in a video game

Basically I have boiled things down to the following situation that needs
to be modelled:



Think of a snooker/pool table (without the pockets) with two balls on it.

The balls bounce around colliding with the sides of the table and each
other. Perfectly elastically for simplicity.

For further simplicity, there is no friction. Maybe they have unit mass.

Basically picture two circles bouncing around inside a rectangle.

My question is:

Given:

1) the dimensions of the rectangle and the circles.

2) the initial velocities of the circles

Is there an equation where I can find the location of the circles at time
t?

I wouldn't expect one, especially if you are allowing for collisions. Start
by thinking about 1 ball bouncing around by itself. Decide how long the
ball will be in motion (and at what velocity) and use a loop to track its
position (iterating every 10th of a second, say).

Good luck, Bill

[Evan]

I don't think so. What you can do though is to break up the path into a
series of discrete chunks. You don't have to do it like Bill97 says
though, checking the position every short interval of time, because the
only time the equation changes will be when it collides with something.
(Though if there are a lot of balls that might be the easiest way.)

Look at just one ball bouncing around for a minute. Let's set up a
couple variables:
- x will be the current x location of the ball (say that x is the
short distance)
- y is the current y position of the ball
- width is the x dimension of the table
- height is the y dimension of the table
- v is the velocity of the ball
- a is the angle the ball is traveling (0 will be positive x and no y;
90 is positive y and no x; I'm actually going to use v and a at the
very beginning then ignore them)
- t is the current time

The table is set with a corner at (0, 0) and extending into the first
quadrant. I'm using real coordinates, not the reversed y axis you see
in CG a lot. ;-)

Furthermore, we assume one of two things: either the ball has zero
radius or the variables width and height should be increased by the
radius, and the whole table offset by r/2 left and down. In other
words, if the ball is sitting at (0,0) it should be touching the left
and bottom sides, and if it is at (width, height) it is touching the
right and top sides.

If we ignore the edges, the position of the ball can be found as
follows (I'm gonna use a bunch of temporary variables from here on to
make this clearer to both me and you):

The x component of the velocity is vx = v*cos(a)
The y component of the velocity is vy = v*sin(a)

Thus x(t) = x + vx*t and y(t) = y + vy*t.

But this only holds until it hits the side, so we have to find when
this will occur:

If the ball will hit the right rail, it will happen at tr = (width -
x)/vx
If the ball will hit the left rail, it will happen at tl = -x/vx
Similarily tt = (height -y)/vy and tb = -y/vy

So we have these equations holding until t reaches reaches the minimum
of the appropriate x choice and the appropriate y choice:
tm = min( (vx > 0) ? tr : tl),
(vy > 0) ? tt : tb) );

At that point, it hits the rail(s) so we bounce it by flipping the
velocity of the appropriate direction(s):
if( tm == tl || tm == tr) vx = -vx;
if( tm == tt || tm == tb) vy = -vy;

(Note that these both might be true if it hits the exact corner, so you
can't use else if)

Then repeat. (You'll need to make allowances for vx or vy being 0.)

So we have an algorithm for computing the position at time t (I'm
assuming height and width are global constants):

pair<double, double> position(double t, double x, double y, double v,
double a)
{
double vx = v * cos(a);
double vy = v * sin(a);

double t_until; // tm above

do
{
if( t_until == t_left || t_until == t_right) vx = -vx;
if( t_until == t_top || t_until == t_bottom) vy = -vy;

double t_right = (width - x)/vx;
double t_left = -x/vx;
double t_top = (height - y)/vy;
double t_bottom = -y/vy;

t_until = min( (vx > 0) ? t_right : t_left),
(vy > 0) ? t_top : t_bottom) );

} while (t + t_until > t_max);

return make_pair( x + vx * t, y + vy * t);
}

(This won't work if a = 0, 90, 180, 270, ..., or if the initial
position is on a rail.)
The case for multiple balls is a (much more complicated) generalized
form of this. Here's an overview:

Instead of keeping just a x, y, v, and a (or alternately a vx and vy),
you will have a vector of each. (This would be a PERFECT use of a
valarray if I remember my STL right.) You'll then compute a vector of
t_right, t_left, t_top, and t_bottoms, and set t_until to the max over
all that. (Actually you don't need to do all that; you just need to
store the minimum as you compute them.)

But that's not all. Because you have to check collisions. My advice is
to start assuming the balls have radius 0. In addition to checking when
they hit rails, you'll have to check when every ball will hit every
other ball. So for n balls you'll have n(n-1)/2 (easy) systems to
solve. You'll have to consider the cases where they don't intersect
(will only happen once you fix the vx or vy = 0 bug above) or when at
least one ball is traveling away from the point of intersection. I'm
not sure of the equations for what happens when a collision occurs. But
I think what will happen is that the velocities of the balls will swap.
That is, if one ball with velocity vector <vx_1, vy_1> collides with a
ball with velocity vector <vx_2, vy_2>, after the collision the first
ball will have velocity <vx_2, vy_2> and the second <vx_1, vy_1>.

Adding balls that have some size complicates that part there. Because
now they collide before the trajectory lines cross, and you have to
find out how much before. My suggestion is to draw diagrams and try to
figure it out; it'll take a bit of trig. Just remember to consider the
case where the lines meet outside of the table but the balls hit each
other inside the borders. (That is, you can't ignore any of the pairs
because they meet outside the borders until you find out where the
balls actually hit.)

Then you've got the skeleton in of a good billards program. ;-) Next
you need to factor in friction. This will just complicate a couple of
the formulas (you'll have to integrate), and also cause vx and vy to
change from iteration to iteration, but won't substantially change the
solution.You'll have to deal with the situation where balls stop
moving. (With perfect numbers this won't happen, but eventually
roundoff will cause the probably value to be 0.)

Then you need to add English. This will change things quite a bit,
because now the balls don't travel in straight lines.

Anyway, have fun... ;-)

[Evan]

D'oh, move the lines that swap the directions AFTER the four 'double
t_<rail name> = <blah>' lines....

[Chris Croughton]

On 20 Mar 2005 00:01:49 -0800, Evan
<ev****@gmail.com> wrote:

Adding balls that have some size complicates that part there. Because
now they collide before the trajectory lines cross, and you have to
find out how much before. My suggestion is to draw diagrams and try to
figure it out; it'll take a bit of trig. Just remember to consider the
case where the lines meet outside of the table but the balls hit each
other inside the borders. (That is, you can't ignore any of the pairs
because they meet outside the borders until you find out where the
balls actually hit.)
It's worse than that (it's dead, Jim!). The resultant trajectories of
balls with non-zero size colliding deoends on where they hit as well as
the velocities involved. A 'clip' or 'graze' has a very different
effect from a collision where the two centers of mass are on the same
line as the relative velocity, even assuming that the balls have no
friction between each other.
Then you've got the skeleton in of a good billards program. ;-) Next
you need to factor in friction. This will just complicate a couple of
the formulas (you'll have to integrate), and also cause vx and vy to
change from iteration to iteration, but won't substantially change the
solution.You'll have to deal with the situation where balls stop
moving. (With perfect numbers this won't happen, but eventually
roundoff will cause the probably value to be 0.)
If you are doing a complete simulation of friction, there is a residual
value which still acts at zero speed so things will come to a complete
stop in the Real World(tm) as well (ignoring molecular and atomic
motions). Friction is decidedly non-linear.

Friction between balls on glancing shots will also introduce spin (and
spinning balls colliding will be an 'interesting' (in the sense of the
curse) exercise).
Then you need to add English. This will change things quite a bit,
because now the balls don't travel in straight lines.
Nor do they bounce off other things in expected ways.
Anyway, have fun... ;-)

I think the phrase is "The rest is left as an exercise for the reader"
<g>.

(There is probably a better newsgroup as well, one on games algorithms
possibly. It's not a C++ problem, anyway, it's a physics one, possibly
some of the sci.* newsgroups will have answers to some of the
questions...)

Chris C

[Howard]

"Dean Ware" <no****@nospam.com> wrote in message
news:eX*****************@newsfe2-gui.ntli.net...

I am trying to construct a model for use in a video game

This is a problem that really has nothing to do with the C++ language, which
is what is discussed here. You might try a gaming or simulation newsgroup
(although I have no idea what those might be), or do some searches on
groups.google.com, using terms like "simulation", "modeling", and
"collision".

That said, making some very strict assumptions (as you have), it is possible
to make the model totally deterministic, such that the same initial
conditions would result in the same "final" state, but any formula to
compute that final state would be horrendously complex (assuming it's
possible at all). Most likely, you'd have to rely on simulation techniques.

One approach might be to find the "next" collision (in time) from any given
set of conditions, then move everything to the state they'd be in at that
time, make your changes to the state of the balls due to the collision, and
repeat the process. At the point where the "next" collision comes later in
time than the desired final state time, step forward just to the final state
time and report your results.

How to calculate the "next" collision, and how to make the transformation(s)
at that point in time, are, as they say, exercises left to the reader. :-)

-Howard

[Dean Ware]

> groups.google.com, using terms like "simulation", "modeling", and

"collision".
I have done those searches. Everyone seems to be using iterative
aproximations.
compute that final state would be horrendously complex (assuming it's
possible at all).

This is what I am interested."Is it possible?" "If so, how" "if not, why
not"

[Dean Ware]

"Dean Ware" <no****@nospam.com> wrote in message
news:Lo*******************@newsfe1-gui.ntli.net...

groups.google.com, using terms like "simulation", "modeling", and
"collision".
I have done those searches. Everyone seems to be using iterative
aproximations.

compute that final state would be horrendously complex (assuming it's
possible at all).

This is what I am interested."Is it possible?" "If so, how" "if not, why
not"

Also apologies. I know this is the wrong group for this question. I tried in
alt.math and alt.sci.physics but most people didn't understand the question.
You did, so I answered here :-p

[Karl Heinz Buchegger]

Dean Ware wrote:

groups.google.com, using terms like "simulation", "modeling", and
"collision".
I have done those searches. Everyone seems to be using iterative
aproximations.

For a good reason.

compute that final state would be horrendously complex (assuming it's
possible at all).

This is what I am interested."Is it possible?" "If so, how" "if not, why
not"

Theoretically it is possible. The billiard players do it all the time.
But as said: taking everything into account it will get tremendously
complex.

You might start with simplifying your billiard model. Personally I would
drop the problem of accounting for rotating balls first. They induce a drag
and the balls don't wander on straight lines any more. But straight lines
simplify the model, since their intersections can easily be computed.

The main problem in simulation is always the same: Reality is much to
complex to do a complete simulation. You need to accept some simplifications
all the time.

--
Karl Heinz Buchegger
kb******@gascad.at

[Thomas Matthews]

Dean Ware wrote:

I am trying to construct a model for use in a video game

Basically I have boiled things down to the following situation that needs to
be modelled:



Think of a snooker/pool table (without the pockets) with two balls on it.

The balls bounce around colliding with the sides of the table and each
other. Perfectly elastically for simplicity.

For further simplicity, there is no friction. Maybe they have unit mass.

Basically picture two circles bouncing around inside a rectangle.

My question is:

Given:

1) the dimensions of the rectangle and the circles.

2) the initial velocities of the circles

Is there an equation where I can find the location of the circles at time t?

A better method is to convert the table into a coordinate system.
Give each ball a location.
In your simulation, just query each ball's location.

_I_ would create a ball class that has properties of the ball,
such as magnitude and velocity as well as current position.
Add some methods for calculating the next position as well
as some methods for bouncing off of the rectangle and
intersecting with other balls.

Let your simulation work in chunks of time, dt (the difference in
time or lenght of a chunk). Add methods to the ball to calculate
its next or current position based on dt. The main loop would
call this method for each ball. You could also add some display
methods too, which would erase their old position and draw themself
at the new position.

In summary, I believe the simulation will be easier if you
think in terms of time chunks. Think of what needs to be performed
during one slice or chunk of time. Think not of trying to figure
out how to perform a window or subscript of the big picture.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library