Particle Systems

Keith Schwarz, Stanford University (htiek@cs.stanford.edu)

In this CS2 assignment, students use a linked list to implement a simple particle system, a collection of graphical particles that move around the screen. Students practice core operations on linked lists (appending items, removing items, and mutating a list during iteration) and are rewarded with an impressive graphical payoff. The assignment works well for a CS2 course with an audience of both majors and nonmajors: CS majors gain practice working with linked lists and nonmajors build a product whose appeal lies outside of pure CS.

Students are tasked with implementing a type called ParticleSystem that manages a linked list of individual particles. In the version of the assignment we've used, we've required students to use a doubly-linked list, but the assignment would work just as well with a singly-linked list (or a circularly-linked-list, XOR-linked list, etc.).

The ParticleSystem type supports the following four methods, which are roughly arranged in ascending order of difficulty. Each method is designed to exercise a specific set of linked list mechanics.

Linked lists are a good fit for maintaining a particle system because they support efficient deletion at random positions. Specifically, we require students to cull particles that move off-screen or that are too old, and to do so during the loop that moves particles. This gives students practice with looping over a linked list while removing items. Furthermore, some particles can "explode" in a shower of other particles, so students must iterate over a linked list while both adding and removing elements.

The student's ParticleSystem type is then used in a collection of "scenes." Each scene supports tick() and draw() methods that advance time forward and render the scene, respectively. We provide students with working code for the six scenes shown below and suggest (but do not require) that students implement more scenes beyond these.

Fireworks Fountain
A fireworks show. Fireworks launch from the bottom of the screen. When a firework reaches the apex of its flight, it explodes and sends colored streamers in all directions. A fountain with jets of water. Individual water droplets gush out from multiple points on the fountain, reach the apex of their flight, and fall back down to the bottom.
Magic Wand Photo Exploder
A magic wand moves around a background, trailing a stream of colorful particles. At one point, a huge shower of particles stream out from the magic wand in all directions. A swarm of colored dots in a seemingly random pattern coalsece back together to reveal a picture of an animal in a forest. The final image is only comprehensible once all the particles reassamble.
Snowy Day Volcano
A window looks out over a dark blue sky. Suddenly, it begins to snow, and a large number of snowflakes drift slowly downward past the window panes. A volcano erupts, sending up clouds of gray particle smoke and ejecting red, yellow, and orange particles in a spray.

We ask students to support three types of particles. Streamers move in a straight line. Ballistic particles accelerate downward due to gravity. Fireworks are like ballistic particles but explode in a shower of streamers after a period of time. We chose the first two because they are useful in simple scenes and the last for practice with appending to a list during iteration. To keep the assignment footprint small, we handle different particle types using an enum of possibilities, but this could easily be changed using subclassing to support a variety of more interesting particles. The difficulty of the assignment can be dialed up by adding other particle types or down by removing fireworks.

We provide students with a test-driver framework that includes 20+ prewritten test cases. Students are then asked to contribute their own test cases for specific parts of the assignment. You can share all the tests with students as we do when teaching the course, or you could hold some of them back for use in an autograder.

Summary Students implement a simple particle system backed by a doubly-linked list, gaining practice with linked list mechanics while building visually impressive demos.
Topics Linked lists, class design, graphics.
Audience CS2.
Difficulty Moderate. Can be made more challenging by requiring the use of singly-linked lists.
Length We ask students to complete this assignment in one week.
Strengths This assignment provides practice with linked lists and class design in a context that has appeal beyond pure computer science. Students appreciated the "wow!" factor of the demos and seeing their code in action.
Weaknesses This assignment does not cover every major operation on linked lists (there's no concatenation, splicing, reversal, etc.) While there is some discussion of big-O notation, the degree of big-O analysis needed here is less than what would appear in a more traditional linked list assignment.
Dependencies The assignment requires a graphics package. In languages like Java that ship with one that's not a big deal, but for courses taught in C or C++ you'll need an auxiliary graphics library to run the demos.
Variants Students could be required to implement their own graphics scenes to get practice being a client of their ParticleSystem type. More types of particles could be introduced into the assignment. Particles could be required to interact with one another.
Teaching Notes We use a doubly-linked list in this assignment so that the logic for removing linked list cells during iteration is easier (there's no need for a previous pointer). Depending on how you teach linked lists, you could easily swap out doubly-linked lists for singly-linked lists, require dummy head/tail cells, make the list circular, etc.

Materials