泡泡射击游戏

图算法在Bubble Shooter中的简单实现

介绍

Bubble Shooter 是一款经典游戏，玩家在充满其他泡泡的场地中射击彩色泡泡。目标是通过射击具有相同颜色的气泡组合来消除场上的所有气泡。基本规则包括：

<1>当玩家匹配3个泡泡时，泡泡就会弹出并从棋盘上移走。

<2> 当任何气泡从根部脱离时，它就变成“漂浮物”并从板上去除。

图实现

让我们从图表的顶点开始：

Bubble 只是一个维护我们需要的所有变量的类。我们首先将深度设置为-1并将discovery设置为false，然后将所有相邻的气泡添加到边缘列表中。

 public class Bubble {
    public BubbleColor mBubbleColor ;
    public int mDepth = - 1 ;
    public boolean mDiscover = false ;
    public final ArrayList < Bubble > mEdges = new ArrayList <>( 6 );
    // ...
}

广度优先搜索

为了找到匹配的气泡，我们使用 BFS 来搜索我们的图表。我们从新的气泡玩家镜头开始，它在与其他气泡碰撞后添加到图表中。然后，我们检查深度，如果它大于或等于2（从0开始），我们只需删除那些深度不为-1的气泡。

 private void bfs ( Bubble root , BubbleColor color ) {
    Queue < Bubble > queue = new LinkedList <>();
    root . mDepth = 0 ;
    queue . offer ( root );

    while ( queue . size () > 0 ) {
        Bubble currentBubble = queue . poll ();
        for ( Bubble b : currentBubble . mEdges ) {
            // Unvisited bubble
            if ( b . mDepth == - 1 && b . mBubbleColor == color ) {
                b . mDepth = currentBubble . mDepth + 1 ;
                queue . offer ( b );
            }
        }
    }
}

深度优先搜索

为了找到漂浮物，我们使用 DFS 来搜索我们的图表。

 private void dfs ( Bubble bubble ) {
    bubble . mDiscover = true ;
    for ( Bubble b : bubble . mEdges ) {
        if (! b . mDiscover && b . mBubbleColor != BubbleColor . BLANK ) {
            dfs ( b );
        }
    }
}

首先，我们从第一行的气泡开始作为根。

 private void popFloater () {
    // We start dfs from root
    for ( int i = 0 ; i < mCol ; i ++) {
        Bubble bubble = mBubbleArray [ 0 ][ i ];   // Bubble at row 0
        if ( bubble . mBubbleColor != BubbleColor . BLANK ) {
            // Search from root bubble with dfs
            dfs ( bubble );
        }
    }
    // ...
}