Xref: utzoo comp.misc:8123 comp.theory.cell-automata:48 comp.theory.self-org-sys:7 comp.theory:286 comp.sys.ibm.pc:43532 Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!mit-eddie!uw-beaver!apollo!nelson_p From: nelson_p@apollo.HP.COM (Peter Nelson) Newsgroups: comp.misc,comp.theory.cell-automata,comp.theory.self-org-sys,comp.theory,comp.sys.ibm.pc Subject: CA question Message-ID: <486e5e96.20b6d@apollo.HP.COM> Date: 3 Feb 90 23:39:00 GMT Sender: root@apollo.HP.COM Distribution: usa Organization: Hewlett-Packard Apollo Division - Chelmsford, MA Lines: 103 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-) ---Peter