So this is a question that came from an idea for a game. This game is voxel-based, and I am interested in calculating structural integrity, with some blocks that break after a limit has been reached.
I know Medieval Engineers and 7 Days to Die implemented something along these lines, though I would like to see if I can solve this (with some help) before ripping someone's implementation.
Of course links to more examples are appreciated.
In a 2D grid of constant size, there exists an anchor which all pixels/nodes must connect to. For example the bottom row will act as the "ground" and anchor all nodes. Finding unanchored nodes is easy, so assume all nodes are anchored.
Each node/pixel will have a mass, for simplification, this will be "1 block" of mass.
From there we need to find how much load each node is under (i.e. the amount of mass the node is supporting), and therefore how much "stress". In this problem load and stress are the same.
For every node:
- Split the mass of a block based on its valid connections i.e. paths that are not a dead end.
- The fraction of mass on the neighbor node represents the fraction of weight of the source node it supports.
- Repeatedly traverse splitting the mass until you get every path to an anchor node.
You should end up with a total number on each node representing how much "mass" it is supporting.
Mass distribution of one node
Each color represents the initial path from the source node/pixel for clarity.
The source mass is divided into three since the bottom path (in this example one block) cannot reach the anchor without going back on itself.
From this we can see the node with the most stress from the source node is D2, with the runner-up being C2. B3 is not affected by the source because it is not supporting it.
Of course there are limitations with this solution:
- Bad time complexity
- Scales poorly with #nodes
- adding or removing one node is expensive
My solution involves finding every path from source to anchor for every block, which is bad.
I made a (very slow) example below, where the bottom of the grid is the anchor.
How do I improve this algorithm or simplify the model in which stress is calculated so it can perform near real-time?