Graph in Bubble Shooter 다운로드 - Graph in Bubble Shooter 소스 코드 다운로드

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