Inactive Liquid Simulation

[Linus]

Cervator edit: Back when last this worked it was in a standalone module, so I moved it to the Modules forum. However it needs a refresh at which point what repo(s) it might occupy should be reevaluated

Name: Cellular Automata and Liquid Simulation
Summary: A system to run block based cellular automata (CA) and the implementation of a CA to simulate water and other liquids.
Scope: Engine
Current Goal: Allow CA's to move between update regions and clean up water implementation.
Phase: Implementation
Curator: DizzyDragon
Related: World generation


CA System
Fluid Dynamics covers the simulation of liquids and gas. The generation of rivers, lakes,oceans, volcano's etc. on the map are outside of the scope of the project. To keep the scope of the project manageable I think it is good to just assume that we already know where the fluids are located on the map.

Reasons for choosing the CA approach
First an volume based approach was chosen for simulating liquids. This was favored over a particle based approach because the world was already divided up into cells. Letting the state of a cell only depend on it's direct neighbors makes it a lot easier to deal with a world where not all chunks are loaded at all times. This considered, it seems a lot more logical to go for a more general CA system, that can easily be reused to do more simulations, than to go for a system that is specifically made to simulate water and nothing else.

Done

• Basic architecture:
  • abstract CellularAutomaton class: Responsible for calling the actual block updates of a system and doing this efficiently,
  • children of CellularAutomaton class: provide update/state transition rules. Should be easy to implement, without worrying about the actual update procedure.
  • CellularAutomatonManager/CellularAutomatonSystem class: Handles calling updates on the CellularAutomaton implementations.
• Synchronous block updates: The system is able to synchronously update a region of blocks. This is by using a buffer to write new block states to instead of directly writing them to the world.

To do list

• Allow CAs to cause updates in neighboring regions
• Fix light updating situation, so only one update call is needed after changing all blocks
• Move CA to it's own thread
• Allow CAs to catch block update events

Liquid CA

Data per block of fluid
To simulate a liquids the following data is stored in the extra data of a liquid block:

• amount of fluid (A)
  (Unsigned) byte to store how much water is currently in a block
• flow direction (F),
  6 bits to be able to set a flag to each direction to which water is flowing out of a block
  Makes it possible to let blocks flow to multiple directions at the same time
• flow magnitude (M)
  How much water is flowing out of the block
  
  extra data int: 0000 0000 00MM MMMM MMDD DDDD AAAA AAAA

Behavior
There are 10 CABWater blocks, each with a number indicating how much water is in them.
CABWater1 has 0-9 water units, CABWater2 has 10-19 units, CABWater3 has 20-29 units and so forth. These block follow the following rules:

• Water blocks can have any ammount of water in them between 1 and 100 (inclusive).
• Water can only flow into air blocks or water blocks.
• If water can flow down it will flow down.
• If water can not flow down it will try to flow sideways
• Water can only flow sideways to blocks that contain less water than the current block
• Water will flow to the side(s) with the maximal possible inflow.

Instructions
For those of you who want to test the liquid implementation, beware that it still far from finished. Water cannot disappears when it crosses the boundary of a UpdateRegion. The purple CAWater block is usefull to find the boundaries of UpdateRegions. At the moment, the only way to force a region to restart updating is by placing a CABWater10 block. When water can no longer flow, the region will stop updating.

Done

• Down flow and side flow
• Reading/Writing flow direction, flow magnitude and liquid ammount to/from extradata.

To do list

• Fix water disappearing in some certain situations
• Add evaporation for small puddles of non-moving water
• Add more stuff: source/sink blocks, buckets, pressure and upflow
• Make the flow direction of a block affect it's neighboring water block flows

 

[Skaldarnar]

Nice wrap up!

First of all, the choice on the volume based approach seems legit, as well as the fact that rivers and lakes are part of the main terrain generation (maybe a post-processing step like cities/forests), but that is indeed another field

Could it be useful to have some octree structure for large bodies of water? The bigger structures might serve as the larger bodies whose state is not changed (because its surrounded by "more" liquids of same type).

Additionally, do you have something like infinite sources in mind? How are they represented with your system (just one more flag)?

Nice stuff, keep going

 

[Cervator]

Great to see this hit Incubator stage!

Think we need to track direction rather than just amount of liquid then simply figure out via adjacent amounts where the liquid wants to go? Two ints seems a lot unless you're saying we should track by chunk rather than by block somehow. I think we could do something interesting with just a couple bytes per block including liquids/gasses in otherwise solid blocks to give clues to growth systems, do interesting stuff like pressurized aquifers and so on

