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.


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.

  • \$\begingroup\$ Yes walls aren't glue by the way. \$\endgroup\$ – ngryman Apr 25 '12 at 10:34
  • \$\begingroup\$ No problem. Don't forget to upvote :) \$\endgroup\$ – ChrisC Apr 26 '12 at 22:09
  • \$\begingroup\$ Can you provide any example of it? \$\endgroup\$ – 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.

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

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



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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.