Prehaps I should be honest and say I actually spend weeks as a kid producing these things on a BBC Micro, and printing them out in a long continuous sheet on a tractor feed Epson RX80 to make what looked like 8' long slug trails. Back then they took hours to run, which was a big win because Mandelbrot sets took days!
So what are these things: A CA is a set of cells. Each cell has a state, and it has a set of neighbouring cells. At each time time it looks at its neighbouring cells state, and its own state and decides what its new state is going to be. At its simplest a cells state is quite commonly restricted to just alive or dead. The simplest neighbourhood might be the cells to my left and right. A simple rule might be "set my state to state of the cell on my right". While this might sound pretty limited, in fact with only a slightly more complex system we can produce something that's a "Turning Complete" - it can do any calculation your computer can do. That's right - a basic cells in a grid, with a simple rule could by made into an emulator to run any video game for example... OK it's actually not very practical, but in theory its possible, and that's not only cool, but its a really important idea in computing.
Lets start build a simple Automata in Sniff. We'll start by creating a list to hold the current state:
make state list of boolean
We'll restrict ourselves to cells which are "Boolean" - they're either on or off. More complex CA can have much more complex states, but not today...
.repeat 8
..if pick random 0 to 1 = 1
...add on to state
..else
...add off to state
.broadcast showState and wait
Simon wanted 8 cells in his list, so here we generate 8 random numbers, and use them to set the 8 states in our list to either on or off.
.forever
..broadcast calcNewstate and wait
..broadcast showState and wait
..wait 0.5 secs
Now we can loop forever, calculating the new state, displaying it, then waiting half a second before moving on.
You'll note that I still haven't defined calcNewstate, or showState. This is an idea called "top down design". If I was designing a car I'd decide I need an engine, some wheels and a chassis, and figure out where they would go. Then the engine team would go off and design the engine I need. The important thing is I figure out that I need an engine, and what it needs to do, then I get someone to make one for me. The alternative is sending a team of to make an engine, a team off to make some wheels, a team off to make the propellers, and then when they finish we assemble them, and hope they make a car. This is called "bottom up design", and its important too but its better as a way of implementing you machine, rather than designing it. In practise any real project is a bit of both.
Now that I've written the top level, lets fill in the details (bottom up!).
make count number
make result string
when showState
.set result to ""
.set count to 1
.repeat length of state
..if item count of state
...set result to join result "*"
..else
...set result to join result " "
..change count by 1
.say result
Lets start with this code to print out the current state. It's useful to write this next as it'll help us see what's happening, when we write the more difficult calcNewstate script. We could output the state to some LED's but for now we'll just print them. The code simply goes through the state list, and adds either a space or a * to the string "result" depending on if its alive or dead. Another thing to note here is that this works for any number of cells in the state list. I know its 8, because that's how many we put in, and that's how many Simon asked for, but one day Simon is going to buy some more LED's and want to have 12 or 16 cells, so lets write our code so that when that happens we're ready for it (exactly how much future proofing you should put in your code is a matter of debate even among experienced programmers - don't waste too much time building things you don't need, but expect things to change in the future...)/
Now we get to the good bits - calcNewstate. We're going to use state to calculate a new state (called new), so:
make new list of boolean
when pushBack
.repeat length of state
..delete item 1 of state
.repeat length of new
..add (item 1 of new) to state
..delete item 1 of new
There's also a new script called pushBack, which copies the new state over the old state ready to go round again. It first deletes all of the items in state, then copies each element over by copying the first element, and then deleting it. There are other ways to do this which might be clearer - I liked it cause it don't use a counter variable! (tech note: its OK to change the repeat count inside the loop - its evaluated once on entry to the loop, in both Scratch and Sniff).
We'll break calcNewstate into smaller pieces to discuss:
when calcNewstate
.set count to 1
.repeat length of state
..
..set left to count-1
..if left = 0
...set leftState to item (length of state) of state
...set leftState to on
...set leftState to item 1 of state
...set leftState to off
..else
...set leftState to item left of state
We're going to go through state one element at a time, so count is the current item we're looking at. To keep things simple, we're going to let a cell look at its left and right neighbours, so we have a variable left which is one less than count, and right which is one more than count. Then we can set leftState and rightState to be the state of the neighbouring cells.
The only catch is what happens at the edges. Simon was actually pretty specific in on respect - the CA wasn't allowed to wrap. Normally we join the edges of CA, so that left of cell one is cell 8, and right of cell 8 is cell 1, but in this case it was banned. However he didn't say what we should do... so we can take some liberties here if left is 0, then we're at the edge, and I've written four possible things we could do: use the state of cell 8 (disallowed), make it always 1, use the state of cell 1, or make it always 0. As these all set leftState, then only the last one actually does anything, so in this case leftState is always off.
Then we set middleState (easy), and rightState, with the same options as last time:
..set middleState to item count of state
..
..set right to count+1
..if right > length of state
...set rightState to off
...set rightState to item 1 of state
...set rightState to item (length of state) of state
...set rightState to on
..else
...set rightState to item right of state
Hey - I cheated there! left of the left edge is always off, but right of the right edge is always on... It makes some rules more interesting, and you can try it lots off different ways. Besides the rules just say it can't wrap, they don't say what it should do...
..set ruleIndex to 1
..if leftState
...change ruleIndex by 4
..if middleState
...change ruleIndex by 2
..if rightState
...change ruleIndex by 1
..
..add (item ruleIndex of rule) to new
..
..change count by 1
.
.broadcast pushBack and wait
Here's the clever but. We know leftState, middleState and rightState, so we can put any code we want here to calculate the new state, but with only three Boolean inputs there are only 8 possible combinations, so we convert them into a binary number: LMR and look them up in a list. We can make any rule just by changing the list!
Then we're done, and move onto the next cell. Finally we use the pushBack script to copy the new state over the old one which we don't need any more.
- 000 - > 0
- 001 - > 1
- 010 - > 1
- 011 - > 0
- 100 - > 1
- 101 - > 0
- 110 - > 0
- 111 - > 1
To define a state we just need to fill in this table. In this case the LMR cells are off off off then the new cell becomes off. Simlarly off off on becomes on.
when makeRule
.add off to rule
.add on to rule
.add on to rule
.add off to rule
.add on to rule
.add off to rule
.add off to rule
.add on to rule
But we can also make up other rules:
when makeRule90
.add off to rule
.add on to rule
.add off to rule
.add on to rule
.add on to rule
.add off to rule
.add on to rule
.add off to rule
If you look closely you'll release that as there are only 3 inputs, that means there are 8 rows to the table. Each row can be on or off, so there are in fact only 256 ways to fill in the table! To make things even easier we can use the on/off's in the table to make a number 01011010 in binary is 90, so we call this rule 90!
* **
* * **
****
** *
*****
** ***
*** **
* * ****
*
* * *
* *
* * **
* ***
* ** *
* **
***** *
** * *
*** * *
* * ***
Unfortunatly one feature of CA is that they tend to get stuck in loops - you'll seed that the last row is the same as one further up, that means from then on the same pattern of rows will repeat. This is inevitable with only 8 cells - the entrée automata only has 256 possible states in so we're going to his a loop pretty quickly.
80 cells on the other hand:
* ** * * ***** * *** *** * * * ** * * ** *** * * * * * * ** *
* * ***** *** * *** ** ** ** * * * ** ** * ** * * * ** *
*** ** ** ** * *** * ****** ** * * ** ***** *** ** * * * *** *
** ** *** ** ** * * * * **** ** * ** ** ** ***** * * * * * ** * *
*** ** * * ** *** * * * * * * ** *** * *** ** ** * * **** *
** * ** ** * * * * ** ** ******* *** * * ** ** * * * ** ** **
** *** *** ** * *** ** * * * *** ** **** * ******* *
*** ** ** ** ** **** * * ** * ** * * * ** *** * ** * * ** *
* * ** ** ** ***** * ** **** * * * * ***** * ***** * * **** * * *
** ** ** * *** * **** ** * ** *** * *** * * * *** ** * *
*** ** ** * ** * * ** * **** * *** * ** * *** ** * ** * ***** * **
** * ** **** ** ** **** * * * ** * ** * * ** *** * * *** ***
*** ** * ************ *** ** ** **** * **** * *** ** *** ** * ** * * *
** ** *** *** **** * ** ** * *** * * * ** * ** * * ** **
** ** * **** ** ** * ** ** *** *** ** ** **** ** *** **** *
** ** * * *** ***** * *** ***** * * * ** ** * ** **** ** * * ** **
** *** * ** * ** ** * * * * * ** ** **** * ** *** ***** **
** * * **** *** **** * * * * * * *** ***** * **** * ** ** * **
** * ** **** **** * * * * ** * * *** *** * ******* * **
*** * ***** * * *** * * * * * * * *** * ** * * *** * ** * ****
* *** *** *** *** * * * * * * ** * ** * * *** * *** *
* * * ** ** ** ** * ** ** * * * * **** ***** * * ** ** * * ***
* ** ** ** ** **** ** * * * * ** *** * * ** * * * ** ** ** * ***
* * *** ** ** ***** * **** * * ** * *** * *** **** ******** *
* ** * ** ** * *** * * * *** * ** * * ** ** * * *** **
* **** ** ** * ** *** ** * * * ** ** * ** ** *** ***** * ** * *
* * ** *** **** ** * * ** ** **** ** *********** **** ** * * ***
* ** **** * * * ***** ******* ** * ***** * * ** *** *** ** *
** * * *** ** ** * **** * ** * **** * ** ** * *** **
*** ** * ** ** **** **** * * *** * **** * * ** * ****** * * *
** ***** * *** ** * * * ** * ** *** * * ** * **** * ** ** *
** * *** *** * ** ** **** ** * * * * ***** * * ** * *** *** * *
** * ** * * * ******* ** ** *** ** * * ****** * ** **** *** * **
**** ** * ** * ****** * ** **** * * * * ** * ** * * * * ***
* ****** * *** * * * ***** *** ***** * * *** ** *** *
*** ** * *** ** * ** * * * ** **** ** ** *** * ****** ** *
** ** ***** * * ** ** ** *** ** * *** **** ** ** * * ** *** * *
** ***** *** *** ******** ** * **** * ** ** * ** **** ** * *** * *** *
** * ** ** ** ** * * ***** * *** ** **** ** * * ** *** * * ****
** * *** ** ****** * ** ** * *** ***** * ***** ** ***** * * * *
**** * * ** * ** * * **** *** * * * * *** ******** * ** ** * *
* *** ** * ***** *** * * ** * * * *** ** ** ** * ***** *** *
*** ** ***** *** ** ** *** ** * * * * ** *** *** * * * ** **
** * ***** * * ** *** ** * ** ***** * * * * ** * ** ** ** * * * ** *
** * ** * ** * * ** ***** * ** * *** ****** ** * ***
*** * * *** * *** *** ** ** * * *** *** ** ** * *** * *** ** *
* * * *** *** ** ** * *** *** * ** **** * ** *** * * ** * * * ** *
* * * * * * *** *** * * * ** * **** * * ** * *** ** **** ** ** *
* * * ** * * * ** * **** * * ** * *** * * ***** * *** *** *
* *** * ** * ** *** ** **** * ** * * *** * **** * *
* * ** ** * * ***** * ****** * ** * ** * ** * * * ** *** * * *
Things get more fun when you add bigger neighbourhoods and more states!
here's the complete code. Have fun with it...
No comments:
Post a Comment