• Advertisement
Sign in to follow this  

Collapsing elements

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

If you intended to correct an error in the post then please contact us.

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:
bam_coll.png
Here, i marked the separated cell group that i need to remove.
Is there any general algorithm that can solve this problem?

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

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

Great, glad it worked :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement