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

wonder

Expert
Licensed User
Longtime User
[SOLVED] See attached project files.
B4X:
'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?

Capture.PNG

Expected result
 

Attachments

  • floodfill.jar
    318.1 KB · Views: 362
  • floodfill.zip
    2.7 KB · Views: 350
Last edited:

ilan

Expert
Licensed User
Longtime User
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

Expert
Licensed User
Longtime User
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
 

Cableguy

Expert
Licensed User
Longtime User
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

Expert
Licensed User
Longtime User
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...
 

wonder

Expert
Licensed User
Longtime User
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?

Capture2.png
 
Last edited:

wonder

Expert
Licensed User
Longtime User
Last edited:
Top