nelson_p@apollo.HP.COM (Peter Nelson) (02/04/90)
I've played with cellular automata for some time and have written
a number of Life-like cellular automatons on my PC in C.
I thought it might be useful to have a general-purpose cellular
automata utility with which I could try out different ideas by
just changing the rules, and perhaps creating a new struct def
to go with them Since I just bought the Zortech C++ v2.0 compiler
I thought that this might also be a good project to experiment
with OOP'ing theory, as well.
But somebody suggested that I should take a look at Autodesk's
CA Lab. Getting technical details from them was like pulling teeth
but when I finally did, it was very disappointing: CA Lab's
universe is a 64K array where each cell is one byte. If you
write your own rules you can read **ONE BIT** from each of 8
adjacent cells, or 2 bits from each of 4 cells, etc, using their
library. No complex data structures here! BTW, another minus
for me is that the graphics version does not support Hercules
monochrome graphics.
OK, so I was thinking about the idea of a CA utility when I
realized that I have a gap in my theoretical understanding of
this kind of problem! Conway's Life - types of simulations
are static, i.e., nothing moves from one cell to the next.
I was kind of hoping I could use my new utility to simulate
systems where "stuff" (information or state or something) does
move from one cell to another. This might be useful in simulating
fluid flow or ecological systems.
But my Life-like CA's don't seem to handle this concept very well.
They all consist of 2 matrices ( or 1 matrix with 2 elements at each
location) for the states at time T and T+1. I examine each cell and
it's neighbors at time T and determine its state at T+1, and then write
it into the T+1 matrix. Simple.
But when stuff moves between cells "collisions" may occur. The
problem is not resolving the collision (that's relatively easy).
The problem is propagating the effects of that resolution through
the matrix, and doing so in a way which is not dependent on the
order-of-evaluation.
-------------------------
|1 |2 |3 |4 |
| | | | | Say A (in cell 5) and B (in cell 7)
| | | | | are both moving toward cell 6 at
------------------------- time T. If I just compute the
|5 |6 |7 |8 | state for time T+1 *sequentially*
| A-->| |<--B | | then when I get to cell 5 I can't
| | | | | determine its state for time T+1
------------------------- without knowing whether it was
|9 |10 |11 |12 | successful in its attempt to move
| | | | | into cell 6. But the state of
| | | | | cell 6 for time T+1 is not known
------------------------- yet, and it is also a function of
7 which I haven't evaluated yet.
Now, suppose I complicate my algorithm by "following"
the path of A into cell 6 and evaluating the state of
cell 6 for time T+1 *before* evaluating the state of
cell 5. The result of such an evaluation would also
determine the state of cell 7 for T+1. Still, although
this is more complicated than a "Life" algorithm, it
would handle this particular case.
However, say that cell 6 has 'C' in it that wants to move
somewhere *else* (to cell 10 in this case). Then we have
------------------------- to keep following that path
|1 |2 |3 |4 | wherever it leads in the
| | | | | matrix because whether A is
| | | | | succcessful moving into 6 will
------------------------- depend on whether C is successful
|5 |6 C |7 |8 | moving into 10. And that may need
| A-->| | |<--B | | following the path even farther.
| | V | | | If the path ever doubles back,
------------------------- say to cells 5 or 6, then I will
|9 |10 |11 |12 | be stuck in a loop!
| | | | |
| | | | |
-------------------------
...So I have doubts about whether this approach can work.
*IS* there a common algorithmic platform upon which both
non-moving cell-type simulations such as Conway's Life and
physical-process or object simulations like fluid flow or
ecological systems can be based? (*** This question is
really the point of my whole posting. ***)
We have a large technical library here (HP/Apollo, Chelmsford,
MA) and there are a number of books on simulation. But they
are all very math-y and none of them seem to address cellular
automata, anyway. I'm just doing this for fun so I don't
want to get too technical.
Thanks in advance for any observations or comments. I'm new
at much of this so if I'm making lots of stupid assumptions
feel free to tell me, but be nice, please. 8-)
---Peterhiebeler@cs.rpi.edu (Dave Hiebeler) (02/04/90)
In article <486e5e96.20b6d@apollo.HP.COM> nelson_p@apollo.HP.COM (Peter Nelson) writes: > [semi-negative comments about Autodesk's CA lab] You might want to check out Cellsim, it is a public-domain cellular automata program (written in C), which runs under SunView. I realize you want something for the PC, but the inner loops for Cellsim are just pure C, and can be run on pretty much anything. It lets you get up to 8 bits from each of 9 neighbors at most, in addition to a couple of 8-bit "global" parameters. Rather than tell you how to get Cellsim, I'd prefer to wait, as I'm currently working on version 2.5, which is substantially better than previous versions. If you're *really* desperate to get the old versions, send me an e-mail note, although I hate to tell people where to get the old version, since the new one will be so much better. :-) > Conway's Life - types of simulations > are static, i.e., nothing moves from one cell to the next. > I was kind of hoping I could use my new utility to simulate > systems where "stuff" (information or state or something) does > move from one cell to another. This might be useful in simulating > fluid flow or ecological systems. Well, in Conway's life (as well as things like the HPP and FHP lattice gas rules), *information* moves from one cell to another. That is, a "particle" might be represented as an active cell; an empty cell that sees a neighbor with a particle moving toward it, will "create" a new particle while its neighbor "destroys" its particle. The net effect is an information transfer, or a particle "transfer". > But when stuff moves between cells "collisions" may occur. The > problem is not resolving the collision (that's relatively easy). > The problem is propagating the effects of that resolution through > the matrix, and doing so in a way which is not dependent on the > order-of-evaluation. > [stuff about following the results of possible collisions...] You should check out the HPP lattice gas model, this has a simple example of how to get around this. The basic solution (on a square lattice), is as follows (I'll describe it in terms of particles, since that's the terminology associated with the HPP model): 1. Each cell can hold up to 4 particles 2. There cannot be 2 or more particles in the same place moving in the same direction. So a "full" (4-particle) cell would have 1 particle moving in each direction: up, down, left, right. 3. If you think about the "worst-case" collision, this would be a cell that is full and whose neighbors are all full. In that case, the cell would "destroy" its 4 particles (knowing its neighbors would get them), and it would get 1 particle from each of its 4 neighbors. That is, the exclusion principle in item 2 above prevents you from having more than 4 items try to come into the same cell. Since each cell can hold at most 4 particles, you're safe. Three sources of information about HPP, which will clarify what I'm trying to say above are: J. Hardy, Y. Pomeau, and O. de Pazzis, ``Time Evolution of a Two-Dimensional Model System. I. Invariant states and time correlation functions'', J. Math. Phys. [14] (1973). J. Hardy, O. de Pazzis, Y. Pomeau, ``Molecular dynamics of a Classical Lattice Gas: Transport Properties and Time Correlation Functions,'' Physical Review A, [13] (1976) 1949. T. Toffoli and N. Margolus, Cellular Automata Machines: A New Environment for Modeling, (MIT Press, 1987). > Thanks in advance for any observations or comments. I'm new > at much of this so if I'm making lots of stupid assumptions > feel free to tell me, but be nice, please. 8-) I've been at this for years, and I still make lots of stupid assumptions and ask stupid questions. :-) Note that I'll be away at the 2nd Artificial Life conference next week, so I'll probably be slow to reply to e-mail queries until Feb 11th or so. I'll try to post a summary of interesting stuff I see at the ALife conference, probably in the following newsgroups: comp.theory.cell-automata, comp.theory.self-org-sys, comp.bio and maybe a couple of other groups, so watch at least one of those newsgroups around Feb 11-15 or so, if you're interested. -- Dave Hiebeler Internet: hiebeler@turing.cs.rpi.edu (preferred) Computer Science Dept. Bitnet: userF3JL@rpitsmts (last resort) Amos Eaton Bldg. Rensselaer Polytechnic Institute / Troy, NY 12180-3590