Graph in Bubble Shooterダウンロード - Graph in Bubble Shooterソースコードのダウンロード

Graph in Bubble Shooter

その他のソースコード

ダウンロード

グラフインバブルシューター

バブルシューターにおけるグラフアルゴリズムの簡単な実装

導入

バブルシューターは、プレイヤーが他のバブルでいっぱいのフィールドに色付きのバブルを撃つ古典的なゲームです。同じ色のバブルを組み合わせて発射し、フィールド上のすべてのバブルを消すのが目的です。基本的なルールには次のものが含まれます。

<1> プレイヤーがバブルを 3 つ揃えると、バブルがポップアップしてボードから消えます。

<2> 気泡が根元から剥がれると「浮き」となってボードから取り除かれます。

グラフの実装

グラフの頂点から始めましょう。

Bubble は、必要なすべての変数を維持する単純なクラスです。まず深さを -1 に設定し、discover を 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 );
        }
    }
    // ...
}