Graph in Bubble Shooter - Graph in Bubble Shooter

Graph in Bubble Shooter

Kode sumber lainnya

Unduh

Grafik-dalam-Penembak Gelembung

Implementasi sederhana dari algoritma grafik di Bubble Shooter

Perkenalan

Bubble Shooter adalah permainan klasik di mana pemain menembakkan gelembung berwarna ke lapangan yang penuh dengan gelembung lainnya. Tujuannya adalah menghilangkan semua gelembung di lapangan dengan menembakkan kombinasi gelembung yang memiliki warna sama. Aturan dasarnya antara lain:

<1> Saat pemain mencocokkan 3 gelembung, gelembung tersebut akan muncul dan dikeluarkan dari papan.

<2> Jika ada gelembung yang terlepas dari akarnya, gelembung tersebut menjadi "mengambang" dan dikeluarkan dari papan.

Implementasi Grafik

Mari kita mulai dari titik puncak grafik kita:

Bubble hanyalah sebuah kelas yang mempertahankan semua variabel yang kita butuhkan. Pertama-tama kita atur kedalaman ke -1 dan temukan ke false, lalu kita tambahkan semua Gelembung yang berdekatan ke daftar tepi.

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

Pencarian Luas-Pertama

Untuk menemukan gelembung yang cocok, kami menggunakan BFS untuk mencari grafik kami. Kita mulai dari tembakan pemain gelembung baru, yang ditambahkan ke grafik setelah bertabrakan dengan gelembung lain. Kemudian kita cek kedalamannya, jika lebih besar atau sama dengan 2 (mulai dari 0), kita hilangkan saja kedalaman gelembung tersebut bukan -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 );
            }
        }
    }
}

Pencarian Kedalaman Pertama

Untuk menemukan floaters, kami menggunakan DFS untuk mencari grafik kami.

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

Pertama, kita mulai dari gelembung di baris pertama sebagai root.

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