Physics for the Browser

Overlayed on the orbits of the inner planets, the orbits of what NASA calls "Potentially Hazardous Asteroids" - AKA death from above. NASA is watching ~1500 objects it finds threatening and used N-Body simulations to determine that the Earth is safe, you know, for at least the several decades.

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. Image courtesy of NASA/JPL/Caltech

Playtime

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.

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.

The Physics

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 Bodies massive enough to exert meaningful gravitational forces on each other., their initial positions and velocitiesSo, speed and direction.:

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. 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. 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: 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.

  1. 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.
  2. 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.
  3. Using the new velocity and the timestep size, you can update the position of every body.
  4. 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. Provided you have a computer and some patience.

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 sizeIn 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., 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. In molecular dynamics, this is referred to as numeric heating. However, my favorite integration artifact has to be flying ice.

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

Numerical integration has always tested the limits computer performance, and this demo is no exception. Crank up the number of particles and you can really degrade the frame rate performance. This leads to an important consideration. Is it okay to use JavaScript for heavy computation? It’s an interpreted language, and it’s dynamically typed. Native code would run much faster, right? Well, things are changing…

For the first decade of JavaScript's existence, its performance was terrible. Something to be avoided by "serious" developers. But, Google's release of the V8 engine in 2008 kicked off a renaissance for the language, leading to better performance in the browser and the inception of projects like NodeJS.

And the improvements keep coming. Starting in 2012, browsers started implementing Just-In-Time compilation. Our browsers now scrutinize the JavaScript they run, categorizing functions into tiers based on how many times they're called or for taking too long to return. If a problem is found, the browser takes the time to apply targeted optimizations. For example, if you look at the simulator code, you can see that I am careful to coerce the strings from HTML inputs into numbers. Without this, the interpreter is forced to turn off some optimizations. And in my experience, that decreases the number of particles the simulator can handle by just under 50%.

Dan has already mentioned that regardless of what kind of web developer you are, we are all JavaScript developers. While heartwarming, there are practical benefits. Every browser can run it, and they compete with each other to do it best. We all benefit from this honing. Ultimately, all you need to do is write your intentions in high-level expression and let the compiler nerds work out the rest.

There are technologies on the horizon to get JavaScript to near-native performance. And today, there is already an experimental subset of JavaScript that can serve as a transpile target for native code. Check out this example where Unreal Engine 4 is used to run a game in a browser without plugins. JavaScript's future is bright.

Special Thanks

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.

Notes