CS130N Assignment 3: Discrete event simulation and some graphics animation

Problem statement:

This is an assignment about the simulation of the motion of balls in a frictionless medium (almost like ice). There are $n$ balls of radius $r$ each, where $r$ is fixed and much smaller than 1. Each ball has the same unit mass (this matters when two balls meet). At time zero, the balls are placed in random locations in a unit square or unit circle and are assigned random initial velocities (associate a vector ${\bf v}$ with each ball; it may be a good idea if the velocities sum up to ${\bf0}$). You can consider either of the following situations:

1. the terrain is a unit square. The balls start moving around with constant speed until they meet another ball or until they hit the boundary.
2. the terrain is the infinite plane. In such a case assume that centers of balls are connected with invisible strings of length 2. The balls start moving around with constant speed until they meet another ball or until one of the $n-1$ ropes emanating from its center gets stretched. If you make sure that the sum of the initial velocity vectors is zero, then the pack of balls will not wander off to infinity (conservation of momentum).

In either case, a collision/stretch event causes the balls to change direction and velocity according to the laws of physics. That is, they instantly change velocity and move in the direction given by the new velocity vector. There is a section further on that helps you with some of the mathematical problems related to collisions, velocities, and geometry.

You have to animate the motion of the balls on a graphic screen up to some finite time. You may choose either of the above options.

Howto:

The simulation has to be driven by events. An event is an impact. For each ball, you have to keep track of the next event, and the next events are kept in a heap, ordered according to the times of the events (smallest on top). Deleting the top of the heap drives your simulation. As you make an event happen, you must recompute the next collision(s) for the ball(s) involved in the event. This may affect some other events, and you may wish to implement the operation "cancel". Also, new events are inserted in the future event heap. You should keep the state of your system in one data structure--this includes for each ball, say, its last known position, the corresponding time, and its velocity; also, you may have for each ball pointers to other balls or to the heap so that you can implement cancel very easily. In fact, it is a good idea to have to-and-from pointers between the items in the state and items in the heap.

Continuous uninterrupted time simulation is usually performed by letting $t$ jump ahead by small deltas. At these multiples of delta, you'll draw a screen. Drawing a screen is treated as any other event--it is something you'll put on the heap. When the draw-screen event comes off the heap, the screen is drawn. For "impact" type events, the screen is not drawn, for otherwise, you would lose the continuity effect. For better performance, you do not redraw the screen. Just erase the old balls (draw again with background colour) and draw new balls. That should give you a juicy real-time simulation on most systems and add some animation/colour to your life!

For the graphics part you should use Java applets. You can look at the following applet demos for tips:

1. Circle demo, Java source
2. Towers of hanoi demo, Java source

You should also look at the html page source.

You may face some problems with running Java applets in standard browsers (IE or Netscape). You may be better off testting your programs with /bin/appletviewer on ccsun50. For this you would need to grab a X-terminal/Sun terminal. You may also run it on a windows or linux machine provided JDK is available.

Submission:

Submit a single file called animation.java by clicking here. The last date is April 15 (firm). This assignment can be done in groups of two.

Some kinetics

Here are a few facts that may help you. If a ball's position at time $t_0$ is ${\bf x_0}$, and its velocity is ${\bf v}$, then at time $t$, it is found at ${\bf x} = {\bf x_0} + (t - t_0) {\bf v}$. Its velocity does not change unless a collision occurs or the ball meets one of the boundaries.

For the meeting of two balls, described at time $t_0$ by $({\bf x},{\bf v})$ and $({\bf x'},{\bf v'})$ respectively, there are three questions:

1. will they meet?
2. where and when do they meet?
3. what are the new velocity vectors after the meeting?

Let us answer these backwards. Assume we know that the balls meet at a given site. At that place, the balls have a common tangent. Picture two coordinate axes at that site, the $y$-axis being aligned with the tangent. The $x$-axis thus goes through the centers of both balls. You can decompose both velocity vectors into their $x$ and $y$ components: thus ${\bf v}=(v_x,v_y)$ and ${\bf v'} =(v'_x,v'_y)$. (Be careful! This is a decomposition with respect to this new system of axes!) Well, here is what happens: the first ball flies off with velocity $(v'_x,v_y)$, and the second one with velocity $(v_x,v'_y)$: they keep their $y$-components, and exchange $x$-components!

Finally, can we determine if, where and when two balls will meet? Let the states of two balls be described by the coordinate velocity pairs $({\bf x},{\bf v})$ and $({\bf x'},{\bf v'})$ respectively. You can choose $({\bf x},{\bf v})$ of one ball to be $({\bf0}, {\bf0})$ and compute the parameters of another ball relative to the first ball as $({\bf y}, {\bf w}) = ({\bf x'}-{\bf x}, {\bf v'}-{\bf v})$ The path of the second ball relative to the first is ${\bf y} + (t-t_0) {\bf w}$. The square of the length of this vector is a quadratic in $t$. Look when it is minimal. If that happens at time $t < t_0$, no collision will occur (the balls are moving away from each other). If it occurs at time $t > t_0$, check if the length at that point is less than $2r$: if it is, the balls will hit each other; otherwise, they won't. Suppose you know that the balls hit each other. Then the hitting time $t$ is the smallest value greater than $t_0$ for which $\Vert {\bf y}+(t-t_0) {\bf w} \Vert^2 = (2r)^2$ (a simple quadratic equation in $t$). At $t$, we know exactly where the two balls will be. The place of impact is the midpoint between the centers. Apply the rules for the impact outlined above, and off you go!

When a rope gets stretched between two balls $({\bf x},{\bf v})$ and $({\bf x'},{\bf v}')$, picture two coordinate axes, the $x$-axis being aligned with the rope, and the $y$-axis perpendicular to it at the midpoint of the rope. The $x$-axis thus goes through the centers of both balls. Again, you can decompose both velocity vectors into their $x$ and $y$ components: thus ${\bf v}=(v_x,v_y)$ and ${\bf v'} =(v'_x,v'_y)$. Here is what happens: the first ball flies off with velocity $(v'_x,v_y)$, and the second one with velocity $(v_x,v'_y)$: they keep their $y$-components, and exchange $x$-components! (This is identical to the situation in which they had actually bounced off each other.)

Of course, the balls will not meet if the meeting point is outside the unit square, in which case the balls will hit the boundary. At a boundary a ball will reflect off in a direction such that the angle of reflection is equal to the angle of incidence with the same magnitude of velocity.

Note: This assignment is an adaptation of an assignment given by Luc Devroye at Mcgill University, Canada in his data structures course.