Difference between revisions of "User:Vasiln"

Latest revision as of 23:02, 23 February 2014

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.

User:Vasiln/Goblin Logic 1: Where I deal with some basic gates and the infrastructure needed to make goblin logic work
User:Vasiln/Goblin Logic 2: Where I go into advanced logic problems, memory addressing, adder optimization, and start writing some programs
User:Vasiln/Goblin Logic 3: Where we deal with practical problems associated with building a programmable goblin logic computer, talk about input and output, and get to multiplexing

I think I'm done with creature logic now. I just feel as if I've solved it, and don't know what to think about next. Feel free to contact me if you've got any questions or problems. There is no logic problem that cannot be solved with a sufficient number of goblins, mechanisms, doors, and hatches.

Here are my designs for the undump.

Toward a comprehensive theory of build order.

Live fire bolt recovery.

The practically useless but technologically interesting 150-tick repeater.

Experiments in minecarts

Sandbox page, currently holding WIP on minecart logic

Difference between revisions of "User:Vasiln"

Latest revision as of 23:02, 23 February 2014

Navigation menu

Search

@@ Line 1: / Line 1: @@
 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=
+* [[User:Vasiln/Goblin Logic 1]]: Where I deal with some basic gates and the infrastructure needed to make goblin logic work
+* [[User:Vasiln/Goblin Logic 2]]: Where I go into advanced logic problems, memory addressing, adder optimization, and start writing some programs
+* [[User:Vasiln/Goblin Logic 3]]: Where we deal with practical problems associated with building a programmable goblin logic computer, talk about input and output, and get to multiplexing
-I use goblins (or elves-- they both work) for my logic designs.  There are a number of reasons for this:
+I think I'm done with creature logic now.  I just feel as if I've solved it, and don't know what to think about next.  Feel free to contact me if you've got any questions or problems.  There is no logic problem that cannot be solved with a sufficient number of goblins, mechanisms, doors, and hatches.
-# Goblins don't die of old age
+Here are my designs for the [[User:Vasiln/Undump|undump]].
-# 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.
+Toward a comprehensive theory of [[User:Vasiln/Build_order|build order]].
-==Goblin Pathing==
+[[User:Vasiln/Adamantine_factory|Live fire bolt recovery]].
-I said that goblins path predictably.  This is true so long as the goblin has one and only one path to the map edge.
+The practically useless but technologically interesting [[User:Vasiln/150_tick_repeater|150-tick repeater]].
-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.
+[[User:Vasiln/minecarts|Experiments in minecarts]]
-Unfortunately, manipulation of path length doesn't help.
+[[User:Vasiln/sandbox|Sandbox page, currently holding WIP on minecart logic]]
-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.)
-==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.
-The only 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.