6.1   Event-Driven Simulation

This chapter under construction.

Simulate the motion of N colliding particles according to the laws of elastic collision using event-driven simulation. Such simulations are widely used in molecular dynamics (MD) to understand and predict properties of physical systems at the particle level. This includes the motion of molecules in a gas, the dynamics of chemical reactions, atomic diffusion, sphere packing, the stability of the rings around Saturn, the phase transitions of cerium and cesium, one-dimensional self-gravitating systems, and front propagation. The same techniques apply to other domains that involve physical modeling of particle systems including computer graphics, computer games, and robotics. We will revisit some of these issues again in Chapter 7.

a good reference

Hard sphere model. The hard sphere model (billiard ball model) is an idealized model of the motion of atoms or molecules in a container. We focus on the two-dimensional version called the hard disc model. The salient properties of this model are listed below.

This simple model plays a central role in statistical mechanics, a field which relates macroscopic observables (e.g., temperature, pressure, diffusion constant) to microscopic dynamics (motion of individual atoms and molecules). Maxwell and Boltzmann used the model to derive the distribution of speeds of interacting molecules as a function of temperature; Einstein used it to explain the Brownian motion of pollen grains immersed in water.

Simulation. There are two natural approaches to simulating the system of particles.

Collision prediction. We review the formulas that specify if and when a particle will collide with the boundary or with another particle, assuming all particles travel in straight-line trajectories.

Collision resolution. In this section we present the physical formulas that specify the behavior of a particle after an elastic collision with a reflecting boundary or with another particle. For simplicity, we ignore multi-particle collisions. There are three equations governing the elastic collision between a pair of hard discs: (i) conservation of linear momentum, (ii) conservation of kinetic energy, and (iii) upon collision, the normal force acts perpendicular to the surface at the collision point. Physics-ly inclined students are encouraged to derive the equations from first principles; the rest of you may keep reading.

Particle collision simulation in Java. Our implementation involves the following data types: MinPQ.java, Particle.java, and CollisionSystem.java.

Data files. We use the following data format. The first line contains the number of particles N. Each of the remaining N lines consists of 6 real numbers (position, velocity, mass, and radius) followed by three integers (red, green, and blue values of color). You may assume that all of the position coordinates are between 0 and 1, and the color values are between 0 and 255. Also, you may assume that none of the particles intersect each other or the walls.

rx ry vx vy radius mass r g b
rx ry vx vy radius mass r g b
rx ry vx vy radius mass r g b
rx ry vx vy radius mass r g b
Here are some sample data files:

p10.txt 10 particles
p2000.txt 2000 particles
wallbouncing.txt 9 particles in a row colliding with 9 particles in a column
wallbouncing2.txt 10 particles in a row not colliding with 9 particles in a column
wallbouncing3.txt 19 particles in a row colliding with 19 particles in a column
p100-.125K.txt 100 particles at 0.125 Kelvin
p100-.5K.txt 100 particles at 0.5 Kelvin
p100-2K.txt 100 particles at 2.0 Kelvin
p1000-.5K.txt 1000 particles at 0.5 Kelvin
p1000-2K.txt 1000 particles at 2.0 Kelvin
billiards2.txt cue ball striking pyramid of 3 balls
billiards4.txt cue ball striking pyramid of 10 balls
billiards5.txt cue ball striking pyramid of 15 balls
diffusion.txt diffusion of particles from one side of slit
diffusion2.txt diffusion of particles from one quarter
squeeze.txt one tiny particle sandwiched between two big particles
squeeze2.txt one tiny particle sandwiched between two big particles
pendulum.txt pendulum effect

