Fluid physics

[caelunshun]

Implement moving of water and lava. Waterlogged blocks should also be handled.

This also includes creation of cobblestone/stone/obsidian when lava and water interact.

[Defman]

As an introduction to the project, I would like to implement water physics. I have a few thoughts on how to go about it and would like some feedback.

• First flowing fluid scan in a 5 block radius to find any air block on a lower y level to try to form a waterfall; I have implemented this scanning as a BFS.
• Next placing water blocks with a higher level (source block has a level of 0) around the source at the position which reduces the manhattan distance to the air block on a lower y level.

However, this scanning would be repeated on every fluid spread and a lot of the same blocks would be scanned. I don't know if there's any way to avoid this since fluid spread is delayed and does not happen instantaneously.

When a water block is placed, a new entity is added to the world with a Fluid tag, Position and counter component. A system then query and checks if the counter has been reached and fluid phystics for the block is processed and the entity is removed from the world.

Attached is BFS which locates the nearest air block on a lower y level.

fn bfs(state: &State, start: BlockPosition) -> Vec<BlockPosition> {
    use std::collections::{VecDeque, HashSet};

    let mut visisted: HashSet<BlockPosition> = HashSet::new();
    let mut queue: VecDeque<BlockPosition> = VecDeque::new();

    let mut depth = 0;
    let mut until_next_depth = 1;
    let mut blocks_in_next_depth = 0;

    let mut drain: Vec<BlockPosition> = Vec::new();

    queue.push_back(start);

    while let Some(pos) = queue.pop_front() {
        // Track visited blocks
        if visisted.contains(&pos) {
            continue;
        }
        visisted.insert(pos);
        
        // If the block below is air, we have reached the depth which contains the first airblock.
        if let Some(Block::Air) = state.block_at(pos + DOWN) {
            drain.push(pos + DOWN);
        }

        // Add all air surrounding air blocks to the queue
        for dir in PLANE {
            if let Some(Block::Air) = state.block_at(pos + *dir) {
                blocks_in_next_depth += 1;
                queue.push_back(pos + *dir);
            }
        }

        until_next_depth -= 1;
        // When until next depth reaches zero we have checked all blocks at this depth 
        if until_next_depth == 0 {
            // If the drain is not empty we should break since we do not want to go deeper
            if !drain.is_empty() {
                break;
            }
            depth += 1;

            // We have reached the max depth
            if depth >= 5 {
                break;
            }
            until_next_depth = blocks_in_next_depth;
            blocks_in_next_depth = 0;
        }
    }
    drain
}

[caelunshun]

@Defman thanks! A few things:

• To optimize the algorithm, a cache of local BFS results could be kept shared between fluid entities sourced from the same block. When the source block is placed, an Arc<FluidCache> component could be added to its entity, and upon spread, the component would be cloned and added to the new blocks' respective fluid entities.
• Fluid entities should be created both when a block is placed and when a block adjacent to it is updated; this way, we can account for things like channels being dug out of a lake.
• There should probably be a way to determine the speed a fluid flows at: lava is slower than water. To allow for modding in the future, this should be done in data-based way—e.g. using a component on the fluid entity.
• Instead of Position, BlockPosition should probably be used for fluid entities, so that we can easily query for the block at that position. I'm not sure if you're already doing this—just want to leave it here.
• Also, is there a plan to handle waterlogged blocks? I'm not sure of the exact mechanics, but I might have to extend the block generator to generate is_waterlogged functions to make this easier.

Feel free to contact me with any questions!

[Defman]

• Currently, I have no plan to handle waterlogged. I wanted to get started with some simple stuff to get into the project.
• I thought about caching the result of the BFS Arc<FluidCache> however the world could be modified in the meantime. That would require some way to invalidating the cache which would most likely add more overhead than just recalculating the BFS.
• Currently, I have a component added to the entity which stores a tick value. When this tick value is equal or greater to the current tick the water spreads. .with_component(Age { ticks: tick.0 + 5 }). The name Age is not very descriptive and bad
• I'll update the BlockUpdateEvent to add entities for adjacent water blocks as well.
• I'm using BlockPostion not Position, I might add a new enum call Face with Nort, East.... and implement Add between BlockPostion and Face. Since I do not know how the compiler optimizes addition of to Positions where 2 of the variables are 0.

[Defman]

One optimization that is possible is to have a map that maps from block position to nearest drain(air block on lower y level). This map is invalidated every tick and will only aid water updates doing that tick and may only speed up the BFS. That is if two water source blocks are placed near each other and are spreading at the same tick it will only calculate the overlapped area once instead of twice.

All that said, I don't think it will improve performance at all due to the max depth being 5 and a total of 25 blocks will ever be scanned.

[Defman]

Terminology:

1. Weak block: a block which water can override/destroy
2. Drain: nearest weak blocks which are on a lower y level and within 5 blocks range.
3. Flowable block: a fluid block which liquid level is low enough such that it is still able to flow.

Algorithm

1. On block update, schedule flow update for itself and all surrounding flowable blocks.
2. When the schedule is triggered use BFS to find all drains.
3. If no drains exist to try to spread water on all faces. else try to spread water on all faces which decrease the manhattan distance to any drain.
4. If there's a weak block below, spread.

I also have to allow drains to be located through other liquids, I'm not sure how Minecraft fluid logic works in that regard.

Waterlogged blocks, luckily the only block which water can flow to and become waterlogged is item frame, which is not a block but an item frame. All other waterlogged blocks have to be a source.

[Defman]

Furthermore, all fluid entities should be saved on server shutdown such that water does not frezz and stops flowing.