[0.6-pre] Wire burning and alghorithms

[malte0811]

This setup causes the 6 wires in the middle to burn once the output on both energy cells is enabled. (Both output cells are set to transmit 2050 RF/tick, to prevent cryo-fluxduct like code from messing with the setup.) This should not happen, as in a parallel circuit with resistors the current would be split, resulting in each wire transferring 2050 RF/tick, which would be far below the burning treshold. The only "proper" solution I can think of is to store every possible way to get from the input to the output (without visiting the same node more than once) in the AbstractConnection-object. And this is where things get complicated: I had an idea for an algorithm that would output such a list of ways, but I suspected it to have exponential runtime. Therefore I looked into this problem from a complexity theory point of view and found out this: The algorithm to calculate the different paths would have non-polynomial runtime, otherwise you could probably win 1000000 $ with that algorithm (It could be used to create an deterministic alghorithm with polynomial runtime to find Hamilton circles in a graph). And the energy transfer code may have non-polynomial runtime as well, but I did not look into that part to much. (For anyone who did not understand what I wrote in the last paragraph: The energy net code would get very slow for large networks if we use this "proper" solution) Now I see 3 options:

1. Leave the code as it is: I personally don't like this solution, as it causes setups that should logically work to cause problems.
2. Implement an algorithm as I suggested above: From a gameplay point of view, this would probably be the ideal sollution. But from a performance point of view this would be quite bad.
3. Implement some other sollution: Maybe someone has an different idea on how to solve this? @BluSunrize Which option should be used (in your oppinion)?

[mindforger]

i was working on a route based solution, where you store all possible routes from A to B with precalculated losses when dropping in a package, this (sorted by lowest loss + biggest capacity first) list will be used to spilt it up

the calculation effort is only present while alternating the net, but depending on the complexity of the net, as you said could become crazy, not to mention the loops (the point where i stopped my work -.-)

this was also my first intend to use better loss calculation in first place that benefits from used up cable capacity to increase the loss when the cable is not fully used

[malte0811]

I just did some calculations for the worst case, a complete graph (an edge between every pair of nodes). The time for energy insertion is O(n!) or something similiarily ridiculous (n is the number of nodes). The number of connections between 2 nodes is Net recalculation may not need to be fast, however energy transfer usually runs every tick and therefore is quite time critical. Using every possible path is (in my oppinion) not an option at all now, since complex nets would be continously using extreme amounts of calculation time.

[BluSunrize]

I'd leave it as is. I'd rather have non-realistic performances than lagging servers.

[mindforger]

@malte0811 therefor the routes shall be precalculated and the transfer shoould be splitted over every possible route by the rule "lowest resistance first" ... if the routes table is empty you can put the remaining energy through by overcharging and conequently burn all routes if there is more power left than able to transmit (this amount should be known by this point as you already sum up all routes and the overcharge amount is a fraction of the transferable default amount) ... but still i can yet not see how the updatetimes will impact on a large scale power net, but i am pretty sure the transfer tick should be very efficient then!

[malte0811]

lowest resistance first

I assume that would involve sorting a list of connections. The minimal runtime for sorting is n*log(n), so for a complete graph it would still be exponential. I have done some calculations (using sagemath) to get some numbers. The first number in each line is the number of nodes in the graph, the second number is the number of connections between any two nodes in the graph:

2:1
3:2
4:5
5:16
6:65
7:326
8:1957
9:13700
10:109601
11:986410
12:9864101
13:108505112
14:1302061345
15:16926797486
16:236975164805

The case with 16 nodes is definitely doable on servers, it takes 16 lv/mv connectors and a little less than two stacks of copper/electrum wire. Even if you would use no more than a single byte per path, storing the connections between two nodes would take up 236 GB of memory, getIndirectConnections would return 15 times that amount. That would OutOfMemory pretty much any server. Even if we ignore the amount of memory it would use, the update time would be insane, therefore it is impossible to use this solution. If nobody can provide an alternative solution, I am going to close this issue.

[mindforger]

well you are listing out absolut worst case and you are ignoring a very essential fact! you travel several routes more than once ... and i NOW remember why this solution is STILL impossible to use .. you need to sort out every route in the list that you have already (partially) used ....

[malte0811]

Closing because this seems to be impossible to fix.