CS184 Final Project Report

Sand Simulation Game

Dennis Feng, Garrett Wesley, Rami Mostafa



Simulation interface


Abstract

We created a two-dimensional, particle-based sand simulation game from scratch using Java. The game simulates particles falling and colliding with each other and, in addition to solid particles like sand, we implemented a variety of different particle types, such as static particles, liquid particles, and gas particles. Different particle types collide and interact with each other in different ways. We designed the simulation for extensibility and abstraction, and used object oriented methodologies such as abstract classes in order to create unique particles like wood, oil, lava, water, fire, and methane that extend the basic static, solid, liquid, and gas particle types. This also allows us to implement unique properties and interactions between particles, such as flammability of oil, wood, and methane. For our graphics, we used the Java OpenGL library (JOGL) in order to render each frame of the simulation into our interface efficiently. Our UI uses Java Swing, and the user clicks in the frame to place particles, choose particle type, and change brush size. We also implemented the additional feature of importing an image as particles into the simulation.


Technical Approach

The technical approaches used in our simulation can be roughly broken down into the basic simulation loop, the object oriented design of the various particle types, and our graphics and user interface API.

Simulation Loop

The simulation simulates the motions of particles in a grid. Every particle is a Particle type object, and the grid is a two dimensional array of Particles (particleGrid). Each particle can occupy one space on the grid and each grid space contains one particle. An ArrayList of Particles (particleList) keeps track of every particle on screen, and is updated if particles are removed or added.

The simulation runs through a permanent while loop, and every iteration of the loop is a simulation step, during which every particle is simulated. This is done by calling each Particle’s simulate() method. Particles, depending on their defined movements and interactions within simulate(), are moved around or altered at every simulation step. The simulate() method’s primary function is to update each Particle’s next position in the form of two integers nextRow and nextCol. After calling every Particle’s simulate(), we call every Particle’s updatePosition() that reassigns its new grid space to itself, and updates its own position parameters row and col.

After every simulation step, a method is called from our custom Swing JPanel to render the frame and display it in our UI. The loop is time-gated so that our simulation refreshes at a maximum rate of 60 frames per second. This is done by measuring the system time as the loop runs and sleeping the simulation if there is time left until the next frame is needed.

At each step, if the mouse is being clicked, we calculate the grid position of the mouse, and the particleGrid’s spawnParticles() method, which creates new particles of the given enum (particleTool) type, in a square of size brushWidth on the grid--as long as an existing particle does not exist in a grid space. The ParticleFactory class handles the creation of the particleTool type of particle. Both the particleTool and brushWidth are set by the UI. Erasing particles in the square and clearing the entire grid are also supported by particleTool.

As we implemented more complex interactions, we implemented finite lifetime Particles, which are particles that disappear after a number of simulation steps. Thus, we added a check during our simulate() calls that removes the Particle from the particleGrid and places it in an ArrayList (particleRemoveList) that is used to remove those particles from particleList. Furthermore, as we implemented behaviors such as burning, we allowed simulate() calls from Particles to return ArrayLists of newly created Particles. These are appended to a particleAddList, which is then appended to the particleList.

One bug we initially encountered was particles being created in the square of specified size, but then immediately “fanning out” to create an extremely dense area of Particles on the grid. We determined this was caused by not checking for Particles being created on top of one another, which resulted in Particles getting pushed out to the sides. We resolved this by not spawning particles in occupied spaces.


(Bug) Particle "fan out" compared to brush width

Another bug we encountered and eventually resolved was the creation of “bars” of sand that extended outwards from a collapsing sand pile. It appeared as though the sand in that row was getting pushed outward by each sand in the row and falling down all simultaneously at every step. We resolved this by randomizing the simulation order of Particles, and the particleList is shuffled before being looped through at each step. Later on, we also implemented the separation of the function of simulate() (which originally calculated the next coordinates, updated the Particle’s coordinates, and moved the particle’s position in the grid) to computing a Particle’s next coordinates only, and having another Particle method updatePosition() to update Particle coordinates and moved its position on the grid. This would’ve also worked to reduce this “sand bar” effect.


(Bug) "Bars" of particles being formed as they fall

Object Oriented Design

The Particle abstract class is the basis for all the types of Particles in the simulation. The main “subgroups” of Particles are the abstract SolidParticle, StaticParticle, LiquidParticle, and GasParticle classes. All the implementations of these “subgroup classes” extend from these abstract classes and inherit--and sometimes override--behaviors defined by them. The diagram below shows all of the Particle classes that we implemented and their inheritances.


Particle classes inheritence diagram

The Particle class defines all the variables and methods that are inherited or overridden by the child classes. The most important methods of the Particle class are the simulate() and updatePosition() methods which calculate the next position of the Particle and reassign its position on the grid, respectively. Most methods are abstract--such as simulate()--but others--such as updatePosition()--are defined directly in Particle.

The parameters defined for each particle include its position (int row, int col), its next calculated position (int nextRow, int nextCol) and its RGB Color. Later on, we added parameters--such as lifetime and flammability--which have default values that are overridden by some classes. Finally, every particle stores (a pointer to) the particleGrid that it is placed in and (a Pointer to) a Random object used for random number generation.

The simulate() method is defined by the abstract subgroup classes, and some . The primary function of simulate() is to define the movement of each of these particles. Below are the steps taken by the simulate() method, regardless of which class has defined it.

  1. The next position is set to the Particle’s preferred next position. For solids and liquids, the next position is the grid space underneath its current position. For gasses, the particle can move randomly up, down, left, or right with a slightly higher probability of up. For static particles, the particle stays where it is.

  2. The collide() method of the Particle is called. The collide() method checks for collisions with the particle in the desired next position. If a particle exists there, each of the subgroup classes defines some behaviors on what to do next. Its behavior is also determined by the canCollide() method, which checks if the type of particle in the next position can be pushed out of the way by the type of this particle. If so, the adjacent particle is moved out of the way using pushParticle() (defined in the Particle class, for use by all Particles). Below are the default behaviors implemented in collide() by the subgroup classes.

    • SolidParticles: The implementation of collide() produces results mainly depending on whether a SolidParticle collides with another solid-like particle (i.e. solid or static) or not. If the cell beneath the SolidParticle’s current position is a liquid or a gas, then the SolidParticle will take the place of the particle below, and push that particle to the side containing free space (or randomly picking a side if both sides are free). However, if the below particle is a solid or static particle, then the current SolidParticle will instead be moved to whichever of the bottom-left or bottom-right cell is free. If they are both free, then one of them is picked randomly. Otherwise, the SolidParticle stays in place.

    • StaticParticles: The StaticParticle class does not have its collide() method defined. This is due to the fact that StaticParticles are immovable, and remain in the same place in the grid where they are initially created.

    • LiquidParticles: The collide() method of the LiquidParticle class behaves similarly to the collide() method of the SolidParticle class. The only differences are that LiquidParticles can only push aside GasParticles, and LiquidParticles do not stay in place if the cell to the bottom, bottom-left, and bottom-right are occupied. If all three of those cells are occupied by a non-gas particle, LiquidParticles also check if the cells to the immediate left and right are free or occupied by a GasParticle. If so, the cell moves to the cell to the left or right, or chooses randomly between both of these cells. This creates the effect of “leveling out” that liquids should do naturally. Only if the immediate left and right cells are also occupied will LiquidParticles stay in place.

    • GasParticles: The collide() method in the GasParticle class simply checks if the cell that the GasParticle is attempting to occupy is within the frame, and not currently occupied by another particle of any type. If both of these checks apply, then the GasParticle is free to move to the next cell. Otherwise, the GasParticle stays in place.

    The below gif shows the behaviors of the different particle types, as exhibited by the Sand, Water, Wall, and Methane particles.


    Colliding behavior of the particle types


  3. The interact() method of Particle is called. The interact() method returns an ArrayList of Particles, and this ArrayList is subsequently returned by simulate(). The purpose of the interact() method is to implement any special behaviors other than movement. For instance, the interact() method usually calls getNeighbors() that gets a map of Particles immediately adjacent to it and their coordinates. Depending on the nearby Particles, this Particle might alter its own parameters or its neighbor Particles’ parameters.

One main usage of the interact() method is to implement the flammability of WoodParticle, OilParticle, and MethaneParticle. Every specific particle is given a flammability constant (double) flammable in the range of [0, 1] (most particles have a constant of 0 except for wood, oil and methane). If a fire or lava particle comes into contact with another particle, the fire or lava particle will attempt to set the other particle on fire. If the other particle has a flammability constant flammable that is greater than 0, then the particle has a probability of flammable of being set on fire.

Once a particle is set on fire, it is given a random (int) lifetime (within the bounds of the particle’s defined (int) minBurnTime and (int) maxBurnTime) which is the amount of time that a particle will burn before it is completely burned out and removed from the frame. Additionally, while a particle is on fire, it has a chance of (double) fireCreateChance of creating new fire particles nearby to set other flammable particles on fire. There are also some special cases with particles burning as well. For example, when a particle burns out, if the particle was a MethaneParticle, then the particle will create an effect similar to an explosion that spawns additional new fire particles. Finally, when water comes into contact with fire or particles on fire, then the fire is extinguished (or given a short lifetime) due to the water.

The below gif shows the burning and extinguishing behaviors of the flammable particles Methane, Oil, and Wood, along with their extinguishing.


Burning behavior of flammable particles

One bug encountered when implementing fire was caused by making methane flammable, specifically methane not dissappearing and burning forever. Methane particles, when they do not move for a simulation step, decrements its lifetime. However, since fire also decrements lifetime, there was a chance to make the methane particles have a negative lifetime. A lifetime of -1 is the defualt value for lifetime and signals a particle has permanent lifetime. This bug was fixed by performing more checks when decrementing lifetime.

Another main use of the interact() method is to execute special interactions between specific particle types. A good example of this is the interaction between water and lava. When water interacts with lava (and vice versa) we have implemented the behavior of the water cooling the lava into a solid particle, and the lava in turn evaporating the water. Therefore, any time that water comes into contact with lava, both the lava and water particles are removed from the frame (given a lifetime of 0) and a new StoneParticle is instantiated to take their place.


Water falling into lava and forming stone particles

In this specific implementation of the interaction between lava and water, a bug was encountered. After removing particles from the frame, the simulation was still led to believe that the cells that contained those removed particles originally were still occupied. This caused stone particles to not be instantiated and created gaps in the simulation. This bug was due to the structure of our code. We had an (ArrayList) ParticleList that held all our currently spawned particles, and the ParticleGrid displayed the particles in the list on the frame. However, particle classes initially could only access the ParticleGrid, and not the ParticleList, and only removing particles from the ParticleGrid was not enough since the particles removed were still in the ParticleList, forcing the ParticleGrid to believe that the removed particles still existed. After some restructuring, especially with the implementation of fire effects and the setting of the lifetime of particles, we were able to remove the water and lava particles from, and add the stone particle to, both the ParticleGrid and the ParticleList, thereby resolving the bug.

The Particle class was the center of attention during our work. Although there are some places that can still be organized for even more extensibility, complexity and readability are still also concerns in a group project such as this one. In the end, everyone contributed to various separate aspects of the Particle classes, and we learned a lot about design patterns and how to run a codebase, from spotting abstractions in existing code to planning future code.


Graphics and Interface

The key technique to efficiently rendering 10,000+ moving particles at a stable 50 fps is to do all of the hard work in the GPU. We decided to use the Java OpenGL library (JOGL) to leverage the hardware acceleration benefits that OpenGl provides to speed up our rendering as it is very computationally expensive. All of our particle rendering takes place in our SandDisplayPanel class which extends a Java Swing JFrame. We embed a GLCanvas inside of this JFRame and set its size to expand to the same size as the parent. Inside of our main display() method, we iterate over each Particle in our particleList, and use a helper function to leverage OpenGL shaders to render each particle in its respective row and column value. We were not able to implement it in time, but this process is easily parallelizable as rendering each particle is independent from each other.

An initial bug we ran into was the simulation rendering differently on Windows and Mac operating systems. On Windows, each particle was significantly smaller and not aligned with the GLCanvas frame. After extensive debugging and online research, we discovered that Mac and Windows displays differed in their Dots per Inch (DPI) value. To solve this, we correctly accounted for this and properly scaled our GLCanvas to render the same on any machine, independent of DPI value.


(Bug) Early image of JOGL high-DPI bug

Color choice was also another key aspect of creating an aesthetically pleasing and realistic simulation. For each Particle type we defined a static list of Color’s, and for each Particle instance, we deterministically select a specific index in the Color List to render for that specific particle. The resulting image gives an appearance of texture that a solid color for all particles could not depict. Below is a visual comparison of sand and water as seen in our milestone and after color variation.

Early gif of sand and water with solid color
Later sand and and water color with color variation

Another key aspect of our application is the Image Import feature. This feature allows a user to select a picture as a starting state for the simulation, where we map each pixel to a corresponding particle type based on its color. We map each pixel to a particle type by using a least squares approximation to find the particle with the least difference in RGB color. This feature provides a fun experience by highlighting the unique particle interactions from an assortment of different particles at the same time.


Mona Lisa imported as particles


Comparisons to Other Sand Games

A lot of our inspiration for particle interactions and overall simulation mechanics came from other popular, browser-based sand simulators. https://sandspiel.club and https://dan-ball.jp/en/javagame/dust/ specifically, also implement the same interactions between lava and water creating stone, and most of our other particles.

Other than having a wider variety of particles, both of these sand games also handle fluid and smoke simulation when gasses and explosions are caused by certain particles, such as smoke billowing off of fire. This happens alongside the particle simulation and in both of these simulations can actually cause particles to blow around. This is actually one of our reach goals that is a good direction to improve our own simulation should we wish to continue working on it.

Furthermore, Sandspiel in particular runs at a very smooth, constant framerate, even when the screen is filled with particles. Sandspiel uses web assembly and WebGL that runs very quickly, and inspired us to implement OpenGL in our simulation from the beginning of the project. Our simulation still slows down when importing images or otherwise simulating an almost-full amount of particles.

Both of these apps lack the ability to import an image as a starting state, which we implemented. Sandspiel has a share feature, which we considered implementing by allowing the simulation to export the particles onscreen as an image, which could be later imported. This is also another interesting feature that can be implemented in the future.


Results

Our results are summarized in our final demo video below.

Our code repository is viewable on GitHub.

In terms of benchmarking our performance, we usually achieve a framerate of around 50 frames per second. While importing images as particles, filling the screen with particles, setting fire to a large amount of particles, and lava meeting water to produce stone, the simulation can bog down. In these circumstances, the frame rate can dip to around 20 frames per second.

Below are some more results captured throughout our development.


"Density experiment" showing sand sinking beneath water and oil floating on top of water


Lava particles have a chance to emit fire particles as "embers", setting other things on fire


Early test of mixing water and sand


References


Team Member Contributions

Dennis:

Rami:

Garrett: