Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a 2D grid based water system in my XNA game, we have a method using cellular automata to simulate water falling and spreading.

Example of water flowing down a slope:

Water Physics

Each tile can contain a mass of 0 to 255 values of liquid, stored in a byte. I do not use floats, the old water system I had did, however it added complications and had a performance hit.

Each water tile updates itself with a simple set of rules:

1. If the tile below has space in it, move as much as possible from the current tile to the bottom one (Flow Down)

2. If the 2 sides aren't the same and aren't zero and both are passable, we get the sum of the 3 tiles (left + current + right) and divide it by 3 leaving the rest on the middle (current) tile

3. If the rule above gived a number of 2 as sum, we should divide the tiles into the two sides (1, 0, 1)

4. If rule 2 gave 1 as the sum, choose a random side to flow into

5. If rule 2 failed, we should check if one side is passable and the other isn't. If that is true, we split the current tile in half for the 2 tiles

How can I expand this logic to include pressure? Pressure will make liquids rise over "U-Bends" and fill in air pockets.

Example on how this is currently fails:

Pressure Fail

The water should flow and equalize on each side of the U-Bend. Additionally, I have created methods to find out how far down a water block is, and therefore how much pressure it is experiencing. Now I need to be able to take these numbers and apply them to the other areas to equalize the pressure

share|improve this question
    
The problem is it's hard to keep it a cellular automata. Since now each block needs to know more than just what's next to it. I created a system similar to the one you're wanting in 3D. It's a pretty complex system, but I think it would be more doable in 2D. –  Byte56 Jul 7 '13 at 22:48
    
@Byte56 Well we don't need it to be cellular automata, as long as we can keep it running at reasonable speed. –  Cyral Jul 7 '13 at 22:50
3  
I'll create a full answer if I find some time this evening. However, simply put, I essentially created pathfinding for the water. Blocks want to find somewhere with less pressure to go. They path find through the other water looking for somewhere that has less water than they do (air next to water included). It solves a large majority of the use cases. –  Byte56 Jul 7 '13 at 22:55
    
Thanks, that would be appreciated. I read some interviews with the maker of Dwarf Fortress and he did this I belive, but I wasn't sure how to overcome some of the problems he ran into, so I never really tried. –  Cyral Jul 7 '13 at 23:01
1  
Note that, once you get air pressure added, the two air-pocket examples are potentially completely valid (closed pressure chambers). I'm assuming you're not using 255 bytes, but rather values 0-255; in any case, you're probably not going to want to use the full range that way. I'd probably limit it to, hmm, 0-15 for '1 atmosphere' of pressure (there is no such thing as 'negative' pressure, right?), allowing higher pressures, which you currently lack. Once you include the 'air' blocks in the sim, the naturally higher 'weight' of the water blocks should cause it to flow around the bends. –  Clockwork-Muse Jul 9 '13 at 23:46
show 4 more comments

5 Answers 5

up vote 5 down vote accepted

Note that I've never done this; these are only ideas which may help. Or might be totally bogus. I'd been wanting to tackle this problem ever since Terraria but am not currently working on such a game.

A way I've considered trying is to give each surface water block (any block with water in it and with no water block above it) an initial pressure value equal to (or a function of) its height from the bottom of the world. The implicit pressure value of any impassable tile is MAX_PRESSURE (say 255), and for an open air tile is MIN_PRESSURE (0).

