Flood fill for the game Go in Visual Basic

Question

I am an amateur in Visual Basic. I am attempting to recreate the game of Go, and I have created the board and am able to place stones on the intersections of the grid.

I now want to start capturing stones which are surrounded. I have looked online and found that flood fill is the best way to go about this. However, I have looked online for days, and I can't find anything that I can use, or manipulate to create this. I do not understand any other programming language, so I cannot use bits of code from Java, etc. And the bits of information for Visual Basic I have found do not make much sense to me as I am still a beginner.

I have attempted to start it by myself, starting off small with the situation of "If one stone were to be captured". I have two representations for the board, one is declared as "grid", and the other as "placed_stone".

"Grid" is the actual board where the users click to place their stones. placed_stone is a copy of this board, but I have used "0", "1" and "2" to represent empty, black and white respectively. I am using Windows Forms to recreate this game. This is the segment of code I have written for capturing the stones:

        Private Sub Panel1_Click(sender As Object, e As EventArgs) Handles Panel1.Click
    Dim board As Panel = DirectCast(sender, Panel)

    ' Figure out where the user clicked: min = 0, max = (gridsize - 1)
    Dim pt As Point = board.PointToClient(Cursor.Position)
    Dim colWidth As Integer = (1 / (GridSize + 1)) * board.Size.Width
    Dim rowHeight As Integer = (1 / (GridSize + 1)) * board.Size.Height
    Dim gridPosition As New Point(Math.Min(Math.Max((pt.X / colWidth) - 1, 0), GridSize - 1), Math.Min(Math.Max((pt.Y / rowHeight) - 1, 0), GridSize - 1))
    Dim newcoordsx As Integer
    Dim newcoordsy As Integer

    ' Now do something with gridPosition:
    If Not Grid(gridPosition.X)(gridPosition.Y).HasValue Then 'If gird(x,y) is empty
        illegalmovelbl.Hide() ' Hides the "Illegal Move" Label
        If cp = True Then ' If current player is Black

This is the part where I got stuck and realised that the coding for every situation will take too long. I managed to write up the code for one situation:

            newcoordsx = gridPosition.X + 1
            If placed_stone(newcoordsx, gridPosition.Y) = 2 Then
                newcoordsy = gridPosition.Y + 1
                If placed_stone(newcoordsx, newcoordsy) = 1 Then
                    newcoordsy = gridPosition.Y - 1
                    If placed_stone(newcoordsx, newcoordsy) = 1 Then
                        newcoordsx = gridPosition.X + 2
                        If placed_stone(newcoordsx, gridPosition.Y) = 1 Then
                            newcoordsx = gridPosition.X + 1
                            Grid(gridPosition.X)(gridPosition.Y) = True 'Place a black stone at Grid(x,y)
                            Grid(newcoordsx)(gridPosition.Y) = Nothing
                            placed_stone(newcoordsx, gridPosition.Y) = 0
                            pass = False
                            cp = False
                            passbtn.BackColor = Color.White 'The passbutton changes colour to white
                            passbtn.ForeColor = Color.Black 'The passbutton font changes colour to black
                        End If
                    End If
                End If
            End If

            'Grid(gridPosition.X)(gridPosition.Y) = True ' Place a black stone at Grid(x,y)
            'placed_stone(gridPosition.X, gridPosition.Y) = 1
            'pass = False
            'cp = False
            'passbtn.BackColor = Color.White ' The passbutton changes colour to white
            'passbtn.ForeColor = Color.Black ' The passbutton font changes colour to black

        ElseIf cp = False Then ' If current player is White
            Grid(gridPosition.X)(gridPosition.Y) = False ' Place a white stone at Grid(x,y)
            placed_stone(gridPosition.X, gridPosition.Y) = 2
            pass = False
            cp = True
            passbtn.BackColor = Color.Black ' The passbutton changes colour to black
            passbtn.ForeColor = Color.White ' The passbutton font changes colour to white
        End If

    ElseIf Grid(gridPosition.X)(gridPosition.Y).HasValue Then ' If gird(x,y) isn't empty
        illegalmovelbl.Show() ' Shows the "Illegal Move" Label
        MsgBox("Place your stone in a vacant point") ' Displays error message
    End If

    board.Invalidate() ' Force the board to redraw itself
End Sub

I have tried to use Wikipedia's algorithm on flood fill, and I understand the logic of how it works, but I just don't know how to program it in Visual Basic.

 Flood-fill (node, target-color, replacement-color):
 1. If target-color is equal to replacement-color, return.
 2. If the color of node is not equal to target-color, return.
 3. Set the color of node to replacement-color.
 4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
 5. Return.

Of course, in Go, instead of colouring in the area, you have to remove the stones when capturing, and you don't start the flood fill from the stone you just placed to capture, you start from the closest stone you wish to capture.

Can you please explain how to use flood fill in Visual Basic in an easy way and how to implement it to this game of Go?

If anyone would like to look at the whole code, please let me know. I would appreciate any suggestions!

Answer 1

I'm not familiar with the rules/game-play of the game Go, so I'm not sure exactly what you are attempting to accomplish, but if you believe that a flood-fill type of algorithm is what you need, then I can at least offer some advice in how you could do that. The primary thing that your code needs is to be broken down into more granular methods. What are the steps that you are attempting to perform when the panel is clicked? Surely it's not just one thing. There are many different things going on--each of which could be performed by a separate dedicated method. For instance, if you had a method like this:

Private Function GetGridPosition(board As Panel, cursorPosition As Point) As Point
    Dim pt As Point = board.PointToClient(Cursor.Position)
    Dim colWidth As Integer = (1 / (GridSize + 1)) * board.Size.Width
    Dim rowHeight As Integer = (1 / (GridSize + 1)) * board.Size.Height
    Return New Point(Math.Min(Math.Max((pt.X / colWidth) - 1, 0), GridSize - 1), Math.Min(Math.Max((pt.Y / rowHeight) - 1, 0), GridSize - 1))        
End Function

Then, in the Panel1_Click event handler, you could simplify the beginning of the code considerably, like this:

Private Sub Panel1_Click(sender As Object, e As EventArgs) Handles Panel1.Click
    Dim board As Panel = DirectCast(sender, Panel)
    Dim gridPosition As Point = GetGridPosition(board, Cursor.Position)
' ...

Sure, that makes the code more organized and easier to read, but that doesn't get you any closer to a flood fill algorithm, right? Well, yes, that's mostly true, but organization and readability are worthy goals in their own right, so lets continue anyway... The next step we need to perform is to make the player's move, and then, if the move was successful, we need to switch to the other player. So, let's first create the method to switch players:

Private Sub SwitchPlayer()
    pass = False
    cp = Not cp
    passbtn.BackColor = GetPlayerForeColor(cp)
    passbtn.ForeColor = GetPlayerBackColor(cp)
End Sub

Private Function GetPlayerForeColor(player as Boolean) As Color
    If player Then
        Return Color.White
    Else
        Return Color.Black
    End If 
End Function

Private Function GetPlayerBackColor(player as Boolean) As Color
    If player Then
        Return Color.Black
    Else
        Return Color.White
    End If 
End Function

You'll notice that I snuck (Chrome auto-spell tells me that isn't a word, but my American upbringing begs to differ) a couple other methods in there while I was at it. I'm sure their purpose is obvious. But stop right there. It's obvious? You'll notice that the comments are gone, yet the meaning of the code is still obvious. That's what we mean by self-documenting code. Comments are great when they're necessary, but it's even better when they aren't necessary at all.

So, pretend for now we have a method like this:

Private Function MakeMove(gridPosition As Grid, player As Boolean) As Boolean
    ' return true if the move was successful
End Function

Then the whole Panel1_Click event handler could look like this:

Private Sub Panel1_Click(sender As Object, e As EventArgs) Handles Panel1.Click
    Dim board As Panel = DirectCast(sender, Panel)
    Dim gridPosition As Point = GetGridPosition(board, Cursor.Position)
    If MakeMove(gridPosition, cp) Then
        SwitchPlayer()
    Else
        ShowIllegalMoveMessage()
    End If
End Sub

Private Sub ShowIllegalMoveMessage()
    illegalmovelbl.Show() 'Shows the "Illegal Move" Label
    MsgBox("Place your stone in a vacant point") 'Displays error message
End Sub

Ok, so now we're getting to the meat of it. So, what are the steps that need to be taken when a move is being made? Well, I don't know, because I don't know the game. I leave that exercise up to you, but, if your inclinations are correct, and you need some kind of flood fill algorithm, then that probably means that you need some kind of PlaceStone action which can be repeated over and over again, so that should be its own method:

Private Sub PlaceStone(gridPosition As Point, player As Boolean)
    ' Do something
End Sub

Obviously the Do something is the key part of all this, and it's the one part that I can't help you with. But, if it's going to be a flood fill algorithm, I can give you a really big hint. Among all the other stuff it's going to do in there, it's going to be calling PlaceStone again, passing it a different grid position (one of the surrounding positions). So for instance, something like this:

Private Sub PlaceStone(gridPosition As Point, player As Boolean)
    Dim north As Position = GetNorthPosition(gridPosition)
    If Floodable(north, player) Then
        PlaceStone(north, player)
    End If
    ' ...
End Sub

When a method calls itself, like that, we call it recursion. But, until you start splitting your code up into dedicated little methods, each with its own encapsulated task, then you can't really add recursion. So, first get organized, then add recursion.