User:Larix/MPL/7

At long last, i explored the potential of switching high-speed minecarts' path via doors and found that this doctrine offers very attractive options for core operations like decoding and arithmetics, requiring very few mechanisms, no power and only a single minecart per function, while the high operation speeds mean the "linear" evaluations still execute at impressively high speeds.

The atom of cart+door-logic: the door switch[edit]

As noted in the article on minecarts, paths of high-speed minecarts can be switched by offering them a track corner backed by a door or other switchable building. If the building is closed, the cart takes the corner. If the building is open, the cart's speed carries it over the corner and through the opening:

-	>	═	═	╗	D	-	>	1
				║
				v
				0

Note: in all diagrams, some track should be engraved under installed doors. The exact configuration is irrelevant (gets ignored at those speeds anyway), but i've seen a case or two where plain floor underneath the doors seemed to cause misfunctions.

The cart must move at speeds in excess of 50.000 to actually switch, slower carts will follow the corner in every case.

A fast cart can derail over a corner if there's no blocking building behind it. If the door D is open (input signal is on/1), the cart continues in a straight line. If the door is closed (input signal off/0), the straight path is blocked and the cart takes the corner.

Benefits and drawbacks[edit]

The advantages of this door switch are:

takes no power to operate, only signals
the "gate" reacts instantly to changing input when a door is used for switching
evaluation time is very short: a cart passes through the array in less than five steps and both "on" and "off" output are reached at nearly the same time.

The disadvantages are:

depending on layout, a cart could end up in the door jamb while the door tries to close. This results in the door staying wedged open. Proper timing of input acquisition vs. evaluation can completely avoid this.
overall space consumption per gate is pretty large, because most paths require walls to keep carts contained
speeds well in excess of what rollers can do are required for operation. That's fortunately easy enough to solve via impulse ramps. Of coure, due to the high operation speeds, dwarfs should be kept out of active circuits.
high speeds can make picking up the resulting outputs difficult: very fast carts can skip past output pressure plates without touching them. This can be solved by using the checkpoint effect.

Designs[edit]

What makes Cart and Door Logic (CDL from here on) so interesting is that it can't just switch a cart coming from one input direction to one of two output paths. It can also switch carts coming from one of two possible input directions to one of four possible outputs:

			I	1
				║
				╚	═	O	1	'
I	2	═	╗	D	═	O	2
			║	║
	O	2	'	O	1

The cart comes from one of the two input directions I1 and I2. If the door D is open, the cart passes through in a straight line and leaves on path O1 or O2. If the door is shut, the cart is diverted and takes the path O1' or O2'.

This fully granular splitting of the inputs to individual outputs means any binary logic gate can be built with two linked doors. Notably, an XOR gate built only from doors will look like this:

╚	═	╗	#
A	#	╚	╗	#
╚	╗	B	╚	═	N	X	O	R
#	╚	╗	#
	#	║
	X	O	R

With the same position of doors, any other logic-gate function can be derived, it only takes different pathing on the output side behind the doors.

Making use of the full spread, decoding of a multi-bit input to single outputs - e.g. when choosing a function specified by an encoded command or addressing a memory location - can be done at relatively low cost in mechanisms and furniture, while offering a fairly short runtime of three to five steps per "gate"/bit consulted.

As a very attractive option, this doctrine can be used to make a powerless full adder with short runtime and very low mechanism count:

╚	═	╗	#
A	#	╚	═	╗	#
╚	╗	B	1	╚	╗	#
#	╚	╗	#	#	╚	═	╗	#
	#	╚	═	╗	C	2	╚	S	'
		#		╚	╗	#	#
				#	S

Inputs A and B are evaluated. If both are on, a carry is produced (1) and sent to the next adder cell. After the "generated" carry has been tested for, the "equal" (northeastern branch) and "inequal" (southwestern branch) results for the A/B comparison are collected and checked from both sides against the carry-in C. If A and B are equal while C is on, or if A and B are inequal and C is off, a sum is generated (S). If A and B are inequal and C is on, a "propagated" carry (2) is sent to the next adder cell. If the sum is not generated, a "non-sum" output can be read at S', e.g. to actively clear a bit at the register to which the result is written.

While this is a ripple-carry adder, the evaluation proceeds at less than ten steps per added bit. If the starting speed is at the limit of what's reachable by ramps, a twelve-bit addition takes less than 100 steps for the evaluation.

What i find particularly interesting about this adder is that it does the complete addition with three switchable doors per bit. Doors A and B are only linked to their input(s), door C is generally linked twice, to both the generated and propagated carry plates of the previous bit. Depending on the design of the components the adder outputs to, a single sum plate per bit could be sufficient, depending on the memory architecture used.

Memory[edit]

Memory cells can of course be built in CDL, and while they tend to take up a lot of space, they react extremely quickly and can be run with very low tolerances. A data-type memory cell with extended functionality can be built like this:

.

#

╔

╗

#

╔

╗

#

▲

║

#

╗

║

#

▲

║

#

╗

║

#

╔

▲

╗

#

▲

║

#

╔

╝

╗

#

╗

║

#

^

▲

r

╔

═

╗

╚

╝

#

╔

╗

╬

╔

═

╗

╚

╝

#

▲

#

╔

╚

▲

╝

e

╝

d

#

╔

#

╔

╚

╔

╝

╚

╝

╗

#

▲

#

▲

#

║

#

║

╔

#

╚

#

║

#

║

╚

═

╝

#

╚

═

╝