Pressure is then spread up/down/sideways from any tile with a higher pressure to tiles with a lower pressure during each tick, cellular automata style. I'd have to get an actual simulation up to figure out exactly what to equalize to. A block's pressure should be equal to its implicit pressure plus the "excess" pressure from around equalized (so you'd only need to store this excess pressure, not the implicit pressure).

If a surface tile has a pressure larger than its implicit height-based pressure would be and if the tile above has free space for water, a small portion of water is moved upward. Water only flows down if the tile both has room as has lower pressure than expected.

This roughly simulates the idea that the deeper the water "point" the more pressure it has, albeit the pressure values represent more the height than actual pressure (since higher tiles are expected to have higher "pressure"). This makes the pressure kinda sorta like the h term in the equation (but not really):

P' = P + qgh

The result is that if the water's pressure is higher than it should be for its depth, it'll be pushed up. It should mean that water levels in closed systems will equalize pressure across all height levels over time.

I'm unsure how to deal with or whether one even needs to deal with the "air bubbles" that would be created (where a non-surface tile will have non-full water amounts as water is pushed upwards). I'm also still unsure how'd you'd avoid loops of water pressures being unequal on one side and then after ticking being unequal on the other side, back and forth.

share|improve this answer
add comment

I created a system similar to the one you're after in 3D. I have a short video demonstrating the simple mechanics of it here and a blog post here.

Here's a little gif I made of the pressure mechanics behind an invisible wall (played at high speed):

enter image description here

Let me explain the data involved, to give an idea of some of the features of the system. In the current system, each block of water contains the following in 2 Bytes:

//Data2                          Data
//______________________________  _____________________________________
//|0    |0      |000   |000    |  |0        |0       |000      |000   |
//|Extra|FlowOut|Active|Largest|  |HasSource|IsSource|Direction|Height|
//------------------------------  -------------------------------------
  • Height is the amount of water in the cube, similar to your pressure, but my system just has 8 levels.
  • Direction is the direction the flow is going. When deciding where the water will flow next, it's more likely to continue in its current direction. This is also used to quickly back trace a flow back up to its source cube when needed.
  • IsSource indicates if this cube is a source cube, meaning it never runs out of water. Used for the source of rivers, springs, etc. The cube on the left in the gif above is a source cube, for example.
  • HasSource indicates if this cube is connected to a source cube. When connected to a source, cubes will try to tap the source for more water before seeking other "fuller" non-source cubes.
  • Largest tells this cube what the largest flow between it and its source cube is. This means if water is flowing through a narrow gap, it limits the flow to this cube.
  • Active is a counter. When this cube has active flow going through it, to it, or from it, active gets incremented. Otherwise active is randomly decremented. Once active hits zero (meaning not active), the amount of water will start to be reduced in this cube. This kind of acts like evaporation or soaking into the ground. (If you have flow, you should have ebb!)
  • FlowOut indicates if this cube is connected to a cube that's on the edge of the world. Once a path to the edge of the world is made, water tends to choose that path over any other.
  • Extra is an extra bit for future use.

Now that we know the data, lets look at a high level overview of the algorithm. The basic idea of the system is to prioritize flowing down and out. As I explain in the video, I work from the bottom up. Each layer of water is processed one level at a time in the y axis. The cubes for each level are processed randomly, each cube will attempt to pull water from its source on each iteration.

Flow cubes pull water from their source by following their flow direction back up until they reach a source cube or a flow cube with no parent. Storing the flow direction in each cube makes following the path to the source as easy as traversing a linked list.

The pseudo code for the algorithm is as follows:

for i = 0 to topOfWorld //from the bottom to the top
   while flowouts[i].hasitems() //while this layer has flow outs
       flowout = removeRandom(flowouts[i]) //select one randomly
       srcpath = getPathToParent(flowout) //get the path to its parent
       //set cubes as active and update their "largest" value
       //also removes flow from the source for this flow cycle
       srcpath.setActiveAndFlux() 

//now we deal with regular flow
for i = 0 to topOfWorld //from the bottom to the top
    while activeflows[i].hasitems() //while this layer has water
        flowcube = removeRandom(activeflows[i]) //select one randomly
        //if the current cube is already full, try to distribute to immediate neighbors
        flowamt = 0
        if flowcube.isfull 
           flowamt = flowcube.settleToSurrounding
        else
           srcpath = getPathToParent(flowcube) //get the path to its parent
           flowamt = srcpath.setActiveAndFlux()
           flowcube.addflow(flowamt)

        //if we didn't end up moving any flow this iteration, reduce the activity
        //if activity is 0 already, use a small random chance of removing flow
        if flowamt == 0
           flowcube.reduceActive()

 refillSourceCubes()

The basic rules for expanding a flow where (ordered by priority):

  1. If cube below has less water, flow down
  2. If adjacent cube on same level has less water, flow laterally.
  3. If cube above has less water AND source cube is higher than the cube above, flow up.

I know, that's pretty high level. But it's hard to get into more detail without getting way into detail.

This system works pretty well. I can easily fill up pits of water, which overflow to continue outward. I can fill up U shaped tunnels as you see in the gif above. However, as I said, the system is incomplete and I haven't worked everything out yet. I haven't worked on the flow system in a long time (I decided it wasn't needed for alpha and I'd put it on hold). However, the issues I was dealing with when I put it on hold where:

  • Pools. When getting a large pool of water, the pointers from child to parent are like a crazy mess of whatever random cube was selected to flow whatever direction. Like filling a bathtub with silly string. When you want to drain the tub, should you follow the path of the silly string back to its source? Or should you just take whatever is closest? So in situations where cubes are in a big pool, they should likely just ignore their parent flows and pull from whatever is above them. I came up with some basic working code for this, but was never had an elegant solution I could be happy with.

  • Multiple parents. A child stream could easily be fed by more than one parent stream. But the child having a pointer to a single parent wouldn't allow that. This can be fixed by using enough bits to allow for a bit for each possible parent direction. And likely changing the algorithm to randomly select a path in the case of multiple parents. But, I never got around to it to test and see what other issues that might expose.

share|improve this answer
    
Thanks! Very informative! I'll start working on this soon and accept it if all goes well. –  Cyral Jul 8 '13 at 18:32
    
Sure thing. I imagine a hybrid of your system and this one would be very effective for a 2D world. Ping me in chat (with @byte56) if you want to discuss details. –  Byte56 Jul 8 '13 at 18:33
    
Alright, might be a day or so before I get a chance to try this out. –  Cyral Jul 8 '13 at 18:35
3  
Understandably. I probably spent months working it out (and re-working it out). I'll be around for a while though :) –  Byte56 Jul 8 '13 at 18:37
add comment

I sort of agree with Sean but I would do it a bit differently:

A block generates a pressure equal to it's own weight (how much water is in it) and applies it to the blocks below and beside it. I see no reason it's position in the world is relevant.

On each tick move water from high pressure to low pressure but move only a fraction of the water needed to equalize. Water can also be pushed up if the pressure in the block is too great for the pressure being applied down on the square.

You will get loops where the water pressure flows too far one way and then has to correct but since you don't move the whole amount of water per tick these will be damped. I think it's actually a good thing as you'll get surge effects as water floods into an area like you would in reality.

share|improve this answer
    
If water were to move up when the pressure being applied from above was too great, it would not be moving into a lower pressure block. In order for the pressure above to be too great, it would have to be greater than the block below. Additionally, pressure has to move up as well as down and left/right. –  Byte56 Jul 10 '13 at 14:00
    
@Byte56 You're misinterpreting what I said. I'm saying the water goes up when the pressure in the block you are analyzing is too high for the pressure being applied from above, not that the pressure from above is too great! –  Loren Pechtel Jul 10 '13 at 23:08
    
OK, so let me rephrase what you said so I understand: "the water goes up when the pressure in the block you are analyzing is greater than the pressure being applied from above". Is that correct? –  Byte56 Jul 10 '13 at 23:14
    
@Byte56 Yes. The pressure in the block should be the weight of water above it or being applied sideways when we have a solid surface somewhere above. Too little pressure on it means there's not enough water above, move water up. –  Loren Pechtel Jul 10 '13 at 23:17
    
Great thanks for setting me straight. –  Byte56 Jul 10 '13 at 23:18
show 1 more comment

You can add a rule that try to go left or right (through the walls) with the tiles until you find a free spot, starting with the layers on the bottom. If you cannot find, then the tile stays on the current position. If you find, then the another rules will guarantee the replacement of the moved tile (if necessary).

share|improve this answer
    
This is also a good idea, not sure if it would work in all cases but I will consider it. –  Cyral Jul 11 '13 at 20:44
    
Ok! Let me know whether it worked or not. regards –  almanegra Jul 12 '13 at 14:35
    
I will, just been a bit busy lately. –  Cyral Jul 12 '13 at 14:36
add comment

why cant you define another type of block that acts as an immovable amount of pressure? Therefore when you use your way of normally moving the water blocks and checking whether it can move up, it cant.

Even better would be to add another definition to those blocks that allows the user to enter the amount of pressure per block, increasing the pressure according to the amount of water blocks adding to it.

share|improve this answer
1  
"herefore when you use your way of normally moving the water blocks and checking whether it can move up, it cant." Yea... It already can't. Thats the problem, I'm not looking for a way to make it stay the same. –  Cyral Jul 10 '13 at 13:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.