3
\$\begingroup\$

I'm creating a game where every user has a network of connected nodes that each have a specific amount of energy. The nodes will try to distribute energy evenly amongst themselves. If a node has more energy than the average, it should deliver to the network. If a node has less than the average, it should receive from the network. An example network would be this, where + means more than average and - means less than average:

enter image description here

Now the one question I've been trying to solve for a while now: how can I calculate the cumulative amount of energy that flows through every edge until all nodes have the same amount of energy? For example we know that the node in the top left will in the end distribute 7 energy to the network, but will it give 5 down and 2 to the right? Or something else?

Is there any algorithm we could use to solve that problem? Could we potentially represent this problem as an electric circuit and solve it like that?

\$\endgroup\$
  • \$\begingroup\$ It depends on how you want to model this. Whatever happens, I think it's going to be an iterative solution. \$\endgroup\$ – Almo May 24 '17 at 20:42
  • 1
    \$\begingroup\$ I am not sure if I understand this question. Do you want to balance out the amount of energy on each node so that each one has the same and want to determine how to do that with the least amount of moves? Or is the charge on each node constant and you just want to calculate the "flow"? \$\endgroup\$ – Philipp May 24 '17 at 21:07
  • 1
    \$\begingroup\$ @Philipp Good question. If you would compare it to 8 water cylinders connected by pipes, then some cylinders have +7 'liters' water in them, others have a hole to fit 5 liter in. The question is: how much water will flow through every pipe until all cylinders have the same amount of water in it? Regarding the floats/integers: we'll definitely need floats, but I used integers here for simplicity... \$\endgroup\$ – Willem Mulder May 24 '17 at 21:10
  • 1
    \$\begingroup\$ Does charge move more than one node at a time? Is there a limit to how much can move through the pipes at a time? For example, if it's infinite range and bandwidth, then it's just one step to equalize (with each node being set to the average of the system). \$\endgroup\$ – MichaelHouse May 24 '17 at 21:34
  • \$\begingroup\$ @Byte56 very good questions :-) Charge (or water for that matter) pushes all the charge/water in front of it, so if the node in the top-left corner wants to distribute it's +7 charge/water, then it will push down +7 into the network, and that will push other charge/water to other nodes etc. In effect, the charge/water can impact many nodes at once. As for bandwidth: in the game the bandwidth is limited, but for this question it doesn't matter yet. I just want to know how much charge/water is flowing through every edge/pipe. Simply setting the nodes to the average does not tell me that :-) \$\endgroup\$ – Willem Mulder May 27 '17 at 18:57
5
\$\begingroup\$

There are many ways we could choose which paths the energy will take, so here are a couple of starting points we could try.

1. Spanning Tree

This approach is inspired by dielectric breakdown, the phenomenon where a large potential difference across an insulator will drill a branching tree of conductive channels through it - lightning is the most familiar example.

We start by giving each edge a score based on the energy difference between its endpoints - we can consider this a measure of how "ionized" this edge is, and how eagerly energy will flow along it.

Next we run a minimum spanning tree algorithm on our graph, using the negative absolute value of this ionization score as our edge weight. Prim's algorithm or Kruskal's will both do great. This gives us a subset of our edges forming a tree that touches every node, which will become our energy distribution network.

Now you can pick a root of the tree arbitrarily, and work through the edges starting from the leaf nodes. Total-up the deviation from the average energy value in each subtree. The amount flowing down (leafward) along the subtree's incoming edge must be the negative of this value.

eg. if I have a leaf node with -1 energy difference from the average, then 1 unit of energy must flow down the edge leading to it.

If its parent has +2 deviation and a second child node with +1 deviation, then the parent's incoming edge must carry 2 energy back toward the root: -1 * (-1 + 2 + 1) = -2

2. System of Equations

Treating the amount of energy carried along each (oriented) edge as a variable, we can construct a system of linear equations, with one equation per node:

  [Node's deviation from average]
+ [sum of incoming edge variables]
- [sum of outgoing edge variables]
= 0

Here's how that system of equations might look for the example graph:

Example graph translated into a matrix representing the system of equations

This system will usually be under-determined, since you'll have more edges (variables) than nodes (equations/constraints), meaning you'll have multiple solutions to choose from - unless of course your graph is a tree, in which case we can use the rule above to find the single unique solution.

The nice thing about this approach is it makes the problem pretty generic - something you can chuck at a general linear system solver library (or integer programming solver, if you want to enforce a constraint that each edge carry a whole number of charges).

By playing with the solver objective function, you can search the solution space for options that spread the load as evenly as possible over all paths, as opposed to the spanning tree approach which necessarily concentrates the flow along a minimal transport network.

\$\endgroup\$
  • \$\begingroup\$ Wow, very elaborate and interesting answer! I'll go and study this some more, and once I understand it properly I'll accept the answer if it works :-) In the meantime a big upvote, even more than 1, if I could. \$\endgroup\$ – Willem Mulder May 27 '17 at 19:00
  • \$\begingroup\$ thanks again! I've tried both approaches (on paper) and in the end they both didn't really do what I needed. The spanning tree approach by its definition will remove specific edges from the network, which is not what I wanted... The second approach worked, and I even built a working version using that method, but in the end there are too many possible solutions. Which means I still have to create another algorithm to determine which distribution is the 'most natural' distribution of them all. And then I'm again well on my way to building a separate algorithm altogether :-) See below \$\endgroup\$ – Willem Mulder Jul 3 '17 at 20:58
0
\$\begingroup\$

It looks like I cannot determine the exact solution directly. What I created in the end is an iterative algorithm that approximates a natural distribution.

Code can be found here:


Roughly it runs like this:

Step 1

For the whole set of nodes, find all the disconnected subgraphs, i.e. find all separate networks.

Step 2

For every separate network, calculate the average energy position. In the example that average energy position is 0. Then calculate what every node should be delivering to the network or receiving from the network. Those are the +7, -2 etc that we see in the example image.

Step 3

We prepare a list of nodes that we want to process. This list initially contains all the nodes that want to distribute any energy to the network.

Then, the algorithm runs for a specific number of rounds. Every round

  1. It will loop over the prepared list and distribute any 'surplus' energy to the connected nodes. These connected nodes store the incoming energy into an 'incoming energy' bucket just for now.
  2. The algorithm loops over all nodes and adds all incoming energy for that node together and sets that as the surplus energy to distribute next round.

So after e.g. 50 rounds, the energy from a specific node has hopped over 50 nodes and distributed itself to quite a big network.

To keep things efficient, I use a few tricks

  1. If there is less than 1 energy to distribute for a node, it will remove itself from the list of nodes that we want to process. This because we don't want to distribute ever smaller amounts of energy around the network. A node will be added back to the list again if any incoming energy for that node moves it surplus energy > 1.
  2. If a node has only 1 connected node, then we know exactly how much energy will transfer between them. For example node A has +3 and connects only to node B. Then we know that A will transfer all that energy to node B, no matter what. So we confirm that energy distribution between those nodes and remove node A from the list to be processed. Even better, if that one connection becomes confirmed, that might mean that node B might be left with only one connection to a node C, which can then be confirmed as well, etc.
  3. If the list of nodes to be processed is 0, then obviously break.

The algorithm seems fast enough right now (1-2 ms for a few not-so-complicated networks).

Any suggestions much appreciated!

Again, full code can be found here: https://github.com/willemmulder/Energia/blob/master/static/js/core.js

\$\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.