Calculating the structural integrity of a pixel grid

Question

Preface
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.
Problem
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.
My Implementation
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.
Example:

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.
[Codepen Example]
Question:
How do I improve this algorithm or simplify the model in which stress is calculated so it can perform near real-time?

Jugbot · Answer

So I found a solution using maximum flow algorithm with some tradeoffs.
The setup involves:

Connecting the source node to every node in the grid with an edge capacity equal to the nodes mass.
Connecting the sink to the bottom layer
Connecting every node in the grid to each other with some capacity defined by the node (i.e. the maximum stress/load from that direction)

After Dinic Max Flow algorithm runs, I traverse the residual graph starting at nodes which do not get the maximum flow from the source (i.e. nodes that can't apply their full mass) and find all nodes which have an edge with max capacity.
[CodePen Example]
Example configuration:

So the algorithm works much faster than mine, and that is because it does not spread mass evenly. As shown above the white squares are nodes which have edges with maximum flow. This does not necessarily mean that the node is overloaded, and as you can see there are alternative flows that are not at full capacity.
However since my goal was to simply find the overloaded nodes and destroy them (and floating parts) this does not matter so much.

Calculating the structural integrity of a pixel grid

Preface

Problem

My Implementation

Example:

Question:

One Answer

[CodePen Example]

Example configuration:

Add your own answers!

Ask a Question