Detecting groups without recursion or stacks/queue

问题:

I was trying out this algorithm for detecting groups of like pieces on a grid. It is a simple game demo that drops pieces randomly on a 12x10 grid and after each piece drop checks the grid for any groups that are three or more adjacent pieces. I am using the following code in an attempt to do this without flood fill, recursion, or stacks/queues. It seems to almost work, but will destroy squares that are not of the same type sometimes, or leave squares that should be destroyed. So, is the logic of the algorithm wrong, or is the implementation/coding wrong?

EDIT: I think this works now. See comment

public void checkMatches(int type)
{
    /*
     * Step 1: Iterate through each square to see how many of the same type are adjacent to it
     */
    for (int i = 0; i < PIECES_WIDE; i++)
    {
        for (int j = 0; j < PIECES_TALL; j++)
        {
            if (grid[i][j].getType() == type) // EDITED IN CODE. Make sure current square is of correct type
            {
                if (i > 0) // Bounds checking
                    if (grid[i - 1][j].getType() == type)
                        grid[i][j].setAdj(grid[i][j].getAdj() + 1);
                if (i < PIECES_WIDE - 1) // Bounds checking
                    if (grid[i + 1][j].getType() == type)
                        grid[i][j].setAdj(grid[i][j].getAdj() + 1);
                if (j > 0) // Bounds checking
                    if (grid[i][j - 1].getType() == type)
                        grid[i][j].setAdj(grid[i][j].getAdj() + 1);
                if (j < PIECES_TALL - 1) // Bounds checking
                    if (grid[i][j + 1].getType() == type)
                        grid[i][j].setAdj(grid[i][j].getAdj() + 1);
            }
        }
    }

    /*
     * Step 2: If there are 2 or more adjacent squares with the same type then it is part of a blob and to be destroyed
     */
    for (int i = 0; i < PIECES_WIDE; i++)
    {
        for (int j = 0; j < PIECES_TALL; j++)
        {
            if (grid[i][j].getAdj() >= 2)
                grid[i][j].setDestroy(true);
        }
    }

    /*
     * Step 3: If there is only 1 adjacent, then check to see if any adjacent squares have been marked to be destroyed (part
     * of a group). If so, set these to be destroyed as well.
     */
    for (int i = 0; i < PIECES_WIDE; i++)
    {
        for (int j = 0; j < PIECES_TALL; j++)
        {
            if (grid[i][j].getAdj() == 1)
            {
                if (i > 0) // Bounds checking
                    if (grid[i - 1][j].isDestroy() == true)
                    {
                        grid[i][j].setDestroy(true);
                        break;
                    }
                if (i < PIECES_WIDE - 1) // Bounds checking
                    if (grid[i + 1][j].isDestroy() == true)
                    {
                        grid[i][j].setDestroy(true);
                        break;
                    }
                if (j > 0) // Bounds checking
                    if (grid[i][j - 1].isDestroy() == true)
                    {
                        grid[i][j].setDestroy(true);
                        break;
                    }
                if (j < PIECES_TALL - 1) // Bounds checking
                    if (grid[i][j + 1].isDestroy() == true)
                    {
                        grid[i][j].setDestroy(true);
                        break;
                    }
            }
        }
    }

    /*
     * Step 4: Iterate through grid and destroy the squares marked for destruction and reset all squares to 0 adjacent and
     * destroy flag to false
     */
    for (int i = 0; i < PIECES_WIDE; i++)
    {
        for (int j = 0; j < PIECES_TALL; j++)
        {
            if (grid[i][j].isDestroy())
                destroyPiece(grid[i][j]);

            grid[i][j].setAdj(0);
            grid[i][j].setDestroy(false);
        }
    }
}

回答1:

You can find groups faster when you sort the items into a bucket. You can use a spatial index for example a kd-tree.