Mine depletion indicators (Muliplexing/Demultiplexing by Modulo Operations)
Posted: Thu Sep 15, 2016 5:02 am
I've already posted a picture of my base in this thread, but there were questions about my mine depletion indicators, so I thought I'd describe them in more detail.
Problem Statement
Iron, copper, coal, and stone mines can be spread quite far over the map. Each deposit has a finite amount of resources, and once a mine is exhausted a new one must be established elsewhere to replace it. Waiting until your base shuts down due to starvation before dealing with the problem can be frustrating, and constantly visiting your mines to check their reserves takes too much time. In true Factorio style, this calls for an automated solution!
Solution Overview
Each of my mines has six buffer boxes (that's the length of a train car). I use combinators at each mine to produce a signal based on whether there is any ore in those boxes. These signals are multiplexed onto a single circuit network spanning all mines across the map, then that signal is brought back to the main base, demultiplexed, and used to illuminate a set of indicator lights, one per mine. The lights get one of three colors: Red implies a depleted mine buffer. Green implies a supplied buffer. If more indicator lights are built than mines, the excess lights default to blue. Here's what the indicator lights look like. From left to right, 5 coal mine indicators, 10 copper, 10 iron, and 5 stone indicators.
(image rotated 90 degrees to fit the screen better. <--- North is that way)
Details
Signal Values
Each mine generates a simple signal based on the contents of its buffer boxes. There are three possible values:
-- 0 -- An "empty signal" indicating that there is no mine built (or at least it hasn't been enrolled in the circuit network yet)
-- 1 -- This mine has no ore left in its buffer boxes. It is depleted or nearly so.
-- 2 -- This mine has ore in its buffer boxes. Things are probably OK.
This value is computed using two combinators.
1. A decider combinator tied to all the buffer boxes. Rule: IF [ore type] > 0 THEN OUTPUT (1 [ore type])
2. A constant combinator that simply puts a out a signal of (1 [ore type])
At coal mines [ore type] is coal, at iron mines, [ore type] is iron ore, and so on. Here's an example of a copper mine with this setup.
You'll notice that the final signal goes through an extra arithmetic combinator before being put on the circuit network. Bear with me. That's going to take some time to explain.
Multiplexing
Now that each mine is computing its "depletion signal" value we need to get those signals back to the base where we can keep an eye on their values. The trick is to keep track of which signal came from which mine. You could try to keep each signal isolated to its own circuit network, but that's going to require a lot of careful planning and way too many power poles. Instead we can borrow a solution form the world of computer engineering called multiplexing. If you're not familiar, the basic idea is to smush a bunch of relatively small numbers together into one really big number in such a way that you can reverse the process downstream and retrieve each individual number again. I'll give you an example. Imagine we take the first copper mine's signal and multiply it by 1. The second copper mine we multiply by 10, third by 100, fourth by 1,000, and so on. Then we add all the numbers together by putting them on the same circuit network. We might get a number like this: 022121. Now the status of each mine is represented by a digit. The ones place is the first mine. It's depleted. The 10's place is the second mine. It's OK. The third mine is depleted. Four and five are OK. The 100,000's place is zero, which means we didn't build a sixth mine yet.
OK, so how do you decode that value back at the base? Here we borrow a mathematical tool from the world of discrete math: the modulo operator, or mod for short. Mod just means "the remainder after dividing". For example, 10 goes into 22,121 a total of 2,212 times evenly with a remainder of --1--, so 22,121 MOD 10 is 1, and that's the signal from our first mine. You can get the second mine's signal by dividing by 10 before applying the mod operator, in general, if your big mutexed value is X, then:
Mine signal 1 = X MOD 10
Mine signal 2 = (X/10) MOD 10
Mine signal 3 = (X/10/10) MOD 10
Mine signal 4 = (X/10/10/10) MOD 10
...
Mine signal n+1 = (X/10^n) MOD 10
"But NPC", I hear you say, "we don't have a MOD operator in Factorio!" Well, you can hack one. Factorio's arithmetic combinators use what's called "integer division". That means when you divide A by B, it doesn't round the result. It simply drops the remainder. For example 999/1,000 isn't one-ish as you'd expect. It's zero. So if you take a number, X, and divide it by another value, B, then multiply it by B again, you won't get back to the X you started with. You'll be short-changed by the remainder of X/B. And that's exactly what we're after. In short: X-(X/B*B) = X MOD B.
Great. Now you have enough conceptual tools to build this thing, right? Technically yes, but there's one more optimization we can make to the design. The mine signal values are always 0, 1, or 2. You can't have a 3, 4, 5, 6, 7, 8, or 9. So it's kind of a waste to use an entire decimal digit to represent them. Can we be more efficient? Turns out yes. We can reach back into our bag of mathematical tricks and pull out non-decimal bases. If you've ever had to work with binary, hexadecimal, or octal numbers you've already played in this space. But we're not going to use any of those bases. We have three unique values, so base 3 is the most efficient way to store them. If these words are foreign to you, don't worry too much. What it boils down to is that we can take all the math from above, and wherever we multiply, divide, or mod by 10, do so by 3 instead. You still get much smaller mutex values, and they'll still be fully reversible (i.e. they can be decoded at the base just fine).
So now you'll understand the role of the "multiplexer" arithmetic combinators in the picture above. They multiply the depletion signal value by a coefficient power of 3.
Mine 1 coefficient is 1 = 3^0
Mine 2 coefficient is 3 = 3^1
Mine 3 coefficient is 9 = 3^2
Mine 4 coefficient is 27 = 3^3
...
Mine n+1 coefficient is 3^n
The mine above happens to be copper mine 2, so its coefficient is 3.
Demultiplexing
I've already explained demultiplexing in the previous section, but since I was mean and pulled a change of base on you, I'll take the time to lay out the real base 3 math with an example. Let's use the stone depletion indicator bank from the first picture since it's smaller than iron or copper.
The multiplexed signal for stone comes in from the top on a green circuit. To be clear, all the mines' multiplexed values are on this circuit, but we're only going to deal with the stone signal in this bank of lights.
Two things to notice: 1) there is an ongoing calculation here, and its overall direction is up. That is, the original multiplexed value comes in to the lowest combinator in the bank and intermediate values are going to be passed up (i.e. north); and 2) there is a repeating pattern of six combinators, three arithmetic, then three decider. The three arithmetic combinators demutex a single mine's signal, and the three decider combinators translate the result to the three colors (blue, red and green). Here are the rules inside those boxes. Assume that the mutexed value on the circuit network is X:
Arithmetic combinator 1: A = X/3 ## Remember we're doing integer division here
Arithmetic combinator 2: B = A*3 ## B=X/3*3. This is encoded as stone bricks instead of stone because we need to compare it with the original stone value in the next step
Arithmetic combinator 3: C = X-B ## C=X-(X/3*3). Remember from before this is equivalent to C=X MOD 3.
Decider combinator 4: IF C = 0 THEN Blue
Decider combinator 5: IF C = 1 THEN Red
Decider combinator 6: IF C = 2 THEN Green
Tie a light to the output side of all three deciders et voila! You have an indicator light.
Now recall that to demutex each signal we have to keep dividing by our base (3) until we get to the digit that represents the right mine. So to demutex mine 2's signal value we first need to compute X/3. Luckily we already did that with arithmetic combinator 1. So Just lay down another bank of six combinators and tie the output from the old combinator #1 to the input of the new combinator #1. Continue chaining banks of six combinators together in this fashion until you get bored, run out of space, or think you'll never build that many stone mines.
Side note: There's a single arithmetic combinator at the very beginning (bottom). All it does is take the value of stone and multiply it by 1. This has two benefits: 1) it filters out all the other mutexed values for iron, copper, and coal; and 2) it keeps intermediate values (specifically the bricks value, B, from combinator #2) from bleeding back onto the larger circuit network. Neither of these are strictly necessary to make the system work, but it does tidy up the signals and make them easier to understand at a glance.
Scalability
In theory this method is infinitely scalable. In practice you're limited by the maximum size for a single multiplexed value. If you had a million iron mines your iron signal could get as large as 3^1million - 1. That's a big number. I'm assuming that Factorio uses 64-bit signed integers to store circuit network signal values, in which case you can have up to 34 mines per resource by my estimation. Any more and you'll cause an overflow. That should be more than enough for sane bases, but of course this is Factorio. Sanity is for the weak. If you really want to expand this design to 35 mines and beyond you could do it by encoding the depletion signals for mines 35 thru 68 with another resource besides ore. I'll leave that as an exercise to the reader.
Happy factoring!
Problem Statement
Iron, copper, coal, and stone mines can be spread quite far over the map. Each deposit has a finite amount of resources, and once a mine is exhausted a new one must be established elsewhere to replace it. Waiting until your base shuts down due to starvation before dealing with the problem can be frustrating, and constantly visiting your mines to check their reserves takes too much time. In true Factorio style, this calls for an automated solution!
Solution Overview
Each of my mines has six buffer boxes (that's the length of a train car). I use combinators at each mine to produce a signal based on whether there is any ore in those boxes. These signals are multiplexed onto a single circuit network spanning all mines across the map, then that signal is brought back to the main base, demultiplexed, and used to illuminate a set of indicator lights, one per mine. The lights get one of three colors: Red implies a depleted mine buffer. Green implies a supplied buffer. If more indicator lights are built than mines, the excess lights default to blue. Here's what the indicator lights look like. From left to right, 5 coal mine indicators, 10 copper, 10 iron, and 5 stone indicators.
(image rotated 90 degrees to fit the screen better. <--- North is that way)
- indicator_lights.jpg (75.9 KiB) Viewed 20021 times
Signal Values
Each mine generates a simple signal based on the contents of its buffer boxes. There are three possible values:
-- 0 -- An "empty signal" indicating that there is no mine built (or at least it hasn't been enrolled in the circuit network yet)
-- 1 -- This mine has no ore left in its buffer boxes. It is depleted or nearly so.
-- 2 -- This mine has ore in its buffer boxes. Things are probably OK.
This value is computed using two combinators.
1. A decider combinator tied to all the buffer boxes. Rule: IF [ore type] > 0 THEN OUTPUT (1 [ore type])
2. A constant combinator that simply puts a out a signal of (1 [ore type])
At coal mines [ore type] is coal, at iron mines, [ore type] is iron ore, and so on. Here's an example of a copper mine with this setup.
- mine_combinators.jpg (253.47 KiB) Viewed 20021 times
Multiplexing
Now that each mine is computing its "depletion signal" value we need to get those signals back to the base where we can keep an eye on their values. The trick is to keep track of which signal came from which mine. You could try to keep each signal isolated to its own circuit network, but that's going to require a lot of careful planning and way too many power poles. Instead we can borrow a solution form the world of computer engineering called multiplexing. If you're not familiar, the basic idea is to smush a bunch of relatively small numbers together into one really big number in such a way that you can reverse the process downstream and retrieve each individual number again. I'll give you an example. Imagine we take the first copper mine's signal and multiply it by 1. The second copper mine we multiply by 10, third by 100, fourth by 1,000, and so on. Then we add all the numbers together by putting them on the same circuit network. We might get a number like this: 022121. Now the status of each mine is represented by a digit. The ones place is the first mine. It's depleted. The 10's place is the second mine. It's OK. The third mine is depleted. Four and five are OK. The 100,000's place is zero, which means we didn't build a sixth mine yet.
OK, so how do you decode that value back at the base? Here we borrow a mathematical tool from the world of discrete math: the modulo operator, or mod for short. Mod just means "the remainder after dividing". For example, 10 goes into 22,121 a total of 2,212 times evenly with a remainder of --1--, so 22,121 MOD 10 is 1, and that's the signal from our first mine. You can get the second mine's signal by dividing by 10 before applying the mod operator, in general, if your big mutexed value is X, then:
Mine signal 1 = X MOD 10
Mine signal 2 = (X/10) MOD 10
Mine signal 3 = (X/10/10) MOD 10
Mine signal 4 = (X/10/10/10) MOD 10
...
Mine signal n+1 = (X/10^n) MOD 10
"But NPC", I hear you say, "we don't have a MOD operator in Factorio!" Well, you can hack one. Factorio's arithmetic combinators use what's called "integer division". That means when you divide A by B, it doesn't round the result. It simply drops the remainder. For example 999/1,000 isn't one-ish as you'd expect. It's zero. So if you take a number, X, and divide it by another value, B, then multiply it by B again, you won't get back to the X you started with. You'll be short-changed by the remainder of X/B. And that's exactly what we're after. In short: X-(X/B*B) = X MOD B.
Great. Now you have enough conceptual tools to build this thing, right? Technically yes, but there's one more optimization we can make to the design. The mine signal values are always 0, 1, or 2. You can't have a 3, 4, 5, 6, 7, 8, or 9. So it's kind of a waste to use an entire decimal digit to represent them. Can we be more efficient? Turns out yes. We can reach back into our bag of mathematical tricks and pull out non-decimal bases. If you've ever had to work with binary, hexadecimal, or octal numbers you've already played in this space. But we're not going to use any of those bases. We have three unique values, so base 3 is the most efficient way to store them. If these words are foreign to you, don't worry too much. What it boils down to is that we can take all the math from above, and wherever we multiply, divide, or mod by 10, do so by 3 instead. You still get much smaller mutex values, and they'll still be fully reversible (i.e. they can be decoded at the base just fine).
So now you'll understand the role of the "multiplexer" arithmetic combinators in the picture above. They multiply the depletion signal value by a coefficient power of 3.
Mine 1 coefficient is 1 = 3^0
Mine 2 coefficient is 3 = 3^1
Mine 3 coefficient is 9 = 3^2
Mine 4 coefficient is 27 = 3^3
...
Mine n+1 coefficient is 3^n
The mine above happens to be copper mine 2, so its coefficient is 3.
- mux_combinator.jpg (236.87 KiB) Viewed 20021 times
I've already explained demultiplexing in the previous section, but since I was mean and pulled a change of base on you, I'll take the time to lay out the real base 3 math with an example. Let's use the stone depletion indicator bank from the first picture since it's smaller than iron or copper.
- stone_lights.jpg (272.37 KiB) Viewed 20021 times
Two things to notice: 1) there is an ongoing calculation here, and its overall direction is up. That is, the original multiplexed value comes in to the lowest combinator in the bank and intermediate values are going to be passed up (i.e. north); and 2) there is a repeating pattern of six combinators, three arithmetic, then three decider. The three arithmetic combinators demutex a single mine's signal, and the three decider combinators translate the result to the three colors (blue, red and green). Here are the rules inside those boxes. Assume that the mutexed value on the circuit network is X:
Arithmetic combinator 1: A = X/3 ## Remember we're doing integer division here
Arithmetic combinator 2: B = A*3 ## B=X/3*3. This is encoded as stone bricks instead of stone because we need to compare it with the original stone value in the next step
Arithmetic combinator 3: C = X-B ## C=X-(X/3*3). Remember from before this is equivalent to C=X MOD 3.
Decider combinator 4: IF C = 0 THEN Blue
Decider combinator 5: IF C = 1 THEN Red
Decider combinator 6: IF C = 2 THEN Green
Tie a light to the output side of all three deciders et voila! You have an indicator light.
Now recall that to demutex each signal we have to keep dividing by our base (3) until we get to the digit that represents the right mine. So to demutex mine 2's signal value we first need to compute X/3. Luckily we already did that with arithmetic combinator 1. So Just lay down another bank of six combinators and tie the output from the old combinator #1 to the input of the new combinator #1. Continue chaining banks of six combinators together in this fashion until you get bored, run out of space, or think you'll never build that many stone mines.
Side note: There's a single arithmetic combinator at the very beginning (bottom). All it does is take the value of stone and multiply it by 1. This has two benefits: 1) it filters out all the other mutexed values for iron, copper, and coal; and 2) it keeps intermediate values (specifically the bricks value, B, from combinator #2) from bleeding back onto the larger circuit network. Neither of these are strictly necessary to make the system work, but it does tidy up the signals and make them easier to understand at a glance.
Scalability
In theory this method is infinitely scalable. In practice you're limited by the maximum size for a single multiplexed value. If you had a million iron mines your iron signal could get as large as 3^1million - 1. That's a big number. I'm assuming that Factorio uses 64-bit signed integers to store circuit network signal values, in which case you can have up to 34 mines per resource by my estimation. Any more and you'll cause an overflow. That should be more than enough for sane bases, but of course this is Factorio. Sanity is for the weak. If you really want to expand this design to 35 mines and beyond you could do it by encoding the depletion signals for mines 35 thru 68 with another resource besides ore. I'll leave that as an exercise to the reader.
Happy factoring!
