How To Make a “Falling Sand” Style Water Simulation

Have you ever wondered how all those “falling sand” games work under the hood? If so, read on. Today I will discuss one of the possible ways how you could implement the “falling” part of the game – sand particles falling under the effects of gravity, water (or other liquids) flowing down a hillside, and so on. Source code and a live demo are also available. This tutorial is along the same vein as my previous fluid simulation post that dealt with pseudo-compressible fluids and pressure, but the specific algorithm is much simpler (and probably quite a bit faster, too).

Side-note : No, I haven’t been completely consumed by an inexorable desire to build fun graphical toys instead of practically useful software, why do you ask? :) In fact, there’ll be some WordPress-related announcements later this week…

Learning To Fly Fall

Falling water movementWhile I can’t claim intimate familiarity with the algorithms the aforementioned games use to simulate fire or explosions, it’s pretty easy to come up with a way to implement falling sand/flowing water. First, you need to figure out under what conditions something can fall/flow downwards. For a basic simulation this could be just a small set of very simple rules :

  • For each entity that is affected by gravity
    • If there’s an empty space below it, move it down.
    • If there’s an empty space down and to the left, move it down and to the left.
    • If there’s an empty space down and to the right, move it down and to the right.

Next, you need to decide how to represent the simulation world and all the objects (like immovable walls, moving water particles et cetera) that it contains. One of the most common solutions is to use a two-dimensional array where each array element is an numeric ID of the material contained in that map tile. For example, 0 = air (or an empty square), 1 = wall, 2 = water, and so on.

Map array

In most falling sand games each array element would correspond to a single pixel on the game’s screen. However, in my example application I used 20×20 pixel tiles instead to make the underlying simulation behaviour easier to see.

If possible, use byte or char as the array element datatype. Using int’s might seem more straightforward, but it would also take up at least four times more memory and hurt performance. It’s also a good idea to make the array just a bit bigger than the actual map dimensions and create a single-tile “buffer zone” around the map so that you can avoid checking for boundary conditions during the simulation.

Finally, during the simulation step we just loop over the entire array and apply the simple rules I mentioned above to each tile that contains material that should be affected by gravity.

Getting It Right

Now that's just silly.If you go ahead and implement the above algorithm as written, you will get a simulation that kind-of works, but quickly grinds to a halt on big maps and sometimes behaves in unexpected ways. For example, you might see sand tiles that seem to “teleport” to the bottom of the map instead of falling gradually and water that always flows left after hitting a free-standing ground tile (even though there’s a perfectly suitable channel available on the right side). Lets see what we can do about that.

Keeping track of updated tiles

The “teleportation” behaviour can happen if our simulation algorithm doesn’t keep track of which tiles it has already moved around during the current simulation step. For example, first it loops over the top row of the map, finds a water tile A and moves it downwards one row. Then it loops over the second row, finds the tile A, moves it again, goes to the third row, moves the same water tile again… and so on, until the water tile A hits a solid tile or falls off the map.

To prevent this bug we need to somehow remember which tiles have been updated already. Since I wanted to keep the memory use low, I used the most-significant bit of each map array element to indicate whether that tile was last updated on an even-numbered simulation step (0) or an odd-numbered step (1). Then, at the start of each step, the algorithm calculates what the flag should be for tiles updated in that step :

update_mask = byte ( ( simulationFrameCount & (long)1 ) << 7 );
//this basically takes the modulo of frame-count / 2 and shifts the result 7 places to the left

…then sets the msb of each tile it updates to that value and automatically skips tiles that have it already set to that value.

Pseudo-random movement

When a falling particle hits a free-standing fixed tile on a 2D map it has two choices – it can either move down and left, or down and right. In the naive algorithm I discussed above it will always try to move left first, leading to weirdness. Obviously we want it to choose at random, but on a big map generating a new random number for each tile would be slow. Instead, lets use the same approach as for the “teleportation” problem and move it either diagonally left if the current simulation step is even-numbered and or diagonally right if it’s odd-numbered. This can still introduce some artifacts in the simulation behaviour, but they’re rarer and and significantly less noticeable.

Optimization

Speaking of optimization, we don’t really need to update each gravity-enabled tile every time. Many of them will eventually end up in a situation where they can’t move anywhere (e.g. water at the bottom of a puddle or sand resting on a flat surface), so it would be nice if we could quickly skip them and not waste our time trying to apply the simulation rules to these static tiles. This would help performance quite a bit.

The way I implemented is with the help with another bit-flag. If the simulation algorithm discovers that it can’t move a tile in any direction, it will set the tile’s “static” bit-flag. It will also skip any tiles that have the “static” bit-flag set.

There’s some additional book-keeping we need to do to make this work as intended. When an empty space is created somewhere in the map (e.g. by a water tile moving down) we need to re-activate any gravity-enabled tiles that are directly above the newly created hole, so that they can fall/flow down into that space.

Possible Improvements

