I'm a software engineer who works on game development part time. I teach game development (on gamedev.stackexchange.com and lynda.com). I'm always working on something, and I'll post updates here. Let me know if there's a game development topic you want to know more about, I probably know the answer, or at least where to get one.

Saturday, October 1, 2011

The latest on flow

Once again, I’ve rewritten flow. I think I’m actually honing in on some kind of optimal solution for my needs. So far in my iterations I’ve come up with two basic methods for moving flow around, push or pull. But first some definitions.

Flow: So far, this is just Water or Lava. 
Cycle: A step through the flow loop. Ideally touches all flowing cubes to update them.
Source cubes: Infinite sources of flow (springs, rivers, etc.). While they will never run out of flow, they have a limited supply of flow per cycle.
Flow cubes: Cubes that have flow in them.

And now the two flow moving methods.
In this method, I keep track of source cubes. Each cycle these cubes had a certain amount of flow they want to get rid of. So I loop through each source cube, and find somewhere logical to put their flow. This is done by stepping out from source cubes until we find somewhere the flow fits, and then filling in that space. I’d skip past cubes that had full flow, to save the trouble of propagating flow through cubes that are already full, and would be full after. Additionally there’s some smoothing involved that lets us look for places where there’s too much flow, and spread it evenly among it’s neighbors.
In this method, I keep track of all the cubes that are not full yet, including empty cubes that are directly adjacent to cubes with water in them. I also keep track of what Y level the cubes are on, lower level cubes get priority. Each cycle I start at the lowest level, and work my way up. This kind of simulates gravity, it makes sure that things will flow down hill before spreading on top of the hill. At each level I select cubes randomly until I’ve gone through all the cubes on that level. When a cube is selected, it follows it’s parent flows back trying to find a source cube. If it finds a source it pulls flow from it. If the source cube is empty for that cycle, it will check it’s parent flow. If the parent flow has two or more flow than the current flow cube, the current flow cube takes 1 unit of flow away. This has kind of a leveling effect.
With both methods I keep track of parent flows. This is required to see if a flow still has a source. This is where I think the pull method works so much better. When there is no source the pull method, it can just seek the highest parent, and take flow from them. See the image below to see what the parent child connections can end up looking like. Here black is the parent and white is the child. Parents can have multiple children, but children can’t have multiple parents. Also, as you can see, flows are non-diagonal only. This simplifies things greatly, but does make for some unintuitive flow paths.

My latest rewrite implemented the pull method. It’s mostly working. There are still a few issues I’m working on, but I’m getting closer. Check out how it looks in the video below. Feel free to ask questions about specifics if you’re trying to implement something similar.

No comments:

Post a Comment