Computer Science Asked by Jugbot on September 27, 2020

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.

[Codepen Example]

How do I improve this algorithm or simplify the model in which stress is calculated so it can perform near real-time?

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

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.

Answered by Jugbot on September 27, 2020

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- Jon Church on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP