CS184 Project: Pixel Physics Simulation

Abstract

We decided to create a cellular automata-based physics simulation engine that only uses pixels as representations of different elements. We aimed to create a live and interactive system where each element will function under its own set of rules, allowing us to birth a complex ecosystem though combinations of said elements. In our final implementation, we have a plethora of elements to choose from such as wood, water, sand, fire and even bees! You can press TAB access a makeshift UI system to view all the possible elements. Once you made your choice, use LEFT CLICK to spawn that element into the scene. Simulation will occur automatically so you can sit back and watch your creation moves in its world. You can use RIGHT CLICK to remove existing elements from the scene. If you want to start over, the R key will clear all pixels from the scene. As different elements collide with each other, we can see realistic results occur. For example, if spawn a fire element next to a long strip of wood, you can see the fire slowly consume the piece of wood, removing it from the scene and converting it into smoke and ash. Pouring water into a bowl shaped solid object will contain the water as it swishes back and forth. In summary, we’ve implemented a version of cellular automata with the goal to mimic reality.

Technical Approach

Engine

We coded the engine in C++ using OpenGL to handle the rendering. C++ is naturally a faster language and allows us to avoid dealing with memory safety. We set up the entire engine from scratch using GLFW for window and input handling, GLAD for OpenGL initialization, GLM for math utilities, and custom-built CMake scripts. OpenGL allowed us to utilize our GPUs to render our simulation though much of the simulation happens on the CPU—though we aimed to parallelize this through multithreading or compute shaders, we ran out of time.

Everything in the game is simulated using a 2D grid of cells and rendered onto a quad which is passed to OpenGL for rendering using a nearest neighbor shader. The game is divided into two main sections, the World and the UI, both of which have their own grid to work with. The world grid is running the main simulation of the game, while the UI grid pauses all simulations to perform custom handling of input and cell behavior. This UI also features text rendering directly within the grid, which is done using a C-based bitmap font that is turned into cells.

Algorithms

The biggest decision of this project was deciding on how to actually simulate the set of pixels. Referencing a talk given at GDC by game developer, Petri Purho, we decided to cellular automata approach which uses a neighbor-based physics algorithm instead of the typical versions used in popular game engines. At a high level, our implementation uses the immediate 8 neighbors of each cell to decide on how the cell should act. We iterate through our entire grid of cells and sample each one. Many sandbox simulators and games like Noita, use this as their preferred method of simulation since it is easy to understand and requires very little overhead. You could even take things a step further by sectioning the grid into “chunks” and use multi-threading to handle each one.

The only data structure we use to represent our cells is a Cell class. Each cell’s properties can be broken into 2 parts:

A single cell behavior enumerator, which dictates how the cell will act,

A series of physical traits (mass, combustibility, lifetime, etc.), which dictates to what degree will the cell act

In layman terms, an element defined by a preset combination of a Cell Behavior and specific physical traits. In our code, this is called a cell.

Here is a snippet of our Cell.h class code:

enum CellBehavior
{
    NONE = 0,
    LIQUID,
    MOVABLE_SOLID,
    IMMOVABLE_SOLID,
    PLASMA,
    GAS,
    BEE

		...
};

class Cell
{
public:
    ...

    /** Name of the cell type. */
    std::string name;
    /** Color of the cell. */
    glm::u8vec3 color;
    /** Type of behavior to expect from this cell. */

    CellBehavior behavior;

    /** Mass of the cell for physics behavior. */
    double mass;

    /** Life time of the cell. Useful for things that should perish i.e. fire. */
    double lifetime;

    /** Some cells just want to see the world burn */
    bool is_combustible;

    /** Chance of the cell proliferating into the air. */
    double spread_chance;
		
		...
};

Here’s a small description about each of our implemented Cell Behaviors:

NONE
- Used to represent an empty cell.

IMMOVABLE_SOLID
- The element is stationary, and does not interact with its surroundings.

MOVABLE_SOLID
- The element mimics gravity by always attempting to fall straight downwards.

LIQUID
- Similar to the MOVABLE_SOLID, except that it also fall diagonally to left or right if available. When on a flat surface of cells, the element will flow left and right, mimicking the look of waves.
  - Directional falling is chosen randomly if possible to make it seem more natural

PLASMA
- Simulates fire-like behavior. Attempts to spread itself to neighboring cells based on its spread chance property.

GAS
- Simulates gaseous matter. Similar line of logic as liquids but considers neighbors above and diagonally above it. Often uses the cell’s lifetime property to remove itself from the scene after a set number of time cycles.

BEE
- The only behavior that functions as a living entity. Imitates a wandering bee that flies around randomly.

Here’s a deeper look into a few of our favorite elements and how they are implemented.

Stone: The most basic element. Not affected by gravity nor can be set on fire. It kinda just sits there. Has no simulation logic, since it’s never expected to move in the scene.

Grass: A solid like Stone, but affected by gravity and quite combustible.

Water: A basic liquid that finds the lowest possible cell it can and will swish around endlessly.

Fire: A “plasma” element that will ignite neighboring combustible cells into new file elements. A single smoke element will also be created.

Smoke: Holds the same logic as water but in reverse. Attempts to go to the highest possible cell it can. Smoke is also limited by a lifetime trait which cause it to dissipate after a set number of time steps.

The last part to touch on is the implementation of our UI. We use another similar but separate 2D grid to act as a UI display. Since we can already handle mouse inputs and map them to coordinates in a grid, we implemented an auxiliary grid (that doesn’t interact with our main physics grid) to hold all the different type of elements we want our users to access to. Then, once we are in UI mode, we can interpret a mouse click as a selection for an element to draw. This design choice allowed us to save time from making a whole separate UI system by reusing features we’ve already developed.

Problems & Lessons

Ed: One of the initial problems we needed to uncover before we even started coding was designing the infrastructure of our simulator. As state previously, we were deciding between a typical real-world physics engine vs a cellular automata style implementation. The real world physics approach would involve too much overhead such implementing a constant check for gravity, fluid motion, air pressure and more. This would only continue to grow as we would add new elements. The cellular automata angle allowed us to view each element in its own box and take a more modular approach. New features could simply be tacked onto our existing cell class and handled case by case in our simulate function. This approach was also much more intuitive for us, since we had real-life examples of it being used in games.

Miguel: Having little experience in OpenGL, getting the engine up and running was quite challenging. After following a bunch of different sources like LearnOpenGL, I was able to get textures to render onto a quad on the screen. It was especially challenging getting the quad to render at an appropriate size without stretching the cells. I initially implemented a system to resize the quad to always maintain its ratio within the window; however, this ended up making the event handling too complicated because it required converting a mouse position to a grid coordinate position with a dynamically sized grid. So I ended up disabling the resizing windows. All that was left to do was turn the grid of cells into textures in every frame.

Johannes: An issue that I found towards the tail end of development was figuring out interactions between specific cells and how to produce results that should be exclusive to two types of Cells i.e. if lava touches a bee, the bee should burn. This was particularly tricky because we didn’t use inheritance to represent different Cell types. Instead, we have a singular Cell type which is characterized by a set of parameters and behavior-type. The former would describe a Cell’s color, velocity, mass, etc while the latter would denote its state of matter. The reason it was difficult to figure out specific interactions was because I did not properly think the Cell class’ parameters through, and ended up bloating the Cell class with extraneous variables to distinguish a Cell type from another. Although it’s not a large issue for this project, had this project needed to scale further, we would run into a lot more code-bloat. In hindsight, I would spend much more time fleshing out the Cell class before diving into the code.

Manh: Water movement has the most issues. One of them was the random direction movement, since C++ rand() is biased, thus std::mt_19937 comes in with a more uniformed integer distribution. Another problem was the grid is updated from left column to right column, then bottom row to top row. However, everything is supposed to happen simultaneously at the same time within one time step. When one cell is moved to another location, the loop might encounter this cell again, and then update it, resulting in jumping pixel effect. One way to solve it was only keep track of one movement at one interaction happen at one time step at a time. Since the grid is updated every discrete delta time, implementing real physical properties such as velocity and force was not as simple. Instead, velocity can be implemented by random delay.