Close
0%
0%

Conway's Game of Life on ATtiny84

ATtiny84-based gamed of life on 8x8 LED matrix with manual setup of 1st generation.

Similar projects worth following
The aim of this project is to demonstrate the possibility to implement Conway's game of life with less than 1KB code on Atmel AVR architecture.
The project allows manual setup of the board cells at its beginning, so that we can then discover the evolution for some of the common "cells patterns" in this game.
Note that although this is named "Game of Life", it is not really a game, so don't expect to play anything real here!

Actually, this project is a practical example of usage of FastArduino library, which goal is to optimize Arduino/AVR programs in terms of size and speed.

Conway's Game of Life

This project implements well known Conway's Game of Life.

Note that this implementation uses Periodic Boundary Conditions to simulate a field of an infinite size, i.e. each boundary is connected to the opposite boundary. This makes algorithm a bit more complex to implement but it mimics better the intent of this game.

How to play

First, you need to setup the initial lives (first generation) on the 8x8 LED matrix.

For that, you use 2 knobs (potentiometers) to point to a cell (blinking LED) and a button to change its state (alive or not).

You can define the first generation any way you see fit.

Once you are done with first generation setup, you can start the game by pressing the START button.

Then, generations get calculated and displayed, one after another, at regular intervals (speed is controllable through the left knob used in the previous setup stage), from a few hundred ms to a few seconds.

The START button can also be used to pause the game, then resume it at a later time.

The situation where we reach a generation with no cells alive, is detected and a smiley displayed to show that.

If the system reaches a stable situation (with live cells that never change), this is indicated by blinking those cells.

The following video demonstrates all that:

Circuit & Prototypes

The circuit is based on an ATmel ATtiny84A AVR MCU that contains all logic.

The ATtiny84A has 8KB flash (code and init data) and 512 bytes RAM (for static and local variables in stack), hence a smaller MCU like ATtiny24 (2KB flash and 128 bytes RAM) would work as well, but I did not have any in my drawers, hence I did not test it.

The ATtiny84 is a tiny MCU with "only" 11 available IO pins (digital and some analogic).

Hence addressing an 8x8 LED matrix is better done using SIPO (Serial In, Parallel Out) shift registers, I used 2 chained 74HC595, one for matrix rows (LED anodes), the other for the columns (LED cathodes). I added current-limiting resistors to all 8 columns, to avoid roasting the MCU. Wiring for this takes only 3 digital output pins of the MCU (data, clock and latch).

LED matrix addressing is done though multiplexing (display one complete row at a time during a few ms, then display the next row, and so on). If all rows get "swept" fast enough, then human eye persistence makes you think all the matrix is displayed at the same time. I determined (after experiments) that showing each row during 2ms, then handling the next, i.e. 16ms to display all 8 rows, was the longest delay I could use. In the final program, I use 1ms for that duration.

For 1st generation setup, I originally used 3 push buttons, one Previous/Next pair to position the "cursor" (blinking LED) to the cell which we want to change state (dead or alive), then one button to switch the state of currently selected cell. This worked fine but that made the first phase very slow to setup for the end user. Wiring here required 3 digital inputs (one per button).

I hence decided to use 2 rotating knobs (potentiometers), just like the famous "Etch a Sketch" toy, to go faster to a position in the matrix. I kept one push button for changing the state of the currently selected cell. Wiring then took 2 analog input pins and 1 digital input pin.

An analog joystick with a button on top would probably be the ideal device for this, but I did not have one at disposal. Anyway, the program and the wiring should remain the same (or roughly so for the wiring).

The circuit has another button, used to start the game (used to tell the system that setup of the first generation is finished) and also suspend it at any time, then resume it.

Finally, to make the project a bit more challenging, trying to use the last available byte of code, I decided to reuse one of the pots used for initial setup for controlling game speed.

Here are the schematics for this circuit (made with KiCAD):

