Grid based puzzle board game block removal algorithm

Question

Grid http://www.imagechicken.com/uploads/1264550987064245200.png

I have a "samegame" grid represented by a 1D array of integers. 0 to 63 to represent an 8x8 grid.

the rules are that same coloured blocks of two or more can be removed by clicking on them. blocks then slide down from above. if a column is empty columns other columns move in from the sides.

when someone clicks on the green blocks in the bottom row the columns should slide in from the sides. columns to the left of the black line slide right and on the right of the black line slide left. so in this case only the two rightmost columns should slide from the right to the black line after removing the green blocks.

The problem i am having is in designing a suitable algorihm to do the collapsing after the removal.

my current approach is to test each column from left to right to see if it is empty. if it is empty then i slide whatever column is to the left (if left of the black line) or to the right (if to the right of the black line) over the blank column and repeat this in the direct i am sliding from.

the problem is this approach fails when two columns are empty as the second empty column slides over the first and then the routine carrys on from the next column rather than shuffling everything across.

I'm wondering if there is an easier way than the approach i am taking?

Public Sub CollapseEmptyColumns()

        For x = 0 + 1 To 7 - 1
            Dim EmptyColumn As Boolean = True
            For y = 0 To 7

                Dim BlockIndex As Integer = y * 8 + x
                If Blocks(BlockIndex).BlockColor <> eBlockColor.None Then
                    EmptyColumn = False
                    Exit For
                End If

            Next

            If EmptyColumn = True Then

                If x < 4 Then ' less than 4 then slide from left

                    SlideColumns(x - 1, 0, 1)

                Else ' greater or equal to 4 slide from right

                    SlideColumns(x + 1, 7, -1)

                End If


            End If

        Next

    End Sub

    Private Sub SlideColumns(ByVal First As Integer, ByVal Last As Integer, ByVal Direction As Integer)

        For x = First To Last Step -Direction

            For y = 0 To 7

                Blocks(y * 8 + (x + Direction)).BlockColor = Blocks(y * 8 + x).BlockColor
                Blocks(y * 8 + x).BlockColor = eBlockColor.None

            Next

        Next

    End Sub

Guffa Guffa · Accepted Answer · 2010-01-26T23:49:09

Check the first three columns from left to right, then check the last three column from right to left:

Private Function EmptyColumn(x As Integer) As Boolean
  For y As Integer = 0 To 7
    If Blocks(y * 8 + x).BlockColor <> eBlockColor.None Then
      Return False
    End If
  Next
  Return True
End Function

Public Sub CollapseEmptyColumns()
  For x = 1 To 3
    If EmptyColumn(x) Then
      SlideColumns(x - 1, 0, 1)
    End If
  Next
  For x = 6 to 4 Step -1
    If EmptyColumn(x) Then
      SlideColumns(x + 1, 7, -1)
    End If
  Next
End Sub

Grid based puzzle board game block removal algorithm

1 Answers