Bubble Shooter es un juego clásico en el que el jugador dispara burbujas de colores en un campo lleno de otras burbujas. El objetivo es eliminar todas las burbujas del campo disparando combinaciones de burbujas que tengan el mismo color. Las reglas básicas incluyen:
<1> Cuando el jugador une 3 burbujas, las burbujas aparecerán y se eliminarán del tablero.
<2> Cuando cualquier burbuja se desprende de la raíz, se convierte en "flotadora" y se elimina del tablero.
Partamos del vértice de nuestro gráfico:
La Burbuja es simplemente una clase que mantiene toda la variable que necesitamos. Primero establecemos la profundidad en -1 y descubrimos en falso, luego agregamos todas las burbujas adyacentes a la lista de bordes.
public class Bubble {
public BubbleColor mBubbleColor ;
public int mDepth = - 1 ;
public boolean mDiscover = false ;
public final ArrayList < Bubble > mEdges = new ArrayList <>( 6 );
// ...
}Para encontrar burbujas coincidentes, usamos BFS para buscar en nuestro gráfico. Partimos del nuevo disparo del jugador de burbujas, que se agrega al gráfico después de chocar con otras burbujas. Luego, verificamos la profundidad, si es mayor o igual a 2 (comenzando desde 0), simplemente eliminamos aquellas burbujas que la profundidad no es -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 );
}
}
}
}Para encontrar flotadores, usamos DFS para buscar en nuestro gráfico.
private void dfs ( Bubble bubble ) {
bubble . mDiscover = true ;
for ( Bubble b : bubble . mEdges ) {
if (! b . mDiscover && b . mBubbleColor != BubbleColor . BLANK ) {
dfs ( b );
}
}
}Primero, comenzamos desde la burbuja de la primera fila como raíz.
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 );
}
}
// ...
}Luego, simplemente retiramos toda la burbuja que no se descubre. (En realidad, configúrelo en BLANCO, no necesariamente lo elimine de nuestro gráfico)
Algoritmo gráfico basado en "Introducción a los algoritmos" de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein
Motor de juego basado en "Mastering Android Game Development" de Raúl Pautals
