GPS in Factorio

This board is to show, discuss and archive useful combinator- and logic-creations.
Smart triggering, counters and sensors, useful circuitry, switching as an art :), computers.
Please provide if possible always a blueprint of your creation.
Post Reply
quale
Long Handed Inserter
Long Handed Inserter
Posts: 54
Joined: Thu Aug 15, 2019 4:16 pm
Contact:
Contact quale

GPS in Factorio

Post by quale »

This is basically useless because you can just get your coordinates. I just thought it would be fun. It uses the Chinese remainder theorem on blueprints snapped to various grids to find your location.
Factorio GPS.png
Factorio GPS.png (4.16 MiB) Viewed 2321 times


Build the receiver first. Then place the other blueprints over the ‘antenna’ in the northeast, as ghosts if you like. Demonstration video. You should now know your location.
Top
blazespinnaker
Filter Inserter
Filter Inserter
Posts: 665
Joined: Wed Sep 16, 2020 12:45 pm
Contact:
Contact blazespinnaker

Re: GPS in Factorio

Post by blazespinnaker »

Useless things are awesome. Thanks for sharing. I played around with it a bit just for fun.
OptimaUPS Mod, pm for info.
Top
User avatar
MEOWMI
Filter Inserter
Filter Inserter
Posts: 309
Joined: Wed May 22, 2019 12:21 pm
Contact:
Contact MEOWMI

Re: GPS in Factorio

Post by MEOWMI »

It took me a lot of thinking to even understand how generating the signal works. That's impressive that you don't need more data points than that to generate the signal! Definitely a very worthwhile creation!
Top
quale
Long Handed Inserter
Long Handed Inserter
Posts: 54
Joined: Thu Aug 15, 2019 4:16 pm
Contact:
Contact quale

Re: GPS in Factorio

Post by quale »

Thanks. I really like how seemingly simple it became myself. I’ll explain it now. Most of the combinators are to drive the display. Beyond the antenna, you only need one arithmetic combinator (northernmost) and one constant combinator (third from the south). The red wire inconspicuously connected to the power pole next to the X coordinate display holds that value. The real smarts are in the arrangement.

You need some numbers with an LCM of at least 2 million, the size of the world. I went with lcm(13, 17, 19, 21, 23) = 2028117, a decent tradeoff between number of placements and combinators per placement. Some alternatives are lcm(34, 37, 39, 41) = 2011542 and lcm(7, 8, 11, 13, 15, 17) = 2042040. Those numbers should be coprime for maximum effectiveness. 12*18 = 216 ≠ lcm(12, 18) = 36 = lcm(4, 9) is just a waste, for instance. You’ll also want to make sure you can’t overflow, although that isn’t really a concern at this scale. An easy upper bound is the number of numbers times the modulus, i.e. 5*2028117 = 10140585, well below 2^31. You’d have to be more creative if Factorio were much larger.

Now comes the actual Chinese remainder theorem. Suppose you have two lines of combinators:

13: 0 1 2 3 4 5 6 7 8 9 10 11 12
17: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Each works very well on its own, but the range is obviously rather limited. To combine them, run the extended Euclidean algorithm on a=13 and b=17. That yields gcd=1, x=4, y=-3. The LCM is a*b/gcd=221. Multiply the values in a’s combinators by y*b/gcd=-51. Multiply the values in b’s combinators by x*a/gcd=52. You could do that with arithmetic combinators, but you can just as well change the constant combinators.

13: 0 -51 -102 -153 -204 -255 -306 -357 -408 -459 -510 -561 -612
17: 0 52 104 156 208 260 312 364 416 468 520 572 624 676 728 780 832

Because you only care about congruence mod 221, you can reduce these numbers. That is important to avoid overflow later. I made them non-negative so a modulo combinator (which preserves the sign of the dividend) likewise has a non-negative result. Mixed signs could produce haphazard outputs in (-221, 221) instead of the clustered [0, 221), requiring another step.

13: 0 170 119 68 17 187 136 85 34 204 153 102 51
17: 0 52 104 156 208 39 91 143 195 26 78 130 182 13 65 117 169

