Sign in to follow this  
sk8beast

Collapsing elements

Recommended Posts

sk8beast    1532
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:
[img]http://noob.hu/2011/04/13/bam_coll.png[/img]
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
robotichrist    193
The correct problem to look for is connected components labelling: [url="http://en.wikipedia.org/wiki/Connected_component_(graph_theory)"]http://en.wikipedia...._(graph_theory)[/url]

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: [url="http://en.wikipedia.org/wiki/Disjoint-set_data_structure"]http://en.wikipedia...._data_structure[/url]

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
jyk    2094
[quote name='sk8beast' timestamp='1302810259' post='4798532']
Thank you! :)
[/quote]
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
sk8beast    1532
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
jyk    2094
[quote name='sk8beast' timestamp='1302898524' post='4798905']
The flood-fill works like a charm (with heavy optimizations).[/quote]
Great, glad it worked :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this