检测没有递归或堆栈/队列的组 [英] Detecting groups without recursion or stacks/queues

问题描述

我正在尝试使用这种算法来检测网格上的相似组件。这是一个简单的游戏演示，可以在12x10网格上随机丢弃碎片，并在每个碎片检查网格后检查三个或更多相邻碎片的任何组。我正在使用以下代码尝试在没有泛洪填充，递归或堆栈/队列的情况下执行此操作。它似乎几乎可以工作，但有时会破坏不同类型的方块，或者留下应该销毁的方块。那么，算法的逻辑是错误的，还是实现/编码错了？

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?

编辑：我认为这现在有效。请参阅注释

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);
        }
    }
}

推荐答案

将项目排序到存储桶时，可以更快地找到组。您可以使用空间索引，例如kd-tree。

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

这篇关于检测没有递归或堆栈/队列的组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！