I would like to note that I am currently sleepy. You'll probably see some sort of silly mistake. Notify me, please?
DROD 2.0 is universal. It can compute
anything in an unreasonable amount of time.
DROD is a very very curious challenge to program. You have practically infinite amount of places to store information (infinite rooms in infinite levels), but permanent memory is too permanent (Room completion, Level completion, Mastery is unusable to my knowledge). Other possible ways to store information is by Beethro's sword (Limited to one bit of information, some logic possible by bombs and tunnels, takes too much space) or by location of room entry.
Fortunately, despite horrendous limitations, it is possible to emulate a universal system in DROD, without even using characters , orbs, multiple levels, or potions.
In particular, DROD can emulate all possible
elementary cellular automatons. Since DROD can emulate
Rule 110, DROD is universal. (from Wolfram's A New Kind of Science, explanation is available
here)
The representation is a bit different from regular CAs (cellular automatons), even though each single room in DROD still represents a single cell. Instead of single cells switching back and forth between "
alive"
and "
dead"
states in a line, the representation of CAs in DROD take place in a more widely seen graphical format, with the history of all cells visible. The next iteration of the CA is done on the next row of rooms. (Go to the linked pages... see those pretty triangles? It's just like that.)
So... how?
-----
The plan is to have unit cells that do almost all the work. Beethro "
scans"
a cell, and follows a path depending on whether or not the current room is solved. The process is done three times (for the three cells which determine the state of a cell in the next generation). There will be eight paths in the end, each leading to the ruleset. The ruleset determines which paths lead to a path which changes the state of the particular cell in the next generation which the scanned cells affect. In the end of this changing of the cell's state (or if the path ends up not affecting that cell), the process begins anew starting a cell to the right.
In the end of the row of cells, Beethro is sent back through a special path going all the way back to the left edge of the level. The path leads to the next row, and the entire process repeats. An ending cell (with stairs) can be placed at a particular column.
The left and right edge cells are regarded as "
0"
, though they can be modified to be "
1"
or even an explicit sequence of 1s and 0s -- though all of the information entered should only be the initial sequence of cells, the width of the "
universe,"
and the number of generations to go through.
-----
The important elements:
This is the splitter. It splits paths, according to whether or not the current room is solved. Nifty mechanism, thanks to infinite supply of slayers.
This is the ruleset. The left column of tunnels denote "
live"
while the right column denote "
dead."
The ruleset follows the regular binary representation of elementary CA rules.
This is the marker, which tags a cell in the next generation as "
alive."
It spans three rooms for trivial reasons, and leads to a path which starts the scanning cycle anew.
Then there's the network of tunnels, possessing no particular function other than to lead Beethro to the right direction. I'll let you look at them in the .hold attached.
-----
Look in the .hold. It shows the parts necessary, etc. In the unit cell, the brain marks the cell as dead (how ironic). Delete brains in the first row of cells accordingly to mark cells as alive.
The ruleset is modifiable to any of the elementary cellular automatons. Try rule 0 for a lesson in futility!
An example level is also shown. It can be modified as you wish to add/reduce cells, it should be intuitive.
The right edge might be a bit counterintuitive (the ruleset is barebones), but it should be trivial to modify.
The level in action:
Oh, and I think the cells aren't quiiiiite *perfect* just yet. They did go through about 5 hours of creating and testing though.
[Last edited by Niccus at 09-19-2006 12:40 AM : Fixes]
