How is structural analysis done in games (e.g.: bridge building, Dig or Die, and 3D)?

Question

From what I understand a typical interactive truss system would need substantial calculations since every component affects the entire system. I think you could arbitrarily stop at a given number of iterations at cost of accuracy in the simulation, but I don't know if that's the approach these games use (bridge building games are an example of truss systems). On the other hand, games like Dig or Die have a quite complex structural system that also takes torque into account (I believe) and compression and is very fast and works on very extensive systems. I guess the basic calculations could be similar, but if not I'm interested in both approaches.

Do you guys know how these are made? Do they have an arbitrary limitation or do they use a different algorithm altogether? Also, I guess whatever you guys come up with can be applied to 3D systems but if not or if it's not obvious please at least give a clue on how you could use it for 3D since I'm interested in this for both 2D and 3D games.

I know I'm not supposed to thanks here but I find unfair not to at least thank you for your time in advance, I hope this paragraph don't get removed.

EDIT: If I were to make a guess I'd say Dig or Die stores vectors for each block and then run an iterative algorithm up to a point that the extra accuracy in the simulation is meaningless for the limits of the system (for example, the system would be too large to not collapse anyway), so it's limited by a semi-arbitrary (because it's based on application) number of iterations. But I could be wrong.

Answer 1

I am the dev of Dig or Die, so I can give a little more details about the game physics

Indeed the most crucial point was the performances, as in the game you can build thousands of physical blocks, and much important I have other things more complex to simulate (rain/water) so I can spare very very few CPU time for the building physics.

So I actually did a sort of... I don't know, a custom personal algorithm not very accurate, but it works fine enough for the game. I've 1 vector for each block intersection (so each block is linked by up to 4 vector, one on each side of it). Each block has a "weight", and "pushes" the vectors around it (equally) so the total of the vectors magnitude is equal to its height. When a block is anchored to the ground, all the forces/weight that are pushed into it are never "pushed back", so naturally with enough iterations the whole system find a balance. The weight/force will sort of "flow" to the anchoring points, and manage very well changes on the structure. You can see the result here (with the ingame "Eiffel Glasses" item):

About torques, I simulate it by multiplying the forces that are transmitted horizontally. It's not perfect but it's enough to feel the big difference between building horizontally and vertically

But honestly I don't like that much my system, for some cases it's not very accurate ; mostly because I don't manage the compression and extension. There is probably a way to do a more accurate simulation than mine without more CPU, but my skills (and time) about it were very limited so I did what I could :-)

(PS: you guesses were very good :-) )

Answer 2

I've personally had good success with Iterative Relaxation. I think it follows the laws of physics quite nicely when dealing with objects made of aggregates of blocs. I believe the BridgeBuilder series is based on such a method, though I have no source to confirm this.

Iterative Relaxation is widely used for trusses, but I've successfully simulated large solid objects (concrete) with it: it's quite simply a truss, whose joints carry load instead of being free-turning.

---

What is interesting, is that relaxation is a technique for resolving static trusses, so it is accurate. In that regard, it is used to iteratively compute a displacement that brings a structure to equilibrium.

But the added value for a game (where we're interested in dynamic environments, because static, at-equilibrium structures are boring) is that we get the chance to actually displace the structure's joints between each iteration, based on the constraints computed so far. You get two major benefits:

• You have a dynamic structure, which responds correctly to any exterior perturbations
• You have a structure which responds accurately to loosing supporting members (think rapid unplanned disassembly) by shifting its strain around to other members. It's actually quite enjoyable watching stress flow being moved as joints get broken in a chain event
• You have a non-linear simulation! Further explanation of what I mean:
  Usually, static analysis makes the hypothesis of small deformation, where the structure does not move far off its initial state. Within these bounds, the static analysis is correct because the joints aren't actually displaced much. But as the structure deforms under crumbling weight, you'll get accurate results all the way the the end with a non-linear simulation, whereas you'll simply get a invalid state from a linear solver

Iterative relaxation is quite simple to put in place, Numerical Stability. I've used RK4 scheme tsuccessfully to achieve stability with large conrete structures. The drawback is it usually has quite small stiffness for performance reason, so may feels quite like soft jelly at times.