Non-throughput-limited 8+ belt balancers?

[sckuzzle]

I've disproven the current running theory that it is impossible to balance a 4-belt balancer without throughput limit.

See: http://i.imgur.com/6wsMrV2.jpg

Basically, what I did was divide each of the 4 lanes into 4 more lanes. I then sent one of the four "quarter" lanes to each of the four outputs, and then recombined them together again. With such a method, the balancer is count perfect, and each input has a direct lane of its own directly to the output.

This method can, of course, be scaled to any number 2^n lanes. Since you can choose to not use an input and an output of any given lane, this means that for any n, there is a count perfect non-throughput limited balancer that exists (ex: for a 13 lane balancer, make a 16 lane and don't use 3 lanes).

Of course, with my proof-of-concept balancing method the balancers get massive very quickly, requiring n^2 intermediary lanes. In all likelihood my example can be condensed and simplified (I'm no good at spaghetti).

[Frightning]

So I thought I'd give a quick mini-tutorial on my belt balancer testing setup and how to make one for yourself. Here's a picture of the whole thing (sans power source which is off-screen to the east):

20160508062801_1.jpg (481.99 KiB) Viewed 11740 times

The middle area is where you build whatever balancer you want to test, be sure to give enough room for any belt balancer design you are interested in testing!

Below that is the belt loading and compression area, each input you (may want) to use should have it's own pair of chests (I use steel chests here, which I recommend for ensuring that you have ample capacity for running longer tests if desired). I use Yellow belts, with 4 segments of Fast belt at the points where the fast inserters load the belt from the 'inner' chest, which is where full compression is achieved, since each fast inserter places 2.22 items/sec and each lane of a yellow belt can handle about 6 and 2/3 items/sec which is just barely over 3 fast inserters worth of throughput. If you wanted to test fast belts, you would need 4 chests and segments of express belt (I'm not sure how to fully compress an express belt with this kind of setup; if that's even possible), but I see no reason to make the loading/unloading setup that much larger and more complex (I see no reason to suspect that anything important to the tests changes with slower belts). The power to the loading area should arrive via a single power line so that you can cut it by removing one of the poles. Cut the power before loading the chests (I recommend approximately twice as many objects in the 'outer' chest compared to the inner because the outer chest will give full throughput whereas the 'inner' chest will give roughly half). Once they are all loaded, connect the input you want to test and the outputs and then replace the missing power pole to start the test (be sure your power supply can handle 16xnumber of input/output belts fast inserters going full force, otherwise you might have problems with belt compression and/or unloading backlogging and messing up the test).

The output side is similar, I choose to use splitters to separate the output so that each half would get unloaded into the output chests, but you could instead just loop around and finish back at the first output chest (other 2 fast inserters that didn't get to unload on the first pass of the belt near that chest). Either way, what's important is that the output belts never backlog (which 4 inserters per lane or 8 per belt is enough to ensure). The output chests will allow you to verify that your balancer is actually balancing properly (might be a few objects off, but error should be quite small). You can observe backlogging in the balancer during the initial phase and if the balancer fails to allow full throughput that will be evident by input lanes halting briefly every so often. This can allow you to diagnose which input lanes are bottlenecked and hence find out where in the balancer the problems are coming from. Usually related to backlogging into the balancer causing a theoretically unstable equilibrium between splitters, which won't be realized in practice and hence in the experiments.

Quick note, when you have the test setup, loaded and ready, create a save. That way after the test, you can just reload the save and switch the inputs and outputs and run it again (almost no down time).

[sckuzzle]

I suggest the use of express belts to quickly spot any eventual problems or lack of compression. In order to achieve this, you must use a splitter to fully compress the belt.

I also suggest using a logistic system for automated filling of input chests.

[Frightning]

I've disproven the current running theory that it is impossible to balance a 4-belt balancer without throughput limit.

See: http://i.imgur.com/6wsMrV2.jpg

Basically, what I did was divide each of the 4 lanes into 4 more lanes. I then sent one of the four "quarter" lanes to each of the four outputs, and then recombined them together again. With such a method, the balancer is count perfect, and each input has a direct lane of its own directly to the output.

This method can, of course, be scaled to any number 2^n lanes. Since you can choose to not use an input and an output of any given lane, this means that for any n, there is a count perfect non-throughput limited balancer that exists (ex: for a 13 lane balancer, make a 16 lane and don't use 3 lanes).

Of course, with my proof-of-concept balancing method the balancers get massive very quickly, requiring n^2 intermediary lanes. In all likelihood my example can be condensed and simplified (I'm no good at spaghetti).

Are you sure that that monstrosity is universally throughput unlimited? Did you test every combination of 1 input to 1 output, 2 inputs to 2 outputs, 3 inputs to 3 outputs, and, of course, full load?

[sckuzzle]

Are you sure that that monstrosity is universally throughput unlimited? Did you test every combination of 1 input to 1 output, 2 inputs to 2 outputs, 3 inputs to 3 outputs, and, of course, full load?

Due to symmetry, I only tested it once for each number of inputs and outputs. I encourage you to try all 69 combinations though. Here's the blueprint string if you'd like to give it a shot and let me know if you find one that doesn't work.

Code: Select all

H4sIAAAAAAAA/7Wd3W7jOAyFX6XodbKwbMk/KPIsg25jLAJ0nSBxgBkUefdtrXSBjGTZ1Me5LXqOKEokj2lZ2R+f3o9vr+9PP3Yf/TAexkN/2X18DK//9rvn
/ufp3F8u2/H8OlxOx/O4/bt/H583p+Pl8x+Pw+7j525bb37ttqa4bfaHc/82/dneNhIGFzLUMgaLGSrMUGIGQxkKSoAtwG7EXsRbAe/GSEDICBpK0FKCDu/l
yQktSAoTQQcIDLWgVCHAU+hgPmhhOgD4AtpP5x+uYEY2A/hwA2SMD/AW2u8g3kL7HcSHSSgjEQN8mMMyxgf4zuMXMNvxuP3nfLwO+wj6c/bjr9Mn9ngdT9fx
WV6HgP2ttyDAXE7vh3Hsz7+ly8lg95cDZWsasQYEjZhgzv2+AjYP5eO+FodBvBSejczMUQJLCSpKUFICo7e6JVvdWV6juWsK6DC5vyIFFODpjqFblsbMPZvI
MY0MQ5NDB/Fths1thm/Mmg0dry7G8Opipv1oc4bfmikWKja+nwN5IjErZpBmKAIbVvugy3DBbKJswpkAqePpsPTABKKlmfWNm/UNK051wGuJz2vqMkcJLA2H
NRlh2QIyhYoSlDglqBCI0lpaljmtrFCE+12OB2sTOiY3JUTWSOSXOd7I7suXq5HFk+OtTFLQAKbxS1OYPIPNLeV30cgPl0hJzrQlLDRgW91LOzHFydySbMn8
72JUiyNqAaxcB3ehXPzMJqow54KlB2rVS2Uk2M2ahDYzeqU0eiQdJp9QjMITSoUZSvyEgmwoVtiQesZhTmyp/Q0laOkaNJSgplOoqQUusCDnWASxoAoIhBZU
4inM6mobrgd58itxiIoJ0h3XRzerFHs/SUAceZZQmXHEd7DFDDYpTfd0J4UxkuvWcLlJiNyDP9OW73DV2MffeUxBtFo5VUTKi3ZLUtZHVyvDrA5uYt8Yzeif
gzGxTAIqyYu8RZWUksZIYhmaNUwk2HPeJRislDFDIdt2XhwvHC1LaOMCSeOGTrnVICAH6xqIr+kEamiAU8CjCVhoQKWAf5wAU9UmXzKkNe2jjSovgMo/wxvJ
ZBq0xZ+xNnSCYi/dKIo2JS6bwRXKNngie7FMJYWeUZGvkerDNCM+4s06tviIOhWPlCBLhnjVg+Uj+UwjkkYlGqrEGor29qiConjaWqR4Yr+D4zs4voXjVxBv
of0VxJfQfgPxJbTfMHzB4dltqdB1QFQEcSRrPAZhlKviw3ySLwpgboGpGVaGjsOhoIFw2k2jcia/l8YUwdSLAsdaLX9njI6PfRGQN3WT8xe6gQk5xqbfLI+9
iCfea+H4LRy/VsAT+50Cnh4AJeNXUvxsc+eeBVQaUDbwCnld7AOcNMPAoeVkM0ztMPSKFLT0GlXt5bD+yfFC01Ulc5VawATrr9cGlJ0RDNt1wD3ifJhqQeqc
dbTQI7DEBhWGPClEowB3JbXOS3asmHXM0VCKQCWyRgUu4rNUtFfA4G04UqBewgs/xFuRg1NPDDV/YsAENSEoNAjyv6Jj/mug8Q10f6uAJ/bXCnj62RrFE/st
HL+CeAvtr2jw/W5/xsVAdHyCL5n/g9wl/6gNeM9vHjFE+KW4lY9i5aM4+SgwdmHqhpkPJn6YNztmfMdGh0UH1rw1emERv2B+Qpwu6o2EOEVaxcBca2Cu9L3x
hhAYDYLILUrL+nLh6quEvmyxvgTXbk144rFWAU/srxXwxH6ngCf2Wzg+DTkL7a8gvqQRD/EltN8wPIQXbPYrEt/69u4jEfycR3hBEoxicRCm+otRP2R2YsGc
xIkx1Yl9vBoWfjwPJtWxcIHFCtZKA6M1X6d4WYS1JclzQZ4X9hG+fA+u15x0EsHXEO8gfjrJl32weyrzXX6CTr4H78DrJn/Cj94kLyNIvqSOOilnYoYteAH9
IndLiIfmw9us6d389Gp+eJk1vMuaXutPf1cAXmUNb7KmPylA8eAme1goOgaHZdJE4va2Obwdh69fSjkM+/4rMyT5brfby7kfr+fh6cdLP+z/A8kHZfx2ZQAA

However, since testing and theory both indicated it is sound, I won't hold my breath.

[Frightning]

Whelp, after testing it 4 times, with increasing numbers of plates per input belt (final test was 1400+700=2100 plates per belt) and leaving in the backlogs from the unused output belt (to reduce time to stabilize). I found that the outputs were indeed not saturated. What was even more interesting was that I couldn't seem to see any hitching or other evidence of this throughput loss on the input side (?!) The last test I watched the input closely for the latter duration of it, and realized that all 6 lanes across the 3 belts were in fact stuttering ever so slightly (so slight that I had thought it was just a consequence of my monitor's refresh rate, game fps, or simulation rate (ticks/sec)). This is the only way I can explain what I observed: Here is a picture from the final test showing the output belts failing to be saturated:

20160508100231_1.jpg (511.88 KiB) Viewed 11721 times

One other thing I did after the last test was explicitly count the plate totals in the output chests (adding the number of plates in each pair of chests on a given output belt together). This gave totals of:
1742, 2373, 2187

Which is surprisingly imbalanced (it should theoretically be 2100, 2100, 2100), which further supports the claim that throughput was indeed limited by the balancer.

[Frightning]

I think I also just figured out why the throughput losses were so hard to detect on the input side:
Because of how large this balancer is, and the fact that the belts are split into more belts. The compression waves from a bottleneck would be distributed over the large number of belts. These compression waves would then arrive at the input side at different times, and with a much smaller, far less noticeable effect. Which explains why they were so hard to notice looking at the input side belts.

[sckuzzle]

Frightning,

I was able to replicate your issue and discovered why it was occurring:

Due to how splitters work, a fully compressed belt will be split into two individual lanes upon splitting. If you don't reach an equilibrium, a shock in one lane backing up or a slight decompression can cause the splitter to shift which belt is receiving which lane (or the ratio in them when backed up). To solve this problem, make one lane copper and the other iron (or only use one lane). The decompression should entirely disappear.

If the problem persists, ensure your input belts are fully saturated.

split.png (1.26 MiB) Viewed 11712 times

I've been watching this for 15 minutes and have noticed no less of compression after switching to copper / iron.

[Frightning]

Frightning,

I was able to replicate your issue and discovered why it was occurring:

Due to how splitters work, a fully compressed belt will be split into two individual lanes upon splitting. If you don't reach an equilibrium, a shock in one lane backing up or a slight decompression can cause the splitter to shift which belt is receiving which lane (or the ratio in them when backed up). To solve this problem, make one lane copper and the other iron (or only use one lane). The decompression should entirely disappear.

If the problem persists, ensure your input belts are fully saturated.
~snip~

That's very interesting that using two resources, one for each lane solves the problem. The issue concerning splitter behavior isn't just the changes in conditions at one splitter eventually affect an earlier one, it's that they can form cycles which naturally prohibit the theoretical equilibrium from existing. A simple example of a situation where that occurs is the forbidden triangle I described earlier in the thread:

What happens there once saturated throughput gets into the balancer is that too much is coming at the last splitter (recall my simple 3-splitter 3-belt balancer), this causes backlogs toward the middle splitter (on it's left belt) and the first splitter (on its left belt). The middle splitter is affected first: here with its left belt backlogged, all of it's input attempts to go onto the output belt (#3), but that's 1.5 belts worth of throughput, hence both the input belt 3 and the belt from the first splitter's right to the left of the middle splitter now begin backlogging. Once that backlog hits the first splitter, it adjusts it's throughput, more to it's left belt (which goes to the last splitter), this changes things at the last splitter, and thus the cycle begins again (hence the periodic nature of the 'flebs' I noted when I tested it). The issue of 1.5 belts going into middle splitter which can only give 1 belt out, causes 1/3 of a belt of throughput to be lost (output 3 ends up only getting 2/3 of saturation, because there's 3/2 of available output in incoming input).

[Frightning]

So I put forth a design challenge to the community to see if anyone can come up with a 3-Belt Balancer that is actually universally throughput unlimited (maybe it's possible, idk; I was reading about splitters on the wiki today and noticed that looped splitter setups can produce divisions by arbitrary integer values, which just might allow for such a 3-belt balancer).
Here is the thread:
viewtopic.php?f=8&t=25080

[ribsngibs]

If you math out the desired division of the input, you see that after the first splitter its:
1/2 1/2 1
After the second:
1/2 3/2 (!) 0

...

I admit I haven't done a careful proof yet, but I did actually consider the idea of splitting the lanes into more lanes, and the problem inevitably shows right back up when you try to recombine the lanes (you'll end up with two belts needing to combine to one but they have >1 belt's worth of combined throughput between them)

Hi - I'm a bit behind on this thread but I disagree with this analysis. The bottleneck only should only (theoretically) happen when there are intermediate belts along the way that want to have >1 belt throughput. If you put 2 full belts into your forbidden triangle, you indeed get 1/2 1/2 1, then 1/2 3/2(!) 0, then a failure to get to 1 1. However, if you put 2 belts at half capacity (1/2 1/2), instead you get 1/4 1/4 1/2, then 1/4 3/4 0, then 1/2 1/2, non of which is a bottleneck. If you do this side by side and then recombine the inputs, a splitter will have no problem taking a 1/2 and 1/2 and merging it into 1 full belt.

Indeed:

dubthreesplit.gif (5.46 MiB) Viewed 11958 times

Similarly, splitting each input into 2 and sending one set of 8 to one 8 balancer and the other set to another 8 balancer, and then interleaving and recombining the outputs (output 1a and 1b > output 1, 2a and 2b > output 2). This shows that example (with only the first 4 belts hooked up because too lazy:

dubeightsplitfull.gif (12.63 MiB) Viewed 11958 times

And I agree with the others that simply placing two 8 balancers in series would work, as there is only a bottleneck in going from, say 4 inputs to 4 outputs, but not from 4 to 8, and not from going from 8 to 4*:

serieseight.gif (15.62 MiB) Viewed 11958 times

*- I did, actually, see some total throughput fails like the kind you saw. I believe sckuzzle is basically right - a splitter on a compressed belt will stabilize in putting all of one lane's items on one belt and all of the other lane's items on another belt, and sometimes a complicated series of belts can result in another pattern of 1/2 compressed but alternating items. Actually, in the image just above (the two 8 balancers in series image),if you look at the 4 belt segments just to the left of the player character, you can see those patterns - it starts with the 2 left belts with single lane items while the 2 right lanes have the alternating pattern, and then the 2 right ones somehow get "fixed" to the 2 single lane pattern.

The total throughput failures, I believe, are caused by the little hitches in the lane patterns (from left lane to right lane, or from left lane to alternating). If one were to split a single belt into two lanes, the two lanes will have perfectly complementary patterns (if the left belt has an alternating pattern, the right belt will have the exact opposite alternating pattern which will zipper right back with the left if combined again - if the left belt has items only on the left lane, then the right belt will have belts only on the right belt, which will also happily merge right back in if combined). However, in these balancers do not have equal path lengths for all belts. So if there is a hitch which changes the pattern (say, left belt from left lane only to right lane only), the other belt will also switch to the complementary pattern, but if the path lengths for the left and right belts are different, then the "left lane only pattern" on the left lane may collide with the "left lane only pattern" on the right lane. So I think the total throughput failure you see with 1/2 output is when two belts have items on the same lane, trying to merge into 1, and the failure you see with 3/4 output is when one belt with items on one side collides with a belt with items on alternating lanes..


e.g. the simplest case: one belt split into two, combined back into one works just fine obviously:

simplegood.gif (3.44 MiB) Viewed 11958 times

but simply adding a little dog leg to one belt (just to make it longer), and removing a single item from the belt (to switch the patterns), will result in the patterns getting offset and result in throughput failure. Sorry, big gif ahead:

simplebad.gif (14.26 MiB) Viewed 11958 times

Keep in mind that one does not actually need to supply a belt with errors in it - I have a video that shows a fully compressed belt which simply starts with a bit of a mistake (the first 5 items are a little funky), which results in a tiny bottleneck, which sends a shockwave down one lane, which switches the belt pattern, which later on causes another bottleneck, which sends another shockwave, switching the pattern again - so a single error may result in a perpetuating series of belt pattern switches. I can post this gif later if people are interested but I am late for work right now!

[Frightning]

~snip~
Keep in mind that one does not actually need to supply a belt with errors in it - I have a video that shows a fully compressed belt which simply starts with a bit of a mistake (the first 5 items are a little funky), which results in a tiny bottleneck, which sends a shockwave down one lane, which switches the belt pattern, which later on causes another bottleneck, which sends another shockwave, switching the pattern again - so a single error may result in a perpetuating series of belt pattern switches. I can post this gif later if people are interested but I am late for work right now!

NICE WORK!

That gif w/ the swapped lanes shows something really interesting about splitters I didn't know: They will only move items to the corresponding lane of the other belt.

The explains so much about the weirdness I was seeing, and why said weirdness was consistent across multiple trials: my start conditions were identical (I would just reload the save to run another trial), and if I didn't change the layout, then exactly the same things would happen for exactly the same reasons.

[Shokubai]

That gif w/ the swapped lanes shows something really interesting about splitters I didn't know: They will only move items to the corresponding lane of the other belt.

The explains so much about the weirdness I was seeing, and why said weirdness was consistent across multiple trials: my start conditions were identical (I would just reload the save to run another trial), and if I didn't change the layout, then exactly the same things would happen for exactly the same reasons.

The effect is only true on fully compressed belts. Any gap in throughput will throw this off since it alternates items 1 for 1.

[taiiat]

sorry if i missed something as i only read the first page, and bit of the second, last page:

i'm far from an expert on this game - but what should help significantly is having Splitters which are faster than the Belts they are attached to.
this will reduce gaps in flow significantly. the Splitters are always the bottleneck, as they do something other than just move forwards, so if they are functionally faster than the belts they're connected to, they are no longer the bottleneck.

expanding the system larger and larger compensates for the bottleneck on each Splitter. eventually getting small enough where it doesn't leave an open gap as it creates less gap than one item worth of space.
alternatively extra Splitters can be placed inline between exchanges to compensate for the gaps created, by splitting the Belt back to itself. that's a bandaid ofcourse...


obviously if you're already using Tier III Belts this is defunct... honestly having a 'Rapid Splitter' that ran on Electricity, would be a late game way to sort and balance things at maximum rate.
but that doesn't solve things currently ofcourse.

- - - - -

additionally, Splitters don't actually move things evenly between belts, you'll notice depending on which side of the Belt it comes into the Splitter, as to where it'll come out of it.
so a belt trying to fully compress one resource must note that. you'll probably end up with self looping Splitters in some form to compensate for it.



that's all i can contribute to this, giant scale spiderweb belts aren't something i've needed to deal with just yet.

[sckuzzle]

Taiiat,

Splitters can't split more items than are coming in nor can they combine more items than there is space for on the output. Splitters are never a bottleneck so long as they have as many output slots as there are inputs (so long as they are the same color as the belts they are with).

Try making a balancer system with yellow belts and splitters, then upgrade the splitters to red. You'll notice that any bottlenecks that were there previously are still there.

[hansinator]

So did anyone find an answer to this topic?

[ribsngibs]

Yes...ish. It seemed like the easiest solution and definitely most straightforward is to simply place two NxN balancers in series. If you pass only A belts in and take only B belts out, the first balancer will spread the A belts onto N, and the second one will put the N belts onto the B you're drawing from. Should be no throughput issues. Aside from the weird left-right side belt weirdness that you can see on this page of discussion (which can affect even a very simple 1->2->1 belt pattern, so that problem is basically unsolvable imo.

[Frightning]

So I got a pretty complete solution to the version of this problem I posted on math.stackexchange from one David Ketcheson, this solution ignores the 2-lane nature of belts and splitter memory, but models everything else. It shows that the classic 4x4 balancer is UTU without considering those effects (and in my tests, most of the oddities in throughput vanished eventually other than the rare spacing artifact that probably can be explained by the tick rate of the simulation and resulting rounding errors). He also gives 3x3 and 5x5 balancers that are UTU. Attached to his post is a link to a notebook he compiled while working on the problem, which contains algorithms that will iteratively test a given balancer for the UTU property.

Stack Exchange post: http://math.stackexchange.com/questions ... 16#1950616
Notebook: https://gist.github.com/ketch/b0e30aae8 ... 79d6b6ca5d

Unfortunately, he has not, as of yet, found an algorithm for producing UTU balancers, and I suspect it's not as straightforward as one might expect, based on what I understand of his solution and the example balancers he found that are UTU (note that the 5x5 UTU balancer he found may not be minimal in # of splitters used).

[hansinator]

He must be wrong. All the constructions the notebook says are UTU fail miserably when I test them.
Edit: And it is not because of the lanes of a belt. If I put lane rebalancers in between everywhere it fails, too. If you operate with one lane on all belts only, it will still fail.

Edit 2:
In the 4 lane balancer case it will work when there are lane balancers between input and exit splitters and if you make sure that it never reaches max compression on all belts. If you go from full flow of all 4 belts to 3 in 3 out it will fail.

I'm testing various configurations since weeks. You can get an UTU for any balancer if you put two in parallel and lance-balance the outputs. A series configuration will not work universally.

I suggest this lane balancer, it doesn't balance the output lanes but treats the inputs fair. A side-loading configuration does not work because it doesn't draw from input lanes equally.


This one also balances the output lanes but is only for one belt.

[ribsngibs]

I agree - it sounds like he is new to Factorio and may be solving a slightly different problem? I'm not sure. But for instance, his 3x3 balancer is indeed not throughput limited for any subset of active inputs and outputs (I think), but unfortunately it is not a balancer.