Collapsing elements

Perhaps 'flood-fill' is what you're looking for.

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!

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.

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

Great, glad it worked :)