N-Body Simulation

Robert Sedgewick and Kevin Wayne
Princeton University
wayne@princeton.edu

Overview

Students write a program to simulate the motion of n heavenly bodies in the plane, mutually affected by gravitational forces, and animate the results. Such methods are widely used in cosmology, semiconductors, and fluid dynamics to study complex physical systems.


In one version of the assignment, students use parallel arrays to maintain the position, velocity, and mass of each body. Calculating the net forces involves nothing more than a double nested loop; updating the velocities and positions are simple loops, as is drawing the bodies. There are limitless opportunities for creativity and enrichment, including modifying the laws of gravity, handling collisions, adding a third dimension, or creating a new universe.

The assignment is nifty because n-body simulation is an authentic and archetypical example of scientific computing. A small amount of code produces striking visualizations.


Resources


Metadata

Summary Students compose a program to simulate the motion of n particles, subject to Newton's laws of motion.
Topics arrays, loops, animation, scientific computing
Audience early CS1 or early CS 2
Difficulty easy
Strengths
  • Highlights a quintessential application of scientific computing.
  • Brings Newton's laws of motion and gravity to life.
  • Produces striking visualizations, using only about 75 lines of code (and no starter code).
Weaknesses
  • Debugging floating-point calculations can be a challenge.
  Dependencies   Requires a drawing library to draw and animate images, such as StdDraw.java for Java or stddraw.py for Python.
Variants Many variations of this assignments are suitable for CS1 and CS2.
  • Extend to three dimensions.
  • Use objects to represent the bodies.
  • Use spatial vectors instead of representing the x- and y-components separately.
  • Apply to other pairwise interactions, such as Coulombic, Biot–Savart, and van der Waals.
  • Achieve improved performance using advanced data structures, such as quad-trees or kd-trees.