[2D CA (non totalistic)] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
2D CA (non totalistic)
(Click here to view the original thread with full colors/images)
Posted by: Alessandro
Greetings,
I need your help to re-implement a 2D CA I already wrote some time ago in C++.
Its scope was to read a BW image, then evolve it according to some
rules. Specifically, by the rules I wrote I am able to "etch" the
input image obtaining a skeleton or graph of the input image...
These rules, if I understand correctly the term, are non-totalistic,
i.e. they don't depend just on the total number of B/W cells in the neighborhood.
Example from my input file:
...............
RuleSEinput
0 0 0
0 1 1
0 1 1
RuleSEoutput
0 0 0
0 0 1
0 1 1
.......................
RuleTreeLeftinput
1 1 0
1 1 0
1 1 0
RuleTreeLeftoutput
1 1 0
1 0 0
1 1 0
........................ etc
my program scans the image with the *input pattern, substituting the
*output pattern if a match occurs (scanning with or without overlap,
i.e. with a step=1 or step=3 along x and y in the case of 3x3 rules) .
Is this a nontotalistic 2dCA?
Now, do you have some hint on how to implement it in Mathematica - or
has something similar already been done?
I know about the function CellularAutomaton, but I don't know how to translate my rules
Given its form CellularAutomaton[rnum, init, t, off], rnum can have different forms, as
n
{n,k}
{n,k,{r_1,...,r_d}}
...
but overall they all are defined (it seems to me) by the rule identifier n.
I don't know what n represents. What I know are the if->then rules shown before.
thanks for any help...
Alessandro
Posted by: Jason Cawley
A fine question.
I can explain how rule numbers are generated and thus how one can translate a list of mappings of the type you describe into a rule number. But you can also just use the explicit rule list form of the CellularAutomaton function, which you would undoubtedly find much more straightforward given what you already have.
If you look at the documentation page for CellularAutomaton in Mathematica, the first entry under "More Information" shows many possible rule forms for the first argument, rule. The one of immediate interest is the second to last in the list, called "explicit replacement rules for lists of neighbors".
All that is needed is a list of rules, each with a left hand side pattern corresponding to the neighborhood you want your CA to have, and a right hand side individual value that the center cell should update to. For a 2D range 1 CA, the left hand sides should be 3 by 3 arrays, and the right hand sides single integers. With just two colors, each entry in the left hand side matrices should be 0 or 1, and the right hand sides should also be 0 or 1. So for example, a single such case might be -
{{1,1,1},{1,0,1}, {1,1,1}} -> 1
- or in words, "if everything around is 1 except the center cell, the center cell becomes 1".
To specify everything that can happen, you make a whole list of rules, each like the one above, but with different left hand side matrices. That list of rules is your overall "rule" and becomes the first argument to the CellularAutomaton function.
You are also allowed patterns, though, which can make this form quite convenient, particularly for sparse lists of rules.
In other words, you might have only a dozen or two left hand side matrices explicitly filled out, and then might have a last rule in the list that says, in effect, "otherwise the center cell is unchanged", or "otherwise the center cell becomes 0". You would write those in "pattern speak" as -
{{_, _, _}, {_, a_, _}, {_, _, _}} -> a
- or -
{{_, _, _}, {_, _, _}, {_, _, _}} -> 0
Mathematica will use the more general pattern at the end of the list only if one of the earlier, more explicit rules does not apply.
For convenience, it would be typical to store your built up list of explicit rules in a variable name, say "ruletable". Once you have it, the actual CellularAutomaton function call looks like this -
CellularAutomaton[ruletable, Table[RandomInteger[{0,1}],{20},{20}, 50]
- if, say, I wanted to run 50 steps starting from a random 20 by 20 array. The second argument can instead by your data, of course. To work correctly with a ruletable meant for a 2D array, obviously the initial condition data should be a 2D array. The last argument is just the number of steps you want to run the evolution for.
Notice that you don't have to specify the number of dimensions anywhere - the CellularAutomaton function will just infer it from the shape of the left hand sides in your list of rules. Similarly, colors don't need to be specified, they will just be obvious from the range of values within the matrices on the left hand sides, and the range of values for new cells on the right hand sides. If you let cells go to values (on right hand sides) that do not appear on left hand sides, eventually the rule list won't have cases that apply, and will just apply the pattern default at the end.
Since there are 512 cases to fill out (from 2^9 possible forms for the left hand sides) for a general nearest neighbor 2 color rule, the total number of rule of this kind is very large. 2 to the 512th power. This makes explicit rule numbers cumbersome to work with, but it can still be done.
The idea is to treat each of the 512 cases as a different digit in the rule number. The first case and thus the "1s digit" is what to do with a pattern of 9 0s, and the last case (The 2 to the 511th power digit) is what to do with a pattern of all 1s. You count up through the possible patterns, filling in 1s in binary counter fashion from the lower right to upper left. So the "2s" digit is all 0s except a 1 in the lower right hand corner; the "4s" digit is all 0s except for a 1 in the middle of the lowest row, the "8s" digit is a 1 in both the lower right and middle of the bottom row, then "16s" is all zeros except a 1 in the lower left. Etc. That tells you which left hand side pattern corresponds to which digit. Now make that digit 0 if the right hand side is to be 0, and 1 if the right hand side is to be 1. Add up the values from all 512 patterns all up to get a single rule number between 0 and 2^512 -1.
This way you could translate your list of explicit patterns into a single rule number. For some industrial strength applications that might be worth doing, because CellularAutomaton will run with its fastest, compiled code if given a rule number. That is if the computer rather than you as a programmer are the rate limiting step. For most of your purposes, though, you would probably find it much easier to work with an explicit list of replacement rules, perhaps much shorter than 512 cases long, with patterns effectively filling out many of the cases at once.
That is why the rule list form is there in CellularAutomaton.
Incidentally, another powerful short form in CellularAutomaton is the functional form, the last listed in the help under possible ways of specifying the first argument, rule. That allows any (named or pure) function to just accept the neighborhood as its arguments, and return the new value of the center cell. This makes it very easy to program CAs that depend on e.g. just the count or spectrum of cell values in their neighborhood (as with many ecological models for example).
From your starting point, though, the rule list form is the one you will want.
I hope this helps.
Posted by: Alessandro
thank you so much for your help!
I'm not being able to have it to work, though - I hope it's not my Math version - it's a 5.2, is it ok?
I'm asking this, since you say:
...
If you look at the documentation page for CellularAutomaton in Mathematica, the first entry under "More Information" shows many possible rule forms for the first argument, rule. The one of immediate interest is the second to last in the list, called "explicit replacement rules for lists of neighbors".
...
but my help page instead says (sorry if I cant copy&paste, I tried with [ m ][ / m ] and different types of "copy as..." but failed so far):
- Possible setting for rnum are:
- n
- {n, <something>} (7 different types of it)
- {fun,{},rspec}
and that's all! In the help there's no mention of explicit replacement rules.
The same I find also in the Help->MathematicaBook(3.2.6), and at http://documents.wolfram.com/mathem...llularAutomaton .
Anyway I tried (hoping it was a hidden feature!) with:
CellularAutomaton[{{_, _, _}, {_, a_, _}, {_, _, _}} -> a, cells, 5]
but I got:
CellularAutomaton::nspec
CellularAutomaton::nspec: Rule number specification (n or {n1, n2, ...} [
0 <= ni < nmax]) expected at position 1 in the rule specification expr.
So far this is it, I'm not having luck - but I feel we're nearer to the solution! (over-optimistic as usual...)
thanks again
Alessandro
Posted by: Alessandro
Further experimentation, more along the lines you suggested: I made a ruletable, containing the 2 rules I wrote in the original post (RuleSE and RuleTree) + the default.
This brought me to the following:
ruletable = {
{{0, 0, 0}, {0, 1, 1}, {0, 1, 1}} -> 0,
{{1, 1, 0}, {1, 1, 0}, {1, 1, 0}} -> 0,
{{_, _, _}, {_, x_, _}, {_, _, _}} -> x};
CellularAutomaton[{ruletable, {}, 1}, Table[Random[Integer], {20}, {20}], 50]
CellularAutomaton::gkspec: "Color specification (k, {k, 1}, or {k, {wt1, wt2, \
...}}) expected at position 2 in the rule specification \!\({{{{0, 0, 0}, {0, \
1, 1}, {0, 1, 1}} -> 0, {{1, 1, 0}, {1, 1, 0}, {1, 1, 0}} -> 0, {{_, _, _}, \
{_, x_, _}, {_, _, _}} -> x}, {}, 1}\).
I think I'm having problems to understand the meaning of the color and neighbor specifications, and/or to understand how to setup the ruletable.
...deeply lost in depressing thoughts...
Alessandro
Posted by: Jason Cawley
Ah yes, I am thinking in 6. Really you should upgrade, 6 is great. That sales pitch out of the way, I'll solve your problem.
First a minor point - what you wrote in your second post above wouldn't quite work even in 6, because the rule form is expecting a list of rules, not a single rule. Even if you want to use just one, the "identity" rule you wrote with your pattern, you have to give it in the expected form. So you'd wrap that rule in one more level of braces. If you had several rules, they all look like that one, are all inside those braces, separated from each other by commas. (You apparently found this part yourself, in your last post above. Well done!)
The explicit rule form was added in 6. But the more general functional form is already there in 5.2, so we can just make a helper function that turns a list of rules of the kind we want, into a function of the kind that form expects.
It is very simple -
FunctionFromRule[rulelist_] := #/.rulelist&
Geez that looks funky to a non-Mathematica person, doesn't it? All it says is, "make a new function" (using SetDelayed, that is the := ) named FunctionFromRule, that takes one argument, calling it "rulelist". Return a pure function (meaning an unnamed one) - that is the & at the end - which just applies the list of rules (that is the /. symbol, which is short for ReplaceAll) to the pure function's argument (that is the # symbol, which stands for "Slot" or the argument of the pure function delimited by the & character). Whew! Long explanation for all the special characters, but a short and conceptually simple bit of code.
Now let's give an example rule list - more than one - and store it in a variable name to make it easy to refer to repeatedly. I decide the rules are, in plain English, "if everything around is a 1 become a 1, otherwise stay what you were". That only needs two rules, like this -
myrules = {{{1,1,1},{1,0,1},{1,1,1}}->1, {{_,_,_},{_,a_,_},{_,_,_}}->a};
Now the only extra wrinkle is that we have to make the actual CellularAutomaton function call using the form expected by the functional form. Which comes in three parts - the function itself, an empty list {} where the "kernel weights" would be in a standard rule number, and dimension and range info in the third position. For 2D and range one, that means {1,1} in the third position. For the function we want to call our FunctionFromRules machine above, passing it "myrules". Let's also store the resulting evolution in another variable, "data", so we can reuse it or plot it etc. So we have -
data = CellularAutomaton[{FunctionFromRules[myrules], {}, {1,1}}, Table[Random[Integer], {5}, {5}], 3]
Which runs the resulting rule starting from a random 5 by 5 array, for 3 steps.
If we want to see the results we'd then use ArrayPlot on each step of that, so we'd write -
ArrayPlot/@data
That says, Map the function ArrayPlot over each top level element in data. Incidentally, you can make an animation of the results by collapsing the resulting output from the cell bracket on the right. This will collapse the output to the first image. Double click within it to play the animation (such as it is - little chance the special case applies so it probably just does "identity" 3 times).
To get a new evolution from a new rule, just change "myrules" to a less "toy" list, and plug in a different initial condition where I had the random array.
I hope this helps.
Posted by: Alessandro
Originally posted by Jason Cawley
FunctionFromRule[rulelist_] := #/.rulelist&
Geez that looks funky to a non-Mathematica person, doesn't it?
to be honest, it looks funky to some Mathematica person too ;-)
BTW, I program in Perl since many years, and I find sometimes the same dangerous habit in both worlds, that is to kill the ability to understand code, trying to obtain the shortest, more efficient programs.
Perhaps we should start a thread on Mathematica-golf, as it was done with Perl-golf http://en.wikipedia.org/wiki/Perl_Golf_Apocalypse !
Hopefully, your reply arrived together with the upgrade link to V6.0, and I am happy to tell you that I was able to make it work, with the rule-based syntax!
I just wanted to thank you for the useful help.
Alessandro
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings