[ R.I.P. ]
MSX Utilities
 by Oleg Alferov aka Secoh 
     

Uplink...

in Russian...


Windows
Utilities



MSX
Emulator...



About...

Links...

Friends...

Mailing List...
 
BASIC Editors    BASIC Visual effects    BASIC Games    Programming studies    File converters

The Game of Life algorithm

The program implements special algorithm to increase the speed of calculations. Since there is no need in analysing cells that are dead and there are no alive cells around, the program maintains a special list of alive cells, and list of cells that can change status on the next turn.

In the beginning of the cycle, there is the field of cells where stored ether 0 for dead cell, or some big value for alive cell (for example, 100). The list of cells contains all alive cells, and only them. The alive cell candidates list is empty. The step one: for each alive cell from the first list, find all its neighbors (8 cells) and increment their field values by 1. After completion of this step, each cell of the field of cells will contain the number of its neighbors. (For the currently alive cells — 100 plus the number.)

Additionally, during the first step, add to the second list: a) the cell that was taken from "live" list, and b) its neighbour, if its value is 0. This guarantees that all cell that can change the status, will be present in the second list.

Clear the first list. The step two: for each cell from the second list, mark it alive (i.e. assign 100 to the corresponding place in the field) if its value there was 3, 102 or 103. Otherwise, assign 0 (dead). Add cell, if alive, to the list of alive cells (first). After completion of the second step, clear the second list.

Performing of cycles of these two steps meets the game of Life rules (verify it!) and provides the fastest possible algorithm. There is room for further enhancements, such as detection of "frozen" cells or groups of cells that perform short cycles. I leave this analysis for my reader.
 


© 2002,
Oleg Alferov
aka Secoh
secoh@anl.gov