Physics for the Browser
Prior to becoming a Panda, I studied as a theoretical chemist. So, while my computer science education is not exactly traditional, I learned a great deal about applying computers to physical models.
The toy I've built for your entertainment honors both the old and new in my life. The browser conducts a 2-dimensional simulation of free particles that exert an attractive force on each other. The resulting dynamics are rendered, live, to the screen via an HTML canvas element. <small> Image courtesy of NASA/JPL/Caltech </small>
There are several parameters available for you to modify. I encourage you to play with them and watch their effects on the particles' behavior. I'll discuss the details more below, but here are some guiding principles.
- More particles require more calculation, so increasing the particle count might allow you to see a frame rate slowdown.
- You can control how quickly time passes in the simulation, but if you try to go too fast, the simulation becomes unstable.
- You can give your cursor a gravity field that will draw in particles.
The simulation operates on an exchange of potential and kinetic energy, and it gives you the ability to manipulate that balance. When the simulation starts, the particles are evenly distributed, giving the system a lot of potential energy. The amount of potential energy depends on the strength of the attraction (gravity) you have set. As the particles draw each other in, the potential energy is converted to kinetic and the particles speed up.
When a particle hits a wall, its reaction depends on the wall's elasticity. An inelastic setting slows the particle and removes energy from the system. An elastic setting conserves energy by reflecting the particle at the same speed, but in a different direction.
This simulation is an example of the N-Body Problem, a classic in the physics and computer science fields. Here's how it's laid out:
Given N bodies in space <small>Bodies massive enough to exert meaningful gravitational forces on each other.</small>, their initial positions and velocities<small>So, speed and direction.</small>:
Can you predict the position and velocity of the bodies at any time in the future?
It turns out that for any setup with more than two bodies, the math gets sticky. You can do some impractical math-trickery for three bodies, but there is no known analytical solution for N > 3. <small> Very frustrating to people trying to work out celestial mechanics. Mathematicians struggled for over 200 years to find a solution. You can approximate the orbit of a planet around the sun with two-body mechanics, but there are always pesky perturbations from the other planets.</small> The integral describing one body's motion includes terms for the influence of other bodies, but that influence changes as everything moves.
To get around this, we need to simplify the problem. The force exerted by gravity can be expressed fairly simply, so it's easy to evaluate if we only look at the bodies' starting positions. The problem is trying to integrate out to some future time. However, in the limit of Δt = 0, the positions don't change that much, so we can assume that the forces involved are constant. That makes things much easier, and if you accept some small amount of error, you can answer the N-Body Problem for some small Δt into the future.
That doesn't sound like much, but it gives us a way to approach the problem:<small> What follows simplifies the process somewhat. The toy uses an algorithm called Velocity-Verlet integration, a standard integration technique valued for its efficiency and stability. What's described below is actually the Euler method, which is good for describing the concept of numerical integration but prone to instability. </small>
- Starting with their positions, you can evaluate the force each body experiences. Using Newton's Second Law, you can get the acceleration each body experiences.
- Remember that we assume the force (and therefore, acceleration) each body experiences is constant so long as you only advance the simulation a teeny, tiny amount. This is called a timestep. Using the constant acceleration and the timestep size, you can update the velocity.
- Using the new velocity and the timestep size, you can update the position of every body.
- We have the slightly updated positions. Now, you can return to step 1 with the new positions and keep going!
Each timestep barely changes the system with its updates. But when chained together, you get accurate dynamics, like frames in a film. This concept is called numerical integration, and it is a powerful way to handle problems that are otherwise difficult to express analytically. <small>Provided you have a computer and some patience.</small>
It's Not All Sunshine and Rainbows
There are downsides to numerical integration. It is the definition of brute-force, and there are limits.
Aside from the complexity of increasing the system's size<small>In our case, ignoring some other tricks we can use, evaluating the force on every body has a complexity of O(n^2). Adding bodies to the system quickly gets painful.</small>, any numerical approach will eventually succumb to instability. You have to feed the algorithm your answer from the previous step to keep going, and that has consequences:
Earlier timesteps are given more importance. That means that errors in the initial conditions are greatly amplified, a problem for complex systems that exhibit emergent behavior. Seemingly small changes can lead to drastically different outcomes, a concept famously popularized by Jurassic Park.
Even if you have perfect initial conditions, you still accumulate errors. And even if the errors are small, over millions of iterations your simulation will diverge from the true future and become worthless for predictive purposes. This is why you can't trust weather forecasts beyond 72 hours and why NASA can't promise we won't be wiped out by a rogue asteroid beyond the next few decades.
It all comes down to the fact that numerical integration is an approximation of the right answer. While it's true that, in the limit of Δt = 0, we can simplify our problem, you can't run a simulation with a timestep size of zero. You have to choose a non-zero size and accept a non-zero error. There is a constant and almost poetic tension between getting an accurate answer and getting it in a reasonable amount of time.
I Took the Path Less Computationally Intensive, And That Has Made All The Difference
My primary objective was to build a toy that is visually appealing. Since the results of the simulation are drawn to the screen immediately, and an ideal frame rate is 60fps, each timestep needs to complete evaluation in under 17ms. It also means that a larger timestep size is desirable because the particles move and flow more quickly. Neither of these favor physical accuracy, so I took some shortcuts.
I restrict the simulation to two dimensions. This greatly reduces the complexity of the force evaluation and allows it to finish faster.
I flatten the gravitational attraction between bodies. Gravity operates via an inverse-square relationship, so its strength grows quickly at small distances. This sudden change in force requires smaller timesteps to integrate properly. Otherwise, the large force is applied for too long, adding energy to the system. <small>In molecular dynamics, this is referred to as numeric heating. However, my favorite integration artifact has to be flying ice.</small>
This tendency for the energy's system to grow motivated me to include inelastic wall collisions to gradually pull it back out. I also include an upper limit on the particle's speed as a final fail-safe for settings with poor integration performance.
I placed the code for this simulator into this repo. There are instructions if you'd like to get it running for yourself and tinker with the code. Oh, and the page is served by Panda Strike's new static server with asset pipelining, Haiku9.
When You Hit A Wall, Smash Through And Keep Going
I would like to thank Dr. Steven Stuart for starting me down this path and for letting me know that, yes, I can make a living doing interesting things on a computer.