2
$\begingroup$

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:

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

$\endgroup$
6
  • $\begingroup$ Can you give a self-contained definition of "load" and "stress"? $\endgroup$
    – D.W.
    Jul 20 '20 at 1:13
  • $\begingroup$ @D.W. load and stress are just how much mass the node supports. $\endgroup$
    – Jugbot
    Jul 20 '20 at 15:44
  • $\begingroup$ Can you give us a primer on the physics / mechanical engineering of this, and what determines how much mass each node will support? $\endgroup$
    – D.W.
    Jul 20 '20 at 18:46
  • $\begingroup$ @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 :) $\endgroup$
    – Jugbot
    Jul 21 '20 at 0:16
  • $\begingroup$ 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. $\endgroup$ Jul 21 '20 at 7:29
1
$\begingroup$

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:

enter image description here

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.

$\endgroup$

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.