# Calculating the structural integrity of a pixel grid

## 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:

1. Split the mass of a block based on its valid connections i.e. paths that are not a dead end.
2. The fraction of mass on the neighbor node represents the fraction of weight of the source node it supports.
3. 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:

• 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?

• Can you give a self-contained definition of "load" and "stress"?
– D.W.
Commented Jul 20, 2020 at 1:13
• @D.W. load and stress are just how much mass the node supports. Commented Jul 20, 2020 at 15:44
• Can you give us a primer on the physics / mechanical engineering of this, and what determines how much mass each node will support?
– D.W.
Commented Jul 20, 2020 at 18:46
• @D.W. I don't know much about the physics/mechanics, and its not necessarily a simulation of real world physics, but basically I assume no torque exists and forces are split equally on each face, and the stress on each side has an equivalent limit. As for the limit itself it could be an arbitrary number to represent how many nodes a specific material could support. Also I added a code example link above :) Commented Jul 21, 2020 at 0:16
• All this talk about "paths" suggests that you might take a look at a maximum flow approach. It won't be quite the same problem, but you might examine how to send one unit of flow from every block to the sink (anchor) nodes while constraining the amount of flow through any given node. Commented Jul 21, 2020 at 7:29

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.

## 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.