กราฟใน Bubble-Shooter

การใช้งานอัลกอริธึมกราฟอย่างง่ายใน Bubble Shooter

การแนะนำ

Bubble Shooter เป็นเกมคลาสสิกที่ผู้เล่นจะต้องยิงฟองหลากสีในสนามที่เต็มไปด้วยฟองอื่นๆ เป้าหมายคือกำจัดฟองอากาศทั้งหมดบนสนามโดยการยิงฟองอากาศที่มีสีเดียวกันรวมกัน กฎพื้นฐานได้แก่:

<1> เมื่อผู้เล่นจับคู่ 3 ฟอง ฟองนั้นจะปรากฏขึ้นและนำออกจากกระดาน

<2> เมื่อไม่ได้ติดฟองอากาศใดๆ ออกจากรูท ฟองอากาศนั้นจะกลายเป็น "ลอย" และนำออกจากกระดาน

การใช้กราฟ

เริ่มจากจุดยอดของกราฟของเรา:

Bubble เป็นเพียงคลาสที่รักษาตัวแปรทั้งหมดที่เราต้องการ ก่อนอื่นเราตั้งค่าความลึกเป็น -1 และพบว่าเป็นเท็จ จากนั้นเราจะเพิ่ม Bubbles ที่อยู่ติดกันทั้งหมดไปที่รายการขอบ

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