Particle System

Part Three: Particle Systems

Many computer-generated visual effects - whether in blockbuster Hollywood movies or in video games - make use of particle systems. As the name suggests, a particle system is a system that consists of individual units called particles. Those particles can have attributes like position, color, velocity, etc., and by maintaining systems consisting of hundreds or thousands of particles it's possible to build some beautiful effects from simple pieces.

In this part of the assignment, you'll implement a simple 2D particle system that can be used to create a variety of aesthetically-pleasing scenes. As a preview of where you're going, here are two of those scenes: a fireworks show, and a water fountain:

Each of these scenes consist of some number of particles. Those are the colorful objects moving around the screen. The particle system is the overall system responsible for maintaining those particles, updating their positions in space, etc.

Your overall goal is to implement the following class:

class ParticleSystem {
public:
    ParticleSystem();
    ~ParticleSystem();

    void add(Particle particle);
    int numParticles() const;
    void drawParticles() const;
    void moveParticles();

private:
    // Described later
};

Let's walk through how this works. You're familiar with constructors and destructors and can probably guess what the top two functions do: ParticleSystem() creates a new, empty particle system. ~ParticleSystem() cleans up all memory allocated by the particle system.

The next four functions are where the magic happens. The add function adds a new particle to the scene. It takes as input a Particle object, which contains information about the particle (where it is in space, which color it is, etc.). We'll describe the Particle type in more detail later on. The next function is numParticles, which says how many particles there are in the system. The drawParticles function, as the name suggests, actually draws the particles on the screen so that the user can see them in all their particular glory. Finally, there's moveParticles, which moves all of the particles a tiny bit in space. How those particles move depends on what kind of particles you're dealing with, and that's described later.

Rather than sharing the remaining details all at once, we'll incrementally introduce the different components of the system. We've broken this project down into several milestones so that you can slowly add features in one at a time.

Milestone One: Implement Core Functions

Your first task is to implement basic functionality for the ParticleSystem type. Specifically, you'll implement the constructor, destructor, add, and numParticles functions.

To provide sufficient context to work through this milestone, let's talk a bit more about the types referenced above. You may have noticed that the ParticleSystem::add function takes as input an object of type Particle, so let's start there. Each particle has some information associated with it. That information is stored in the Particle struct type defined in "Particle.h". Here's what that looks like:

struct Particle {
    double x, y;   // Position
    Color color;   // Color

    /* ... four other fields we'll describe later. ... */
};

Let's walk through what these fields mean. The x and y data members tell you where in space the particle is. The coordinate system we use here is the same as for the Grid type: the upper-left corner of the scene is at (0, 0), with $x$ increasing from left to right and $y$ increasing from top to bottom. The color field, unsurprisingly, tells you what color the particle is.

When a client of ParticleSystem calls add, the particle they provide needs to be stored somewhere internally inside the ParticleSystem. To see how, let's look at the private section of the ParticleSystem type, which is shown here:

private:
    struct ParticleCell {
        Particle particle;
        ParticleCell* next;
        ParticleCell* prev;
    };
    ParticleCell* head;

The ParticleCell type represents a doubly-linked list cell that contains information about a particle. The particle field represents the actual particle. The two pointers next and prev represent pointers to the next and previous particles in the scene, respectively.

Inside the ParticleSystem type, the actual linked list of particle cells is pointed at by the head data member. This should initially be set to nullptr if there are no particles, and otherwise should point to the first particle in the list.

Whenever you add a new particle to the system by calling add, that particle should be inserted at the back of the doubly-linked list. (There's a good reason for this that we'll describe later.) Your implementation of add should run in time O(1) though, which means that you'll need to find a good way to track where the end of the list is so that you can jump there without having to scan the entire list.

Finally, let's talk about the numParticles function. This function should return how many total particles are in the list. However, it must run in time O(1) meaning that the runtime of the function should be independent of the number of particles in the list. This may require you to do some extra bookkeeping somewhere.

To hit the time bounds for add and numParticles, you will need to add your own member variables to the private section of the ParticleSystem class. Our test cases aren't programmed to look at the values of those variables. You will therefore need to write at least one custom test case, and possibly more, to make sure that those values are correct.

With that all being said, let's summarize what you need to do:

Some notes on this problem:

• In this part of the assignment - and more generally, throughout this assignment - you must not use any container types (e.g. Vector, string, Map, Set, etc.) and you must do all your own memory management. After all, the purpose of this assignment is to help you get accustomed to working with linked lists, which necessitates thinking about data storage in a different way.

• Draw pictures! You don't need to write much code here, but the code you write will require a good deal of attention to detail about which objects link to which.

• You are welcome to add as many helper functions as you'd like to the ParticleSystem class.

