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.<uint> 2^30 long, Flash hangs, then crashes.
Let’s assume for now that we’re going to deal with Life in 3×3 cell chunks. I’ll explain why later on. We’ll start with a 9×9 set of cells:
Then break that up into 3×3 chunks of cells.
Let’s look at 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 3×3 set of cells we need the ring around it, making the chunk we need to look at a 5×5 chunk of cells.
This is what ultimately limits the size of the chunks we can easily cache. 5×5 cells mean we need 25 bits to make them into a uint. 5×6 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 5×5 chunk, turn the pixels into bits, then put them together to make a uint.
Now we have the center chunk’s current 5×5 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.
Note that the ring around the 3×3 chunk is all empty. Since what we’re calculating for is the 3×3, that’s all we care about. We needed the 5×5 to be able to say what the 3×3 became and in the result we store the uint with only the 3×3 chunk filled out.
Once this is done for all of the 3×3 chunks, you run it all over again. In order to get the 5×5 you can mask out the bits needed in the neighbors, bitshift them, and bitwise-or them together to get the 5×5 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 1440×599) and then again to get a random start state. ‘p’ pauses the animation. Enjoy!
Update: I’ve posted my code for this on Github.