Now suppose you want to add a line of 19. You can perform the same steps again, this time treating 13 and 17 as a unit with their LCM. The extended Euclidean algorithm on a=221 and b=19 yields gcd=1, x=8, y=-93. The LCM is 4199. Multiply the values in a’s combinators (both 13 and 17) by -1767. Multiply the values in b’s combinators by 1768. Reduce again as desired.

13: 0 1938 3876 1615 3553 1292 3230 969 2907 646 2584 323 2261
17: 0 494 988 1482 1976 2470 2964 3458 3952 247 741 1235 1729 2223 2717 3211 3705
19: 0 1768 3536 1105 2873 442 2210 3978 1547 3315 884 2652 221 1989 3757 1326 3094 663 2431

You can repeat this process with any groupings you like. The order can have an effect if your numbers aren’t coprime. Otherwise, the end result is the same. I arranged the math to work regardless. For better efficiency, only keep track of multipliers at first. The first pair of multipliers was -51 and 52. The second pair was -1767 and 1768. Fill line 19 with increments of 1768. Now, going backward, multiply the previous pair of -51 and 52 by -1767. Reduce mod 4199 if you like, yielding 1938 and 494. Now you can fill line 17 with increments of 494. 1938 would go to the previous pair if it existed, but since it’s just line 13, fill that line with such increments.

To get your location, all you have to do is add the values (circuit wires are your friend) and do % lcm in an arithmetic combinator. To support negative values or any shifted range you please, add a constant to the output of the arithmetic combinator. A constant combinator will do that for you. You’ll also need to adjust grid offsets. -2099 would give you a symmetrical range centered on zero. That is then also your grid offset, which you can reduce modulo the step size. -2099 is congruent to 7 mod 13, 9 mod 17, and 10 mod 19.

The display is similar in the complexity it hides. It supports the full 32-bit range. It hides leading zeros. It does show a single 0 for zero. It shows a minus sign in the right place. It does everything in three ticks.

The first phase divides by powers of 10. Each of the 11 places gets its own signal. One arithmetic combinator divides the number by the corresponding power of 10, provided by a constant combinator on the other color wire. Another divides by a tenth of that, to provide access to the next most significant digit under the same name, amenable to parallel computation using each. The ones place is passed through separately to exempt it from treatment as a leading zero in the next phase. The input isn’t connected directly to the next phase as ones place, both to maintain a constant gate delay (so the display doesn’t glitch no matter how the input changes, unimportant as it may be in this application), and to render interference from the other combinators (using each) benign.

The second phase finds the glyph index for each place. It is only implemented once for both coordinates. The arithmetic combinator is simply each % 10, producing an output in [-9, 9]. Those are the glyph indices for all digits, with nonzero digits duplicated. One decider combinator adds 10 if the input (ignoring the ones place) is zero. That makes 10 the glyph index for a leading zero. There are two problems with that: you can’t find zero signals using anything/everything/each, and you can only output the input or one. I solved that with a constant combinator on the other color wire adding 10 to all inputs. Now, if the adjusted input is 10, that input is sent to the output. The other decider combinator adds the minus sign. It outputs one if the next most significant place is in [-9, -1]. Because this is also a leading zero, the glyph index becomes 11. It performs the range check by adding -2147483648 to all inputs using a constant combinator. That shifts [-9, -1] all the way up to [2147483639, 2147483647]. Then you only have to check the lower bound, because anything above the upper bound will have overflowed.

The third phase selects the actual glyph from the font to drive the lamps. There is one signal per pixel. The font contains those signals, storing their values for each glyph in different bits. The arithmetic combinator performs each << index to shift the desired bit into the sign bit. The shift amount wraps into [0, 32), so our negative indices end up selecting the least significant bits. Fortunately, no compiler seems to take advantage of undefined behavior in bit shifts. Signals in the font therefore look like 0123456789_-xxxxxxxxxxx987654321 in binary. The lamp turns on if its signal is negative, i.e. the sign bit is set. I went with a seven-segment-like look because it seems most readable at this size.
Top
Post Reply

Return to “Combinator Creations”