Introduction: A Cellular Automaton

Conway's Game of Life is the ultimate toy for the mathematically inclined. It is a simple cellular automaton that simulates the life and death of cells using extremely simple rules. It's playground is an infinite, two-dimensional grid of discrete, square cells that can either be alive or dead. At each step of the simulation, the following rules are apllied to all cells at once:

1. A living cell with less than two neighbours dies of loneliness
2. A dead cell with exactly three neighbours is "born" and alive next turn
3. A living cell with more than three neighbours dies of overpopulation

The Program

Draw cells onto the plane with the mouse. Then click the play button to make a single step, or the fast forward button for continuous simulation. At the start, you are using the cursor tool to switch single cells on or off. You can also use the 'stamp' tool to edit a preset colony, and stamp it all over the board. Or you can use the 'presets' tool to bring very special formations onto the plane. Use the arrow keys or scrollbars to scroll and the plus and minus keys to zoom.

Techniques: A Fast Computation Algorithm for Conway's Game of Life

The most naive implementation is to simply form two two-dimensional arrays, one buffer and one field of play. Place the cells on the field of play, and for a step of the simulation, go over each square of the buffer and apply the rules to it based on the field of play's living cells. After that swap both boards, clear the buffer and repeat. This is obviously suboptimal, since each cell is queried eight times for it's status, and the complexity is near O(8n²). So 2D-Arrays don't seem to be optimal.

There are hundreds articles on the Internet how to implement really fast algorithms for theGame of Life. Unfortunatley for me, each of those I found assumed that you wrote it in C++ or C. With enough knowledge, you can make predictions about how the register will be filled and use that to your advantage - Bitmasks are the magic word. Now that is all nice and well, but Actionscript is a script. It does compile to bytecode, okay, but I couldn't use the approach learned from other algorithms. So I had to find my own one. The requirements were as follows:

• Simulation of at least 10,000*10,000 sized colonies at acceptable speed
• Infinite size of board
• Algorithm ignores inactive areas on the board

I did not want to find and implement something too complex either, since that was not the focus of my work. Based on some other ideas I came up with the following data structure:

1. An array of integer, representing the live cells (even indexes including 0 indicate x-coordinate, odd indexes indicate y-position) called, well, cells
2. A 2D-Array of integer (Hey, didn't I want to go without these?!) - I call it the Neighbourhood-Matrix or short NHM. It basically holds the number of neighbours of a particular cell at the cell's coordinates.
3. A second array of the same structure as the first,the position of promising candidates, and so named candidates

How the algorithm works:
For the first step do assume there are a number of cells entered in the cell-array already.

1. create new empty array and assign it to candidates.
2. create a new empty NHM.
3. iterate over cells. For each cell,
   1. if it's value in the NHM is undefined, set it to 10, otherwise increase it by ten.
   2. add the cell to candidates
   3. for each of it's eight neighbours, look up the neighbour's value in the NHM and:
              a) if the value is undefined, set it to one
              b) otherwise increase value by one
              c) if the value equals three, add it to candidates (Note: This results in every cell
                 with a value of >= 3 to be in candidates)
4. Note: At this stage, the NHM holds all the information we need to decide whether a cell will live or die. According to the rules, we can deduce three magic numbers: 3 (Was dead and will be born), 12 and 13 (was alive and will survive)
5. create new empty array and assign it to cells.
6. iterate over candidates. For each cell, check if it's value in the NHM equals 3, 12, or 13. If so, put it in cells.

Source Code

I will make the Actionscript Files that correspond to the model of the program available. They contain the most interesting code anyway. The control and view components have suffered from my initially clumsy attempts to make Flex and Flash work together, since flash did the view part whereas the controls were written in flex. They should not be used as a template. The files will be posted here in the near future.

Credit where Credit is due

The predefined shapes and descriptions are taken from the Lexicon of Life by Edwin Martin, who in turn recompiled it from Steven A. Silver's Life Lexicon. Here you can find the full credits. Their work allowed me to import descriptions and cell-formations very convieniently for which I am very thankful. My edited version can be downloaded here. You are free to copy and distribute it as long as proper credit is given. And Mr. Martin and Mr. Silver deserve it more so than I.

If you got interested in the Game you should also check out Martin Edwins Game of Life Program. It is written in Java and far more perfomant than my implementation. It can be downloaded here.

Conclusion

It was nice to program in Flash again. It is a bit unfortunate that Adobe decided against a proper coding environment in the Flash IDE, but there are ways to get around this. I personally recommend using Flex Builder for programming and Flash for design only. The outcome is little more than a toy, but I strived for accessibility rather than complexity - and as such I am quite satisfied with the outcome.