Also just for reference here are a few older threads with more discussion:

• http://forum.movingblocks.net/threads/my-thoughts-on-realistic-water.602/
• http://forum.movingblocks.net/threads/real-liquids.444/
• http://forum.movingblocks.net/threads/organic-growth-simulator.104/ - growth simulator that could benefit from more per-block data like moisture
• http://forum.movingblocks.net/threads/per-block-data-storage.146/ - old thread on block data

 

[Immortius]

On velocity, depending on what you need in that space you can use a byte or less. If you only allow movement in axis directions, that's 6 directions plus not moving for 7 different values - 3 bits. If you allow diagonal combinations, that's 27 values. If you want integer speeds in x/y/z axis you can have up to +/- 42 stored in a byte.

 

[Linus]

Could it be useful to have some octree structure for large bodies of water? The bigger structures might serve as the larger bodies whose state is not changed (because its surrounded by "more" liquids of same type).

Do you mean to check for updates or to store data about the larger bodies of water?

Additionally, do you have something like infinite sources in mind? How are they represented with your system (just one more flag)?

Infinite sinks and sources could be represented with just an additional flag, I think. Making sure the amount of water in the sink source blocks stays constant over time should do the trick. A sink block would just be a liquid block with a constant liquid amount of 0, while a source block would have an amount >0.

Think we need to track direction rather than just amount of liquid then simply figure out via adjacent amounts where the liquid wants to go? Two ints seems a lot unless you're saying we should track by chunk rather than by block somehow.

Storing velocity has the benefit of being able to have flowing water, without having to update it each tick.
I did go a bit overboard with 3 bytes for velocity, though. Thanks Immortius for pointing that out.

 

[Skaldarnar]

Do you mean to check for updates or to store data about the larger bodies of water?

Not sure if you can update a large body at once. We may loose a bit of realism, but if every liquid block in the body has the same properties you could just equally distribute the change to all blocks in the body.

 

[Linus]

Update

I implemented the foundations of a simulation system. It is nowhere near a finished product, but at least there is something for me to experiment with now.

What has been implemented so far:

• Basic architecture:
  • abstract CellularAutomaton class: Handles calling the actual block updates for a system,
  • children of CellularAutomaton class: provide update/state transition rules.
  • CellularAutomatonManager class: Handles calling updates on the CellularAutomaton implementations.

• Synchronous block updates: The system is able to synchronously update a region of blocks. This is done by storing the new states separately and applying them all at once at the end of a region update. (Regions are currently just chunks.)
• Two toy CellularAutomaton implementations:
  • An ocean water CA, which makes a water block expand to the side and down when possible.
  • A 3d version of Game of Life. I found this quite useful for testing purposes.

To do list:

• Updates are very slow, because once a chunk is flagged for updating, the system will just do a massive for loop over all blocks within it. This can be improved using finer flagging.
• The updating will need to be moved to a new thread, so it doesn't stall the rest of the game.
• CA's are currently confined to a single chunk, this will need to change once updating is a bit faster.

This screenshot shows a structure build generated by 6 3DLife blocks.

Edit: I forgot to mention that the system uses the extra data of blocks to store the Cellular Automaton related states in. This means that blocks can either be part of a system or have their own extra data. Is this acceptable or should this change?

 

[Cervator]

Very cool! I tested it and yeah while the life blocks are extremely laggy and brings the game to its knees pretty fast I can see it working. I made a highlighted build to test it but probably should wait till it gets optimized to really push it on the social outlets

As for block-level data architecture then that has come up in the past some, but doesn't have an elegant solution yet. There's some old discussion in the per-block data thread and might also be some newer stuff in the sparse chunks thread (unsure). At first I was thinking about squeezing more multi-purpose data into the existing primitive engine data types, but we do need a way to support modules adding new per-block data types, even if such data could be extremely expensive.

The way the life blocks follow rules and expand based on that also reminds me of the organic simulator woodspeople wrote (in Python) where trees grow organically based on rules about water, nutrients, sun, and fun stuff like that. Not sure if the implementations are similar enough to synergize some, would be cool if implementing one helps half-implement the other

 

[Immortius]

Edit: I forgot to mention that the system uses the extra data of blocks to store the Cellular Automaton related states in. This means that blocks can either be part of a system or have their own extra data. Is this acceptable or should this change?

We will likely be refactoring the chunk system to allow for arbitrary extra data per block later, so I wouldn't worry about it. Where possible avoid using extra data of course - if the simulation can run entirely based on the blocks present that is ideal, although not always achievable.

 

[Linus]

Update:

First implementation of mass preserving liquid is done. I will update the incubator so it accurately describes the current state of the project.

What is done:

• CA can now have update functions which consists of multiple steps. For update functions with multiple steps, the end result of each step is calculated for every block and written to a buffer. This buffer will then be the input for the next step. Only the result of the final step is written to the world. In the liquid CA this is used to calculate the outflow direction and magnitude before calculating the new water amounts.

• Liquid CA: A ruleset for liquid, so that it flows sideways and down naturally.
  
• UpdateRegions added. These are 16x16x16 regions, which also have a flagging system to greatly reduce the amount of unnecessary block state updates.
• Found the reason why region updates to so long in the previous version. This was mainly caused by the light updates, which could initiate after every block update. (+/-4000 possible updates in a 16x16x16 region update)
  This has temporarily been solved by just not doing any light updates.

To do list:

• Allow CA's to cause updates in neighboring regions.
• Fix water disappearing in some certain situations.
• Real fix for light update situation.
• More water featured: source/sink blocks, buckets, pressure and upflow

One way the light recalculation could probably be fixed is to implement the setBlocks() functions in the WorldCoreProviderImpl, so a whole region of blocks can be updated at once and the light recalculated only once per region update.

Edit: just updated the top post

 

[Cervator]

Yay progress! Thanks for the update

I tested your branch and can see CAB10 work briefly, spreading out into lower blocks, but then the game crashes. Every time, same error. Lower blocks do not spread at all, unless I "trigger" them with a CAB10 (which then still crashes). Error:

22:31:22.512 [main] INFO  o.t.c.items.InventorySystem:74 - Receiving item Cabwater10 for toolbar
22:31:31.404 [main] INFO  o.t.c.CellularAutomataSystem:93 - CABWater added to chunk (0, 0, 0)
22:31:31.409 [main] INFO  o.t.c.CellularAutomataSystem:93 - CABWater added to chunk (0, 0, 0)
22:31:32.007 [main] ERROR org.terasology.game.TerasologyEngine:500 - Unhandled exception in main loop!
java.util.ConcurrentModificationException: null
    at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:761) ~[na:1.6.0_33]
    at java.util.LinkedList$ListItr.next(LinkedList.java:696) ~[na:1.6.0_33]
    at org.terasology.cellularAutomata.CellularAutomaton.update(CellularAutomaton.java:59) ~[na:na]
    at org.terasology.cellularAutomata.CellularAutomataSystem.update(CellularAutomataSystem.java:110) ~[na:na]
    at org.terasology.game.modes.StateSinglePlayer.update(StateSinglePlayer.java:114) ~[Terasology/:na]
    at org.terasology.game.TerasologyEngine.mainLoop(TerasologyEngine.java:474) [Terasology/:na]
    at org.terasology.game.TerasologyEngine.run(TerasologyEngine.java:206) [Terasology/:na]
    at org.terasology.game.Terasology.main(Terasology.java:39) [Terasology/:na]
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) ~[na:1.6.0_33]
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39) ~[na:1.6.0_33]
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25) ~[na:1.6.0_33]
    at java.lang.reflect.Method.invoke(Method.java:597) ~[na:1.6.0_33]
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:120) [idea_rt.jar:na]
22:31:32.008 [main] INFO  org.terasology.game.TerasologyEngine:428 - Shutting down Terasology...
22:31:32.729 [main] INFO  o.t.rendering.world.WorldRenderer:978 - It took 9 ms to save chunks to file E:\Dev\Terasology\Git\integrate\SAVED_WORLDS\World8\World8.chunks

The CA life block is working great, stays solid at 60 fps I was wondering if I could freak out the system by placing a few extra blocks in a hurry, dived into a boiling mess of CALife blocks, placed a few, managed to lock up the game Bet I hit just the right condition (re)placing a block triggering an infinite loop or some other issue.

 

[Linus]

Thanks for the bug report. I have fixed the bug that resulted in the crash, so it will be fixed in the next push.

The game does indeed sometimes lock when you place a new block in a region that has a CA running in it. I don't know what exactly is causing this yet. It's just a guess, but it might an issue of multiple threads trying to claim the same world area.

The code responsible for activating a region is currently just placeholder code with CAB10 hardcoded into it. That's why CAB1 to CAB9 don't update when placed.

 

[Marcin Sciesinski]

Just wanted to ask, so that bucket does not consume the whole block of liquid (like it does in Minecraft). One block is 1mx1mx1m of liquid (1000 litres), but bucket holds only about 20 litres. So it should be - one block = 50 buckets. If a minimum amount you can represent in a block is above the 20 litres, then please make the bucket contain the minimum you have in your system.

 

[UberWaffe]

A similar discussion went on around the finite liquids mod done for Minecraft.
Some ideas discussed over in that thread might be of use here as well. Seems like you already have most of them implemented/planned, but I'll throw them out there anyway.

Active/Passive liquid blocks:

Spoiler

Similar to UpdateRegions, each liquid block has a flag to indicate it is active or passive. (Might even use two separately defined blocks/entities).

-Active blocks (busy trying to flow somewhere) will only attempt to find somewhere to flow to for a certain (say 3) number of consecutive world ticks. If the active liquid fails to find anywhere to move to all 3 consecutive times, it becomes a passive block.
-Passive blocks do not try and flow at all. (No direction flags, no flow rate number. Only amount.) Passive blocks turn back into active blocks if an adjacent block triggers a block update.
Note that adjacent liquid blocks will only generate block updates if they change state (i.e. their stored amount changes).

Reason: No need to scan all liquid blocks all the time. (I.e. avoid OnTick or similar repeating triggers. More block update driven.)

Over pressure liquids:

Spoiler

Each liquid type defined has a maxAmount variable (as in stored per liquid class/definition, not stored per block).
If a liquid block contains an amount of liquid more than its maxAmount, and it cannot flow down or to any side, it can flow upwards (until amount <= maxAmount)

Reason: Can you image over pressure lava blocks underground that erupt into your cavern when you mine into them?
Or oil wells that spout up to the surface?

Additional consideration: You mentioned using multiple blocks per liquid type. This could (if required for the liquid type) be extended.
For example a Extreme-pressure oil-liquid block, and an oil-liquid block. When an extreme-pressure oil block drops to amount = 1, then it converts to a oil block with amount = 100.
That way you can make truly extreme eruptions.
This would not need any special functionality, since the modder can add in the code to convert one liquid of a certain amount to another liquid of a certain amount.
But a default function might be useful... maybe.

Liquid trail:

Spoiler

Each liquid type defined has a minAmount variable.
A liquid block cannot drop its amount below this through flowing. (Even vertically.)
If a liquid, say amount = 20, has a minAmount = 1 is placed up in the air. It will drop down, leaving behind liquid blocks with amount 1 each.
You will end up with a 20 block tall pillar of liquid, each with amount = 1.

Reason: Ability to generate waterfalls without needing a infinite water generating source at their origin.
By making the said liquid block always leave behind at least 1 amount (i.e. a little bit) you can have clients render that block to look like little streams or waterfalls.

Iffy, but does eliminate some problems with infinite water generation and consumption.

Natural Stable Elevation:

Spoiler

Each liquid type defined has a naturalHeight variable.
A liquid will flow down only if its y > naturalHeight. Else, if y < naturalHeight it will flow UP. Else, if y = naturalHeight, it will not flow up or down. (Only possibly sideways).

Reason: Allows the liquid mechanics to also then be used for gasses, simply by defining a 'liquid' with a naturalHeight of 12000 or something similar. (I.e. upper atmosphere). You will get a liquid that flow up, essentially then being a gas.

 

[Cervator]

Hello UberWaffe and thanks, good stuff! Yeah, I'm thinking that's the same MC mod that was mentioned in this older liquids thread and it is indeed neat. Pity it is so hard to keep mods maintained to the latest level of MC - which is then part reason we're here

Are you interested in helping with design like that, perhaps even implementation, or just passing by for a topic of interest?

 

[UberWaffe]

Yes, I read through the older liquid thread and had not noticed these points being mentioned specifically.

I'm willing to help with design and implementation.
I'll grab a fork of github and play around with it.

I am however (<- Yes, there it is) currently stuck on a work project that requires me to work 6 days a week, 10 hours a day, so do not expect a lot of progress on it.

What milestone and aims are currently envisioned for this?
I.e. What should I be aiming for next if I want to help out?

 

[Cervator]

"Howevers"s and "but"s are quite common around here, no worries!

Well, we've had lots of discussion in the past, but DizzyDragon is the first to begin an implementation - so we're breaking new ground here

Liquid sim is a very deep topic so I'd like to think there's enough space for design talk among a small group, even if there's only one implementer. Or there could be occasional small side tasks contributed akin to the multiplayer branch headed up by Immortius with a lead implementer.

When Dizzy's first stable implementation is ready and merged to develop (hopefully soon!) maybe we should line up a series of target features here along with some design talk for each. Could then make issues for them on GitHub with the desired approach and associate them all with a milestone. Then Dizzy can pick a few he'd like to focus work on and others can be up for grabs for whomever has a little time to help out?

 

[UberWaffe]

That sounds like a good plan. Projects (commercial or communal) succeed or fail based entirely on the combined effort (i.e. how many people are working together to achieve a common goal).

Now, to that effect, I might be bombastically stupid here, but where is the current github branch for Dizzy's liquid code?
I can only find a github branch for waterWIP by begla, and that seems to be several months old.


In the meantime:
Starting off by defining 'What we want from this system' is probably a good point. I'm sure we all have an idea what the CA system is aiming to do. But writing it down and assigning priorities to them does help a lot in the long run. Especially with scope creep.

I'll try and convert Dizzy's first post into a requirements list of must, should, ought to.
As per the very useful MoSCoW method.

Also, sneaking in some requirements... Shhh! Don't tell anyone!

Attempt 1:

Spoiler

The system MUST be able to:

1. Provide a means to implement any liquid with.
2. Allow simulation of individual liquid blocks to calculate liquid flow.
3. Provide a means to propagate liquid blocks based on calculated flow.
4. Allow liquids to flow upwards (i.e. like some gasses).
5. Allow liquid blocks to contains varying amounts of liquid.

The system SHOULD be able to:

1. Have no noticeable impact on engine performance, even when concurrently simulating up to 1000 blocks. (<- Utterly arbitrarily chosen number for now.)
2. Be able to provide additional information on a liquid type (not per block, but per type):
   • Mass of liquid per liquid amount
   • Name of liquid
   • Additional type specific data

The system COULD be able to:

1. Allow simulation of groups of liquid blocks to calculate as a whole (I.e. an entire chunk of a single liquid type interact with another entire chunk of the same liquid type as if both where just single blocks).

The system WOULD LIKE TO be able to:

1. Perfectly simulate liquids and flow dynamics.
2. Prevent the social and moral decay of humanity.

As a note. The requirements typically should make no specific claim to HOW they are met. Just what results are required.

Please feel free to add/change the list.

Also, maybe the Terasology engine should have a function to do block updates that do not trigger lighting recalculations. And a function that does lighting recalculation without a block update.
(Something along the lines of a 'Hey, neighbors, I changed. Check if that affects you... somehow.')

(For instance, if I swap one non-opaque block for another, then no light update is required.
Or in this case here, do several hundred liquid block updates and then only do lighting recalculations afterwards.)

 

[Linus]

Github branch is here: https://github.com/LinusVanElswijk/Terasology.
IMO it's best to wait for the next push, before really digging into the code though. I'm currently implementing UpdateRegion interaction and had to change a lot on the system end.

I don't know if this was clear from my previous posts, but my goal is to separate the system and the actual implementation of liquids. If you look at the current implementation of liquids or the implementation of 3DLife, you'll see that these do nothing more then just telling what the state of a block at the next timestep should be.

My aim for the next push is to have most of the system in place so that the simulations run as expected in the world. It should be no problem to have some people work on the liquid implementation while others work on the system.

Also, MoSCoW is a great idea, and I'll add it to the first post.

 

[Cervator]

Good first attempt requirements!

Of of my main things to ponder is exactly how to handle the per-block extra data, and whether it really is per-block data. I'm not sure from current descriptions whether the extra data is handled per block (like with a TeraArray, which I don't think is the case) or in some other construct that only tracks the data for liquid blocks.

My earlier thoughts were to throw some of the very basic type per-block goals together to come up with the most possible optimized use of per-block data that goes beyond liquid blocks to cover stuff like (quoting myself):

Visible liquid height in liquid blocks (or partial blocks like stairs / slopes), moisture in air (weather potential), moisture in dirt (growth system / fun with aquifers), oil and gas in deep minerals (bring your mining canary)"

Finally found all three of my old threads on the topic: block storage, block integrity, block dynamics bits of which are way out of date so keep that in mind.

The question in a nutshell: Do we support some base set of extra block data in one big pile (optimal efficiency), in the engine or a module if so, or keep everything that uses per-block data entirely isolated to itself (multiple modules, maybe with some frameworks). Some of the possible configurations include lighting data so definitely would be engine.

In other words - raise the minimum data footprint to always offer some basic functionality that may not always be needed (flat world without water as an example) or aim for minimalism in the engine even if it leaves more modules likely to use less efficient per-block data and several different systems processing different parts?

Panserbjoern has done some impressive chunk optimization that leaves it better to use bigger data types (can do away with nibbles) for the performance gain with compression limiting the memory footprint. So bit-level per-block data might be out of fashion either way