0
\$\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 when the network rebalances itself? For example we know that the node in the top left will distribute 7 energy to the network, but will it give 5 down and 2 to the right? Or something else?

Could we potentially this problem as an electric circuit and then solve it like that somehow? Note that every edge has the same 'resistance'.Should the energy sources be represented by voltage sources ?

\$\endgroup\$

closed as unclear what you're asking by Enric Blanco, Dmitry Grigoryev, PeterJ, uint128_t, winny Jul 10 '17 at 15:07

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ Solve what? You have never mentioned any dynamics and what is the goal. The only thing that is clear from this description is that in the end every node will have the average energy. \$\endgroup\$ – Eugene Sh. May 24 '17 at 20:40
  • \$\begingroup\$ The goal is to find the cumulative amount of energy that has passed through every edge until all nodes have the average amount of energy. What do you mean by 'dynamics'? What extra information would you need in order to solve this problem? \$\endgroup\$ – Willem Mulder May 24 '17 at 21:08
  • 2
    \$\begingroup\$ For example say you have a triangle network with nodes 1,2 and 3. So which portion of 2 will go to the 1 (if any?) and which portion of 3 will go to 2 and 1? These things are not defined. \$\endgroup\$ – Eugene Sh. May 24 '17 at 21:14
  • 1
    \$\begingroup\$ No, wait. There is a problem in this model. The energy will become zero as it will dissipate on the resistors... Update: No, sorry, the "energy" is actually a "charge" in this model, so it should be fine \$\endgroup\$ – Eugene Sh. May 24 '17 at 21:27
  • 1
    \$\begingroup\$ @EugeneSh. - It wont become zero. Consider that resistors connect only positive terminals of capacitors, and the negatives are all set to ground. There will be some energy loss while recharging, but when the voltages are equal there will be no loss (for ideal capacitors). Well it is good to say that this energy loss persist in electrical model, but not in hydrostatic model I proposed. \$\endgroup\$ – Todor Simeonov May 24 '17 at 21:33
1
\$\begingroup\$

You can't. There is something missing.

You can look at this as an electrical problem, where each node is a capacitor charged at a specific voltage. When connecting them simultaneously trough equal resisntances a current will strat to flow trough each edge(resistor) to equalize the voltage. Am I right?

You can also think of it as a hydrostatic problem. Each ot the nodes is cylindrical tank filled with water to a certain height. All tanks are connected at their bottoms by pipes with equal cross-section. The water will flow till all the tanks equal their water levels.

The thing you are missing is (a) the capacitance of the capacitor (electrically) or (b) the diameter ot the water tank. Actually the same thing.

In either way the curent or the water will flow for a certain time until voltage/height is equal. The current flowing during this period will not be constant - it will decrease with the voltages getting close to each other. The process is transient and is hard to calculate for more than 2 nodes. That's why all electric simulators use numerical methods of prediction, trying different values and etc. till they solve all variables for a given moment of time, then move to next moment of time... an so on...

UPDATE: Say you've got only 2 tanks - with 10m of water in the first tank and 6m in the second. In the end both will have equal level and the interesting thing is that the level may not be 8m !!! It will depend on both tanks diameters. Only if they are equal the level will be 8m. Same is electrical - depends on the capacitance.

The other thing - if you assume they are equal you can easily get the final level. But to know the exact ammount of water flowed from one tank to another except height you must know the diameter(cross-section) to calculate the volume. Its the same with electricity - except voltage delta you must know the capacitance to calculate the ammount of energy in Joules that moved from one cap. to another.

\$\endgroup\$
  • \$\begingroup\$ The water-tank-pipe is a great example; thanks! What I'm interested in is the cumulative amount of current/water that has flown through the edges until the voltage/height is equal in all nodes. I can't seem to understand how the diameter of the tank would matter... In any case the total volume pushing down into the pipes would be the same, right? \$\endgroup\$ – Willem Mulder May 24 '17 at 21:05
  • \$\begingroup\$ @WillemMulder see the update. \$\endgroup\$ – Todor Simeonov May 24 '17 at 21:20
  • \$\begingroup\$ Ah I see :-) I interpreted your example as if we would talk about liters/volume of water pushing down; in that case the diameter would not matter because we would only be interested in total volume of water, not in heights or widths of how that water is stored at a specific tank. But if we were, let's just say that all diameters are the same, so that heights are comparable between tanks. \$\endgroup\$ – Willem Mulder May 27 '17 at 19:06
1
\$\begingroup\$

Indeed you can accomplish this with something looking like very much the graph itself:

Charged sphere instead of the dot and conductor with ammeter and "close at the time 0+" switch instead of line. The dot's value will be the total charge of the sphere at the time 0- as being some multiples of a unit you determine. Then, integrals of the currents from time 0 to infinity will provide the answer.


* update *

I promised to improve my answer but it is very hasty and wrong. Better to forget it.


New answer:

Here we all intuitively supposed that the system has to reach an equilibrium. That requires a lossy medium and so there has to be an energy output into out of the system. That created the confusion and your question has been rejected.

I want to revive the question because there is not such a requirement. A LC network will fit with the rules. It will oscillate like boiling water until infinity, because it is just trying to do one particular thing: "...The nodes will try to distribute energy evenly amongst themselves...". It is basically a frictionless potential-kinetic energy problem, like a clock pendulum.

Now, if you look for some relation about the energy levels at t=0 and distribution after t=0, power spectrum of each inductor is the way to go.

The circuit is someting like that and your computer won't like it:

enter image description here

I showed it for one node, its beginning voltage is the square-root of the energy level because energy is proportional to the square of the voltage of the capacitor.

\$\endgroup\$
  • \$\begingroup\$ Whew, that's a bit over my head :-D Could you elaborate a bit more by e.g. giving an example or is there something I could read to better understand what you're suggesting? \$\endgroup\$ – Willem Mulder Jul 4 '17 at 9:27
  • \$\begingroup\$ OK, I will eleborate later. @WillemMulder \$\endgroup\$ – Ayhan Jul 4 '17 at 11:17
  • \$\begingroup\$ See the update. @peterJ \$\endgroup\$ – Ayhan Jul 19 '17 at 14:34
  • \$\begingroup\$ See the update. @WillemMulder \$\endgroup\$ – Ayhan Jul 19 '17 at 14:50
  • \$\begingroup\$ Thanks! Interesting! I can't turn that into an easy algorithm unfortunately, but that should not spoil the fun :-) \$\endgroup\$ – Willem Mulder Aug 1 '17 at 14:00
0
\$\begingroup\$

Unless @TodorSimeonov comes up with something great, I've sort of given up to 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 still much appreciated!

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

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.