Making Sandspiel

Sandspiel is a falling sand game I built in late 2018. I really enjoyed writing this game, and wanted to put into writing some of my goals, design decisions, and learnings from that process. If you’re reading this and but you haven’t played sandspiel, you should probably go try it!

I love falling sand games.

If Sandspiel is the first “falling sand game” you’ve played, it’s important to understand that it fits into a genre of games, which are developed independently and usually distributed as free webgames in the form of flash or java applets. In each game, you’re given a pallette of virtual solids, liquids, and gasses, and it’s up to you to paint them onto the screen to discover how they interact.

I think that I love these games so much because their mode of play is creative in a way that activates many parts of your imagination. Playing with the elements means asking questions, building experiments, and inventing stories and games of your own.

“What does fungus do?”

“Let’s make a cool volcanic island!”

“Does anything destroy lava?”

“What happens if I do this?”

In sand games, just like in other cellular automata (such as the Game of Life), the behavior of any single element is very simple. The interactions between the elements and across the space is where the interesting complexity of the simulation unfolds. The result is a system with surprising depth and variety to explore.

It’s also important that this system is engaging not just for its actual depth, but also because of the ways your imagination sees reality reflected in it. Predicting how a scenario will play out based on your physical intuition is a form of play, as is projecting your imagination over what you see represented on screen. Much like playing with dolls or other simplistic model, the pixels flowing around on the screen are stand ins for the story you tell yourself about them.

“Low-fidelity art is also appealingly open to interpretation. If a character is only eight pixels tall, a large part of what we see is within our own imagination.” – Loren Schmidt

Microcommunity

Every loves to opine on their forgotten, weird corners of the internet, and mine is the upload gallery of dan-ball.jp’s Powder Game around 2007-2013. There was a beautiful micro-culture of people making games, toys, demos, propaganda, and art.

Powder Game’s upload galleries were a special place — the accessible venue to build something and share it led to people inspiring each other, riffing, and pushing the game in incredible directions! Sand games captured my free time and imagination throughout my childhood in large part because of this weird community.

It’s also important that this system was built right into the game — every player had a immediate audience for their creation, in contrast to a culture built around a few famous youtubers or streamers, or even that peculiar sort of self-selecting community you find on enthusiast forums. There was a wide variety in complexity and motivations among posters. All this with no comment section!

Three archetypes of upload I remember fondly:

Games for the player, often with empty promises of some reward for voting.

Grotesque “Don’t Smoke” educational demonstrations. (I think these were directly fueled by children coming home after D.A.R.E. programs at school)

Cool volcanos. (a true classic)

Beautiful pixel-art architecture to destroy.

The added dimension of an audience brings so much depth to playing around with sand. I wanted to facilitate this in sandspiel with the upload system.

Building Sandspiel

The first thing you should know is that Sandspiel is actually my third or fourth attempt at building an interactive falling sand simulation.

“HTML5”

The first proper attempt was pure javascript in 2015. (You can try it out here!)

It’s… a falling sand game! You can set things on fire, draw fountains, and there’s even a fluid simulation that allows particles to float around in the wind. I think my favorite things about this game was making pixel art with the rainbow “Dust” element, and the way that “Dirt” absorbs and diffuses water to become mud.

On the negative side, resolution is only 100×100 (Sandspiel has 9x more pixels), doesn’t work on a phone, the interface is confusing and keyboard based, and the element logic is pretty janky.

It’s also rendered with canvas APIs, and the code is not organized in any intentional way. Plenty of dynamic typing, gnarly switch statements, and global variables. All of this made implementing and debugging each successive element’s logic increasingly difficult— to the point that it resulted in bugs that I domesticated and kept in the game, such as the element “Glitch” which behaves differently depending on what element you have selected.

I was really proud of this game and had a great time building it, but it followed the familiar arc of a system collapsing under its own weight as progress became more difficult and motivation waned. The last commit message was kind of classic, and I never did follow up on that “impending refactor”.

LÖVEly

The second approach was with Lua in 2018, and my work here turned out to be the direct prototype for Sandspiel.

A few things are briefly worth saying on this experience:
First I need to gush that lua is super fast thanks to LuaJIT, and the LÖVE framework is lovely tool for building games.
Shaders, input handling, update and render loops — everything clicked together thanks to LÖVE and made life easy – I could get things running quickly with minimal yak shaving and boilerplate.

Coming from the browser, a tool into which I have personally sunk many hundreds of hours learning APIs, edge cases, and performance characteristics, it was a big surprise to see how effective a minimal programming environment for building games could be. So much complexity that we put up with is due to legacy and sunk costs!

Coming into this second attempt to build a sand game, I had 3 years of experience beyond what I had when building the pure javascript version. I also had an important new goal – not only did I want the game to be fun to play, but I also wanted elements to be fun to write.

I approached the project with a focus on the ergonomics of defining elements with code because I was imagining a new type of sand game with a fully sandboxed programming interface that would allow people to not only paint and share their compositions, but also to code their own new elements and share those too!

My hope was that a community of people collaborating to build a plethora of weird elements would find really interesting interactions that hadn’t been covered in other sand games.

However, this was a big goal, and the first step of the process was still building out a game engine and initial set of elements on my own. While building these, I was thinking carefully about the needs of the future element authors. Viewing the game engine as a public API meant designing it to move as much complexity as possible inside the engine and away from being the responsibility of the individual elements.

function updateGas(particle, getNeighbor, setNeighbor)
    local d = {x = math.random(-1, 1), y = math.random(-1, 1)} 
    if (getNeighbor(d) == species.empty) then 
        setNeighbor({x = 0, y = 0}, species.empty) 
        setNeighbor(d, particle) 
    end
end

This meant defining a format that elements were expressed in — I settled on a single update method which defines the behavior of a single particle for a single update tick. The code inside the method can interact with the system only via special methods which provide safe reading and writing to their neighbors.

This API abstracts away concerns such as:

• The particle needing to know its absolute position (setNeighbor and getNeighbor deal in relative offsets),

• Interactions with the edges of the grid (all of the edge condition logic is in the engine),

• Enforcing a small local read/write neighborhood for the particles (no “action at a distance”).

That work relieved the individual elements from needing to take on these concerns into their own logic, and made the system more consistent and easier to experiment with as I implemented my cast of elements.

Focusing on making the definition of a new element simple and self-contained really paid off, even though I ultimately ended up being the only person consuming these APIs. The system being more fun to iterate on was rewarding enough to justify the extra care put into the architecture early on.

I was excited about this approach and it was working well, but wanted to build the game in a way that I could reach users. Despite everything good I had to say about LÖVE, the web is too powerful of a platform to pass up, and it’s worth the quirks and warts.

I decided to put down the lua implementation and switch to Rust, but I was able to directly translate many lessons and patterns over. Having a good idea of what my data-structures would be and what types of APIs would be defined between components made writing the Rust version much smoother.

Implementing one idea multiple times was a huge strength in my ability to structure my codebase, forsee pitfalls, and make more thoughtful and intentional tradeoffs. I would strongly recommend this experience to anyone – If you have a project that you’ve attempted in the past but either didn’t finish or made compromises on due to your technical skills or endurance, taking another crack at it can a great opportunity to sweat the details and see new approaches.

Architecture:

Sandspiel.club can be described as four main components

• the particle simulation code, written in Rust
• a fluid simulation, written in JS & GLSL
• user interface written in React & JS
• a CRUD backend written with TypeScript and Firebase Postgres

The main simulation, controlling the movement and interactions of all of the elements, takes place in Rust in a class called Universe. This is the class holds the game state and exports a set of methods to be called by the Javascript application, which do things like process a frame of the simulation, paint some pixels, or return a pointer to the particle state buffer.

This means that I don’t try to handle an event loop, do rendering, or interact with the browser from inside the Rust code – all of that would be perfectly possible, but I’m very happy with this division of labor between the JS and Rust. Everything low level or CPU intensive happens within the Rust-generated Web Assembly code, while all of the the glue related to human interface, WebGL calls, and browser APIs takes place in the Javascript.

Data format

The first most notable aspect of Sandspiel’s architecture is the compact data format I used for the game state. By setting some constraints on the system, I was able to benefit from a uniform format that performed and serialized well. This came in handy several times!

The state for a single particle is represented as a 32 bit struct.

#[repr(C)]
pub struct Cell {
    species: Species,
    ra: u8,
    rb: u8,
    clock: u8,
}

The first field, species, is a custom enum type which represents the varieties of particles as numbers:

#[wasm_bindgen]
#[repr(u8)]
pub enum Species {
    Empty = 0,
    Wall = 1,
    Sand = 2,
    Water = 3,
    ...
    Seed = 19,
}

ra and rb are two 8 bit “registers” for storing extra some cell state beyond species, such as what color a given flower petal is, or how hot an ember of fire is. They’re used in different ways by different element species, and some species don’t use them at all (for instance, a Wall particle has no extra state to track). The two state registers only differ in that ra is initialized to a random value, and rb is initialized to 0. ra is also used in rendering to determine how light the pixel should be, which is where the slight visual grain effect comes from.

clock is just used to prevent a single particle from being simulated multiple times in a single tick if it moves in the same direction as the update scans. Because we execute cell update functions one at a time from left to right and top to bottom, if a particle something is moving down, it will keep bumping itself ahead of the “scan line” and could move many spaces in a single frame. Clock is meant to keep track of what elements have been simulated already – this could have been accomplished single bit that is flipped back and forth but it’s important that my Cell type is represented by a total of exactly 32 bits, and I didn’t have any use for the other 7 bits!

Nowhere in this cell state struct is a concept of location. This is because, as opposed to a particle simulation where we maintain a list of entities and their positions, here we store all particles in a dense 2D array, and directly encode the position of a cell as its location in that grid.

Update Function

The most important pieces of code in the game are the set of functions, one for each type of element, that define how particles of that type interact with their neighbors each frame. Theoretically, you could delete these functions (which live in species.rs ) and write a new set that transform the game into a cellular automata simulator for some other system, such an ant farm, a petri dish, a city-scape, a paint canvas, an aquarium, or an abstract fractal playground.

Here’s an example of how one of our elements is defined:

pub fn update_sand(cell: Cell, mut api: SandApi) {
    let dx = rand_dir(); 
    let neighbor = api.get(0, 1); 

    if neighbor.species == Species::Empty { 
      api.set(0, 0, EMPTY_CELL); 
      api.set(0, 1, cell); 
    } else if api.get(dx, 1).species == Species::Empty { 
      api.set(0, 0, EMPTY_CELL); 
      api.set(dx, 1, cell);  
    }
}

SandApi is a struct provided to the function which holds the location of the particle without directly exposing their values. It exposes some important functions, like get and set, which accept relative coordinates and let you read and write to your neighboring cells. For instance, api.get(0, 1).species tells you the species of the particle below you, and calling

api.set(0, 0,
   Cell {
      species: Species::Fire,
      ra: 150,
    }
  );

will write a Fire particle to your current location (erasing yourself in the process).

Designing and tuning these update functions was a lot of fun, and I was able to test out a lot of ideas and play with different interactions. I didn’t make use of syntax macros or anything as fancy as that, but the experience was a lot like that of building a system by first building a “Domain Specific Language” which encodes the shared behaviors and invariants of the system, and then scripting its inhabitants in that simplified DSL.

Another thing to note here is that these update functions, which hold so much of the gameplay logic, are run thousands of time per frame! This means that they’re simultaneously critical to the feel of the game, and are some of the hottest lines of code in the project. Rust’s commitment to enabling expressive, high level code without invisible performance cliffs really allowed me to write the logic how I wanted to write it, without accidentally causing a bunch of slow heap allocation or writing code that a JIT will capriciously decide not to optimize. It’s probably possible that there are people out there who could carefully craft some high-performance javascript that would be competitive with my Rust code, but I was able to mostly “just code” and not worry too much about performance.

Zero cost abstractions!

Last interesting anecdote here is that I unwittingly wrote most of the game with my rustc optimization strategy on “z”, which means the compiler will optimize for binary size. Once the project was almost finished, I realized this and switched it to “o3” which does things like inlining and gave me a big performance boost, where I had been being frugal! That was a nice surprise, it performed better and the WASM output only increased in size from 66Kb to 84Kb.
A big mistake I made was to immediately take this extra performance budget and “spend it” to increase my canvas size from 250×250 to 300×300, because now I could still get 60 fps on the 300×300 canvas.
This was a blunder because there are a ton of devices which can’t run sandspiel at 60fps, and I should have held onto this spare performance headroom so that more devices could run the simulation at full speed.

Rendering

I mentioned that the simulation takes place in Web Assembly, and that the Javascript manages the WebGL rendering (it’s totally possible to call WebGL APIs directly from web assembly, but I didn’t want to compound my WebGL inexperience with my Rust inexperience).

Rendering is basically as easy as reading each cell of our gamestate grid, and painting a corresponding pixel with a color according to its species and ra values.

We just need to make sure that our fragment shader (the code which runs on the GPU and decides what color the pixels should be) has access to the game state, which is stored in the Web Assembly heap.

In order to move the game state from Web Assembly to WebGL, we construct a Javascript typed array view over the game state array which lives in Web Assembly memory, and pass that view to our fragment shader (GPU code) as a texture.

const cellsData = new Uint8Array(
  memory.buffer,
  universe.cells(), <- 
  width * height * 4
);

gl.bindTexture(gl.TEXTURE_2D, cellTexture);
gl.texImage2D(
  gl.TEXTURE_2D, 0, gl.RGBA,
  width, height, 0, gl.RGBA, gl.UNSIGNED_BYTE,
  cellsData
);

Because our game state data is arranged in such a way that it happens to be a valid image texture, we can ship the whole grid over to the GPU with minimal copying and allocation! This was a big deal for making Sandspiel’s rendering performant- the rendering code blocks the CPU for less than 1 millisecond, critical for meeting the strict 16ms budget needed to achieve 60FPS.

This is also one of the reasons it was so important that our Cell state was stored as an array of 4 byte chunks. WebGL has a lot of restrictions on the formats of data that can be used in textures, but RGBA textures where each pixel is 4 unsigned bytes are well supported.

Fluid Dynamics

Sandspiel’s fluid simulation usually really stands out to people who play with it, which makes me feel a little bit guilty, because it’s largely ripped from Pavel Dobryakov’s WebGL Navier-Stokes implementation. I’m extremely grateful to have had such a quality implementation to learn from— adapting and extending this code was the most personally challenging technical hurdle I faced building the game.

Adapting the code was difficult because, in order to have interactions between the wind (simulated on the GPU) and the particles (simulated on the CPU), I needed to pass data from Web Assembly to WebGL (in the same fashion as I mentioned for the rendering), and from WebGL back into to Web Assembly (this bit was trickier, as WebGL can by picky about which buffers are readable, and when you can read from them).

I also needed to do this in a way that used only the subset of WebGL features supported on most phones – WebGl is a pretty large spec, and for hardware and driver reasons, not all of it is available on all devices.

This process was made worse by the fact that my only phone on which to test code runs iOS, and Apple only allows you to connect to the mobile safari developer tools from a Mac (which I don’t have). So I was debugging many of these WebGL device-specific limitations without so much as a console. Frustrating!

User Interface

Sandspiel’s interface is actually much simpler than most falling sand games. I made an intentional effort to keep the UI light and fun on a touch screen, by avoiding interactions that require multiple taps to complete. Some examples of this are that none of the tools require cycling through different settings or drop-down menus, and I dropped the system of two-stage selection that other games use to implement elements like clone and firework.

I also put care into the line drawing itself – there’s some fiddly edge cases related to handling taps, drags, scrolling, and other interaction events on the canvas. This is the sort of tuning that should be invisible if it’s working, but I ran into a lot of interaction scenarios while testing the game, and tried to sand down the rough edges.

As part of this work, I disabled pinch-to-zoom – it would be an interesting challenge to try to fit that back into the space of supported interactions.

Facilitating and disambiguating multiple gestures in a single arena is a complex and fascinating corner of algorithms and human computer interaction, and I have new respect for the often invisible work that goes into building rich touch screen experiences.

UI Code

I threw the interface together mostly in React. If you have one takeaway about Web Assembly from this project, I want it to be that WASM is not an all or nothing undertaking! Having the ability to put low-level and performance-critical logic into Rust and still handle all the browser API stuff, glue code, and UI in Javascript was critical to this project coming together quickly and having a nice interface.

Leveraging the npm ecosystem for tools like React, Regl, and GLSLify, as well as exercising Javascript’s flexibility to toss data anywhere I needed it without much planning or refactoring enabled me patch things together quickly and loosely.

Nothing I wrote in JS would have been impossible to accomplish in Rust, but it wouldn’t have come together as easily and I wouldn’t have been able to test as many ideas along the way.

Sharing & Persistence

To fully capture the creative micro-community of other falling sand games, I wanted there to be functionality for uploading creations, and browsing others’ works. I decided to try using Firebase to handle my backend needs, and I think that worked out pretty well!
One design decision that turned out to be important was that I wanted to avoid dealing with accounts and authorization. I find that stuff annoying for the user and boring to implement so I went to some lengths to do without it.

The way that I handled data security without auth was putting all data writing inside of api endpoints, and using these to constrain what the client could do. (basically, GET, INSERT and voting only, no editing or deleting of other posts). My workaround for voting deduplication was to use IP addresses, which is possible to manipulate, but I don’t really care enough to try to fight it.

I run these API endpoints as a cloud function, cloud functions seem cheap and great.

A cool thing here about the storage functionality is that I serialize the game state as a PNG file, which is lossless and highly compressible. Plus, browsers have efficient PNG encoders and decoders built in, so that’s more code I don’t need to import and ship with my bundle.
Here’s what the data looks like as a PNG: (remember, in each RGB pixel, “red” is species, “green” is ra, and blue is rb)

The basic architecture of my backend is something like this:

There were times while debugging when I was really just wished I was writing a http server backed by a redis instance and a directory full of files, with nothing hidden behind proprietary services and configuration languages. But I don’t want to be on the hook for availability, persistance, and server management – especially when the other things running on my VPS are already fragile, stateful, and ad hoc. Firebase was harder to debug and run adhoc scripts against, but I don’t have to think about it now that the service is deployed, and it’s reliable and cheap enough.

Running the game for a few months started to become expensive as traffic ramped up, 99% dominated by Firestore reads. (I think the architecture I had of listing out large sections of documents without caching or pagination wasn’t well suited to Firestore.)

I didn’t want to continue paying $50 a month for Firestore, and I also wanted to implement more interesting query capabilities, including full-text search.

This led me to migrate my ~60k records off of Firestore and into a Postgres instance, which I’m really glad to have done. Operating Postgres has been about 10% of the price, significantly lower latency, and allows me to run complex queries to power new features like the search box.

Community

A couple thousand people play with sandspiel every day now! The upload boards get spammed with all sorts of beauty and nonsense, and it warms my heart to see people playing, interacting and (mostly) having fun. The playerbase skews pretty young, and uploads are filled with memes, kids promoting their youtube accounts, etc etc. For the most part, it gets used as a paint program, and the actual simulation aspects are an afterthought!

If you load one creation, this irreverent homage to the Notre Dame cathedral might be my favorite:
(Make sure to press ▷ once it’s loaded)

People have uploaded more than 70,000 creations, ranging from sophisticated rube goldberg reactions, coloring book “complete the drawing” prompts, impressionist paintings, crude kinetic graffiti, and everything in between.

One upload that surprised me was when someone manipulated the data buffer directly, to upload out-of-range species data. This resulted in a pink element with no intentionally defined behavior, like the ”MissingNo.” of sandspiel. It totally made my day when I realized what had happened, as this was not something I thought was possible! I like to call it “belp”.

There’s a healthy remix culture of people making new takes on popular templates. Two favorites are doonaloona, the lithuanian puppy queen of sandspiel




and these images of reggie that someone was able to somehow hack into the game in different elements.

Thank you so much for reading this long post!

The Rust Wasm Book is a great succinct resource that covers all aspects of writing a hybrid JS & Rust application. I had basic rust knowledge before starting Sandspiel, but no knowledge of web assembly, and was able to follow this book to bootstrap the game. A lot of code from the book actually ended up in my game, since their example was cellular automata related.

The Book of Shaders I didn’t specifically reference TBoS during this project, but I take any opportunity I can get to recommend it to anyone interested in learning graphics programming. I wish this book was a part of high school math curriculums.

WebGL Fundamentals & WebGL2 Fundamentals Really solid & complete explanations of WebGL basics, put into context of common tasks and patterns. Finding those two things together is rare!

Fast Fluid Dynamics Simulation on the GPU is a chapter from the book GPU Gems, which details the math and mechanics that go into a beautiful and buttery Navier Stokes fluid simulation. It’s really interesting how physical concepts like pressure, advection, and diffusion, all expressed as math operations on grids of floats, can be composed into a convincing simulation.

Also, thanks to Chris Crawford, Nikhilesh Sigatapu, Thais Correia, Pavel Dobryakov, the Rust WebAssembly working group, and ha55ii for inspiration, knowledge, code, and feedback!

sandspiel source code

@sandspiel_feed twitter feed of uploads