╚

═

╝

#

╚

═

╝

#

b

u

i

l

d

i

n

g

s

a

n

d

t

r

a

c

k

(

i

m

p

u

l

s

e

)

r

a

m

p

s

.

All absolurely required walls are displayed, although more walls may be desirable to keep citizens out of the circuit.

In normal "dormant" state (all doors shut), the cart circulates counter-clockwise either in the northern or the central loop, constantly accelerated and thus held at very high speed by a line of three impulse ramps. When the "e"nable door opens, the cart leaves its loop and tests the state of the "d"ata door by approaching it from the west. When this door is closed, the cart is diverted to the north, into the "off" holding loop. When the data door is open, the cart passes through its tile and passes through the southern branch and to the central "on" holding loop. The cart will keep going through the test cycle until the enable door closes again. As an important note, the enable door must turn off before the data door returns to its default state or the cell may settle into an erroneous state.

When the "r"ead door in the west opens while the cart is in the "on" loop, the cart will leave this loop, touch the pressure plate once and then keeps circulating in the westmost loop until the read door closes again. At this point it will return to the normal holding loop in the centre. The cart is guaranteed to touch the pressure plate upon entering the loop because it moves from a ramp to the flat corner with the plate - making this tile a checkpoint and thus guaranteeing the presence of the cart in the tile. In all subsequent passes, the cart will be moving at significantly more than one tile per step and goes through the longer loop. Now, the tile just north of the plate is a checkpoint and due to the high movement speed, the cart is guaranteed not to touch the plate - it simply skips past the entire tile, always.

The cell reacts to read and to write signals with a delay of less than ten steps and outputs a minimal-length signal cycle upon receiving a "read" request. All that for the cost of three mechanism-operated doors, the absolute minimum possible for this functionality. The main downside is the great space consumption of close to fifty tiles floor space. And it probably can't be packed tighter than 80-90 tiles per cell, offering around 200 bits of memory per entire z-level on a 3x3 embark (vs. 2000 with water or mechanical-minecart memory cells).

Another significant disadvantage is that it's based on switching of doors, which is extremely FPS-hungry: everytime a door opens or closes via mechanisms, the entire connectivity map for the entire embark must be re-built. When many doors keep opening and closing in short order, the game gets awfully choppy.

Afterthoughts[edit]

1. I've sketched a few more designs; incrementation, derivation of the binary complement and comparison should be quite feasible in CDL - fast and with few mechanisms. Using weight-calibrated pressure plates and providing different-weight evaluation carts could offer deriving very different functions from the same overall device: the adder should be able to also do bitwise AND and bitwise XOR without changing anything in the switching and output logic, merely by picking different carts to run the course. Input selection would also allow doing direct copy from source to target and bitwise OR.

2. To provide carts with sufficient speed for proper and fast evaluation, a simple impulse-ramp circuit is recommended:

		#				#
#	╔	╗	R	#	╔	╗
#	▲	║		#	╗	║
#	▲	║		#	╗	║
#	▲	║		#	╗	║
#	╚	╝	#	#	╚	╝	#
#	D			#	║

D: door opened to start an evaluation/operation run. R: return path feeding the cart back into the holding coil. Carts should only return once D is shut again, or you get multiple runs.

Just enough ramps in a row that there's a full step of acceleration on every cycle. The cycle takes a while to rev up to full speed, but once it's at full speed, it holds that speed for an indefinite time, responds to opening of the door in at most five steps and the speed loss in my twelve-bit adder was compensated in short order.

3. Carts in these circuits should preferably move at speeds well in excess of one tile per step. Making sure that a cart actually touches an output pressure plate cannot be guaranteed by spacing - which tiles are actually visited depends on distances travelled and speed (largely influenced by the number of turns a cart takes, which varies). However, the checkpoint effect can be used: when moving off a ramp to a different tile, a cart will always touch the tile past the ramp and spend exactly one step there, regardless of speed. I put an impulse ramp before every pressure plate in the adder, which increases space and time consumption a bit, but there's no reliable alternative. The under 100 steps for a twelve-bit addition include that regulation cost.

4. It should be evident that a door can bifurcate as many input paths as it has "faces", i.e. four (five if going very crazy and including carts dropped from above). I've designed a layout for a three-in-six-out switch that can reduce door/mechanism count in large decoders another notch. I've built and tested a sample four-bit decoder using a total of seven doors for the decoding work: on the fourth bit, where eight paths must be forked into sixteen, runs through three doors, two three in/six out, one two in/four out. The three-to-six split looks like this:

.		A		B		C
		║		║		║
		║		╚	═	╬	═	═	╗	#
#	╔	╚	╗	D	╔	╝	╗	#	║	#
#	║	#	║	║	║	#	║	#	║	#
	C		a	B	c		A		b

D is the single door switching the three input lines A, B, C to the output lines A/B/C when the door is open, a/b/c when shut. The main downside of this switch logic is evidently that accounting for the various decoding results is messy because results are all over the place. Probably worth it when looking at machinery costs (~one door and link per 2-3 outputs produced, no power) and speed (read-trigger-to-decoded-output of 10-15 steps, can decode once every 140 steps).

Four-in-eight-out switches are possible but ludicrously large.

As per usual, all circuits presented here have been built and tested. They are only presented in diagram form because i find it easier to explain their function this way (and don't want to spam the site with even more screenshots).

Link[edit]

Video of the twelve-bit full adder: http://mkv25.net/dfma/movie-2716-powerlessminecartadder