Thursday, September 24, 2009

Conway's Game of Life on an Arduino

I'm finally back in Davis, but unfortunately one of the first things I did once I got here was come down with a miserable head cold. I therefore took the opportunity to play with my Arduino micro-controller, which I haven't really gotten a big chance to mess around with for a while.

For those who don't know, an Arduino is a very small computer, except it's designed to be hooked up to other basic electronics, i.e. LEDs and switches, instead of computer monitors and keyboards (which are actually possible). Last year I went down to Halted, and splurged on a 16x2 alphanumeric liquid crystal display for it, so I can quite easily display text on it, at the cost of 6 of the 14 I/O pins.

HD44780 based screens, like mine, have a pretty complete character set (page 17-18). On the off chance you need a few more specific characters that they don't happen to have, they have the ability for you to program 8 custom characters, simply by feeding it the 5x8 bitmap of the character. This is useful for when you want something iconic like a smiley face, but others have gotten more creative by using them to make bar graphs, etc, since you can program anything you want into it.

The idea came to me: with 8 custom characters, you could essentially make a 20x16 matrix display, which would be perfect for the Game of Life. 100 lines of C code later, I had a working Life engine. Another 60 to add extra features like checking for when it's in a steady state, and this is what I end up with:

How I store the world isn't especially elegant. I use an entire byte for each grid, where I really only need two bits for the basic engine (current state and the state for the next step). I thought about doing all the crazy bit packing needed to access each individual bit, but decided against it. Instead, I stored the current state as a 1, then as I calculated the state for the next step, stored it as a 2. Once I finished working through the whole world, divide everything by 2, and all you have left is the next steps state. That's 320 bytes, for those of you counting at home.

I then ran into the problem that, eventually, the world is going to end up being a lot of steady state blocks, or oscillators, which posed a problem. If I was only worried about it being frozen, I could just keep track to see if anything changed while calculating the next step, and set a flag, but the oscillators will change, rather uninterestingly, every step. According to Wikipedia, the oscillators can have a period of up to 30, but I figured the only ones I was really worried about were 2 and 3, since anything more than that was unlikely on such a small world, and probably pretty cool anyways. To deal with this issue, every 6 steps I save a copy of the world and compare it to the world from 6 ticks ago. Now if the only thing left is oscillators, they will end up in the same state 6 steps later, and the engine will catch it and reset the world. That is another 320 bytes, which is 8 times what I really need, and now means I'm using 640 bytes of only 1k of RAM just to store the world. Not great, but since that's all I'm doing, it's ok, right?

Calculating each step only takes a few milliseconds, so I have a 300ms delay on the end of each tick, so it could be run quite a bit faster. For those who are interested in seeing the code for it, here it is: