Sean Cooper recently ran a challenge at Lolapps to create the fastest version of Conway's game of life in Flash that we could. Of course, he first showed us his version which uses a convolution filter, but that's not what this challenge was about. The idea was to figure out how to make AS3 both perform and display as fast as possible. Of course I immediately found someone else's Pixel Bender version but after playing with that I went my own route to see what I could do in pure AS3.
For the impatient, you can view an animation which helps to explain the concept or jump straight to the result.
Pretty quickly, the discussion I was a part of moved towards the possibility of caching. After getting the initial naive version of Life finished, I let the caching idea bounce around in my head and finally came up with an idea. Since (basic) life has only two states per pixel, alive or dead, these map trivially to bits. Taking an arbitrary rectangle of the map and reducing it to a simple integer then is easy. Additionally, operations on this section can be done via bitshifting and bitwise operations, which tend to be extremely fast. Unfortunately, the uint in AS3 is only 32 bits long, so this limits the size of the "chunk" we can put into a single uint, but then again 2^32 would be a lot of states to possibly store and/or calculate. I also found that if I try to make a Vector.
Let's assume for now that we're going to deal with Life in 3x3 cell chunks. I'll explain why later on. We'll start with a 9x9 set of cells:
A 9x9 section of cells
Then break that up into 3x3 chunks of cells.
3x3 chunks
Let's look at the center chunk:
The center chunk
The simple life rules make each cell depend on its immediate neighbors in every direction.
- If a cell has less than 2 live neighbors it dies (or stays dead) due to loneliness.
- If a cell has 2 live neighbors it stays as it is, dead or alive.
- If a cell has 3 live neighbors it is alive in the next iteration (dead cells come alive, live cells stay alive).
- If a cell has 4 or more live neighbors it dies of overcrowding.
To run these rules for a single cell we need the ring of cells around it to calculate its next state. In the same way, to calculate the next state of a 3x3 set of cells we need the ring around it, making the chunk we need to look at a 5x5 chunk of cells.
5x5
This is what ultimately limits the size of the chunks we can easily cache. 5x5 cells mean we need 25 bits to make them into a uint. 5x6 would make 30 bits and a simple array that big crashes Flash.
Now that we've established the basics of what we need it's just a matter of figuring out how to efficiently calculate, store, and retrieve the values.
We'll store the state transitions in a simple vector of uints. The index will be the current state and the value is the next state. For the current state we take the 5x5 chunk, turn the pixels into bits, then put them together to make a uint.
5x5 as bits, the top-left is the least significant bit (2^0)
= 9870129
Now we have the center chunk's current 5x5 state as a uint. 9870129 will be the index into the state transition map. Now we need the state that this will become after the rules are applied.
The next state
Note that the ring around the 3x3 chunk is all empty. Since what we're calculating for is the 3x3, that's all we care about. We needed the 5x5 to be able to say what the 3x3 became and in the result we store the uint with only the 3x3 chunk filled out.
Result bits
= 4194688
Once this is done for all of the 3x3 chunks, you run it all over again. In order to get the 5x5 you can mask out the bits needed in the neighbors, bitshift them, and bitwise-or them together to get the 5x5 uint to index back into the state transition map. To speed things up even more you can store those masked and bitshifted parts separately so all you need to do is bitwise-or them together to find out what the next state is.
If you made it this far, thanks for reading. Here again is a link to the explanatory demo, which is where the screenshots above came from.
And, finally, the result. The fastest Life implementation I've made thus far. :-) You can press 'r' to switch to another pattern (try resizing to 1440x599) and then again to get a random start state. 'p' pauses the animation. Enjoy!
Click to view the completed application
