Graph in Bubble Shooter下載 - Graph in Bubble Shooter原始碼下載

Graph in Bubble Shooter

其他源碼

下載

泡泡射擊遊戲

圖算法在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 );
        }
    }
    // ...
}