Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Larix]

Yep, i did it again. Invented yet another sub-discipline of minecart logic and successfully applied it. The machine is not fully debugged, but got the right result in the test run (and the repeat).

I added 206+230 (1100 1110 + 1110 0110), and got the correct 436 (1 1011 0100).

I made a video of the repeat run: http://mkv25.net/dfma/movie-2661-signallesseight-bitadder

What's so peculiar and new about it? Well, the only moving parts in this adder are the minecarts. Construction took four in-game months, requiring a lot of digging and engraving, as well as the building of one bit of floor, seven track stops, 32 ramps inside the adders and about 40 more to speed up the read-out of the two topmost bits. 24 minecart routes needed laying out and supplying with carts.

And of course, the chief metric of complicated machinery:  Mechanism count: zero. The output consequently only consists of minecarts being placed in the output array or not.

Operation speed depends on the inputs of an adder - the slowest propagation of operation i had was 129 steps, the fastest 56 (yes, shorter than the reset time of a pressure plate). There was also a 45-step propagation in there, but that was actually too fast and will need fixing (didn't cause a false result in this case, though). The last output takes 129 steps from being triggered until the cart reaches its output position. The whole calculation from dwarven push to complete result took 903 steps.

The A- and B- input carts automatically return to their starting positions, only the activated sum carts leave their circuits, to actually provide an output. To change the calculation input, carts must be assigned (and removed) via the route management menu. Obviously, this is ludicrously slow.

The whole "calculation" consists of nothing but minecart collisions, using carts of different weights and with different speeds to stand in for the possible input combinations. Due to conservation-of-momentum calculations, the pushed carts in those collisions gain different speeds depending on inputs, and those speeds are separated into four different outputs by the design of the adder cells. Carts used are adamantine, willow and oak (indistinguishable by pressure plate); to push, either an adamantine (zero) or willow cart (one) is used, the pushed cart is either willow (one again) or oak (zero).

I think i'll have to explain this stuff some more at a later date. For now, some pictures:

Spoiler: four bits of adder, main level (click to show/hide)

Spoiler: top level, cart return paths and the like, four bits and a half (click to show/hide)

Spoiler: result display (click to show/hide)

[Larix]

Alright, i've debugged the device and it seems to be running its calculations reliably. There were some tight corners to navigate, but all conceivable input-output combos have worked correctly in the final tests.

What's the guiding principle? Pretty simple:

Spoiler: collisions as calculations (click to show/hide)

if a cart moves into another, it will stop moving entirely, passing its entire momentum on to the other cart. In most cases, the pushed cart's speed after the collision is limited to the incoming cart's speed before the collision. This definitely holds true for moving carts slamming into standing carts, you cannot accelerate past incoming speed this way.

If a heavy cart pushes lighter-weight carts, the outgoing speeds will be all the same (equal to incoming speed), regardless of the exact weight of the pushed cart. However, if a lighter cart pushes a heavier (or at least no less than same-weight) cart, the outgoing speed depends on the weight differences between carts. As a formula, outgoing velocity v(o) is the product of incoming velocity v(i) and incoming mass m(i), divided by outgoing mass m(o):

v(o) = v(i)*m(i)/m(o) (capped at v(i) in moving-vs.-standing collisions)

By bashing carts of different weights and speeds into standing carts (once again of differing weights), we can turn different inputs into specific speeds as output. So once we "measure" those speeds, we have properly processed our data. Turning speed into measurements can be done in different ways, e.g. by using a timing circuit and measuring how far a cart goes in a specified time. This can be done simply via falling - carts and creatures seem to have the same gravitational acceleration regardless of any other speeds, so two carts starting at the same vertical speed will always fall the same distance in the same time, but will cover different horizontal distance while dropping if moving at different speeds. Trivially, you can simply offer a series of separate holes in the floor; carts take seven turns (or was it six?) to register on the lower level, so that e.g. a wall will block them from going forward, while a faster cart can jump past that wall.

But with minecarts, we have other, less space-consuming options.
* Carts coming from flat track will only enter a downward ramp or take a track corner not backed by wall if they're moving at ~50k speed or less. By offering such architecture, we can divide "derail-capable" from slower carts.
* Carts passing over downward ramps perpendicular to their movement direction can pass through or be diverted (to varying degrees) depending on their original speed. This is notoriously tricky to regulate, since the speed bands of different pathing behaviour are quite narrow and thus immensely speed-sensitive, but i've pulled this off successfully.
* Carts of different derailing speeds can be separated by offering architecture that slows them down, like opposing impulse ramps or high-friction track stops. Opposing impulse ramps are quite elegant, because they can have connected track above, directly moving the cart off to the output path once speed is low enough.

Spoiler: translating into binary-ish logic (click to show/hide)

I had experimented with a three-result switch before (two different paths on ramps, one derail) which worked nicely, so a full adder was just the next step (towards a fully programmable signal-less computer ); the base principle demands handling three binary inputs (Summand A, Summand B, Carry) with eight possible combinations, resulting in four distinct outputs, manifested in two binary outputs (Sum, Carry).
Ideally, the carry should be produced in a form that can directly be taken as input by the next adder.

Spoiler: Speeeed! (click to show/hide)

Quite sensibly, i chose different cart weights as input for the two summands. The carry would be represented by cart speed, regulated by different amounts of acceleration, reached by different input paths:

Code: [Select]


###########▼#
A▲▲▲▲▲▲▲▲▲═▼B
╚════╝

###########▼#
A╚╚╚╚╚╚╚╚╚═▼B
╚════╝

Cart A is pushed either east or south (by a dwarf in the prototype tests). On the southern path, it goes over four more ramps and thus crashes into the output cart at B with much higher speed.

Two different weights are possible for cart A, two for cart B. Cart A is either adamantine (8kg) or willow (15,6), cart B either willow (15,6) or oak (28). Thus, the output speeds will be the following percentages of input speed:
adamantine vs. oak ~29%
adamantine vs. willow ~ 51%
willow vs. oak ~ 56%
willow vs. willow 100%

Since the incoming cart will stop upon collision, i opted for a "self-cleaning" design: put a ramp (that the cart jumps over) under the spot where it'll stop and construct a return track to get the cart back in position. This can be done with a simple return loop on the same level, but for the more complicated circuits, the only useable direction to pipe carts back into position was from above.

Spoiler: processing (click to show/hide)

Code: [Select]

#########
B▼╗▲▲▲▲▲##  ╔══
#▼║####3#║  ║
#01▲▲2═╔═▼▼A'▲▲
#║║####▼###▼##
#║║####▼##═▼##
#║╚══▼▼S###║##
#╚═══╚═╬═══╝

#########
╬╬╗╝╝╝╝║#
#║║####║#
#║║╚╚══╔═╚═╬
#║║####║###║
#║║####║##═╝
#║╚══╔═╗###║
#╚═══╚═╬═══╝
The outgoing cart is immediately offered a ramp to enter. It will only do this if moving at less than derail speed. If the cart enters the ramp, it's then confronted with a NSEW ramp, with only S as down direction. Sufficiently slow carts will leave to the south (0), faster carts have enough speed to pass in a straight line and leave to the east, turning the track corner there and taking their own path south (1). The slowest carts are produced by an adamantine cart hitting an oak cart after going over the reduced number of ramps.

A cart leaving at derail speed will pass over the ramp and track corner immediately behind it and goes into the series of opposing impulse ramps. All but the fastest lose enough speed to take a corner and leave before passing the fourth ramp. They are then moved south and return to the operation level from another ramp, emerging on path "2". The fastest carts go past the fourth ramp, bang into the wall and are accelerated south (3) at a more appropriate speed.

For output, a cart is located in position S. Both fast carts going through the ramp and fastest derailing carts enter double-ramps which make them bump into this "sum" cart, pushing the cart to the output display area and sending the pushing cart back out the ramp. The "carry" and "no carry" result paths are then combined and sent to push the Summand A' cart of the next cell, sending it either on the path with more ramps (if carry was produced) or on the "slow" path (if no carry) before cart B is pulled up to the return path and brought back to its starting position.

Disclaimer:
I simplified the circuit to show the principles, leaving out the return paths, misrepresenting the "flyover" of less-than-top-speed derailing carts and leaving out some of the extra impulse ramps i installed to regulate and speed up the processing.

Afterthought: the concepts i came up with to set additional carts in motion suggest that a double-ramp with _possibly_ a cart sitting on its exit tile offers yet another way to build a binary switch:

Code: [Select]

I
▼
▼
╚═O
║

The evaluating cart comes from the south, goes through a simple double-ramp pit (NS track) and tries to leave to the north. If the "input" tile there is occupied, the evaluating cart is reflected, leaves the ramp to the south and follows the corner to the east, with a "true" Output. If the location is not occupied, the cart leaves to the north. If there's wall directly north of the input location, each evaluation will result in a cart standing in the input position, if there's open track to the north, there'll always be an outgoing cart to the north and _no_ cart in I after evaluation.

[expwnent]

That's quite promising. If you can get past the 100 tick delays inherent to water-based dwarfputing, then you can make circuits that are a lot faster.

[Krawdad]

Wow that is a pretty cool concept and you did a good job of explaining it. Bravo!

Also, next time somebody says that the DF graphics are hard to understand just show them those screenshots and say, "No way, look at how easy it is to see that this system of minecart tracks can perform binary addition!" 

[Larix]

Before anyone asks: this machine does not kill goblins. So far, it has crippled one cat and broken a dwarf's left foot. Since it cannot take input other than dwarven pushes and theoretically creature-opened doors (no mechanisms, remember), its ability to communicate with the rest of the world is... well, "limited" would be an understatement.

I expanded the thing by adding a bit shifter that goes to town on the result of the calculation. Movie: http://mkv25.net/dfma/movie-2662-advancedsignallesscalculator

Spoiler: How do i shift bit? (click to show/hide)

Bit shift basically means you take the content of one bit and move it to the next higher (or lower) bit. Bits going "out of bounds" are either discarded or just shifted back in at the opposite end. I opted for the second possibility, because this way i didn't need to set up a discarded bit depot.

The hinted-at "minecart bouncing into another cart at the top of a ramp" concept proved exactly what i needed for the purpose. Primitively, it'd be built like this:

Code: [Select]

out
#X═shift in
.▼.
.▼═shift out
.║.
.in

z-1
###
#║#
#╚#
###

Incoming cart goes through the ramp-pit and tries to leave north (towards "out"). If a cart is in position X, the incoming cart bumps into it and sends it off towards "out" anyway, while the incoming cart rolls back, takes the corner ramp outside and goes to the _next_ bit location (shift). If the previous bit was set, another shifted cart will arrive from "shift in" and enter position X. Obviously, the shifting carts must arrive in their new positions _after_ the evaluation cart has gone through, but since the latter moves in a straight line, while shifting carts have to go around loop tracks and start out by reverting on a ramp, timing's never been a problem.

Since, however, every double-ramp pit provides a significant amount of acceleration, carts would soon derail, go on silly jumps and mess up the process. Thus, to bleed off excess speed, every second passage between bits isn't a simple double-ramp pit, but rather a "drop hole" with wall behind (using smooth floor instead of track on the bit position to force carts to jump, bang into the wall and lose horizontal speed), where the cart will then re-accelerate on a track ramp and then go through the standard test ramp.

Spoiler: How much do you want to shift? (click to show/hide)

Since shifting bits just once is _so_ passé, i added a "counter", another collision-evluator, but this time, it doesn't check the evaluated cart's presence, but rather (sort of) its position:

Code: [Select]

   stop
in═╚▼▼0123456══out   Track on ramps: ══

The incoming cart goes through the ramp-pit and continues until it hits the resident cart. The collision moves the sitting cart of and stops the incoming cart in the _previous_ position, i.e. the circuit "counts down". The outgoing cart starts the next round of the desired repeat action, and returns for the next check. This continues until the resident cart is in position 0. Upon collision, the incoming cart will now not come to rest in the loop but rather returns and goes onto the "stop" path. Of course, the resident cart will once again start on its round. That could be a problem. Well, never fear, the "continuation" path consults _another_ "presence gate", and the "stop" path knocks the resident cart out of that location, so that the "continuation" cart is _not_ reflected but rather stops in that position:

Code: [Select]


st.in.#
═══╔▼▼X═
...║  ▼
 stop ▼
 out  ╚═ cont.out
      ║
    cont.in

All track on ramps is straight along the length of the ramps.
Bit of a mess to look at, but that's what happens: as long as the count goes on, the continuation cart comes from its "in" direction, bounces against the cart at X without moving it (since there's a wall to the north) and returns south then east to continue operation. If the "stop" got triggered, the "stop" cart arrives first, bumps into the cart at X and moves it out of position (since there's no wall to the east), returns west then south to do whatever's supposed to be done when operation stops. The continuation cart will check the place a bit later, finds no cart present and climbs the ramp and comes to rest against the northern wall, making it the new resident cart.

I had to forbid all carts in this circuit during operation - they'd start and stop over and over, and they'd of course keep shifting roles all the time, so the poor haulers would have gotten mortally confused.

Well, that's the _logic_ of the matter. I'm not mentioning the _nuisance_ - ramps, when used for complicated pathing tricks, often impart diagonal movement which must be carefully cancelled out via track corners, excessive speed can be gained in the most innocuous circuits leading to derails etc. Building the whole thing took about a month (my miners and engravers are pretty good by now), but ironing out all the bugs took over six weeks and lots of colourful curses at the screen.

I think the countdown controller qualifies as a primitive approximation of a program loop; it can be set to different values, and with some completely insane efforts, it could probably be set by a running program itself. The whole expansion took a whopping three extra minecart routes and a bunch of impulse ramps to keep things speedy. Apart from that, just mining and engraving. Still not a single mechanism.

PS: i think it _is_ a proper (if crude single-use) "while loop", i.e. it goes

- while counter >0
{reduce counter by one; do something}
- once counter = 0
{do something else}

now, this circuit's only "do something" option is "shift stored data one position to the left" and the only "do something else" option is "halt". Giving other options, however, would be possible. Not worth the effort, but possible.

It also does "add summands A and B, send sum to storage" before triggering the shift loop, so it's notionally performing an algorithm which is sequential and performs a (condition-limited) loop, which could be made infinite by removing the counter cart. I guess this system is capable of universal computation (what are good requirements for that? the wikipedia page on turing completeness is too advanced for me), but proving it is far beyond my capabilities.

To reiterate: the major peculiarity of this whole system is that it does all its operations _without processing signals_. All data it processes are positions, weights and speeds of minecarts, and it notionally is not fully bound to the binary logic built into DF's signal processing. Especially in the bit shifter and countdown loop it can be seen that a well-designed signalless circuit can process data at speeds in the 20-50 step range, potentially faster than many kinds of signal-based logic - e.g. when "off" signals from pressure plates or delayed-reaction buildings are in use, but also logic that must observe pump switchoff latency. Of course, a mechanical adder can add two arbitrarily long numbers in ten steps, you can't really compete with that.

[wierd]

it's a shame about some of the really long signal lines between your registers.

Latency between them can approach asinine levels if the bit depth is great.
An interesting idea might be to stack it vertically beween Z levels with hatches and switch tracks? That way you could make use of the "near instant" travel over a Z level, and keep total path distance between components low.

One of these days, I will compile all your logic gate structures together in front of me, and assemble something neat out of them. Timing looks like it is going to be a major issue for the creation of any large scale project made from multiples of these systems. 

More than likely I would just produce a re-implementation of a simple 4 or 8 bit cpu with an instruction word store done with "wire logic" (static minecart tracks), with some minimal compliment of RAM and an output device.

I should see if there is a way to mass-create the needed structures using DFHack and some kind of template.  That would produce the hardware, but leave the software up to me.

Something that exploits impulse ramps does not need dwarven interaction, so the computer could be installed way deep down in the bowels of the fortress, and be used to do automatic fun stuff in the fortress upstairs.  hmm..... Maybe later.

[Miuramir]

Before anyone asks: this machine does not kill goblins. So far, it has crippled one cat and broken a dwarf's left foot. Since it cannot take input other than dwarven pushes and theoretically creature-opened doors (no mechanisms, remember), its ability to communicate with the rest of the world is... well, "limited" would be an understatement.

Theoretically, you could have input routines that checked for the presence of things that temporarily block carts, although it would require quite a lot of spare carts (effectively, a cart-machinegun across an invader path for instance). 

Perhaps more usefully, as carts can pick up and deposit fluids, you could arrange for some mechanism-free I/O that way.  Detect the onset of winter by whether a cart plunges down into water or skids across the ice?  Doomesday dead man switch where if enough buckets of water aren't poured down a hole in a specific "temple ritual" in a given time period, a timer increments; when the timer reaches some value, the fortress implodes into the volcano?  Some of these may not be *practical* in terms of complexity, but should be *possible*. 

... I guess this system is capable of universal computation (what are good requirements for that? the wikipedia page on turing completeness is too advanced for me), but proving it is far beyond my capabilities.

Strictly speaking, it requires infinite resources.  In practice, it is usually used as long as the resources are extensible; in other words, both computation and storage can be expanded by fairly arbitrary amounts given enough resources.  You've got a "branch if zero", a decrementer, and an adder, which is most of it; and I think you theoretically could have extensible memory although frankly the cart-logic level here is complex enough that I haven't had the time to work out all the implications.  I think you could probably get a way to read the output and store it into memory; the other way around may be trickier (ultimately, you would need to be able to treat a memory location as the input to the adder, via copy or move). 

At a more general level, you've got a nice adding machine, but what makes it a universal computer is the ability to use the output of one adding machine as the input of another, with some sort of flow control possible.  (With a suitable design, the second adding machine may be the first one again, but in an updated state.)  I think it's theoretically doable with this design style, but not sure whether it's practical. 

None of this should be construed as a criticism; you've got a very clever design that pushes the boundaries of dwarven computation in some interesting new directions. 

[expwnent]

In case you haven't already, you should definitely add this to a talk page on the wiki and link to it from the dwarfputing page to ensure it doesn't get lost forever.

[Larix]

Good idea. I've made another branch off my user page: http://dwarffortresswiki.org/index.php/User:Larix/MPL/6

I fiddled with the possibilities. I'm not sure using this logic to power your RAM would be a good idea:



This is a read-/writeable one-bit memory cell under this logic. The basic interactions just don't lend themselves to this application; it can be done, but it's hilariously overcomplicated.

The cart in the northeast is pushed south to read the state of the memory without changing it. It is pushed straight west to set memory to one, and pushed north to set memory to zero. In order to set the cell to zero, it must _first_ be set to one - setting to zero if already zero otherwise bugs up.

On the other hand, binary incrementers built under this logic are easy to build and fast (recovery time of 45 steps when switching to "one", just under sixty when switching to "zero". Counter loops are similarly easy to build, although not as fast (~130 steps per iteration reliably). To demonstrate, i built a bunch of connected loops and a stack of twenty incrementers. The construction can trivially multiply several numbers. It's not a real option for multiplication, since it works by incrementation, making it abysmally slow; in addition, "setting" it to a specific value is insanely complicated, i just went and etched the desired factors into the stone - i.e. i _built_ the desired calculation. To get different factors, it would be necessary to dig some new holes and erase/engrave a few track bits. Since the calculation performs at ~2600 per year (a calculation with a result of 2600 takes a year to finish; one for 1 000 000 takes 400 years), the time spent "entering" the equation is not a real factor, though.

Video of the machine in action:
http://mkv25.net/dfma/movie-2663-multiplicationbyloopedincrement

I calculated 1x1x1x1x2x3x4x5x6x7 with it, i.e. the result was 7!, but it wasn't actually programmed as a factorial. It takes ten factors ranging to eleven each (a zero _does_ give the proper zero product, unneeded factors must be set to one), the actual product is the numbers of turns carts took through the last-factor loop; for display, that loop is connected to the incrementer. It calculated the number correctly, but of course i had mis-engraved a single tile, so there was a little mess at the end; fortunately, it was salvageable and the fixed machine calculated 6x7 and then stopped properly.

To calculate 7!, it took 21 months game-time.

It's not really a calculator, but could probably be used to control program loops and branches.

Optimisation update: i got the loop to a minimum return time of precisely 100 steps (if loaded with same-weight carts) during continuation. The end-of-loop routines slow the overall counting speed down a bit, but not much when the loops are fairly long.

The incrementer, however, is impressively speedy. It can take a new input every forty steps. It can even be run by a 33-step repeater and keeps accurate track - i.e. if you ran a multi-stage binary counter consisting of such signalless incrementers off a top-speed repeater (powerless minecart repeater, obviously), only the third stage would be slow enough that signal-operated counters could handle it:

Code: [Select]

...Z     
╔═╗▼     ╔═╗║
║#B▼     ║#╬╝
║#1║     ║#║║
║#▼║     ║#║║
║#▼╝     ║#╚╝
╚═A#     ╚═║#
..▼        ║
..▼        ║
╔═╝      ╔═╝
╚D╝      ╚═╝

D - Driver cart (cycling in the southern loop every 33 steps)
A, B - "counter" carts, switch role between pushing and pushed every round.
1 - "on" position of the counter cell.
Z - push cart's position of the next counter cell or other output.

If the to-be-pushed cart is in the "off" position at B, the incoming cart stops in the "on" position at 1 after the collision. If the 1 is occupied, the incoming cart rolls back into the pit, gets turned around to the east, goes around the corners to the north, pushes the next cell's pushing cart at Z, bounces back through _that_ pit and gets lifted out to the "off" position at B.

In the 33-step incrementer, the driver cart enters its push pit one step before the counter cart reaches position A and if a "carry" was sent, the push cart enters the pit inside the counter cell before the other cart reaches position B.

Of course, slower oscillators are also usable, e.g.

Code: [Select]

  A
  ▼
  ▼
╔═╝
║ ║
╚═╝

Has a period of exactly 40 steps, and reconfiguring the incrementer loop to a five-count, like so

Code: [Select]

   X
 ╔╗▼
#╬╝▼
 ║║║
 ║▼║
 ║▼╝
 ╚╬#
  ▼

sends one output for every five inputs received. With the 40-step oscillator, you get a (tested and proven) 200-step signal at X, which can be converted into a pressure plate signal for a clock. Materials needed - four minecarts (one driver, two counter, one receiver). If you want to make it stoppable, you'll also need one building material and two or three levers to build and link up a track stop.

The absolute minimum distance between countable inputs i could realise under this doctrine is 29 steps, feeding a count-to-four circuit (output period of 116 steps); you could place pressure plates on each of the four possible "rest" positions in the circuit, and you'd get the exact number out of it once stopped, so the "off" plates could recover.

I also worked on the loop a bit and got one with a maximum capacity of five to a regular circulation time of 69 steps, quite a bit faster than i had thought possible. It takes a bunch of impulse ramps to speed up the return of the counting cart from the "while-operation" trigger back into the main loop, and a highest-friction track stop to get back down to proper operation speed. In the "end loop" round, the controller cart is pushed out of the counter cart's way a full four steps before the latter arrives. Plenty of time. Longer loops take longer to run, but ~80 steps are still possible with a ten-capacity loop. So that's two actions that can perform too fast for pressure plates to keep up - "while loops" and incrementation. To actually get those speeds, machinery must be very tightly packed together. (Impulse) ramps can help with transfers between processing units, but for operations in ramps, speed must be regulated down to less than derail, or the counter carts end up moving too quickly to properly switch off when the loop ends.