Need physics algorithm for modeling ceiling collapse in voxel-based game

Question

I'm looking for algorithms on how to model the physics of cave-ins/collapses for a game idea I am working on. The game allows the player to extensively mine 3D voxel-based asteroids, and I want areas that are insufficiently supported to collapse under their own weight. Making the problem even more challenging, gravity will be non-uniform (the direction it pulls will depend on where a given voxel is in relation to the asteroid's center of mass), and the number of voxels in the asteroid will be too large to model them all individually (I am using a sparse voxel octree to model the asteroid).

Hopefully, someone will be able to provide links to articles discussing suitable algorithms, or can provide ideas on how to solve the problem. If you need more details, please ask.

Edit 1: It does not need to be very accurate, I'm looking for something that would be a reasonable approximation for a Minecraft or Dwarf Fortress style game. I am mostly interested in how to determine where sections should break off when blocks are added or removed, moving the bodies after they break isn't part of this issue.

Edit 2: My initial idea was to calculate the force on each block then iteratively distribute the forces amongst neighbors. However, this would require an entry for each block, while only blocks on the surface have entries in the data structure. Modeling all blocks on the scale I want would likely be prohibitive - I would like to have bodies of at least 10,000,000 voxels, of which 200,000 will be on the surface and need to be stored.

Answer 1

You are making an artistic decision; that's the right way to approach it. You have a non-realistic medium, so you are picking and choosing what physics you want to apply anyway.

But this exercise is not difficult. Structural engineers pick and choose what kind of physics they care about enough to include them in their calculation of...whether or not a ceiling will collapse.

You could probably figure out enough math by extrapolating one-dimensions beam stress into two dimensions. There you can determine where stress exceeds the shear limit. I don't mean for this link to be smarmy, it's just a good google query for you: http://lmgtfy.com/?q=beam+stress

Answer 2

You note that you only represent blocks which are on the surface — I assume this includes ceilings. But we can assume that interior things are well-supported, i.e. not themselves the source of a collapse, and so they don't need to be considered!

Here is my idea for a model — I haven't tested it, and I'm sure a structural engineer could find plenty to criticize. It is designed to be efficient and use little data, but has the disadvantage of not representing horizontal forces (so a column will never buckle).

---

For each surface block, store a number (not a vector) which I'll call 'displacement'. This represents the infinitesimal displacement downward from an unloaded state of the same structure. It is intended only to manage breaking, and need not be graphically represented.

Whenever a block is disturbed, iteratively update these values (i.e. update neighbors and their neighbors until values stop changing much), applying two kinds of 'forces':

1. For each attached neighbor, a linear spring force based on the difference between this block's displacement and its neighbor's displacement.
2. A gravitational force, scaled by the total mass of this block and every interior block directly above (opposite to gravity) this block (e.g. count how many solid voxels a ray cast upward traverses before hitting an upper surface; apply a 'cone' correction if you're feeling fancy).

(Note that these are not actual forces, because this model does not include velocity. If I'm not confused, this should basically work as if the system is extremely damped.)

---

If the difference in displacement values between two neighbors becomes greater than a threshold, consider them to have broken apart — no longer affecting each other. (Depending on the material, the threshold should likely be relative to the direction of gravity; for example, for neighbors which are oriented (mostly) vertically, if the upper block has a higher displacement, they are under compression, whereas if the lower block has a higher displacement, that is tension.)

If the displacement of a group of blocks is constantly increasing, then that group is unsupported and should start actually visibly falling, which I recommend handling with a regular physics engine (or adjacent-voxel movement), independently of this system. I leave it to you to figure out how to detect that complete group.

Answer 3

Complex physics simulations that are based in situations other than those here on earth tend to require specialized implementations. Many physics simulations are able to be done efficiently due to estimations, and assumptions that are made about the context they will be simulating in. Unless you are writing the entire physics framework yourself, you may want to consider using something like PhysX, or bullet to provide rigid body simulation, and with clever use of constraints and restrictions you can create the illusion you want. The type of situation you refer to though isn't something you can simply achieve by implementing a single algorithm, it is a larger collection of physics principles working together.