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.
Answer
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.
No comments:
Post a Comment