# Collapsing elements

This topic is 2771 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Im currently working on a "bust a move" style game, but have no idea how to solve the collapsing elements problem.
The gamefield is represented as a simple 2D array, and no color matching rule right now (like in the mentioned game).
The main question, how can i check if a cell (or a groups of cells) is separated from the others?

I made a picture:

Here, i marked the separated cell group that i need to remove.
Is there any general algorithm that can solve this problem?

##### Share on other sites
Perhaps 'flood-fill' is what you're looking for.

##### Share on other sites
The correct problem to look for is connected components labelling: http://en.wikipedia...._(graph_theory)

You can solve it in linear time using any standard graph traversal (ie breadth first/depth first search). However, since it seems like you are updating the graph by incrementally adding elements and removing sets, you may be better off using a union-find data structure to keep track of each component. Here is a link to the relevant material: http://en.wikipedia...._data_structure

The union-find will give you nearly constant time cost for locating and updating connected components, and it is also pretty damn easy to code up.

Thank you!

##### Share on other sites

Thank you! :)

Does that mean you found a solution? :) If so, what was it? (It might be helpful to others who might read the thread in the future.)

##### Share on other sites
Ohh, sorry.
Yes, i found the solution. The flood-fill works like a charm (with heavy optimizations).
The wiki article about flood-fill starts with a list of games using this method, and this games are the same type like what i working on...

Thanks again, i never managed to find it out from myself this solution.

##### Share on other sites

The flood-fill works like a charm (with heavy optimizations).

Great, glad it worked :)

1. 1
Rutin
33
2. 2
3. 3
4. 4
5. 5

• 13
• 9
• 9
• 9
• 14
• ### Forum Statistics

• Total Topics
633329
• Total Posts
3011381
• ### Who's Online (See full list)

There are no registered users currently online

×