Monthly Archives: July 2012

I made quite some progress on my water simulation. As well as plenty of other “behind the scenes” things like threading (managed to get average increase of ~20fps), saving/loading level to file and plenty of other small tweaks and changes.

Inner Workings of the simulation

Let’s start with the basics: liquid is represented as an integer number and at the moment any block can have from 0 to 15 units of liquid (which is water at the moment, but I plan to have more types, one of them obviously being lava). I use integer numbers because of couple reasons, even though floating point number would be better and simulations would be a lot more physicaly accurate if used with Shallow Water Simulation Model (See this paper for more info), it has its disadvantages: at the moment I use only 1 byte for liquid per block and using floats would need 4 times that, also due to the nature and precision errors in floats in many cases it would take a long time for larger bodies of liquid so reach stable state where no simulations would be needed. Integer numbers also have problems obviously, main one being that distributing 7 units of water into 2 blocks is quite hard, and if flow is prevented when difference between neighbours is only 1 unit, cases like 5|4|3 will appear, creating this ramp/stair effect which would imply that liquid has very high surface tensions which is not true for water.

The most basic liquid simulation using cellular automata would be something along those lines: check if liquid can flow straight down, if it can, perform flow operation and then if there are liquid left, or flow down was impossible, perform spread out operation which would distribute liquid to all the neighbours until most balanced state is reached (It is very easy to do using float numbers, however integers have problems there). Of course this has all the problems mentioned before, as well as some other related problems, one of them being Waterfall problem – when falling water creates a pillar and in some cases full amount of liquid can flow down so it spreads out in mid air, causing wider stream, as well as creating a large ramp if large amount of liquid is used.

In my implementation liquid is simulated in three stages:
First Stage – flow directly down, if any amount of liquid can flow down, perform flow and skip other stages until next simulation frame. This slows down the liquid flow speed, however if helps to deal with waterfall problem, it does not solve it completely, but it looks a lot better.
Second Stage – flow to the sides, this stage is only reached when conditions of stage one were not met, if possible in this stage liquid tries to flow to four sides, to the blocks with lowest amount of liquid. I test all 4 neighbours and pick the one with lowest amount of water, then flow 1 unit of water to it if possible (main block has at least 2 units more liquid, so it balances out 7 5 to 6 6), this operation is repeated until no more flow is possible.
Third Stage – this stage is only executed if no flow happened in stage two. In this stage path finding is used to search small area around the main block for possible outlets in a similar fashion as described in Here (I suggest to read the whole article, it is an interesting read). Path finding creates a list of all blocks that have space for liquid, then this list is sorted based on the distance to the original block, and flow is perform in that order until either there is no more liquid to flow, or all of the blocks in the list cannot accept any more. If that happens, outflow block is marked as static so no more simulations are performed unless it is woken up by other blocks. This also creates a limited liquid pressure.

Having three stages allows to distribute work better over multiple frames. Performing all the stages or even just stage three for each block would take a lot of time, even threads are used, it would cause problems where liquid would be simulated only in small areas because by the time it would be finished, the next stage would be triggered and it would need to perform simulation again from the start so simulation would not reach block segments (world is split up into small cubes for frustum culling, and other octree based optimizations) which are at the end of the queue until stable state is reached etc. At the moment my implementation has quite a few limit on how many stage threes can be performed in a single frame, before it quits simulation early, which helps to keep frame rate stable and makes sure that all block segments which need to have liquid simulated get at least some processing done. That means the overall liquid flow will be slower, but this will not cause any excess lag in other aspects of the game.

There are plenty of other smaller things I did not cover like: removing requirement for back buffer, exact details of path finding and so on, if you are interested in any specifics feel free to ask!