Fill [RESOLVED]

[Nove]

I'm working on a function to work as a fill, this is for a tile editor but it has the same principles you would use when working with a bitmap. The only solution for creating a fill function that comes to mind is to start at an initial point and from within in the function check and see if the current tile matches up with any corresponding tiles, then once the change has been made, call itself with a new x,y point. This would work great, except I run out of stack space real quick. Does anyone have a workaround for this? Thanks.

[Fox]

You can get around any stack problem by putting the data into a seperate list (because you can step through the list in a loop, thus not needing a recursive function).

[wossname]

How many tiles are we talking about? Call stack overflow normally only occurs with ENORMOUS amounts of data or an unterminated recursive function.

[Nove]

Well, the space was 200x200 and it stopped somewhere around 72,31. It's somewhat of a balloon movement so I don't know how many calls of the function were running at that moment.
Fox, what are you proposing? I don't think I understand.

[Fox]

Pseudo code:

Sub FloodFill( StartX, Start )
    CreateTodoList() 'Empty list that holds the items we have to check
    CreateDoneMap( Width, Height ) 'Bool map storing already processed positions
 
    TodoList.Add( StartX, StartY ) 'Adds first item to list
 
    While( TodoList.Count > 0 ) 'While there is something to do...
        Position = TodoList.RemoveFirst() 'Remove one item (get x and y)
        DoneMap( Pos ) = True 'Mark current position as done
 
        If FreeTile( x, y ) Then 'If current position is free
            FillTile( x, y ) 'Process that tile, eg. fill it
 
            'Add neighbours if they were not already checked
            If Not DoneMap( x, y-1 ) Then: TodoList.Add( x, y-1 )
            If Not DoneMap( x+1, y ) Then: TodoList.Add( x+1, y )
            If Not DoneMap( x, y+1 ) Then: TodoList.Add( x, y+1 )
            If Not DoneMap( x-1, y ) Then: TodoList.Add( x-1, y )
        Endif
    Wend
End Sub

Have fun.

[Fox]

I just felt like writing some sample code out of this ^^'

Public Sub FloodFill(DC As Long, x As Long, y As Long, w As Long, h As Long, Color As Long)
    Dim StartColor As Long
    
    Dim TodoList As New Collection
    Dim DoneMap() As Boolean
    
    Dim TempPos As cPos2D
    Dim NewPos As cPos2D
    
    ReDim DoneMap(w, h)
    StartColor = GetPixel(DC, x, y)
    
    Set TempPos = New cPos2D
    TempPos.x = x
    TempPos.y = y
    TodoList.Add TempPos
    DoneMap(x, y) = True
    
    While TodoList.Count > 0
        Set TempPos = TodoList.Item(1)
        TodoList.Remove 1
        
        If GetPixel(DC, TempPos.x, TempPos.y) = StartColor Then
            SetPixelV DC, TempPos.x, TempPos.y, Color
            
            Set NewPos = New cPos2D
            NewPos.x = TempPos.x: NewPos.y = TempPos.y - 1
            If NewPos.y > -1 Then
                If Not DoneMap(NewPos.x, NewPos.y) Then
                    TodoList.Add NewPos
                    DoneMap(NewPos.x, NewPos.y) = True
                End If
            End If
            
            Set NewPos = New cPos2D
            NewPos.x = TempPos.x: NewPos.y = TempPos.y + 1
            If NewPos.y < h Then
                If Not DoneMap(NewPos.x, NewPos.y) Then
                    TodoList.Add NewPos
                    DoneMap(NewPos.x, NewPos.y) = True
                End If
            End If
            
            Set NewPos = New cPos2D
            NewPos.x = TempPos.x - 1: NewPos.y = TempPos.y
            If NewPos.x > -1 Then
                If Not DoneMap(NewPos.x, NewPos.y) Then
                    TodoList.Add NewPos
                    DoneMap(NewPos.x, NewPos.y) = True
                End If
            End If
            
            Set NewPos = New cPos2D
            NewPos.x = TempPos.x + 1: NewPos.y = TempPos.y
            If NewPos.x < w Then
                If Not DoneMap(NewPos.x, NewPos.y) Then
                    TodoList.Add NewPos
                    DoneMap(NewPos.x, NewPos.y) = True
                End If
            End If
        End If
    Wend
End Sub

Usage:

FloodFill Picture1.hdc, 10, 10, Picture1.ScaleWidth, Picture1.ScaleHeight, RGB(255, 0, 255)

To make life easier I used the Collection class, unfortunately it only accepts objects so you have to add a new object module to the project, name it cPos2D and add the following lines to it:

Public x As Long
    Public y As Long

And don't forget the API declares in the module of your choide:

    Public Declare Function GetPixel Lib "gdi32" (ByVal hdc As Long, ByVal x As Long, ByVal y As Long) As Long
    Public Declare Function SetPixelV Lib "gdi32" (ByVal hdc As Long, ByVal x As Long, ByVal y As Long, ByVal crColor As Long) As Long

Yeah it's dumb but it shows that the code works

[edit] Speedfixes... [/edit]

[Nove]

Ok, I see now, incredibly helpful, thank you very much. Thanks for all the help thus far

[Fox]

If you're going to implement the technique please pay attention to the example code. But as long as you got the point it's up to you to keep it stable and optimized (eg. the <0,<0 and >w,>h checks are absolutely necessary)

[Nove]

Yes, I probably won't implement the code directly, but you got your point across. Thank you very much.