moony wrote:Could someone give/find me an explanation for Quicklife or a similar nonhashing algorithm?

I'm developing a simulation program for Life, Life-like, and Non-totalistic rules and am planning on using the quicklife algorithm. (High memory overhead really isn't something I want, and a bounded grid is already in mind.)

EDIT: Forgot to note that i already have googled it.

Heh, I just tried that, and didn't find much either.

The fastest non-hashing algorithms all use various low-level bit manipulations -- shifting, masking, XOR, recombining -- to effectively find the future state of a whole row of cells, say 32 or 64 cells, in one calculation.

Depending partly on the language you're developing in, you may or may not want to tackle all of that. Even without bit-twiddling tricks, there are a number of easy improvements on the naive algorithm.

(Naive algorithm summary: loop through all cells in Universe 1 bounded grid, calculate next state and record in Universe 2; when loop is done, swap Universes 1 and 2.)

My suggestion would be to start by reading

Alan Hensel's general summary for his fast Java applet -- there are a lot of good clues in there. QuickLife was originally partly inspired by that algorithm.

Then if you really want to know how QuickLife works, there really may not be any better place to start than the

source code, as Tom has suggested. Don't worry about reading the actual code at first, though. Just go through and read all the comments, top to bottom -- they're unusually good as these things go.

If that seems too complicated, then consider this for a start (if it isn't what you're doing already). In your bounded grid, keep a simple hash table containing all your ON cells. At each tick, make a list of the neighbors of each of your ON cells. For each of those cells, check to see if *its* neighbors are in the hash table. If you count the right number of neighbors, add that cell to a new hash table. Then check each of your ON cells and add them to the same table, but only if they should remain ON. Clear the universe, draw the cells in the new hash table, and repeat.

This works surprisingly well for moderate-sized bounded grids in many rules, just because many rules settle into fairly sparse arrangements of scattered cells. For all its disadvantages, at least this algorithm never spends any time looking at big empty spaces.

If that seems too simple... an alternative you might want to investigate is

Calcyman's lifelib, which is somewhat faster than QuickLife, I believe. However, it's probably faster partly because it uses even more tricks specific to modern CPUs, that I don't really understand except vaguely -- maybe loop unrolling, and maybe clever use of cache memory, and so on.