natural 'water' flow through web of nodes.

Question

Hopefully this will be clear enough.

I have a 2d map made of tiles, and I want "water" to travel through this map. It comes out of a pipe onto a specific tile, and then needs to fill up, like water, all the tiles to reach a certain other tile. I currently have the map inputted into the game with each tile being a node and each node having connections to all appropriate tiles around it. I have the nodes stored in a sorted array, first by x, then by y. Additionally, some tiles are 'gate' tiles, which can stop water from flowing through them. These are part of the same grid of node tiles and are just flagged when active.

The problem is how I disperse the water.

Initially I had each pipe (which drops water) keep track of a list of 'current' and 'full' water tiles, and it would disperse water directly to the 'current' tiles, and then switch them to its 'full' list when appropriate. The 'current' list was expanded by getting surrounding tiles of the already 'current' tiles. In any case, this worked well, and water flowed nicely, but I couldn't figure out how to make it work with the gates so that the flow of water could be stopped, and re-allowed, (and stopped again, etc.) at a specific point.

Right now I have it where the water dumps into one and only one tile, and then while a tile has too much water, it pushes the water incrementally onto a random neighboring tiles (unless the tile is an active gate.) The problem with this is that the water 'sloshes' around already filled tiles instead of flowing 'outward.' It will get there eventually, but the flow is much less natural.

Thus concludes my dilemma.

The code is written in python.

Edit: New idea. I could have the pipe search through the nodes for a suitable free tile to place the water every update, but this seems horribly inefficient--particularly with multiple pipes.

Answer 1

Does your model include a concept of potential difference or pressure?

Say an empty tile has zero pressure, a full tile a pressure of 10. If theres a pipe between two tiles then water flows to equalise the pressure, a gate closes a pipe so nothing flows.

Answer 2

Some heuristics on the assumptions:

• discrete "drops" which occupy exactly one square each
• the water never remains more than one high on a given tile,
• the water always remains continuous
• when the barriers are up they are like walls
• when the barriers are down they are like open squares

For every puddle, maintain a list of edge squares and open squares next to the edges.

When a barrier goes down

amend the lists of edge and open squares for any puddles that were touching it

When a barrier goes up

if (it was covered)
    pick a non-wall square next to it at random, and add the drop from the barrier there.
amend the lists of edge and open squares for any puddles next to the block

When you add a drop:

if (the square "under" the pipe is empty)
   fill it
else
   consult the list of edge square associated with the pool under the pipe, and select the one closest to the pipe (if more than one is closest, choose from the candidates at random), and fill it.  
amend the lists of edge and open squares for the puddle (be prepared to merge with neighboring puddles if necessary)

When you remove a drop

 find the edge (not open!) square farthest from the sink (or randomly select from the equivalent candidates), and empty it
 amend the lists of edge and open squares for the puddle

(a frill available here is to make the "farthest" bounded by equal distance to other sinks, so that squares in the middle of a puddle can become empty if they are between sinks)

This isn't very realistic, and doesn't get you any dynamics to speak of, but will maintain continuous puddles "under" the dripping pipes and fill up the available space given enough drips.

Answer 3

This comes up a lot in game development -- there have been many GDC talks and Gamasutra/Game Developer magazine feature articles on this very subject. The best for your purposes I think is Jos Stam's "Real-Time Fluid Dynamics for Games" from the 2003 GDC.

He describes a simplified way of performing advection via a linear backtrace which suffers from some problems but works quite well for incompressible fluids (that is to say, it works better for water than for gas). Linear backtrace means basically that he sets up a grid representing fluid density at each point in space (that's your tiles), and then for each frame visits each point and asks, "based on the pressure at the surrounding points, where is the fluid likely to come from?" This turns out to be easier than solving it the other way ("where is the fluid from this point going to go?").

Mick West's article on fluid dynamics for Gamasutra extends Stam's paper in some ways that may improve performance, so you may want to start there.

There is also a recent Intel-sponsored GameDev article that offers a more complete solution, but it's rather complicated and focused more on the graphical rendering side in 3d.

You can look at Dwarf Fortress for an example of tiled 2d fluid mechanics, but his solution seems to have a bunch of problems dealing with fast-flowing or pressurized fluids; sometimes his water moves way more sluggishly than you'd expect, or gets caught up in blocks and corners.

Those papers summarize the math and algorithm way better than I could cram into a Stack Overflow box, but there's two general points I'd like to make too:

1. Water simulation is very computationally expensive. Since you're working in Python, this may result in a real performance problem -- be sure to set up some means of profiling your algorithm to find the hotspots in case your loop takes so long that it kills framerate. You may have to resort to Numeric Python to get fast C-based array operations.
2. There is way more math in game development than most people expect!