Jump to content
  • Advertisement
Sign in to follow this  

Selecting contiguous objects

This topic is 2553 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

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).


Share this post

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

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!