Sign in to follow this  
CombatWombat

Selecting contiguous objects

Recommended Posts

CombatWombat    673
I would like some help in deciding exactly which algorithm I need to research.

My problem is this:

I have a parent object I call a "Group". Physics in my game are simulated at this level.
The parent objects are made up of many child objects called "Blocks". These blocks are axis aligned to each other within the same group. They are all of unit size and evenly spaced (so they all line up neatly in a 3d grid). They do not move relative to other children once created.

Blocks can be added and removed from the group on the fly. When a block is destroyed, I need a way to check that the group is still contiguous. Meaning, I need to make sure all the blocks are still connected to one another. If they are not, I need to split them into their own groups, such that they are physically simulated independently. The quantity of blocks in any one group could be 1000 or more.

I found a few possible methods, but I don't really know which one to pursue. For starters it sounds like each block should maintain a pointer to its (up to) 6 neighbors. I already maintain a std list of all children which belong to any group. So I can have a tree of sorts to work with. My worry is that this tree isn't going to have many dead ends, and so might be awkward to traverse?

From there...
1) Flood Fill algorithms. This seems the most promising, but I'm not positive which subtype I should be looking at.
2) Pathfinding? I could arbitrarily pick any block, and try to path randomly to other blocks until they are all hit or all possible paths are exhausted. This sounds like it could be very slow.
3) Disjoint-Set / Union-find. Unfortunately I did not really follow the wiki entry on this one. Bit over my head. There also doesn't appear to be a SPLIT. Only Union and Find?

Does anyone have any suggestions? Speed is important here, as this algorithm must run everytime a block is destroyed, which is likely during an already math-intense time (combat).

Thanks!

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