Games [SOLVED] Using a FloodFill Algorithm For Fluid Drop Simulation

[wonder]

[SOLVED] See attached project files.

'Static code module
Private Sub Process_Globals
    Private fx    As JFX
    Private stack As List
End Sub

Public Sub Initialize
    stack.Initialize
End Sub

Public Sub Fill(value As Int, x As Int, y As Int, grid As Grid)
    Dim top = y As Int
    Dim matrix(,) = grid.matrix As Int
    If value = matrix(x, y) Then Return
    '--------------------------------------------------------------
    stack.Clear
    Dim x1 As Int
    Dim spanAbove, spanBelow As Boolean
    '--------------------------------------------------------------
    stack.Add(Array As Int(x, y))
    '--------------------------------------------------------------
    Dim p() As Int
    Do While (stack.Size > 0)
        p = stack.Get(stack.Size - 1)
        x = p(0) : y = p(1) : stack.RemoveAt(stack.Size - 1)
        '----------------------------------------------------------
        x1 = x : Do While (x1 >= 0 And matrix(x1, y) == 0) : x1 = x1 - 1 : Loop
        '----------------------------------------------------------
        x1 = x1 + 1 : spanAbove = False : spanBelow = False
        '----------------------------------------------------------
        Do While (x1 < grid.sizeX And matrix(x1, y) = 0)
            matrix(x1, y) = value
            '------------------------------------------------------
            If (spanAbove = False And y > top And matrix(x1, y - 1) = 0) Then
                spanAbove = True : stack.Add(Array As Int(x1, y - 1))
            Else If (spanAbove = True And y > top And matrix(x1, y - 1) > 0) Then
                spanAbove = False
            End If
            '------------------------------------------------------
            If (spanBelow = False And y < grid.sizeY - 1 And matrix(x1, y + 1) = 0) Then
                spanBelow = True : stack.Add(Array As Int(x1, y + 1))
            Else If (spanBelow And y < grid.sizeY - 1 And matrix(x1, y + 1) > 0) Then
                spanBelow = False
            End If
            '------------------------------------------------------
            x1 = x1 + 1
        Loop
    Loop
End Sub

Public Sub Flood(value As Int, x As Int, y As Int, grid As Grid)
    Dim matrix(,) = grid.matrix As Int
    If value = matrix(x, y) Then Return
    '--------------------------------------------------------------
    stack.Clear
    Dim x1 As Int
    Dim spanAbove, spanBelow As Boolean
    '--------------------------------------------------------------
    stack.Add(Array As Int(x, y))
    '--------------------------------------------------------------
    Dim p() As Int
    Do While (stack.Size > 0)
        p = stack.Get(stack.Size - 1)
        x = p(0) : y = p(1) : stack.RemoveAt(stack.Size - 1)
        '----------------------------------------------------------
        x1 = x : Do While (x1 >= 0 And matrix(x1, y) == 0) : x1 = x1 - 1 : Loop
        '----------------------------------------------------------
        x1 = x1 + 1 : spanAbove = False : spanBelow = False
        '----------------------------------------------------------
        Do While (x1 < grid.sizeX And matrix(x1, y) = 0)
            matrix(x1, y) = value
            '------------------------------------------------------
            If (spanAbove = False And y > 0 And matrix(x1, y - 1) = 0) Then
                spanAbove = True : stack.Add(Array As Int(x1, y - 1))
            Else If (spanAbove = True And y > 0 And matrix(x1, y - 1) > 0) Then
                spanAbove = False
            End If
            '------------------------------------------------------
            If (spanBelow = False And y < grid.sizeY - 1 And matrix(x1, y + 1) = 0) Then
                spanBelow = True : stack.Add(Array As Int(x1, y + 1))
            Else If (spanBelow And y < grid.sizeY - 1 And matrix(x1, y + 1) > 0) Then
                spanBelow = False
            End If
            '------------------------------------------------------
            x1 = x1 + 1
        Loop
    Loop
End Sub

PS: Here's the difference between Flood() and Fill(): https://www.diffchecker.com/OO65W6Jm

Initial post:

This question is aimed at @Informatix or anyone who's able to help.

Given a true/false matrix, as shown below, where black is true and transparent is false, I believe I could use a path finding algorithm for simulating "filling the gaps with water", given the entry point shown in red.

The question is, how can we achieve this?

Expected result

 

[ilan]

Create a type water

Water should have a variable called side
This will be a random int 0/1

When u create a water block he start fall
And the behavior should be

Water looks always first under it if block is air if true water goes to this block if not water tries to go to side that u choosed as random if success water try again go down until down is ground and side is or water or wall

 

[Cableguy]

I would say keep a dinamic array equal to thé existint water blocks, an then check each adjacent block to see if it's true of false, then fill the need/found space, refresh the array with the new blocks, deleting those that are already "not expandable", and repeat the true/false check.

P.S. my user title says expert, but I really am a noob leerking this forum for over 12years

 

[inakigarm]

Have so fun with this type of questions !! Surely I'll not code them but it forces to squeeze my brain.

I've find a general answer in wiki (https://en.wikipedia.org/wiki/Flood_fill), maybe too general but it has several anims that makes it very instructive

EDIT: with code http://lodev.org/cgtutor/floodfill.html

 

[wonder]

So, what I need is a modified version of flood fill which accounts for gravity (or at least, only goes downward).

 

[Cableguy]

So, what I need is a modified version of flood fill which accounts for gravity (or at least, only goes downward).

I would say it depends on how realistic you want your water fill to be...
From the given links, they all start the filling sideways, in the case of water, you need to take into account gravity and fill speed..
As @ilan proposed, you need to first come down as much as possible going around obstacles, filling sideways, and keep checking if going down is still possible, like in a staircase case...
Also, realistically, the first horizontal layers that are not absolute bottom should fill at slightly different rates, taking into account the space to fill.

A lot of variables to take care of!

 

[wonder]

it depends on how realistic you want your water fill to be

I'm not looking into having any kind of animation, so I don't care how the fill is executed, as long as I get a proper end-result (as seen in the first post).

As for now, I have a rudimentary (buggy) implementation which appears to be similar in principle, to @ilan's suggestion, but I would like to tweak, instead, my maze-solver lib (@Informatix's algorithm) to do this, I just don't know how. It should be possible...

 

[Informatix]

I suggest also to use a flood fill algorithm. You don't need to manage gravity, just set properly the bounds of your algorithm. If y=0 is the sea level and y=-15 the sea bottom, then the upper bound is 0 and the lower bound -15.

 

[wonder]

How about "valleys" below sea-level (think The Netherlands)? Those should not be filled...

EDIT: Okay, I think I start to see the point, maybe the flood-fill algo needs no modification at all... right?

 

[Informatix]

How about "valleys" below sea-level (think The Netherlands)? Those should not be filled...

EDIT: Okay, I think I start to see the point, maybe the flood-fill algo needs no modification at all... right?

View attachment 49875

This valley won't be filled by the algorithm if you don't allow him to go above the sea level (above the red square).

 

[wonder]

Perfect!! I rewrite the algo and share with the community once done.

 

[wonder]

code http://lodev.org/cgtutor/floodfill.html

I got it to work!!! Thank you so much!
Solution uploaded to the first post.

 

[ilan]

very nice but i am afraid your code does not take in account the Law of connected vessels.

https://en.wikipedia.org/wiki/Communicating_vessels

but i think with a little bit coding you can make it perfect

 

[wonder]

Indeed, it is not a full simulation, but for my current needs, it does the job...