Graph in Bubble Shooter

График в пузырьковом шутере

Простая реализация графового алгоритма в Bubble Shooter

Введение

Bubble Shooter — классическая игра, в которой игрок стреляет цветными пузырями по полю, полному других пузырей. Цель состоит в том, чтобы уничтожить все пузыри на поле, стреляя в комбинации пузырей одного цвета. Основные правила, в том числе:

<1> Когда игрок сопоставит 3 пузырька, пузырьки всплывут и исчезнут с доски.

<2> Когда любой пузырь отсоединяется от корня, он становится «плавающим» и удаляется с доски.

Реализация графа

Начнем с вершины нашего графа:

Bubble — это просто класс, который поддерживает все необходимые нам переменные. Сначала мы устанавливаем глубину на -1 и обнаруживаем значение 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 );
        }
    }
    // ...
}

Затем мы просто удаляем все необнаруженные пузырьки. (На самом деле, установите его в ПУСТОЕ значение, не обязательно удаляйте его из нашего графика)

Демо

Ссылка

Графовый алгоритм основан на «Введении в алгоритмы» Томаса Х. Кормена, Чарльза Э. Лейзерсона, Рональда Л. Ривеста и Клиффорда Стайна.

Игровой движок основан на книге Рауля Пауталса «Освоение разработки игр для Android».