A better particle simulator

Taking CS 61B at UC Berkeley, the first “mini-project” for this semester is to build a particle simulator according to the spec. But, there are some oversimplifications within this spec that cause the resulting “correct” particle simulator to be quite unrealistic. Here, I attempt to make it slightly better.

Types of Particles

First, we make particles fall into the following types instead of having them all be a Particle:

• Solids (SolidParticle)
• Powders (PowderParticle)
• Liquids (LiquidParticle)
• Gases (GasParticle)
• Effects (EffectPaticle)

This simple change actually causes us to change a lot of the underlying structure that underpins the original simulator. Firstly, a grid of Particles isn’t really “particles” — rather, it’s a grid of “holder” classes that contain some particle attributes.

The problem is that before, all of our particles were just the Particle class, so changing some attributes worked. But now, we want to encapsulate different actions for each type of particle with each particle’s subclass. However, since the grid of particles only supports using Particle, we can’t exactly just copy over the flavor of the particle: this loses all of the customized actions we had for each type of particle.

Therefore, we change the base Particle class to just be a “holder” for its subclasses. It doesn’t actually hold any direct information about the flavor of particle in it: all it has is a pointer to the actual particle subclass that it contains. This is achieved by introducing a “contains” and “parent” attribute:

public ParticleFlavor flavor;
public Particle contains;
public Particle parent;

public Particle() {
    this.flavor = ParticleFlavor.EMPTY;
    this.contains = null;
    this.parent = null;
}

public Particle(Particle contains) {
    this.flavor = ParticleFlavor.EMPTY;
    this.contains = contains;
    this.parent = new Particle();
}

Instead of directly creating new particles, we can create a static helper method to handle this for us:

public static Particle newParticle(ParticleFlavor flavor) {
    Particle holder = new Particle(null);
    if (POWDER_PARTICLES.contains(flavor)) {
        holder.contains = new PowderParticle(flavor, holder);
        return holder;
    } else if (LIQUID_PARTICLES.contains(flavor)) {
        holder.contains = new LiquidParticle(flavor, holder);
        return holder;
    } else if (SOLID_PARTICLES.contains(flavor)) {
        holder.contains = new SolidParticle(flavor, holder);
        return holder;
    }
    return holder;
}

This means that we can now write our moveInto() function like so:

/** Move the current particle into another particle. Must be called from a subclass of Particle. */
public void moveInto(Particle other) {
    other.contains = this;
    this.parent.contains = null;
    this.parent = other;
}

Sand

One of the most noticeable problems with the base simulation is that the way powders work (or in this case, sand) is very unintuitive — they just stack up in a line! Instead, powders should fall into a slope formation. To achieve this, instead of simply falling down, PowderParticles should also check for the diagonals:

We also need to update our Direction enum:

public enum Direction {
    NORTH,
    SOUTH,
    WEST,
    EAST,
    NORTHWEST,
    NORTHEAST,
    SOUTHWEST,
    SOUTHEAST
}

I’ve changed it to use the cardinal names for directions. Next, we change the default fall method to:

/** If the particle below is empty, fall into that particle; otherwise, fall diagonally. */
public boolean fall(Map<Direction, Particle> neighbors) {
    // check the particle below
    Particle down = neighbors.get(Direction.SOUTH);
    if (down.contains == null) {
        moveInto(down);
        return true;
    }

    // otherwise, randomly start checking the left or right diagonal
    int choice = StdRandom.uniformInt(2);
    Direction[][] dirs = {
            new Direction[]{Direction.SOUTHEAST, Direction.EAST},
            new Direction[]{Direction.SOUTHWEST, Direction.WEST}
    };
    for (int i = 0; i < 2; i++) {
        Particle diagonal = neighbors.get(dirs[(choice + i) % 2][0]);
        Particle adjacent = neighbors.get(dirs[(choice + i) % 2][1]);
        if (diagonal.contains == null && adjacent.contains == null) {
            moveInto(diagonal);
            return true;
        }
    }
    return false;
}

Notice that this method returns a boolean now. This is because later, we want to know whether or not the particle was successful in finding a place to fall.

Water

The flow of water is another egregious example of how the base simulation is terrible: it assings an equal probability for water particles to either stay in the same place, move to the left, or move to the right.

In fact, water should move in much of the same way as sand does, except this time we also want it to spread left or right randomly:

