# Bubble shooter falling algorithm

To complete this question about the same color search algorithm, I would like to know if someone knows which is the best implementation for making other bubbles fall when they are no longer attached. More precisely, how can I detect islands of isolated bubbles.

My data structure is a NxM matrix.

-
+1 great question, welcome to GameDev.SE! – ashes999 Apr 24 '12 at 17:46
@ngryman Have you find a right way to do this? – Hemant Singh Rathore Jan 25 '14 at 18:26
@Hemant Yes. Accepted answer below using a flood fill algorithm. – ngryman Jan 25 '14 at 18:36
Thanks for Reply. But i have implemented DFS for bubble search and i don't have much time so i want to do this with DFS because i am not familiar with flood fill algorithm. – Hemant Singh Rathore Jan 25 '14 at 18:49
gamedev.stackexchange.com/questions/69392/… i am facing above issue – Hemant Singh Rathore Jan 27 '14 at 7:35

Every bubble that isn't floating must have some path going back to a top bubble (are we assuming the side walls aren't "glue"?). Apply a flood fill algorithm for every bubble found in the top row. Doing this for every top bubble is essential because it'll work flawlessly in any case, in particular if there are several columns of bubbles hanging from the top but not touching each other.

Flag all "filled" bubbles for each iteration of the algorithm, and skip any already filled bubbles in the top row to save time.

When all top bubbles are filled, drop the bubbles that haven't been flagged.

-
Thanks! I guess this is the simplest method :) – ngryman Apr 25 '12 at 10:28
Yes walls aren't glue by the way. – ngryman Apr 25 '12 at 10:34
This works perfectly. Thanks! – ngryman Apr 25 '12 at 13:58
No problem. Don't forget to upvote :) – ChrisC Apr 26 '12 at 22:09
Can you provide any example of it? – Hemant Singh Rathore Jan 24 '14 at 19:23

One simple method would be to write a function that starts at a bubble touching the top wall and runs through all it's neighbors (and recursively their neighbors with a method to prevent going to ones that have already been visited) then check to see any that didn't get visited by the function call. Any that didn't aren't attached to anything and therefor should fall.

Another method would be to take into account the fact that any falling bubbles must have been attached to the bubbles that were just removed. Rather than make a function to walk every bubble, have a function walk from a particular bubble and try to reach the top. Preference for going up will make this faster per call, and once you've verified a bubble is connected to the top, all it's neighbors can immediately tell that they are as well. If you run out of bubbles to try and you haven't reached the top then you (and all the bubbles you ran through) need to fall as they are no longer attached to the top.

-
Thanks! I like method 1 (similar to @CCRicers's one), I didnt' even thought about it -_- – ngryman Apr 25 '12 at 10:26
Method 1 is the ... ONE :) – ngryman Apr 25 '12 at 13:59
@Lunin i have got an array of unvisited nodes but i am not able to verify which bubble is connected to the top. – Hemant Singh Rathore Jan 27 '14 at 7:23

Search the non-ceiling edges for non-bubbles, and then check for non-bubble paths between these nodes.

Example:

``````------------
005163215101
205143122500
100064131001
215061356132
``````

In this case, there is a path from the top-left corner (non-bubble touching the non-ceiling left wall) to the 4th spot on the bottom edge consisting entirely of non-bubbles. This means that everything along the edge between them (down the left side, across the bottom) is disconnected and should fall (along with everything attached to those). Simply grab the first bubble along the outer page (the 2 at the start of the second row), and drop it and every bubble connected to it.

There is no path from any of the outer non-bubbles to the non-bubble on the right edge, so we don't drop anything over there.

-