Print

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

[Sphalerite]

For the last few months, I've been building a megaproject which is an implementation of Conway's Game of Life in a dwarf fortress mechanical computer.  It is nearly finished.  This is how it works.

Theory

Spoiler (click to show/hide)

My Dwarf Fortress implementation represents each cell with a single-tile storage cell, with full 7/7 water indicating 'alive' status and anything less indicating 'not alive'.  Each cell has surrounding it a mechanism for calculating the next statue of that cell and then updating the storage cell.  An external sequencing clock controls the actions of all cells to make all steps are performed synchronously.

The Game of Life cellular automata operates by a fairly simple set of rules:  cells with four or more neighbors die, cells with zero or one neighbors die, cells with three neighbors are set to alive, and cells with two neighbors stay alive only if already alive.  We split this into three basic operations:

First, the overpopulation check: If at most three neighbors are alive, we pump water from a supply channel into a temporary storage register.  The temporary storage register actually holds two tiles of water, for reasons which will be covered further down.

Second, the underpopulation check: If at most two neighboring cells are alive, or at most one cells is alive if the prior state of the cell was 'alive', we pump the water out of the temporary storage register.  Or, to put it another way, if the number of neighboring cells and local cells combined who are live is not more than three.  At this point the temporary register will have water in it if three neighboring cells are alive, or if two neighbors alive and this cell is alive.

Thirdly, we transfer the contents of the temporary register to the storage cell, clearing the contents of the temporary register in the process.  At this point the cell will have been updated to its new status.

The mechanism

Spoiler (click to show/hide)

Each cell and associated machinery fits in a cube 5 tiles on a side.  The design is as follows:

Level 5

Code: [Select]

.....
>.W..     > = down stair
..W..     WWW = windmill, must be exposed to the sky, resting on gear on level 4
..W..     . = open space
.....

Level 4

Code: [Select]

.+++.     + = floor, . = open space
X+*+.     X = up/down stair
.***.     * = gear assembly, center gear is always on and connects to pump below
.+*+.     all other gears switched by neighboring cells
.....

Level 3

Code: [Select]

+OOO+     + = floor, O = wall
X*b+.     X = up/down stair, b = single-tile retracting bridge, * = local cell state gear
+*P++     PP = pump, pumping from north, * = mode switch gear
.*P*>     * = gears connected to neighboring cells
.....     > = down stair, . = open space

Level 2

Code: [Select]

OODOO     O = wall, D = access door
XFh.F     X = up/down stair, F = transfer floodgates, h = transfer hatch
OOPOO     PP = pump, pumping from south
+*P*X     * = gears, connected to neighboring cells
..b..     . = open space, b = single-tile retracting bridge

Level 1

Code: [Select]

OOOOO     O = wall
XD^DO     X = up/down stair, D = door (left access, right transfer), ^ = pressure plate
OOFOO     F = manual set floodgate
++++<     + = floor, < = door up
+++++     bottom two rows are full of water

This mechanism performs both of the 'less than N cells active' with gear load logic.  Each mechanism has a windmill on top which provides exactly 40 power.  Finding a site with a consistent 40 wind over the entire map was a requirement for building this fortress.   Connected to the windmill is a gear assembly and two pumps, which require 25 power to operate.  We then have eight gears which are also connected to the pumps and fixed gear, each of which is connected so as to be on only if one of the adjacent cells is on.  It doesn't actually matter which of these gears is connected to each adjacent cell, so long as exactly one cell is connected to each gear, but I did maintain a consistent ordering just to keep things straight during assembly.  Gears are initially engaged when built, so I had to build a preset lever to switch them all to disengage by default so they would then engage for each adjacent cell being active.

Now since the windmill is providing 40 power, the fixed gear and pumps draw 25 power, we can have up to three additional gears connected and still have the pumps turning.  If four gears are engaged, we need 45 power.  There isn't enough power, so the pumps halt.  This is how we perform our overpopulation test - the pumps will halt if four or more cells are active.

The central gear on level 3 - the one labeled 'mode switch gear' - is engaged to perform the underpopulation check.  This adds an additional 5 more power required.  It also engages the 'local cell state gear' which is engaged if the local cell is alive, which means the pump stack will only be able to run if 0 or 1 neighbors are alive, or if 2 neighbors are alive but the local cell is not.

This basic operation is the only thing we need to implement the Came of Life cellular automata in Dwarf Fortress.  The only other key part of the mechanism is the temporary storage register (located in the middle of level 2), and the mechanism for smoothly and reliably transferring the contents of the register from the temporary storage register to the cell register on level 1.

Sequence of operations

Spoiler (click to show/hide)

The entire cycle of operations which is required for a full iteration of the cellular automata is controlled by the sequencing engine, a fairly complex bit of engineering by itself.  The sequence engine has six stages.  Each stage is outputs an 'on' trigger signal for 200 steps.  Each state triggers the next stage with a delay of 101 steps, so that each cycle overlaps the next for 100 steps and the entire cycle repeats every 606 steps.  The sequencer is controlled by a set of levers, one which controls whether the machine will stop at the end of the current cycle, and another used to manually start the first stage.

At the start of the operation, all bridges are extended, all floodgates, doors, and hatches are closed.  The 'mode switch' gear is engaged, and all other gears are engaged only if the cell associated with that gear is 'alive'.  The two spaces making up the temporary storage register on level 2 are empty, or nearly so (they may have 1/7 water left over in them).  The storage cell on level 1 has 7/7 water if the cell is 'alive, or some lesser amount of water if the cell is 'dead'.

The sequence starts by disengaging the mode switch gear.  This removes the load of the mode switch gear, as well as the load from the local cell state gear if the local cell is 'alive'.  At this point both pumps will be running if less than 4 neighboring cells are 'alive.  Note that no water is being transferred even if the pumps are running because both pumps have their input tiles block by single-tile retracting bridges.

About 200 steps later, the bridge on level 2 retracts.  This is the 'load' bridge, and when it retracts it allows the lower pump to draw water out of the supply channel and fill the temporary storage register with water.  At the same moment that the bridge retracts, the mode switch gear engages.  This will add an additional load of 5, plus 5 if the local cell is 'alive'.  This will cause the power required to be too great for the windmill if 3 neighbors are 'alive', or if 2 are 'alive' and the local cell is 'alive'.  This would cause the pump to stop, but since pumps continue turning for 50 steps after their power source is removed the pump will run long enough to fill the temporary register.

About 200 steps later, the 'load' bridge closes, and the 'drain' bridge located on level 3 opens.  Now if the pumps are still running, they will drain the water out of the storage register and dump it back into the supply channel.  The temporary storage register may retain 1/7 water in its tiles, but this does matter.  At this point the temporary storage register will still contain water only if the pumps were operating in the load phase but halted for the fill phase, which will only happen if three neighboring cells are active, or 2 are active and the local cell is already 'alive'

About 200 steps further on, the 'drain' bridge closes and the transfer stage activates.  'Open' signals are sent to the two floodgates on level 2, the floor hatch on level 2, and the eastern door on level 1.  (The western door on level 1 is for construction access, and should be kept locked when the machine is in operation.  Likewise for the door on level 2.).  The transfer mechanism takes advantage of the fact that floodgates have a 100 step delay on opening, while doors and hatches open instantly.

When the door opens, it creates a tile of empty space next to the storage cell.  At the same moment, the opening of the door and the hatch allow the contents of the temporary storage register to fall into the storage cell and the space where the door was.  If the temporary register was full of water, then the storage cell and the door tile will be completely full of water.  If the storage cell was already full of water, then a tile's worth of water will remain in the temporary storage register.  This will drain out through the access stairs when the floodgates open 100 steps later.

If the temporary storage register was empty or had only 1/7 water in it, then after the hatch and door open the storage cell will only have 3/7 or 4/7 water in it.  This will cause the pressure plate to turn off, indicating that the cell is 'dead'.  The door will then destroy the water that flowed off the storage register cell when it closes.

The pressure plate in my design is actually set to be triggered when the water level is 0-6, and untriggered when the water is completely full.  This means that a pressure plate being triggered indicates that a cell is 'dead', while an untriggered pressure plate is 'alive'.  Since gears toggle state when triggered, this does not affect the operation of the cellular automata.  I built it this way so that the display grid would work, since buildings linked to pressure plates vanish when triggered and I wanted then to appear when the cell was 'alive'.

This mechanism transfers the contents of the temporary register to the storage register cleanly, without any spurious momentary on or off pulses, and empties out the temporary storage register in the process.  The only complaint I have about it is that pressure plates seem to have a delay on turning off, so when the display grid updates at the end of a cycle cells dying disappear before cells coming to life appear.

The Fortress

Spoiler (click to show/hide)

5800 power generated, all through windmills
291 pumps
About a dozen legendary mechanics
Over 9000 installed mechanisms
Single-digit FPS



Gloveflier (yeah, a randomly generated name) was specifically and carefully chosen for this project.  A 2X2 site (large enough to fit the originally planned 16X16 array) on perfectly flat forest.  Multiple limestone layers because I originally wanted to make a lot of the parts out of steel.  (I ended up making it mostly out of rock, wood, gold and silver to save time).  No sand, which in retrospect was a mistake – if I was building this from scratch again I'd embark on a site with sand and make everything but the mechanisms out of green glass.

I was running my experimental Uplift Engine mod when I created it, so there are several dozen procedurally generated animalperson civilizations in the world.  Not that this matters, since I walled off the entire map edge with drawbridges a year into the project to keep out distractions.  I later turned off temperature, weather, and invasions, not that this seems to have made much of a difference in FPS.

The original plan was to build a 16X16 cellular automata.  I later scaled this down to 16X8 when I realized how much work even the smaller array would be.  The foundations and work spaces are all sized for the full 16X16, so it would still be possible to expand the design to the full size, but I don't think I'm going to bother.  At the moment the fortress is running at 10FPS when the calcualtor is halted, and drops down to about 2FPS when it's running.

The array of calculating cells is built on the surface, a massive tiled grid of the 5X5X5 cubical device described above.  A two-stage pumping system draws water from the river, first into a main supply channel and then into individual supply channels for each row of cells.  Water supply is actually a major problem for this design – when all the cells activate their load stage at the same time it draws a lot of water out of the supply channels.  If I was to build this design again from scratch I'd built it over an ocean, the brook I'm using here struggles to meet the demands of this monster.

A 4 tile wide ring was channeled out around the entire device down to the rock layer, and then the entire map border was smoothed and carved into fortifications as a water drain.  My original idea was to simply dump excess water on the surface and let it drain into the brook.  This was not a good idea, it took forever for it to all drain away or dry up.

Underground and not visible here is the display grid (a 16X8 array of single-tile bridges), the grids of manual cell set and clear levers, the control room for starting and stopping the sequencer, as well as all the workshops and storage rooms and living quarters.  I will be putting up a map and save files soon once I'm done testing and have gotten the fortress to the point where the cellular automata runs reliably.

Testing has revealed some issues in which a sudden water draw from the array feed pumps causes water pressure to drop throughout the system, sometimes resulting in the sequencer locking up mid-sequence.  It's actually reminiscent of how noisy logic gates in digital systems can cause noise on the power rails and lock up gates elsewhere in the system.  I'm currently doing some minor redesign of the water supply system to address this.  I have also learned the hard way that it is critical to lock off access to the array while it's in operation.  Just because a dwarf has no reason to open that access door doesn't mean he won't anyway.

Movie of the display grid as the calculation runs:
http://mkv25.net/dfma/movie-2278-gloveflier-gameoflifedemo

Map file: 
http://mkv25.net/dfma/map-9792-gloveflier

Save folder: 
http://dffd.wimbli.com/file.php?id=3346

[veok]

You've won dwarf fortress.

[DukeOfVandals]

You've won dwarf fortress.

Seriously.

[Dariush]

You've won dwarf fortress.

Seriously.

No kidding.

[The Merchant Of Menace]

Awesome, now modify it to work under other rulesets than Conway's game.

[Lormax]

When I first read the subject, I thought it was the Milton Bradley game   Very awesome though.

[Fayrik]

This is fantastic.
Can't wait to see the final version!

But, aparently there's a low FPS? Have you tried deleting every creature that isn't directly involved by means of a tool like Runesmith? It could just be that those donkeys that're getting trapped up the top there are trying to move and causing some lag. (I know that the way DF deals with deaths means that unless you hack these things out, their bodies are gunna stick to the unit's list like glue.)

[Dwarf]

Have you attempted making a turing machine which would run Dwarf Fortress?

[Sphalerite]

I suspect that the low FPS might have more to do with 145 windmills and all the pumps and gears they're driving.  But I didn't even know that there were phantom animals stuck in the edge wall bridges till I generated a Stonesense screenshot.  I'll try editing those out, or maybe just lowering and raising all the edge bridges to crush them.

I also have a fair number of cows and elephants in the food production section, but they're all either chained or caged.  No other animals.  There are also a whole bunch of forgotten beasts wandering the sealed-off caverns who got in before I turned invaders off.  Can Runesmith delete forgotten beasts?

[Johnfalcon99977]

I suspect that the low FPS might have more to do with 145 windmills and all the pumps and gears they're driving.  But I didn't even know that there were phantom animals stuck in the edge wall bridges till I generated a Stonesense screenshot.  I'll try editing those out, or maybe just lowering and raising all the edge bridges to crush them.

I also have a fair number of cows and elephants in the food production section, but they're all either chained or caged.  No other animals.  There are also a whole bunch of forgotten beasts wandering the sealed-off caverns who got in before I turned invaders off.  Can Runesmith delete forgotten beasts?

Yes. Just click the GENOCIDE button. Its my favorite.

[Vicid]

Should I go to college or try to be a cop?

[Lormax]

Both.  A recruit with a degree will go places.

[KillerClowns]

You've won dwarf fortress.

Seriously.

No kidding.

Another nod of agreement to this.  Wow.

[plarf]

+1 for making me go read about Conway's Game of Life.

[Rolan7]

Amazing!
And over 9000 mechanisms, haha.  That must have been rough.  Good job, both with the theory and the execution!