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?
Collapsing elements
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.
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! :)
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.)
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement