3

I have a wall mesh that is divided into destructible pieces. As it gets destroyed, the wall can collapse into separate objects with physics that can be destroyed as well. (Cut the wall in half horizontally and the top wall becomes a separate object with its own physics).

I already have the adjacency info to know neighbors, but how should I store the pieces so that I can detect when to split them into separate objects? What kind of tree would suit this and know when the branch was severed and what pieces to make a new object out of?

A test would be to smash a circle out of the wall, and the middle of the circle would fall out and contain only those remaining connected pieces as a new object.

Any examples out there?

Edit: would a graph structure work using shortest path? Anything more effecient?

Thanks!

6
  • Your mesh is a data structure with links that connect nodes together then? Jun 13 '16 at 4:02
  • Well, the mesh(es) are 3d representations of the wall (individual breakable pieces), but they can be viewed as connected nodes that are removed as they are destroyed.
    – Nubsauce
    Jun 13 '16 at 4:10
  • Then I could pick one and navigate to it's neighbors and so on? Jun 13 '16 at 4:20
  • Yep. Each node knows its immediately adjacent nodes.
    – Nubsauce
    Jun 13 '16 at 4:34
  • And a cut will end this ability to navigate to your former neighbors? Jun 13 '16 at 4:39
1

I already have the adjacency info to know neighbors, but how should I store the pieces so that I can detect when to split them into separate objects? What kind of tree would suit this.

Rather than a tree I'd use a graph.

and know when the branch was severed

This could be as simple as waiting until the severing code finishes (and testing for partition after that) to whatever stores the branch info raising an event (see observer pattern) on a change.

and what pieces to make a new object out of?

Since we're dealing with a graph this is an old computer science problem called strongly connected. If I can start at a random node and reach every other node then the graph is strongly connected. If I can't then someone has cut your wall into pieces.

There are a few algorithms that solve this problem. I'm not going to detail them here. I will mention them and a few facts about them you may find important.

Kosaraju's algorithm demands an adjancecy list if it's going to be linear. It is the conceptually simplest efficient algorithm. Unlike the other two this must perform two complete traversals of the graph.

Tarjan's strongly connected components algorithm has links to implementations in many languages. Uses a vertex-indexed array of preorder numbers.

Path based strong component algorithm first made linear by Dijkstra, performs a depth first search, requires two stacks besides recursive stack.

2
  • Awesome, TYVM! That's the same conclusion I came to last night (and updated the original post) but haven't used one so your response confirmed it.
    – Nubsauce
    Jun 13 '16 at 13:26
  • I implemented sourceforge.net/projects/satsumagraph/?source=navbar and it worked great. Very simple to use. Added undirected adjacency to a customgraph then used a subgraph to call a stronglyconnected query that returns a list of strongly connected nodes.
    – Nubsauce
    Jun 16 '16 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.