Graph in Bubble Shooter - Graph in Bubble Shooter

Graph in Bubble Shooter

شفرة المصدر الأخرى

تنزيل

الرسم البياني في فقاعة مطلق النار

تطبيق بسيط لخوارزمية الرسم البياني في Bubble Shooter

مقدمة

Bubble Shooter هي لعبة كلاسيكية حيث يقوم اللاعب بإطلاق النار على فقاعة ملونة في حقل مليء بالفقاعات الأخرى. الهدف هو القضاء على جميع الفقاعات الموجودة في الملعب من خلال إطلاق مجموعات من الفقاعات التي لها نفس اللون. القواعد الأساسية بما في ذلك:

<1> عندما يقوم اللاعب بمطابقة 3 فقاعات، ستظهر الفقاعات ويتم إزالتها من اللوحة.

<2> عندما يتم فصل أي فقاعة من الجذر، تصبح "عائمة" ويتم إزالتها من اللوحة.

تنفيذ الرسم البياني

لنبدأ من قمة الرسم البياني لدينا:

إن الفقاعة هي ببساطة فئة تحافظ على كل ما نحتاجه من متغيرات. قمنا أولاً بتعيين العمق على -1 والاكتشاف على خطأ، ثم نضيف جميع الفقاعات المجاورة إلى قائمة الحواف.

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