My first prototype was originally developed on an Arduino UNO (it uses an ATmega328P, compatible with ATtiny, with just more pins, more bytes...

Read more »

conway.dump.txt

The assembly dump file of Conway program for ATtiny84. This demonstrates the code size is under 1024 bytes (962 bytes exactly).

plain - 24.57 kB - 12/30/2016 at 08:39

Download

  • 1 × ATtiny84A Microprocessors, Microcontrollers, DSPs / ARM, RISC-Based Microcontrollers
  • 2 × 74HC595 Electronic Components / Misc. Electronic Components
  • 1 × Red LED matrix 8x8
  • 1 × Tantalum capacitor 10uF
  • 3 × Ceramic capacitor 100nF

View all 15 components

  • Project is now ready for contest!

    Jean-François Poilpret12/29/2016 at 23:01 0 comments

    I have just finalized all code and documentation, on github, for this project.

    The project is now ready to be submitted to the Hackaday 1KB contest.

  • Almost finished!

    Jean-François Poilpret12/16/2016 at 16:00 0 comments

    The boards are finished (see project newly updated picture), the program currently runs fine and is less than 1KB.

    I still need to:

    - Add some matrix cleanup at the end of the game

    - Possibly add possibility to change game speed through one of the pots

    - Add an electronics schema of the global circuit

    - Finish the README on github

    In addition, I consider one improvement to the code, by making it parametered on matrix size (not fixed to 8x8) and check if program size would still fit under 1KB for e.g. 16x16.

  • Board design is ready!

    Jean-François Poilpret12/10/2016 at 17:14 0 comments

    During the past few days, I have been working a lot on designing the boards for the project.

    Since I am a fan of stripboards and I have a bunch of these in my drawers, I decided to go with these, rather than PCB (maybe in the future).

    I decided to use 90x50mm stripboards which I designed with LochMaster, a tool I have been using for several years now, and perfect for the job).

    The project will use 2 stripboards, stacked on one another, just like Arduino and its shields. That is the only option I found in order to fit all components in rather small form factor.

    Under board

    Above board

    Now the design is over, I'll start preparing these boards (cut strips, cut wires, solder all components and check everything in the end) so hopefully I can soon post pictures of the finished boards.

    Besides, I am improving the source code in order to make use of the latest available byte (max 1024 allowed for the contest): now it is detecting the end of game (still life or no life at all) and it will soon show a blinking smilie when there's no live cell left.

    I am also working on pausing the game through reuse of the START button (the one which is sued once you have finished setting up the board configuration with the first generation of cells).

    Finally, if there is still space left, I'll use one pot to change generation evolution speed). More on that next week.

  • 2nd prototype

    Jean-François Poilpret12/07/2016 at 21:30 2 comments

    I have just finished updating my current prototype to use 2 potentiometers (row/column) to locate a board cell, in replacement of 2 previous/next buttons.

    That makes the first stage (1st generation setup) much easier to perform for the end user.

    In addition, this change even reduced current program size on ATtiny84: only 912 bytes used currently!

    Now I have to go on with my stripboards design to make thsi proejct look better.

    Regarding the program itself, since I still have a huge amount of memory left (112 bytes), I need to find some way to use this amount; here are my ideas (not exclusive):

    • allow suspend/resume of 2nd phase of the game (reuse START/STOP button)
    • modify generation refresh speed (reuse one of the 2 potentiometers in 2nd phase
    • detect end of game (empty board or still generation) and display some hardcoded smilie

  • Project status update

    Jean-François Poilpret12/06/2016 at 22:54 0 comments

    Project is still in progress.

    I had a hard time trying to figure out how to put all this stuff onto a 90x50mm stripboard, and finally decided to stack 2 stripboards of that size:

    • LED matrix, buttons and pots above
    • all IC, caps, resistors underneath

    with pin headers to connect both stripboard (a bit like Arduino shields).

    Board design is not complete yet but I'm almost there, hope to finish it tomorrow and implement it this week-end. Design is available on github (as LochMaster files).

    Besides, I have ported the current prototype (with only buttons) from Arduino UNO to ATtiny84 and it works fine.

    However, I noticed some issues with the light level of LEDs in the matrix; reducing resistors values helped a little bit but not that much; I need to find a way to provide enough current for a complete row of LEDs but I'd like to avoid adding transistors to the circuit...

    Finally, on FastArduino library, I could finally implement Analog Digital Conversion, hence I'll soon be able to replace buttons to move cursor backward/forward with 2 pots (one for X, one for Y), which will make it faster and easier for the user to select LEDs to set for the first generation of the game.

    Hopefully this week-end, the prototype will be running fine with 2 pots.

  • 1st prototype

    Jean-François Poilpret12/04/2016 at 11:14 0 comments

    Project has started on November 26th.

    So far I have a running prototype (Arduino UNO for the moment) where initial board setup is done though simple buttons.

    Next steps are to replace some buttons with pots, to make it easier to select a LED in the matrix, hence make initial board setup step faster. The challenge here will be to check the code size will still fit in 1KB.

    In addition, I am just starting to design a simple stripboard for the whole circuit (except battery holder).

View all 6 project logs

Enjoy this project?

Share

Discussions

Jean-François Poilpret wrote 12/15/2016 at 18:47 point

Hi Yann, calculating the full popcount was intentional, to be consistent at this level of computation. I did not change the rules of the game though, I just rephrased them to fit the whole count:

- any count other than 3 or 4 means a dead cell

- a count of 3 means that the cell must be live, whatever its previous state

- a count of 4 means that the cell must keep its previous state

This is what is implemented based on the ok and code flags returned by the neighbours() method.

I have already checked several standard patterns (still life, glider, periodic) that fit the 8x8 board, and it works fine.

Regarding inlining, this is already done thanks to the GCC options I use during compile and link time. If I look at the produced assembly, the whole program has only the following functions:

- AbstractButton::_unique_press() not part of the algorithm

- Matrix8x8Multiplexer::refresh() not part of the algorithm

- main() contains all the rest, including the whole game algorithm inlined

As of now, with current code size of 908 bytes, I don't think I'll need to further optimize the code, as the only feature I want to add now is the possibility to change the speed of generation evolution with one of the existing pots.

Another test I will do is to improve the current code so it can be parametered further to handle other matrix sizes; then I'll check the new code size for a 16x16 matrix.

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/17/2016 at 01:00 point

I'll have to think through all of this... Thanks for the explanations !
Do you mind if we continue talking about this in private or in my project page ?

  Are you sure? yes | no

Jean-François Poilpret wrote 12/05/2016 at 18:14 point

Thanks Yann, this looks interesting. I'll take a depper look at it once I have progressed on other parts (hopefully in one week). Cheers

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/05/2016 at 21:30 point

Enjoy !
And if you need, you can contact me.

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/05/2016 at 15:07 point

For the computational part, you can use the system I developed at #Game of Life bit-parallel algorithm since the screen resolution equals the register width :-) A simple example is provided in C, you can strip the range detection parts and loop over 8 lines. I'm sure it will run faster and use less memory :-)

  Are you sure? yes | no

Jean-François Poilpret wrote 12/14/2016 at 22:30 point

Hi Yann, I just finished implementing bit-parallel computation on my prototype. I have to admit that it took me some time to understand the principles you explained. Once I udnerstood those principles, I decided to reimplement by myself to ensure I fully understood it. I had to perform quite some debugging until it worked by now it is fine. I may even have optimized what you proposed (not 100% sure on that one though). If you are interested you can check the implementation here: https://github.com/jfpoilpret/fast-arduino-lib/blob/master/examples/complete/Conway/Game.hh

I am very happy by the amount of code gained by using this algorithm: more than 100 bytes less!

Now, my program is using 908 bytes of code, and it is almost finished. The last (according to my current improvements ideas) stuff to implement is to allow setting the wait time between each generation by reusing one of the pots I already use. That should not take more than a few dozen extra bytes; we'll see.

Cheers

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/15/2016 at 08:42 point

Hi !

Glad to read this !

I looked at the code and there might be a little issue, though I couldn't simulate well in my head. I'm also not familiar with C++ (which doesn't make sense in this context, but who am I to judge ? :-D). My concern is with the first adder, there must be a first half-adder with row1 and row3, THEN a full adder with row1, row2 and row3. Otherwise you perform a full "popcount" over all 9 neighbours, which is a different rule than Conway's game.

Did you see the complete analysis at https://hackaday.io/project/14628-ambap-a-modest-bitslice-architecture-proposal/log/49599-what-about-a-game-of-life ?

regards :-)

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/15/2016 at 08:53 point

furhtermore I encourage you to thouroughly test your code with known patterns, such as the glider and glider gun. You'll find my test code in the project. It runs on 64 bits and the glider gun won't fit but I have doubts about your code so I'm eager to see it run for real :-)

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/15/2016 at 08:58 point

Finally, if code space is critical, you might try to "unroll" or "inline" the add functions, because I suspect that the function parameter dance (push parameters on the stack, call, return, clean the stack) might waste quite a bit of space compared with doing the computations right away.

  Are you sure? yes | no

Similar Projects

Does this project spark your interest?

Become a member to follow this project and never miss any updates