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

Assignment handout, as offered in Spring 2017.
Helper files, including a variety of real and artifical universes and associated image and sound files.

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.