Revision as of 22:39, 1 September 2011

My principal interest these days (in DF) is creature logic. I figure I might as well save some of my techniques here in case anybody stumbles over them.

Principles of Goblin Logic

I use goblins (or elves-- they both work) for my logic designs. There are a number of reasons for this:

Goblins don't die of old age
Goblins don't have babies
Goblins don't need to eat, drink, or sleep
Goblins don't need "citizens trigger" pressure plates (which leads to build hell)
Goblins are readily available, in huge quantities, on almost all maps
Goblins path predictably to map edge (after capture, at least)

I avoid mounts and other invader animals. I have had bad luck with them, and any tightly closed door breaks path.

Goblin Pathing

I said that goblins path predictably. This is true so long as the goblin has one and only one path to the map edge.

That requires some explanation. It's fine if multiple paths exist, so long as all paths lead through the same next tile. As soon as multiple tiles exist from which a goblin can escape to the map edge, we no longer have predictability.

Unfortunately, manipulation of path length doesn't help.

This leads to our basic three rules of goblin logic:

Goblins will only be allowed to move if they have one and only path
Goblins without a path will be constrained to a single tile
There must always exist a path to the map edge from any logic circuit we build

Map Edge

The fact that goblins require a map edge for predictable motion does not mean that we can't wall up our fortress! There are a number of ways around this. We can build our logic circuits separate from our main fortress; we can have a bridged connection, such that goblin logic paths through the fortress normally, but through an alternative path when we wall up.

We can even connect our logic to the underground (not recommended, and not tested), or over a bridge 10 z-levels above the ground to the map edge (tested, and very safe).

Probably the safest way to run goblin logic is through a tightly closed artifact hatch leading to the surface. Building destroyers will not path through it, nor will they be able to break it. Creatures will not be able to pass it, but goblins will. Most or all creatures that will path to a goblin to kill it are either building destroyers or undead animals. No guarantees, though-- haven't tested everything.

The rules

AND gate

Consider an AND gate.

####
gDD^
####

g is goblin, D is door operated by mechanism, ^ is a pressure plate, # is a wall.

The goblin must make it through two doors to hit the pressure plate. The doors are opened by some sort of memory cell, such that if P1 is true, the left door is open.

What happens when P2 is true but not P1? No path.

But what happens when P1 is true but not P2? No path-- but the goblin may still wander into the space occupied by the left door. If our situation changes, say, such that P1 becomes false and P2 becomes true, the goblin will have a path, despite falsity of P1 AND P2.

This is because we forgot one of our rules: if there is no path, constrain the goblin to a single tile.

#####
g.DD^
#####

. is hatch over channel, triggered by mechanism, currently open

Now, we don't constantly evaluate the truth of P1 AND P2-- we only evaluate when neither P1 nor P2 are in the process of change. We specify when to evaluate this by sending a close signal to the hatch. If P1 AND P2, the goblin triggers the pressure plate. Otherwise he doesn't.

But if P1 is false, the goblin can still block off the door, the same as before. We need to send a null path, so that the goblin, when triggered, definitively returns true or false.

NAND gate

########
^h.g.DD^
#h######
###

h is hatch, triggered by mechanism

Now, we send close signals to the hatches on either side of the goblin. When we do so, the goblin paths predictably to one side or the other, and doesn't dawdle anyplace. This is because we've added a NAND gate to the left of our goblin. Anytime an AND is true, a NAND is false, and vice versa.

NOR gate and OR gate

I'm just going to show you these last two gates, because we can do any logical operation with NOR and NAND. You don't need any other gates. I'll show a simple OR, just because it's the opposite of NOR-- that is, if NOR is true, OR is false, and vice versa.

########
^hh.g.d^
######d#
########

That's it. Those are all the logical operators you need. (I'll probably point some others out anyways.)

Path to map and return to position

You might notice that all of the designs so far are single use. We have to load them with a new goblin every time we use them. We don't want that. Here's a NOR/OR expanded to show how we're going to do that.

############
<h^hh.g.d^h<
########d###
############

< is upstairs, pathing to map edge

All that we've done is add a hatch cover and a path to map edge. The peripheral hatch covers are each linked to the adjacent pressure plate. When the goblin arrives at either NOR or OR, the hatch opens, and his path to the map edge is blocked. There's one problem: at that point the goblin has no path, and so he won't path predictably. But we can fix that:

######<#####
######.#####
######g#####
<h^hh.#.d^h<
########d###
############

By now, maybe you realize why the hatches next to the goblin are open: it's because he's standing on a pressure plate that, like all of our pressure plates, triggers the adjacent hatches. Let's draw the same picture, but with no goblin:

######<#####
######h#####
######^#####
<h^hhh#hd^h<
########d###
############

Let's define a term: the goblin's position after running one of these tests is his reset position.

I want to point out one problem with this design as shown. Remember how I said that the goblin needs to always have one and only one path, or be constrained to a single tile? Here, after he evaluates NOR/OR, he has no path until his hatch opens-- which will occur after his evaluation. That makes his behavior unpredictable-- for instance, we can't be sure that a CLOSE will rapidly follow his evaluation. It's not a huge problem, but it's one we want to avoid.

Signal types

I mentioned how we were going to prompt the goblin to choose a path before-- we were going to send a close signal to the hatches adjacent to him. (Obviously, we won't want to send a close to the hatch preventing his escape to map edge though.) But sending close signals is easier said that done. Our pressure plates send opens when activated, and closes ~100 ticks after deactivation. We have a few choices. Consider:

###
#l^
###

l is lever, ^ is citizens trigger pressure plate

This is our basic input. The lever is linked to nothing-- its only purpose is to get a dwarf to run across the pressure plate. In this case, our pressure plate should be linked to the two hatches permitting our goblin to choose NOR or OR. The dwarf runs across the pressure plate, opening the hatches-- but they're already open. 100 ticks later, it sends a close signal to both hatches, which close, opening path to our goblin. Let's define a term: this kind of a signal, a rapid OPEN-CLOSE, is a trip.

But what if our goblin isn't in the proper position? What if he's currently running a test? Those hatches won't be open, and opening them will block his return to reset. That's not a big problem in this simple circuit, but we want to avoid it in general.

####
#l^d
####

All we've done is add a door, and linked the pressure plate at reset to this door. Now, the door doesn't permit tripping unless the goblin is at reset.

Except that's not quite true. The door will be open 100 ticks after the goblin leaves reset. A small revision:

############
#l^        d
############

Not perfect, but it works.

Of course, we don't want things to be run by dwarves. We want complicated logic circuits involving the interplay of multiple goblins.

Long paths

This should look familiar:

            ######<#####
            ######h#####
##################^#####
#<h^           hhh#hd^h<
####################d###
            ############
            ############

It's just our trip lever hooked up to our NOR/OR. Imagine a few of these in operation, with the NOR end tripping the reset hatches of the next. You can see that it won't be a huge problem to run trips from goblins instead of dwarves.

But there is a very large problem with this circuit. The hatch granting reset path will close before the goblin reaches our NOR pressure plate. There is a risk that our goblin will just run half-way to NOR, then back to reset, without triggering anything.

            #######<####
            #######d####
            #######h####
###################^####
#<h^           hhh#hd^h<
#####################d##
            ############

Now we've added a door to the reset path, triggered by reset position. This door will close at the exact same time as the hatch, so we block reset path. But we still have the problem of getting the goblin to reset, because now no path exists, and even if one did, we have the risk of the goblin oscillating around the NOR path. We could build a complicated ground path to drag the goblin around. But instead, let's try something much more general purpose.

  ##################<#
 ##               h#h#
 #d################^#####
 ##^           hhdh#hd^h<
 #h##################d###
 #<#                ###

Now, reset position is linked to adjacent hatches, as well as doors blocking forward progress. NOR position is linked to adjacent door.

Let's trace it through. Hatches are tripped, goblin heads to NOR. Hatch to reset path closes at the same time as door to reset path closes, no path. Goblin continues to NOR, trips NOR. Hatch blocks NOR path. Door opens, permitting return to reset.

You might think that there's no room to make a similar loop for OR, but that's not true. We can hook it into the same return to reset arm.

                  #####
                 ##   ##
                ## ### #
  ############### ##<# ##
 ##               h#h## ##
 #d################^####d#
 ##^           hhdh#hdd^##
 #h###################d#h#
 #<#                 ###<#

There's got to be something more elegant, right? There is.

<        <
h########h
#^hd   h^#
#h######h#
# #    #d#
# #    # #
# #    # #
# #    # #
#d#    # #
#h######h#
#^h   dh^#
h########h
<        <

Each pressure plate is linked to the adjacent hatches and the nearby door. Arrival at one permits continuation along the loop, as controlled by other devices. We don't actually need four arms, but it makes it pretty. Each arm contains an operation that we trip along the way. Each of the 4 pressure plates in the corner is a reset. We cause an operation by tripping the hatch clockwise of each pressure plate (we can trip all 4 at once safely, don't worry).

Here's what a NOR/OR arm might look like:

    ###
<  ##d##  <
h### d^###h
#^hd### h^#
#h##hh^##h#
# #######d#

We could build further operations into additional arms, but the next arm doesn't actually have to perform any operation. Consider the following:

    ###
<  ##d## <
h### d^##h
#^hd###h^#
#h##hh^#d#
## ##### #
###     ##
  #######

This is a functional, return to reset NOR/OR, that operates reliably for goblins of any movement speed, and returns goblins to the original position. It follows our rules: a goblin either has 1 and only 1 path, or is on a single tile. It returns a true or a false (although we can safely ignore the false, if we don't care) in the form of a trip-signal-- which is the same kind of signal that starts this device. Given equally fast goblins, two of these could trip each other, although that would be pointless.

Since the second arm of our loop does nothing, and doesn't even need a trip for the goblin to path down it, let's call the rightmost path to surface the completion point.

There's only one thing to be careful of, and that's making it too small or making it run too frequently. Return of goblin to reset does not mean the entire circuit is reset yet! We need to give time for the hatches by completion to close before making another run through the circuit. Ideally, no circuit should be repeated until 100 ticks from the time that the goblin has returned to reset; for one arm loops like this, it's good enough that the circuit not be run again until 100 ticks after leaving the completion point. Notice one thing-- running the completion point generates a trip signal itself, that doesn't send a close for 100 ticks. Linking the completion point to the start hatch ensures running this circuit as frequently as it can be run. (Not that we want that. We need time to be able to write to memory.)

In larger loop, all we need to be careful of is that we don't run the operation again until goblin has returned to reset position.

Any further discussion is going to get hopelessly complicated if you don't understand this basic loop. There is an operation, and there is infrastructure, and you need to know which is which. Our infrastructure is never going to change, but our operations are, and mostly, I'm not going to show you infrastructure again.

Infrastructure

Infrastructure is only ever linked to from within the circuit itself, with one exception (the begin hatch) which is linked to plates both inside and outside of the circuit.

Pressure plates: The leftmost pressure plate is reset position: it lets us know the operation is ready to be run again. The rightmost pressure plate is completion point: it serves an infrastructure purpose, and if we want to, it can let us know the operation has been completed.

Hatches: The hatches adjacent to reset position and to completion point are infrastructure. Infrastructure hatches are linked to adjacent pressure plates. They limit movement through the operation. The hatch immediately to the right of reset is a special hatch: tripping this one begins the operation. We'll call this special hatch 'begin.' Other than begin, no hatches are linked to anything except the adjacent, infrastructural pressure plates.

Doors: The door just to the right of begin, and the door one tile south of completion, are infrastructural doors. They are linked to reset and completion respectively, and block retrograde pathing for long loops.

Operations

Operation structures are only ever linked to from outside of the circuit.

Doors: The two doors in the middle, on the uppermost arm, are operations doors. Their layout forms an OR decision.

Hatches: The two hatches in the middle, in the arm just below the OR decision, are operations hatches. Their layout forms a NOR decision.

Goblin memory and more signal management

But what sets the doors and hatches that constitute evaluation of NOR/OR? Obviously, we can't set them with a trip signal.

########
<h^hh^h<
########

Hopefully, if you've followed me so far, I don't have to explain the above. Each pressure plate is linked to the immediately adjacent hatch.

This is our crudest form of goblin-based memory. One or more of our pressure plates is linked to comparison doors and hatches. To toggle our memory state, we send a trip signal to the two middle hatches.

For an example circuit, consider two memory cells and our NOR/OR. The rightmost pressure plate of each cell is linked up to one of the doors and hatches in the center of our NOR/OR. We'll call this rightmost value '1'. Our OR arm trips the central hatches on memory circuit 1. We run the operation, to begin with, by tripping the hatch clockwise of reset.

What happens?

Memory a is 1, memory b is 1: Memory a becomes 0.
Memory a is 0, memory b is 1: Memory a becomes 1.
Memory a is 1, memory b is 0: Memory a becomes 0.
Memory a is 0, memory b is 0: No change to memory.

This is a fun demonstration, but you can see that we want more features than just toggling our memory. We want the ability to set memory to a certain value.

  ###
###d####
<h^hh^h<
####d###
   ###

This is our settable memory. Let's change it so that instead of linking OR to the hatches, we link it to uppermost door.

Memory a is 1, memory b is 1: Memory a becomes 0.
Memory a is 0, memory b is 1: No change to memory.
Memory a is 1, memory b is 0: Memory a becomes 0.
Memory a is 0, memory b is 0: No change to memory.

Or we link it to the southermost door:

Memory a is 1, memory b is 1: Memory a becomes 1.
Memory a is 0, memory b is 1: No change to memory.
Memory a is 1, memory b is 0: Memory a becomes 1.
Memory a is 0, memory b is 0: No change to memory.

You might also notice that this memory forms a loop-- just as we settled on for our NOR/OR. A goblin running between the two pressure plates always runs in a certain direction, and steps on each tile of the loop exactly once. All good goblin design forms loops like this. Notice, too, that it follows our rules: so long as we write to it no more frequently than every 100 ticks, our goblin always has one and only one path, or is standing on a single tile.

(By the way, I am incredibly indebted to Fenwah and his high speed creature switches described in http://www.bay12forums.com/smf/index.php?topic=62798.0 for this memory design, and from that, for everything I'm writing here.)

Hopefully you're noticing just how important signal management is. I said that we needed trips to execute our comparison loop, but like I said, that won't work for our comparison parameters. We need stable values-- open or close. That's where memory comes in. We just have to be careful not to write to memory at the same time that we're reading memory, or our comparisons won't make any sense. In a worst case scenario, a door might close on a goblin, or a hatch open up underneath him, and computation stops.

Practical concerns with goblin based computing

Let's take a break from logic and design for a minute. It's easy to forget that these aren't just bits moving around our fortress computer-- they're still invaders.

You have to pit them into your memory cell. If dwarves walk under or over our logic, they'll get interrupted. If a dwarf with a crossbow gets interrupted, he'll shoot your goblin. If you want to make changes to your logic designs, you have to kill any goblins occupying the space first.

To manage all of this, there are a few things you should do before pitting any goblins. All pits and all stairs to goblin access should be hatched over. Not locked hatches, of course, because that would break pathing. All spaces underneath channels should be walled off, or at least doored off. All objects (including stone) in the logic areas should be removed, so that dwarves don't path there. And you should have a couple of crossbows and a couple of bolts, because it can be a pain to find a melee route to a goblin in one of these circuits.

Cats pose a special problem. I've never seen them screw up goblin pathing, and I'm not sure they will, but they path into logic areas because these areas spawn vermin. Cats block doors when they close, and vermin corpses block doors too. Tightly closed hatches over your paths is a good start, but generally insufficient-- if a cat wants in, it will get in eventually.

There is one design decision that can solve this problem for you. Instead of doors, you can use hatches over ramps or staircases.

Hatches are really interesting because, depending on the surroundings, they can be built to allow path when closed (as when over a channel) or when open (as when over a ramp or staircase). And the big thing is that they never get stuck open.

One drawback that I've found with using hatches instead of doors is design convenience. It's hard to visualize a circuit when it spans multiple z-levels. The other drawback is the difficulty in designing doorless memory. It's possible, but inefficient.

Incrementing memory and percolating functions: the two-bit add

I want to show you a special kind of memory.

  ###<#
 ##h#h#
## #^##
#hd#dh#
##^#^##
#h#h##
#<###

This, of course, requires some explanation.

NE pressure plate corresponds to true. It is linked to both adjacent hatches. SW pressure plate corresponds to false. It is linked to both adjacent hatches. To set equal to true, open the west door. To set equal to false, trip the hatch to the NW of true. SE pressure plate sends a trip when state changes from true to false when triggered via 'toggle with carry.' It is linked to both doors of the next memory cell. To toggle with carry, open both doors.

In other words, this is an unnecessarily complicated memory cell to use on its own, but it has nice functionality when put in a line of several, with the 'carry' plate of each linked to the doors of the next. We can still use it as normal memory (although it's a little slow for that purpose). It still forms a loop that follows our rules.

Imagine two of them, the first linked to the second (but not the second linked to the first!) When we toggle with carry to set memory a = 1, we don't do anything to memory b. But when we toggle with carry to set memory a = 0, we also send a toggle to memory b.

Imagine now that we have four bits of memory and an operation to add them. We have memory a1, memory a2, memory b1, memory b2.

#######
#d^#d^#
r## ##c
#h #h #
#######

r is reset position, c is completion point; you can see that I left out infrastructure

The western doors and hatches are linked to a1, the eastern, to a2. The western plate carry-toggles b1, the eastern plate, b2.

Here's how it works in code:

If a1 then b1=b1+1
If b1>1 then b1=0 and b2=b2+1
If b2=2 then b2=0
If a2 then b2=b2+1
If b2=2 then b2=0

We're adding bits! There's one problem, and I hope you noticed it. We can't write to memory twice at the same time! This percolation forms a write, and the second arm of our write operation isn't going to play pretty with it. We could do this:

#################
#d^###########d^#
r##           ##c
#h ###########h #
#################

That would slow it down, but isn't guaranteed to work.

This is better:

#################
#d^###########d^#
r##h         h##c
#h ###########h #
#################

In this case, the two central hatches we've created should be linked to the memory a1's carry-toggle, so that we institute an automatic 100 tick delay between writes. This is still not foolproof, but it's more foolproof.

Instituting Delay

The problem is that it's not safe to write to the next bit until the previous bit has had time to percolate. Since percolation uses a trip signal, we need to wait 100 ticks, plus any time for the goblin to move to his new position.

#########
<h^h^h^h<
#########

This looks a lot like a memory cell. There's one extra pressure plate in the middle, though. It's not linked to any hatches in this circuit though.

When we send the two interior hatches a trip signal, they'll get a redundant open, then close 100 ticks later. Our goblin will run across the central plate, sending a trip.

Let's rebuild our adder. Remember, all operations are loops-- completion point can as easily serve as reset position for the next arm.

#######
#d^#d^#
1##2##c
#h #h #
#######

1 is reset1, 2 is reset2

I haven't shown you infrastructure. We link reset2 to the interior hatches on our delay. But we can't link our delay trip to the begin hatch for reset2-- that's insufficient delay. Rather, we build a second delay circuit, linked to the first delay circuit-- that is, delay1 trips the interior hatches of delay2, and delay2 trips begin2 of our 2 bit adder. We now have >200 ticks delay before running the add on the second bit.

Hopefully, it's obvious how this can be expanded to add any number of bits. Hopefully, it's also obvious that percolating functions can be very slow. A 6-bit percolating add takes more than one in-game day to complete.

Multiple arm operations: two-bit compare

Let's build an arm that evaluates bits a1, a2, b1, and b2 and returns true if b>a.

   ##############
  ##           ^##
### ########## # ##
#dh#     #### ### ##
r###     ##dh## ## #
# ######## ########c
## #dd  # #dd   ^# #
 ## #### ######## ##
  ## #hh# #hh ^# ##
   ## #### #### ##
    ##hd###hd# ##
     ### ####^##
       ##    ##
        ######

If you notice, there are 12 paths to run through from reset to completion. These paths are chosen such that one and only one is ever open. The goblin traces through two sets of evaluations. The first set of evaluations, on the left, correspond to b2 and a2 respectively; on the right, b1 and a1 respectively. That is, the most northwestern door corresponds to the state of b2, and the southeastern door corresponds to the state of a1. The northeast pressure plates returns true if b>a; the others are only necessary if we expand it.

Here's our goblins flowchart:

If b2 and not a2 return true
If a2 and not b2 return false
If a2 = b2 then
  If b1 and not a1 return true
Else return false

You can see that this > comparison actually contains all possible ordinal relationships of a and b: greater than, lesser than, and equal. We can put pressure plates anyplace we want to evaluate this. We can make those pressure plates do something or not do something with other circuits-- in other words, this is a complete 2-bit compare.

You might also suspect that an 8 bit compare of this design would be huge-- but not really. Look at the return from the southern and northern compare of bit 2. The design is as tall as it needs to be-- we only need to make it wider. With each bit we compare, we only have to continue our compare if a and b at a particular bit are equal. If one is larger or smaller than the other, we divert them into true or false returns.

Difference between revisions of "User:Vasiln"