The reason for making this project is that I was always fascinated by Conways Game of Life. It's a great demonstration of the fact that simple things with a very simple set of rules can do wonderful things: spawn more of them, modify themselves, do logical operations, even create Turing machines. I suspect much more can be done using them, but there are even more interesting methods of doing so.
I made a simple implementation of Life on a PC, but so have a bazilion other people before me, of which I found very useful this one. My implementation is on a simpler device: An AVR with a 4x20 character display.
Here's the youtube video:
The Rules of the Game
The rules are very simple: There's a 2D space organized into an XY grid of cells. A cell can be either DEAD or ALIVE. Each cell has 8 neighbours. The game is not a real time one, but a "turn based" one.The behaviour for the next-generation of cells is this:
- Any live cell with fewer than two live neighbours dies, as if by loneliness.
- Any live cell with more than three live neighbours dies, as if by overcrowding.
- Any live cell with two or three live neighbours lives, unchanged, to the next generation.
- Any dead cell with exactly three live neighbours comes to life.
The outcome of these rules is somewhat complex - a simple patern may create real marvels. Try loading some examples from the link above.
I play with AVRs alot - therefore I have chosen to use an AVR to control the process. The circuit is extremely simple - one AVR - the ATTiny2313, two resistors, a button, an LCD, two caps and that's it! The resistor is there to limit the current flowing into the backlight of the LCD. The button adds a few random cells into the space.
The AVR is the brain. It must be programmed with the hex file contained in the ZIP file down below. The AVR must be programmed to use the internal RC oscillator running at 8MHz without the internal prescaler. The fuses can be left on the factory setting, but the whole system will run at 1/8 of the desired speed. Which may be useful for those who wish to view in more detail the complex interactions of the cells. Oh, and you also need to enable the brouwnout detection for 4.3V or so. There's only one board, which I made on an universal board and soldered together with wires. You can see it on the picture on the right
The whole device runs of 5V. Power consumption is quite low - when you have no backlight on the LCD. If you have, than it can be anything from 100mA to 0.5A, depending on the type of the LCD used.
And here's the schematic (click for a better view):
NOTE: The pinout of your specific LCD might not be the same as the one I used. Beware
The Life implementation
The Game of Life requires quite a lot of space - not program, but it requires a lot of cells to grow in. The disadvantage of any character LCD is its size - the biggest have 4 lines and 40 columns, which totals up to 160 characters.
By defining custom characters that represent two cells in one character this can make up to 320 cells. But that's still not a lot. I'm using a 4x20 display, and the custom characters, so I'm at 160cells. That's a quite small number, therefore I used toroidal space - the end of the screen is connected to the bottom of the screen (space) and the x end ofthe space is connected to the x start of the space. While this is not exactly what Conway had in mind - to limit the space to a field of 8x20 cells - it produces very interesting paterns that wouldn't work elsewhere - for instance two oscillators that I found that work only in this space:
So, while it's a bit of cheating - it makes this possible for me. And here's a screenshot:
The software for this piece is very simple: it only uses two global arrays (makes the program smaller (in output size) than playing with pointers most of the time), a simple set of functions to determine whether a cell at x,y is alive, how many neighbours does it have, to liven it up or kill it, or display the output onto the display.
At first I used my own custom library to do the communication with the LCD. It worked, but then I tried using Peter Fleurys LCD library, which is very cool, is tested and worked like a charm. I'm not lazy to build one my self, but why not use a great one that's prebuilt and well documented?
The code flow is very simple: First, the HW is initialized, than the space is filled with a random patern (the random paterns are different each time - the device stores the previous settings in it's EEPROM), then goes into a loop where it displays the old generation, then recalculates the next generation of cells, storest it into the old generation, and detects whether the patern displayed is boring. Then it loops.
The Boredom Detection algorithm was the most problematic at first - in such a small space, the partern will not last for ever. If not properly planned (or a random patern) any patern will decay into a few elementary static (or simple oscillating) blocks, such as a block a blinker or a boat
These blocks are stable, but provide nothing interesting to see. At first I was trying complex algorythms to detect paterns, provide bizzare statistics, do calculations, but they were thwarted when for instance two blinkers and one block were left over. And what's more of a problem: they taken up vast amounts of memory - of which I had a limited amount - 2k of prog memory and 128b of RAM.So in the end I chose a simple definition of a boring patern:
-If the frame is static (the old generation is equal to the new generation) or there have been less than 2 changes, than it is boring.
-If there's less than 6 live cells on the whole space, than it is boring.
-If 200 generations have passed since the last boredom event occured, than it is boring.
-If the user pressed the boring button it is boring.
As soon as a space is considered boring, a random set of cells is inserted to liven up the space. They will interact with the remaining cells, or create a patern of their own. While this may not be the best aproach - it's an efficient approach, which gaurantees that the patern doesn't get boring. And it works quite well. If the user want the system to add random cells, he can always press the Button...
The software was written in C and compiled using the WinAVR avrgcc distribution, and using AVRStudio as the main IDE. The sourcecode is also included in the zip file.
contains the .hex file (main.hex) which needs to be programmed into the processor, the source codes, and the schematic, both in png and in eagle.
I have created this device for fun and to help me understand the Universe a little better. If you decide to build one - feel free to do so, but send me a photo - I will post it here and link it to your page. The source and everything is distributed under the GPL licence, with the exception of the library of Mr. Fluery, which is his own creation and a different licence may apply to it.
And in case you were wondering: The whole device looks like this:
Ghastly, isn't it? 🙂