Other potential data files


  1. Particle collision game. Implement the game Particles: you control a red ball with a mouse, trying to avoid colliding with blue balls that behave according to the laws of elastic collision. After a certain interval of time, introduce a new blue ball at random.
  2. Brownian motion. In 1827, the botanist Robert Brown observed the motion of wildflower pollen grains immersed in water using a microscope. He observed that the pollen grains were in a random motion, following what would become known as Brownian motion. This phenomenon was discussed, but no convincing explanation was provided until Einstein provided a mathematical one in 1905. Einstein's explanation: the motion of the pollen grain particles was caused by millions of tiny molecules colliding with the larger particles. He gave detailed formulas describing the behavior of tiny particles suspended in a liquid at a given temperature. Einstein's explanation was intended to help justify the existence of atoms and molecules and could be used to estimate the size of the molecules. Einstein's theory of Brownian motion enables engineers to compute the diffusion constants of alloys by observing the motion of individual particles. Here's a flash demo of Einstein's explanation of Brownian motion from here.
  3. Free path and free time. Free path = distance a particle travels between collisions. Plot histogram. Mean free path = average free path length over all particles. As temperature increases, mean free path increases (holding pressure constant). Compute free time length = time elapsed before a particle collides with another particle or wall.
  4. Collision frequency. Number of collisions per second.
  5. Root mean-square velocity. Root mean-square velocity / mean free path = collision frequency. Root mean square velocity = sqrt(3RT/M) where molar gas constant R = 8.314 J / mol K, T = temperature (e.g., 298.15 K), M = molecular mass (e.g., 0.0319998 kg for oxygen).
  6. Maxwell-Boltzmann distribution. Distribution of velocity of particles in hard sphere model obey Maxwell-Boltzmann distribution (assuming system has thermalized and particles are sufficiently heavy that we can discount quantum-mechanical effects). Distribution shape depends on temperature. Velocity of each component has distribution proportional to exp(-mv_x^2 / 2kT). Magnitude of velocity in d dimensions has distribution proportional to v^(d-1) exp(-mv^2 / 2kT). Used in statistical mechanics because it is unwieldy to simulate on the order of 10^23 particles. Reason: velocity in x, y, and z directions are normal (if all particles have same mass and radius). In 2d, Rayleigh instead of Maxwell-Boltzmann.
  7. Pressure. Main thermodynamic property of interest = mean pressure. Pressure = force per unit area exerted against container by colliding molecules. In 2d, pressure = average force per unit length on the wall of the container.
  8. Temperature. Plot temperature over time (should be constant) = 1/N sum(mv^2) / (d k), where d = dimension = 2, k = Boltzmann's constant.
  9. Diffusion. Molecules travel very quickly (faster than a speeding jet) but diffuse slowly because they collide with other molecules, thereby changing their direction. Two vessels connected by a pipe containing two different types of particles. Measure fraction of particles of each type in each vessel as a function of time.
  10. Time reversibility. Change all velocities and run system backwards. Neglecting roundoff error, the system will return to its original state!
  11. Maxwell's demon. Maxwell's demon is a thought experiment conjured up by James Clerk Maxwell in 1871 to contradict the second law of thermodynamics. Vertical wall in middle with molecule size trap door, N particles on left half and N on right half, particle can only go through trap door if demon lets it through. Demon lets through faster than average particles from left to right, and slower than average particles from right to left. Can use redistribution of energy to run a heat engine by allowing heat to flow from left to right. (Doesn't violate law because demon must interact with the physical world to observe the molecules. Demon must store information about which side of the trap door the molecule is on. Demon eventually runs out of storage space and must begin erasing previous accumulated information to make room for new information. This erasing of information increases the entropy, requiring kT ln 2 units of work.)
  12. Metric space. Extend to support spheres and hyperplanes in an arbitrary metric space.
  13. Cell method. Useful optimization: divide region into rectangular cells. Ensure that particles can only collide with particles in one of 9 adjacent cells in any time quantum. Reduces number of binary collision events that must be calculated. Downside: must monitor particles as they move from cell to cell.
  14. Multi-particle collisions. Handle multi-particle collisions. Such collisions are important when simulating the break in a game of billiards.
  15. Kinetic heaps or kinetic data structures. (Guibas)

Creative Exercises