• You will need to use a mix of the arrow (->) and dot (.) operators in this part of the assignment. Here's how to tell them apart. If you are working with a pointer to an object, you must use the -> operator to select items out of the object being pointed at (this is why we see list->next in the context of linked lists). If you have a concrete, honest-to-goodness object and want to select a field out of it, you must use the . operator (hence mySet.contains when working with a Set).

Milestone Two: Draw Particles

You now have a rough outline of a particle system, but right now there's no way for anyone to see the particles you're storing. How sad - you've painted your masterpiece and then hidden it from the world! Let's rectify this.

Your next task is to implement the ParticleSystem::drawParticles function. As the name suggests, this function should draw all the particles that are in the system. You should draw them in the order in which they're stored in the particle system, so older particles (toward the front of the list) should be drawn before newer particles (toward the end of the list).

We've provided you with the handy function

void drawParticle(double x, double y, Color color);

that takes as input an $x$ and $y$ coordinate and a color, the draws a particle of the given color on the screen at that location. This function is defined in the header "DrawParticle.h", which you'll need to #include at the top of ParticleSystem.cpp to use.

To recap, here's what you need to do:

Some notes on this problem:

• You should implement this function iteratively rather than recursively, since when dealing with large particle systems there might not be enough stack space to recursively walk over all the particles.

• Our provided test cases make use of a custom type called ParticleCatcher. This is an object that intercepts calls to drawParticle so that instead of drawing the particles on the screen, the particles get written down for later inspection. We'll use this type more extensively in the later parts of this assignment as a way of checking that you've got all the particles in the right place.

Milestone Three: Move Particles

Your next task is to implement the ParticleSystem::moveParticles function, which moves all the particles in the system by a small amount. In order to do so, we're going to need to expose a bit more information about the Particle struct. In addition to the x, y, and color fields you've seen thus far, the Particle type has these others:

struct Particle {
    double x, y;   // Position
    Color color;   // Color
    
    double dx, dy; // Velocity

    /* ... two other fields we'll describe later. ... */
};

The dx and dy variables represent the velocity of the particle. Each time you call the ParticleSystem's function moveParticles, each particle's x and y fields are increased by the value of its dx and dy values, respectively. So, for example, if a particle has dx = 0 and dy = 1, then each time moveParticles is called the particle's x field will be unchanged and the particle's y field will increase by 1. This has the next effect of moving the particle down a little bit: its x position remains the same while its y position gets closer to the bottom of the screen. On the other hand, if a particle has dx = 3 and dy = -4, then whenever moveParticles is called that particle's x coordinate will be increased by 3 and its y coordinate will be decreased by 4. This has the effect of moving the particle up and to the right. Finally, it's entirely possible that a particle has dx and dy set to zero, in which case it doesn't move.

Note that in this process the values of dx and dy for each particle don't change. Later on we'll revisit this and make it possible for particles to have changing velocities - but you don't need to worry about that now.

When you create a particle with add, the Particle struct you are provided will include a dx and dy, which you should store inside your ParticleSystem. Depending on how you wrote add, you may or may not need to edit add to make this happen. You'll then use the dx and dy values of each particle to move that particle in the moveParticles function.

Once you've done this, run our tests to confirm that everything is working correctly.

Here's a summary of what you need to do:

Some notes on this problem:

• By default, if an EXPECT_EQUAL fails when comparing two real numbers, it will suffix the letter d to those numbers to indicate that they're doubles. Don't be surprised if a test case says that, say, one particle's x coordinate is 0d or 100d, for example. Just treat those as if they're 0 and 100, respectively, but that they're doubles.

• As with drawParticles, don't implement this one recursively. Iteration is your friend!

• The velocity of a particle can be arbitrarily large or small, and you shouldn't make any assumptions about the sign or magnitude of dx and dy.

• Each particle has its own velocity, which is independent of the velocities of all other particles.

• In case you want to use helper functions here, remember that C++ has quirky syntax for helper functions that return types nested inside a class. For example, if you have a helper function in your ParticleSystem that returns a ParticleCell*, when writing out the return type in the .cpp file you'd need to refer to it as ParticleSystem::ParticleCell*. See the note about this in Assignment 6 for more details.

Milestone Four: Cull Particles

So far, your particle system only has a mechanism for adding particles, and there's no way for particles to be removed. However, particles don't live forever. Specifically, there are two circumstances where particles can be removed.

First, you should remove a particle if that particle goes out of bounds. To make sure we aren't tracking particles that can't appear on the screen, when a particle is no longer on-screen, you should remove it. Specifically, a particle is considered off screen if its $x$ or $y$ coordinate is less than 0, if its $x$ coordinate is greater than or equal to the special constant SCENE_WIDTH, or if its $y$ coordinate is greater than or equal to the special constant SCENE_HEIGHT.

Second, you should remove a particle if that particle's lifetime ends. Inside of the Particle struct is an int called lifetime, as shown here:

struct Particle {
    double x, y;   // Position
    Color color;   // Color
    
    double dx, dy; // Velocity
    
    int lifetime;  // How much longer the particle lives

    /* ... one final field we'll describe later. ... */
};

Here's how lifetime works. Each time a particle moves, its lifetime decreases by one. As soon as a particle's lifetime is negative (that is, not zero, and not positive), the particle ceases to exist. If a particle has a large lifetime, it will move for a very long time before disappearing (unless it goes out of bounds). If a particle has a small lifetime, it will only move a few times before disappearing. A particle's lifetime is initially specified by the value of the Particle passed into the add function based on the needs of whoever is using the particle system.

There are two places you need to check for particles that need to be removed, First, when moveParticles is called, a particle could either move offscreen or have its lifetime run out. In that case, as soon as your call to moveParticles realizes this, it should remove the particle. Second, it's possible that the particle's position was never onscreen to begin with when it was added in add, and similarly a particle might initially have a negative lifetime when add was called. Either way, your add function shouldn't add these particles in the first place.

You will need to make some edits to your code in order to support this functionality. The trickiest bit will be in your moveParticles code. Remember that rule is that as soon as a particle needs to be removed, you should remove it. This means that you should just have one loop in your moveParticles function, which will loop over the particles, moving each particle and adjusting lifetimes, and immediately removing particles that are out of bounds or whose lifetimes end. You will need to be careful when doing this. In particular, you'll be removing particles from the doubly-linked list at the same time that you're iterating over that list. Pay close attention to how you advance from one particle to the next to make sure that you don't try looking at a ParticleCell that's been deleted, that you don't skip over particles, etc. Draw lots of pictures as you do this; it will make it a lot easier to see what you need to do here.

This property of particle systems - that arbitrary particles might need to be removed from the system - is the reason why we're storing particles in a linked list. If we used, say, a regular dynamic array, then the cost of removing a single particle would be $O(n)$ in the worst case, since we'd need to shift all the other particles back a spot. On the other hand, using a linked list allows us to remove a particle in time $O(1)$ by just splicing it out of the list.

To recap, here's what you need to do:

Some notes on this part of the assignment:

• Draw pictures! The linked list manipulations required here are not exceedingly complex, but they aren't trivial either. Having a diagram of what pointers point to which cells will help you better understand what you need to do - and debug things if something goes wrong.

• If your code crashes, run the program with the debugger enabled. You don't need to set any breakpoints to do this - just run the program until it crashes and the debugger will pause the program at the exact spot where the crash occurs. Then, use the skills you developed in the labyrinth escape: draw out the linked list nodes in memory, see what links where, and try isolating the root cause of the crash.

• Removing a particle will require you to update the doubly-linked list of ParticleCells so that the cell is no longer present in the list. You will also have to delete the memory used by the ParticleCell that you no longer need. These are two separate steps.

• Reiterating a point from above: iterating over a list while removing items from it is tricky, and you will definitely want to draw pictures here. Make sure to handle the case where the item you're removing is at the front of the list, the back of the list, and somewhere in the middle of the list. It's easy to introduce bugs into any of these places.

• Feel free to add as many helper functions as you'd like.

Milestone Five: Support Different Particle Types

You now have a working particle system - nicely done! Your final task is to make that particle system more interesting by supporting three different types of particles.

There is one final field in the Particle type that we haven't talked about yet. It's shown here:

struct Particle {
    double x, y;   // Position
    Color color;   // Color
    
    double dx, dy; // Velocity
    
    int lifetime;  // How much longer the particle lives

    ParticleType type; // What kind of particle?
};

Here, ParticleType is an enum class defined as follows:

enum class ParticleType {
    STREAMER,
    BALLISTIC,
    FIREWORK
};

These three options correspond to the three different types of particles you will need to support.

The first type is ParticleType::STREAMER, which is the sort of particle you have seen so far. It has a lifetime that drops each step and moves according to a fixed velocity.

The second type is ParticleType::BALLISTIC. This type of particle works exactly the same way as a streamer but with one change: every time a ballistic particle moves, after it moves its dy increases by one. This tiny change means that ballistic particles feel the effects of gravity and move downward faster and faster on each frame. Ballistic particles are otherwise completely identical to streamers. (Those of you with a physics background might see why this will work, but physics is by no means necessary to code this one up!)

The final type is ParticleType::FIREWORK. A firework acts like a ballistic particle in that, after it moves, its dy increases by one. However, there is one difference between a firework and a ballistic projectile. When a firework's lifetime decreases below zero, it explodes. The firework particle is removed (as usual - it now has a negative lifetime) and is replaced by a bunch of new particles representing the explosion. Specifically, create 50 new streamer particles. Each of those particles are positioned at the firework's last position. They're then given a random dx and dy between -3 and +3 and a random lifetime in the range [2, 10] (between 2 and 10, inclusive). Each streamer is given the same color, and that color should be chosen randomly. (In other words, there will be 50 streamers of the same color, but what color that is will be chosen randomly.) You can choose a random color using the function Color::random().

