ts@cup.portal.com (Tim W Smith) (10/02/90)
A fun programming challenge is to do a really fast life on a fixed size array. The fastest I ever managed was 32 clock cycles per cell per generation on a 68000. Anyone out there done it faster? (512x512) By the way, a 68000 takes at least 4 cycles to access memory, and it would seem that you need 9 reads and a write per cell just to get the state of the cell and the neighbors and to write back the new state, so that at least 40 clocks per cell per generation would be needed just for data movement, and thus I must be telling an untruth in the first paragraph. But I am not lying. So, what's the trick? This makes a great programming puzzle (or interview question). Tim Smith
deadman@garnet.berkeley.edu (Ben Haller) (10/04/90)
In message <1266@doctor.Tymnet.COM>, carl@doctor.Tymnet.COM (Carl Baltrunas) says: > I know that there's a really fast LIFE program that runs on the Amiga (no > flames please)... it does it by using the blitter chips to do bit arithmetic > on the cell arrays and then displays the result. > If you try to do the work one cell at a time, you can't possibly handle a > large array in reasonable time... maybe you could implement is software > what the blitter chip does in hardware using some XOR or other functions :-). Yes, it is possible to implement Life using logical instructions such as XOR. And, in fact, that is the fastest way to implement it. I believe the fastest Life program I have ever seen for the Mac is called LAZ-Life or some such name. Unfortunately I couldn't find it on my HD, so I'm not sure this is the one I mean. Oh well. There is a program that can do a whole screenful of 2 by 2 dots and actually be fast. The problem with using logical operations is that a really nice thing for a Life program to do is keep track of how long a particular cell has been alive, and display longer-lived cells with different colors. A good example of this is the little Life demo in the MacEnvy cdev. A little ago I wrote what I believe to be the fastest possible code for the 68000 to do Life (although it probably could be faster, I just don't know how it could be...) while keeping track of cell ages. It displays direct to screen in 1-bit, 8-bit or 32-bit depths, and it's quite fast - a screenful of dots (3x3 or 4x4, can't remember) updates several times a second. This may be released in conjunction with the After Dark screen saver program put out by Berkeley Systems, although I can't, of course, say for sure if or when it will be released. It will allow editing, saving and restoring of Life documents, etc. Note this is *not* the Life screensaver that has already been released for AD, it is much nicer. Well, enough leaking. All the above was intended only to contribute to the discussion of Life algorithms, not as a press leak or anything. The point is, you can use logical operations to calculate Life, but you lose the (possibly important) information of how long a cell has been dead/alive. An important aspect of how fast a Life program is on the Mac is whether it uses Color SlowDraw to go to screen or whether it goes direct to screen. I believe LAZ-Life goes direct. Mine certainly does (when have I been known to use SlowDraw?? :-> ) But unfortunately, Life is just not a fast algorithm to implement. One final thing: LAZ-Life keeps track, I think, of an "active rectangle" which things are happening inside of, and only calculates inside that rectangle. So it lets you have a *very* large grid, and still goes fast unless you're actually using the whole grid. My Life doesn't do this, although I may implement this later...maybe not...it's a nice feature, though, for sure. But you get one glider going off to never-never land, and it stretches the whole active rectangle and slows the whole thing down. Maybe an "active region"...maybe that's what LAZ-Life does. I don't know. I'm blathering. Time to stop. Later... -Ben Haller (deadman@garnet.berkeley.edu)
ts@cup.portal.com (Tim W Smith) (10/04/90)
There are two kinds of fast life programs. The first kind tries to be fast on a fixed size array. The other kind tries to be fast on a very large unspecified array (i.e., it only keeps track of live cells). What's the fastest anyone has seen for the second class? I've done it in O(N log N), where N is the number of live cells, but I'm told that it can be done in O(N). If anyone wants to write a life program, I can post some code that does does the "fixed array via logical operations" method. It is implemented for clarity rather than efficiency (although the bit manipulation is done in assembly), so you will want to tweak it, but it is a good starting point. On a Mac II, it can do about 350,000 to 400,000 cells per second. This might be an example of where graphics that use separate bit planes for each bit of a colored pixel (e.g. the Amiga?) would be nice. By computing each new generation into a new bit plane, you would not have to lose history information if you wanted to color code cells. Tim Smith
chrisj@ut-emx.uucp (Chris Johnson) (10/05/90)
In article <1990Sep29.060028.26340@nntp-server.caltech.edu> julius@tybalt.caltech.edu (Julius Yang) writes: >Having read Martin Gardner's _Wheels, Life, and Other Mathematical Games_ >I am interested in obtaining a well-programmed version of life (I can't believe >there's not one here at Tech). >My requirements are: > >1. Runs on a Mac IIci >2. Fairly fast >3. Fairly large "playing field" e.g. at least 200x200 (but I'll take smaller) >4. ftp-able and, hopefully, fairly compact >5. Ease of use > >roughly in that order. I appreciate any help (e-mail answers please). > >Thanks! >julius@tybalt.caltech.edu >"come see the violence inherent in the system" I've recently come across what I consider to be two good life programs, both of which meet your criteria. The first is "gadlife" by Garth Dickie which is the fastest life program for the Mac that I've come across (there may be much faster ones - I don't know; I haven't run into many of these). Its feature set is fairly simple, but it works very well, particularly when your monitor is in black & white mode. The second Life program is "LifeLab" by Andrew Trevorrow. This program isn't as fast as gadlife, but makes up for it admirably with all the extra features it provides like the the abitity to save dishes, variable magnification of the dish, as well as searching and editing facilities. It also comes with a lot of sample dishes that illustrate various interesting life forms. Both are available for anonymous ftp from ix1.cc.utexas.edu (128.83.1.21) or ix2.cc.utexas.edu (128.83.1.29). They live in the microlib/mac/game directory. Cheers, ----Chris (Johnson) ----chrisj@emx.utexas.edu P.S. Want to help me round out this collection of life programs? Let me know about other good ones....