thecloud@dhw68k.cts.com (Ken McLeod) (09/23/88)
Has anyone else on the net tried to implement the Hodgepodge
algorithm described in the August issue of Scientific American
(A. K. Dewdney's column)...?
I've been getting some unexpected results, which I think may be
due to my workaround of a hazard in the formula for "infected
cells." The formula is [S/A] + g. When A = 0, obviously you need
to assume something else for the new cell state value! But what?
The only thing that yields somewhat interesting results is simply
setting the cell state to 0, rather than evaluating the formula.
However, only types 1 and 2 behavior appear, and these are "backwards"
(the "waves" of infection travel *toward* the center, not away from
it.)
I noticed a version of Hodgepodge has been posted to comp.binaries.mac,
but the author of the program (Douglas Wood) doesn't have a net address.
If anyone has implemented the program and/or can send/post the algorithm
to me (preferably in C) it would be *greatly* appreciated!
-ken
--
========== ....... ===========================================
Ken McLeod :. .: uucp: {spsd, zardoz, felix}!dhw68k!thecloud
========== :::.. ..::: InterNet: thecloud@dhw68k.cts.com
//// ===========================================rjchen@phoenix.Princeton.EDU (Raymond Juimong Chen) (09/24/88)
(Apologies if this got posted twice. inews and I don't get along well.) From article <12032@dhw68k.cts.com>, by thecloud@dhw68k.cts.com (Ken McLeod): > Has anyone else on the net tried to implement the Hodgepodge > algorithm described in the August issue of Scientific American > (A. K. Dewdney's column)...? I don't have the article with me, but I have implemented the HP algorithm. > The formula is [S/A] + g. When A = 0, obviously you need > to assume something else for the new cell state value! As I recall, S was the sum of the infectedness of all of its neighbors. One workaround (which is in keeping with the spirit of the algorithm) is simply to include the infected cell itself in the sum. That way, A will always be at least 1 (namely, itself). A more fatal flaw in the algorithm as presented in the article is as follows: Suppose all of your "infected" cells can be enclosed in a "bounding box", that is, a rectangular region (x_0, y_0) - (x_1, y_1). Then I claim that the infection can never spread beyond that box. This means that, if you let your CA run for a while, it will gradually break up into little rectangular clumps. (If it never does, then just consider the entire set of infected cells a "clump" for the purposes of the description below.) It follows, then, that if ever a clump "shrinks" (i.e., all of the cells on one of the edges becomes healthy all at once, so that the bounding box gets smaller), then it can never "expand" to its original size. This is, I feel, contrary to the phenomenon which the CA is attempting to model. Proof: Look at the transition formula for a healthy cell. Observe that with the choices of k_1 and k_2 suggested in the article, that it requires at least two "infected" cells to induce a healthy cell to become infected. But each cell on the bounding box is in contact with only one cell of the interior. (And cells at the corners are in contact with none.) Thus, those cells can never become infected. It is clear that if you have a "wall of health", then the infection can never spread past that wall. End of proof. I observed this phenomenon after running a few CAs. I saw that the "active" region was gradually shrinking, and I at first assumed that I had coded the program incorrectly! If there is sufficient demand for the source code, I'll post it generally, else I'll just send it to Ken. (The code is written for Turbo C 1.5 on an IBM PC, but it can easily become curses-ized for those with other machines.) -- Raymond Chen UUCP: ...allegra!princeton!{phoenix|pucc}!rjchen BITNET: rjchen@phoenix.UUCP, rjchen@pucc ARPA: rjchen@phoenix.PRINCETON.EDU, rjchen@pucc.PRINCETON.EDU "Say something, please! ('Yes' would be best.)" - The Doctor
coy@ssc-vax.UUCP (Stephen B Coy) (09/27/88)
In article <12032@dhw68k.cts.com>, thecloud@dhw68k.cts.com (Ken McLeod) writes: > > I've been getting some unexpected results, which I think may be > due to my workaround of a hazard in the formula for "infected > cells." The formula is [S/A] + g. When A = 0, obviously you need > to assume something else for the new cell state value! But what? When calculating infected cells include the cell itself in the totals. This insures that A>0. The most puzzling part of the article to me was what values of g to use. The terms "small" and "larger" don't convey a whole lot of insight. What I've found is that with n=128 interesting values of g are around 45. Does anyone else have nay insight into this? FYI I'm running this on my Amiga doing 160x100 cells and getting about 1 generation every 6-7 seconds. Oh, I'm also using an 8-connected neighborhood. With just 4 neighbors I couldn't get anything that looked interesting. > -ken > ========== ....... =========================================== > Ken McLeod :. .: uucp: {spsd, zardoz, felix}!dhw68k!thecloud > ========== :::.. ..::: InterNet: thecloud@dhw68k.cts.com Stephen Coy uw-beaver!ssc-vax!coy