The result is a pretty basic and plain simulation that is useful to explain the basic principle, but it wouldn’t really qualify as a full game. Here are some ideas you could use to improve it :

  • Make water flow horizontally if there’s another water tile on top of it. Consider adding a simple pressure model [link to my prev. article].
  • Implement fluid density. This one is easy – if the current tile is more dense than the tile below it, swap them.
  • Add tile generators, e.g. a faucet that creates a water tile below itself on each simulation step (included in my demo application).
  • To improve performance, use a quadtree to keep track of which regions of the map have interacting tiles and quickly skip inactive regions.
  • Explore the source code of existing games and look for interesting ideas. Some open-source examples : wxSand, SDL Sand.

Live Demo & Source

Like my previous fluid simulation app, this one was also written in Processing. In addition to a working implementation of the algorithm discussed above it also lets you draw and erase water/ground/faucet tiles using your mouse, pan around the map with the WASD keys, zoom in/out with the mouse wheel and more. However, be warned that the map rendering code is not very optimized so the simulation will degenerate into a slideshow if you zoom all the way out, regardless of how fast your system is.

Related posts :

14 Responses to “How To Make a “Falling Sand” Style Water Simulation”

  1. Ross Shannon says:

    Good tutorial, thanks. I don’t understand the problem with particles teleporting downwards though — it seems to be that the only reasonable way to program this is to do the simulation updates bottom-to-top. Otherwise, if you update top-to-bottom, when you update the game state array, any particles that have another particle above them will be overwritten by the top particle falling into their position?

  2. White Shadow says:

    You are correct, updating bottom-to-top is a good approach. I didn’t mention it in the post, but that’s exactly what my demo app does.

    However, that alone wouldn’t be enough to prevent “teleportation” in a more complex simulation. For example, if you added a rule like “if this fluid particle has another fluid particle above it, move this one sideways” (i.e. a very basic pressure factor), you’d get particles teleporting left or right depending on the direction of your X loop. So tracking which particles have been updated still makes sense.

  3. Henk says:

    Neat tutorial, I followed it on a bored friday evening :). I implemented the teleporting thing using a simple ‘updated’ boolean 2d array that sets fields to true if they’ve been updated during that round, but that’s mainly because I’m not much of a bit twiddler.

    Haven’t got the water going horizontal right yet though. It’d probably become either very complex, or need to be rewritten if I ever add other materials.

  4. Grant says:

    There is a very easy fix for the “teleporting” problem. Before the main loop (updating every tile), copy the entire world into a “copy” array. Then, whenever a particle is updated, it gets its information about the world from the original array, but modified the copy array. At the end of the main loop, you copy every value from the “copy” array into the origininal array. The reason it works is: every particle gets its information from a non-updated array! No particle can influence another particle DURING the updating process!

  5. Grant says:

    Whoops! Instead of “…but modified the copy array…”, it should read “…but modifies the copy array…”

  6. White Shadow says:

    True, but I suspect performance would suffer if you copied the entire world (twice!) every frame.

  7. shpen says:

    I’m having problems with creating an even falling pattern. Because I am iterating through each sand particle one by one, from left to right, the sand tends to fall to the left, since a slot on the left is opened before one on the right. Is there any way to fix this and cause an even falling pattern?

  8. White Shadow says:

    Hmm, I don’t see how that could happen. If you’re iterating left to right, bottom up, the entire lower line should fall down “at once”, from the perspective of the simulation.

  9. shpen says:

    I’m actually going from top to bottom, but bottom to top still causes the same problem.

    Maybe you can take a look at my source and help me figure out what’s wrong:
    http://dl.dropbox.com/u/77961/GameTemplate.java

    Also, here’s a jar which will show you what the problem looks like:
    http://dl.dropbox.com/u/77961/SandTest.jar

    Thanks!

  10. White Shadow says:

    Ah, now I see it.

    One possible way to fix the problem would be to only allow a sand particle to move left/right if both the corresponding diagonal and horizontal neighbours are empty:

    if ((x > 0) && (sand[x - 1][y + 1] == 0) && (sand[x - 1][y] == 0)) {
    	left = true;
    }
    
    if ((x < (WIDTH - 1)) && (sand[x + 1][y + 1] == 0) && (sand[x + 1][y] == 0)) {
    	right = true;
    }
    

    (I haven't tried this myself.)

  11. TenCashMan says:

    I would like to say thanks a lot for this post!
    I have been looking for something like this!

    With this post I was able to put together a small falling sands app for the psp!
    Thanks man!

    Also, In some falling sands games (well, most actually) you see particles have random left and right movements as they fall, would it be wise to implement that into the program?

  12. Jānis Elsts says:

    Just try it and see how it plays. That’s probably the best advice I can give.

  13. TenCashMan says:

    Ok, I tried to make another falling sands kinda game for PC (c++ and allegro) and I am running into alot of trouble.

    Sand doesn’t fall down correctly going to the… right side. It stacks up and flows down one layer at a time, but it works fine going to the right side.
    Also sometimes when it goes to the right side, it forms “cacti” so to speak. The water will sometimes start going in random directions before falling the down.

    It’s probably pretty hard to look at, but here is the if statements for when water should move.
    http://pastebin.com/ZSP71r8S

    I would appreciate any help.

  14. feee3.com says:

    Thanks for any other magnificent post. Where else could anyone get that type of information in such a perfect method of writing? I have a presentation subsequent week, and I’m at the search for such information.

Leave a Reply