Conway’s Game of Life is a nice demonstration of how simple rules can generate complex structures. It’s also a great introduction to the fascinating world of Cellular Automata.
see also: Game of life (revisited)
The Game of Life, or simply ‘Life’, takes place on an infinite 2-dimensional grid, populated by cells. In every next generation, the new state of each cell depends on the current state of the eight surrounding cells (its ‘Moore neighborhood’), following this simple set of rules:
- Living cells die if they have less than 2, or more than 3 living neighbors.
- Dead cells are brought to life if they have exactly 3 living neighbors.
The initial state of the system completely determines the further process, in which order and chaos can easily get involved in a continuous arm wrestling game.
Mathematicians and Life enthusiasts have found some incredible patterns like the Gosper Glider Gun, the Puffer Train and the Breeder. This video starts on a grid with ~25% of the cells ‘alive’ (randomly chosen).
The main challenge of running a simulation of ‘Life’ on an Arduino Uno lies in its limited RAM memory size (2K only!). Since the rules are applied to all cells simultaneously, we need to store both the old and the new state of the grid.
First I used Booleans to store cell states, but since every boolean claims a full byte (8 bits), the largest grid that Uno could handle was about 17×17 in size. The trick was to use bytes instead, where each byte now holds the state of eight consecutive LEDs in one of the rows, thus replacing eight boolean bytes!
With this new approach, Arduino Uno can simulate a 64×32 cell grid on my 128×64 pixels monochrome I2C Oled display (using 89% of Uno’s precious RAM). In that configuration, cells are represented by 2×2 LED squares, lit when alive and unlit when dead.
Note that you can define the initial state of the grid within the seed() function of the sketch. I used a simple border rule for the video: neighbor cells outside the grid are considered dead.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
/* Conway's Game of Life on Arduino Uno: 64x32 cells on a 128x64 oled display. Initial state generated by seed() function: ~25% randomly selected cells are alive. Sketch written by PaulF (2017) */ #include <Wire.h> #include <Adafruit_GFX.h> #include <Adafruit_SH1106.h> #define OLED_RESET 4 Adafruit_SH1106 display(OLED_RESET); const byte n_cols=64; const byte n_rows=32; const byte n_col_bytes=8; const byte cell_size=2; byte grid[2][n_rows][n_col_bytes]; byte gi_new=0; byte gi_old=1; void setup() { randomSeed(analogRead(0)); display.begin(SH1106_SWITCHCAPVCC, 0x3C); display.clearDisplay(); display.display(); delay(1000); seed(); disp(); delay(1000); } void loop() { gi_old ^= 1; gi_new ^= 1; calc(); disp(); } void seed() { for (byte r=0;r<n_rows;r++) { for (byte c=0;c<n_col_bytes;c++) { grid[0][r][c] = random(0,256)&random(0,256); } } } void calc() { for (byte r=0;r<n_rows;r++) { for (byte c=0;c<n_cols;c++) { byte nb = count(r,c); verdict(r,c,nb); } } } void disp() { for (byte r=0;r<n_rows;r++) { for (byte c=0;c<n_cols;c++) { byte bnr = c>>3; byte pos = c&7; if (bitRead(grid[gi_new][r][bnr],7-pos) == 1) { display.fillRect(c*cell_size,r*cell_size,cell_size,cell_size,WHITE); } else { display.fillRect(c*cell_size,r*cell_size,cell_size,cell_size,BLACK); } } } display.display(); } byte count(byte r,byte c) { byte count=0; for (int br=r-1;br<r+2;br++) { for (int bc=c-1;bc<c+2;bc++) { if ((bc!=c || br!=r) && bc>=0 && bc<n_cols && br>=0 && br<n_rows) { byte bnr = bc>>3; byte pos = bc&7; if (bitRead(grid[gi_old][br][bnr],7-pos) == 1) count++; } } } return count; } void verdict(byte r,byte c,byte nb) { byte bnr = c>>3; byte pos = c&7; switch (nb) { case 2: if (bitRead(grid[gi_old][r][bnr],7-pos) == 1) { bitSet(grid[gi_new][r][bnr],7-pos); } else { bitClear(grid[gi_new][r][bnr],7-pos); } break; case 3: bitSet(grid[gi_new][r][bnr],7-pos); break; default: bitClear(grid[gi_new][r][bnr],7-pos); break; } } |