7
\$\begingroup\$

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.

|improve this question
\$\endgroup\$
  • \$\begingroup\$ I would say that there's a non-trivial gameplay issue here: if you're dealing with a round body, cubes are not how to model it. If you try that, what you will find is that some structures that function perfectly well in one place will collapse in another. Or that structures will collapse for reasons that don't seem... reasonable or obvious to the player. Either thing is not going to be good for your game. \$\endgroup\$ – Nicol Bolas Mar 7 '13 at 2:01
1
\$\begingroup\$

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

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ P.S.: if you want to do this without calculus, then you are depriving yourself of a good excuse to use calculus. \$\endgroup\$ – Seth Battin Feb 9 '13 at 2:54
  • \$\begingroup\$ P.P.S.: Now that I think about it, a voxel game doesn't really allow for continuous math anyway. But you can still sum the total stress across a ceiling by iterating through the array of blocks. \$\endgroup\$ – Seth Battin Feb 9 '13 at 2:56
  • \$\begingroup\$ My initial idea was to do roughly that; calculate the force on each block then iteratively distribute the forces amongst neighbors. However, only blocks on the surface have entries in the data structure, and modeling all blocks on the scale I want would likely be prohibitive. \$\endgroup\$ – Sir_Lagsalot Feb 9 '13 at 16:52
  • \$\begingroup\$ Some way of decomposing the body into volumes and then doing the calculations between volumes could be a potential solution... The question then becomes how to determine volumes. \$\endgroup\$ – Sir_Lagsalot Feb 9 '13 at 17:04
  • \$\begingroup\$ I think you could pay for the cpu cost, as long as you don't try to recalculate every block every frame. You could aggregate the stress calculations for small groups of block, a small fraction per frame. Then you could determine the overall effect. I believe that is the method used by Dwarf Fortress's collapse events. \$\endgroup\$ – Seth Battin Feb 9 '13 at 23:07
1
\$\begingroup\$

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.

|improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ I am mostly just interested in how (at a very high level) I can go about determining where pieces should break in an efficient manner. It is a block based game so it doesn't need to be extremely accurate. \$\endgroup\$ – Sir_Lagsalot Feb 9 '13 at 2:54

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.