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.

• @ngryman Have you find a right way to do this? Jan 25, 2014 at 18:26
• 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. Jan 25, 2014 at 18:49
• gamedev.stackexchange.com/questions/69392/… i am facing above issue Jan 27, 2014 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.

• Yes walls aren't glue by the way. Apr 25, 2012 at 10:34
• No problem. Don't forget to upvote :) Apr 26, 2012 at 22:09
• Can you provide any example of it? Jan 24, 2014 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 -_- Apr 25, 2012 at 10:26
• Method 1 is the ... ONE :) Apr 25, 2012 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. Jan 27, 2014 at 7:23
• gamedev.stackexchange.com/questions/69392/… Jan 27, 2014 at 7:33

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.