A note on fireworks: the newly-added streamers should go, as all new particles do, at the very end of the list of particles. That way, if a firework explodes during a call to moveParticles, the new streamer particles will also move by one step. (In fact, that's why we had you add particles to the back of the list all the way in Milestone One!)

You probably won't need to modify much code here to get this working, though depending on your implementation you might find that you need to decompose out some of your logic into helper functions to keep things readable.

We have provided some basic test coverage here to ensure that ballistic and fireworks particles accelerate as they are expected to. However, we haven't added tests to check for the other requirements here. You should write at least one test case that checks for some property that was not described here.

To summarize, here's what you need to do.

Some notes on this part:

• Decomposition is your friend. If you try writing all the logic to manipulate particles in the moveParticles function, you are going to end up with way too much code in one place and bugs will be very, very hard to track down.

• Be careful with the ordering of events. Specifically, don't remove a firework particle and then try reading its $(x, y)$ coordinates.

• Fireworks only explode if their lifetime ends, not if they move off-screen.

• Consult the Stanford C++ Library Documentation for information about how to generate random numbers in C++. It's been a long time since you last used these functions in Assignment 1!

• On some systems, you might get a warning in Qt Creator that talks about the predictability of the Color::random function. You should ignore this warning; such a warning message is meant for applications where random numbers are used in a secure context, and randomly choosing colors and directions isn't such an application.

Milestone Six: Watch the Show!

You now have a 2D particle system - nicely done! We've created a number of "scenes" (graphics demos) that use your particle system as an essential component. To see your particle system in action, select the "Scenes" option from the top-level menu. After doing so, go to the bottom of the window and use the dropdown menu to select a scene and click the button to load it. Here are the five scenes we've provided for you:

• Fireworks: A fireworks show that illustrates your firework and streamer particles.

• Fountain: A simulation of a water fountain that uses ballistic particles.

• Magic Wand: Move the mouse to wave the wand and see ballistic particles. Press the mouse down to see streamers.

• Snowy Day: A view out the window on a snowy day, made entirely of streamers.

• Photo Exploder: Use streamer particles to "explode" an image, then reassemble it.

Take some time to reflect on your journey here - isn't it amazing what you can do with linked lists?

(Optional) Part Four: Extensions

This assignment is all about linked structures, and there’s plenty of room for you to do Fun and Exciting Things with the topics we’ve covered here. Here’s some thoughts to help get you started, but the sky’s the limit here!

• The Labyrinth!: Our provided code generates random mazes using combinations of several famous algorithms and data structures. (The normal maze is generated using Kruskal’s algorithm and a disjoint-set forest, the twisted maze is generated using an Erdős–Rényi random graph with connectivity guaranteed via breadth-first search, and the starting locations are chosen by a procedure that uses the Floyd-Warshall algorithm as substep.) There are lots of fairly accessible articles online about how to generate random mazes in other ways. For example, you can use a randomized depth-first search to build mazes with lots of long, twisted hallways, or randomized Prim’s algorithm to build mazes that branch out from a central location. Wilson’s algorithm produces mazes that are sampled uniformly at random from the space of all possible mazes. Play around with these and see what you find!

  Other things you could consider: could you build a visualizer that draws the maze given a pointer to your starting location? Or could you write a program that automatically finds the shortest paths out of a maze?

• Particle Systems: There are plenty of opportunities for extensions here. You could introduce your own particle type to create effects that otherwise can't be done with what you have. Some examples: add "wiggler" particles that act like streamers, but which have a small random amount added to their $x$ and $y$ coordinates after each step. Or add "cooling" particles whose color gets darker over time. Or add "branching" particles that have a 75% chance of disappearing when their time expires and a 25% chance of creating two new branching particles in its place, each with a different velocity, when its time expires. Or add "orbiting" particles that rotate around a fixed central point.

  Each of the particle types you've seen so far move independently of all other particles. Could you introduce particles that interact with each other? For example, you could make "attractor" particles that try to move together, or "repulsor" particles that try to move away from one another. If you're up for a challenge, look up boids, a particle system that simulates flocking behavior.

  You can also create your own scenes! To do so, visit the file Scenes/MyCustomScene.h for instructions, and check out the various scene .cpp files to see how we put our scenes together. Each scene is represented by a C++ class that implements two functions: tick, which advances the scene forward one step, and draw, which displays the scene. What else can you come up with? If you create something really impressive, we'll ship it with future versions of the starter files so hundreds of future CS106B students can appreciate your handiwork!