public boolean fall(Map<Direction, Particle> neighbors) {
    // try the standard falling sand algorithm
    boolean fell = super.fall(neighbors);
    if (fell) {
        return true;
    }

    // otherwise, randomly spread left or right
    int choice = StdRandom.uniformInt(2);
    Direction[] horizDirs = {Direction.EAST, Direction.WEST};
    for (int i = 0; i < 2; i++) {
        Particle horizontal = neighbors.get(horizDirs[(choice + i) % 2]);
        if (horizontal.contains == null) {
            moveInto(horizontal);
            break;
        }
    }
    return false;
}

Directional Bias

At this point, you will realize that the water flows to the left way more than the right. This is because we start processing from the left, which cause the actions to be biased toward the left.

However, we can’t just simply randomize all the coordinates. By doing so, particles falling might exhibit some chaotic behavior when we process particles that are higher up before those that are lower, causing gaps and particles to wander unpredictably. Instead, we randomize the x-coordinate by shuffling the columns, while still preserving the bottom-to-top processing order:

public void tick() {
    // shuffle all the columns to update in random order
    List<Integer> columns = new ArrayList<>();
    for (int i = 0; i < width; i++) {
        columns.add(i);
    }
    Collections.shuffle(columns);

    // process each particle
    for (int y = 0; y < height; y++) {
        for (int x: columns) {
            if (particles[x][y].contains != null && particles[x][y].contains.updated) {
                continue;
            }
            if (particles[x][y].contains != null) {
                particles[x][y].contains.updated = true;
                particles[x][y].contains.decrementLifespan();
            }
            if (particles[x][y].contains != null) {
                particles[x][y].contains.interact(getNeighbors(x, y));
            }
            if (particles[x][y].contains != null) {
                particles[x][y].contains.action(getNeighbors(x, y));
            }
        }
    }

    // reset all updated flags
    for (int i = 0; i < width; i++) {
        for (int j = 0; j < height; j++) {
            if (particles[i][j].contains != null) {
                particles[i][j].contains.updated = false;
            }
        }
    }
}

Notice that I’ve also added a updated flag for each particle. This is so that gas particles, which move upwards, don’t get processed twice in a single tick.

Fire

This will be our first effect particle. Effect particles, like fire, require some sort of activator particle next to it in order to sustain the effect; otherwise, it will cause its lifespan to run out:

// reset lifespan if next to an activator
for (Direction dir : Direction.values()) {
    Particle neighbor = neighbors.get(dir);
    if (neighbor.contains != null && activators.contains(neighbor.contains.flavor)) {
        this.lifespan = 300;
        break;
    }
}

Steam

Time to implement a gas particle! Fire by itself isn’t very interesting — but if you mix it with some water, we can create some steam. The key here is to implement an interact method that handles interactions between different particles:

@Override
public void interact(Map<Direction, Particle> neighbors) {
    // reset lifespan if next to an activator
    for (Direction dir : Direction.values()) {
        Particle neighbor = neighbors.get(dir);
        if (neighbor.contains != null && activators.contains(neighbor.contains.flavor)) {
            this.lifespan = 300;
            break;
        }
    }

    // steam when fire meets water
    if (this.flavor == ParticleFlavor.FIRE) {
        Particle north = neighbors.get(Direction.NORTH);
        Particle south = neighbors.get(Direction.SOUTH);
        Particle east = neighbors.get(Direction.EAST);
        Particle west = neighbors.get(Direction.WEST);
        if ((north.contains != null && north.contains.flavor == ParticleFlavor.WATER) ||
                (south.contains != null && south.contains.flavor == ParticleFlavor.WATER) ||
                (east.contains != null && east.contains.flavor == ParticleFlavor.WATER) ||
                (west.contains != null && west.contains.flavor == ParticleFlavor.WATER)) {
            this.parent.contains = new GasParticle(ParticleFlavor.STEAM, this.parent);
            if (north.contains != null && north.contains.flavor == ParticleFlavor.WATER) {
                north.contains = new EffectParticle(ParticleFlavor.FIRE, north);
                north.contains.updated = true;
            }
            if (south.contains != null && south.contains.flavor == ParticleFlavor.WATER) {
                south.contains = new EffectParticle(ParticleFlavor.FIRE, south);
                south.contains.updated = true;
            }
            if (east.contains != null && east.contains.flavor == ParticleFlavor.WATER) {
                east.contains = new EffectParticle(ParticleFlavor.FIRE, east);
                east.contains.updated = true;
            }
            if (west.contains != null && west.contains.flavor == ParticleFlavor.WATER) {
                west.contains = new EffectParticle(ParticleFlavor.FIRE, west);
                west.contains.updated = true;
            }
        }
    }
}

With all of this in place, we now get a much better-looking particle simulation: