From: "fiziwig" Newsgroups: comp.theory.cell-automata Subject: Fast GOL alogrithm that doesn't examine neighbors. Lines: 117 X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2800.1106 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106 Message-ID: NNTP-Posting-Host: 148.64.12.173 X-Complaints-To: abuse@starband.net X-Trace: twister2.starband.net 1046484409 148.64.12.173 (Fri, 28 Feb 2003 21:06:27 EST) NNTP-Posting-Date: Fri, 28 Feb 2003 21:06:27 EST Organization: Starband Communications Date: Sat, 01 Mar 2003 02:06:27 GMT Implementing the game of life without examining neighboring cells. I haven't coded this yet, but I'll provide some benchmarks once I do. When implementing the game of life and similar cellular automata the most frequent operation performed is examining the cells in the neighborhood of the cell being updated. A total of 9 array access operations must be performed for every cell in the arena. But there is another way of computing the next generation that never looks at neighboring cells, and seldom accesses neighbors at all. This can be accomplished by inverting the way the rules are implemented. Instead of a cell examining its neighbors learn its state, each occupied cell sends a single message to each of its neighbors. Since unoccupied cells never send a message they never access their neighbors and so if the population of the arena is, say, 20% of the total area then 80% of time no neighbor cells need to be accessed at all leading 1/9th as many array accesses and computation speeds up to 9 times faster per generation. In addition, this alternate way of computing the next generation is computed in place without the need to use a second copy of the arena to hold the intermediate results. This is accomplished by using 18 states per cell instead of 2 states. Instead of just being alive or dead cells can be alive in 9 different ways or dead in 9 different ways. These states are numbered 0 through 17. During the first pass through the arena the current state of each cell is fetched, and if the rule for that state calls for it, 1 is added to the state of each neighbor of that cell. In a sparse arena most of the cell states will not call for a contribution to be made to the neighbors and so the work on that cell is done as soon as the cell itself has been examined. After the entire arena has been updated in pass one a second pass is made during which each state found in a cell is replaced by the state called for in the rules. This completes the updating of the next generation. Each cell ends up either in state 0 (empty) or state 9 (full) and cells of any other state occur only during the generation loop, but never after it has been completed. This sedcond pass can be done at virtually no additional cost by making it part of the loop that updates the display. The inverse rule set is: st = current state. add = how much to add to each neighbor's state in pass one next = state to change to in pass two st add next 0 0 0 1 0 0 2 0 0 3 0 9 4 0 0 5 0 0 6 0 0 7 0 0 8 0 0 9 1 0 10 1 0 11 1 9 12 1 9 13 1 0 14 1 0 15 1 0 16 1 0 17 1 0 Verifying that it works: If a cell is in state 0 and has 3 neighbors its state will become 3 by the end of pass one which will transition to state 9 in pass 2. Thus, an empty cell with three neighbors will give birth to a cell with state 9. An empty cell with other than 3 neighbors will become some state less than 9 and other than 3. All of these states contribute nothing in pass one and transition to state 0 in pass two. If a cell is in state 9 or higher it will contribute 1 to each of its neighbors. If a cell is in state 9 and has 2 or 3 neighbors its state will become 11 or 12 in pass one, both of which transition to state 9 in pass two. If a cell is in state 9 and has other than 2 or 3 neighbors it will become a state greater than or equal to 9, but not equal to 11 or 12. All of these states transition to state 0 in pass two. Therefore at the conclusion of the generation loop there will be only two states, 0 and 9, which correspond exactly to the two states in GOL, and which follow the same birth and death rules as GOL. Pseudo code: // pass one for x = 0 to arenaMaxX for y = 0 to arenaMaxY if ruleAdd[arena[x,y]] not zero for dx = -1 to 1 for dy = -1 to 1 if dx not zero OR dy not zero arena[x,y] = arena[x,y] + 1 next dy next dx next y next x // pass two for x = 0 to arenaMaxX for y = 0 to arenaMaxY arena[x,y] = ruleNext[arena[x,y]] update display for cell[x,y] next y next x