Conway's Life

Duane · Posted: Sun Feb 27, 2011 7:07 pm

Here's the source for Conway's Life.

/**
 *
 * Conway's Life
 *
 * Conway's life is a simple cellular automaton - the playboard is a grid of "cells". Each cell follows
 * certain rules - for each generation a "off" cell turns "on" if it has exactly three of its eight neighboring
 * cells "on", and stays "on" if either two or three neighbors are "on", otherwise the cell turns "off".
 *
 * Most programs keep two grids, however, this device is very limited in memory, so only a single buffer is kept.
 * In addition, several optimizations have been done given the known, fixed dimensions of the display.
 *
 * This version uses a clever trick to count neighbors, adapted from the Smalltalk-80 "Blue Book" pp 412-413
 * that uses simple Boolean operations.  This should keep the CPU load down, a precious commodity in a small
 * embedded device.
 *
 * Copyright (C) 2011, Duane Maxwell [email protected]
 *
 * Permission to use, copy, modify, and/or distribute this software for  
 * any purpose with or without fee is hereby granted, provided that the  
 * above copyright notice and this permission notice appear in all copies.  
 *  
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL  
 * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED  
 * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR  
 * BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES  
 * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,  
 * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,  
 * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS  
 * SOFTWARE.
 **/

#include <pulse_os.h>
#include <pulse_types.h>
#include <stdint.h>

// a simple random number generator
uint32_t m_w, m_z;

void mysrand() {
   struct pulse_time_tm tm;
   pulse_get_time_date(&tm);
   m_w = (((tm.tm_hour<<6)+tm.tm_min)<<6)+tm.tm_sec;
   m_z = (((tm.tm_year<<4)+tm.tm_mon)<<5)+tm.tm_mday;
}

uint32_t myrand() {
   m_z = 36969L * (m_z & 65535L) + (m_z >> 16);
   m_w = 18000L * (m_w & 65535L) + (m_w >> 16);
   return (m_w & 65535L) + (m_z << 16);
}

void clearLine(uint32_t *dst) { // clear the line
   dst[0] = dst[1] = dst[2] = 0;
}

void randomLine(uint32_t *dst) { // fill line with random data
   dst[0] = myrand();
   dst[1] = myrand();
   dst[2] = myrand();
}

void copyLine(uint32_t *src,uint32_t *dst) { // copy src into dst
   dst[0] = src[0];
   dst[1] = src[1];
   dst[2] = src[2];
}

void rolLine(uint32_t *src,uint32_t *dst) { // Copy src rotated 1 bit left into dst
   dst[0] = (src[0]<<1) | (src[1]>>31);
   dst[1] = (src[1]<<1) | (src[2]>>31);
   dst[2] = (src[2]<<1) | (src[0]>>31);
}

void rorLine(uint32_t *src,uint32_t *dst) { // Copy src rotated 1 bit right into dst 
   dst[0] = (src[0]>>1) | (src[2]<<31);
   dst[1] = (src[1]>>1) | (src[0]<<31);
   dst[2] = (src[2]>>1) | (src[1]<<31);
}

void andLine(uint32_t *src, uint32_t *dst) { // AND src into dst
   dst[0] &= src[0];
   dst[1] &= src[1];
   dst[2] &= src[2];
}

void xorLine(uint32_t *src,uint32_t *dst) { // XOR src into dst
   dst[0] ^= src[0];
   dst[1] ^= src[1];
   dst[2] ^= src[2];
}

void orLine(uint32_t *src,uint32_t *dst) { // OR src into dst
   dst[0] |= src[0];
   dst[1] |= src[1];
   dst[2] |= src[2];
}

void andNotLine(uint32_t *src, uint32_t *dst) { // AND the NOT of src into dst
   dst[0] &= ~src[0];
   dst[1] &= ~src[1];
   dst[2] &= ~src[2];
}

#define INTS_PER_LINE (SCREEN_WIDTH/sizeof(uint32_t)/8)
#define NUM_LINES (SCREEN_HEIGHT+2)

uint32_t grid[NUM_LINES*INTS_PER_LINE];
uint32_t *lineStarts[NUM_LINES];

color24_t white = {0xff,0xff,0xff,0xff};
color24_t black = {0x00,0x00,0x00,0x00};

void initGrid() {
   for (int y=0;y<NUM_LINES;y++) {
      lineStarts[y] = &grid[y*INTS_PER_LINE];
   }
}

void resetGrid() {
   mysrand();
   for (int y=1;y<NUM_LINES-1;y++) {
      randomLine(lineStarts[y]);
   }
}

void drawGrid() {
   pulse_set_draw_window(0,0,SCREEN_WIDTH-1,SCREEN_HEIGHT-1);
   for (int y=1; y<=SCREEN_HEIGHT;y++) {
      uint32_t *line = lineStarts[y];
      for (int i=0;i<3;i++) {
         uint32_t segment = line[i];
         for (int j=0;j<32;j++) {
            pulse_draw_point24((segment>>31)==1 ? white : black);
            segment <<= 1;
         }
      }
   }
}

void acc(uint32_t *line, uint32_t *nbr1,uint32_t *nbr2,uint32_t *nbr4, uint32_t *carry2, uint32_t *carry4) {
   copyLine(nbr1,carry2); // copy one's digit to first carry
   andLine(line,carry2);  // compute the carry
   xorLine(line,nbr1);      // compute the partial sum

   copyLine(nbr2,carry4); // copy the two's digit to second carry
   andLine(carry2,carry4); // compute the new carry from one's digit overflow
   xorLine(carry2,nbr2);  // compute the partial sum

   xorLine(carry4,nbr4); // compute the partial sum for four's digit (we don't care past this digit)
}

void nextGrid() {
   uint32_t last[INTS_PER_LINE];
   uint32_t lastR[INTS_PER_LINE];
   uint32_t lastL[INTS_PER_LINE];
   uint32_t curr[INTS_PER_LINE];
   uint32_t currR[INTS_PER_LINE];
   uint32_t currL[INTS_PER_LINE];
   uint32_t next[INTS_PER_LINE];
   uint32_t nextR[INTS_PER_LINE];
   uint32_t nextL[INTS_PER_LINE];

   // copy first and last lines for wrapping
   copyLine(lineStarts[1],lineStarts[NUM_LINES-1]);
   copyLine(lineStarts[NUM_LINES-2],lineStarts[0]);

   // create first "current" line
   copyLine(lineStarts[0],curr);
   rolLine(curr,currL);
   rorLine(curr,currR);

   // create first "next" line
   copyLine(lineStarts[1],next);
   rolLine(next,nextL);
   rorLine(next,nextR);

   for (int y=1;y<=SCREEN_HEIGHT;y++) {
      copyLine(curr,last); // copy "current" to "last"
      copyLine(currL,lastL);
      copyLine(currR,lastR);
      copyLine(next,curr); // copy "next" to "current"
      copyLine(nextL,currL);
      copyLine(nextR,currR);
      copyLine(lineStarts[y+1],next); // fetch new "next"
      rolLine(next,nextL);
      rorLine(next,nextR);

      // create accumulator/carry buffers
      uint32_t nbr1[INTS_PER_LINE];
      uint32_t nbr2[INTS_PER_LINE];
      uint32_t nbr4[INTS_PER_LINE];
      uint32_t carry2[INTS_PER_LINE];
      uint32_t carry4[INTS_PER_LINE];

      // clear them
      clearLine(nbr1);
      clearLine(nbr2);
      clearLine(nbr4);
      clearLine(carry2);
      clearLine(carry4);

      // accumulate the eight neighbors
      acc(lastR,nbr1,nbr2,nbr4,carry2,carry4);
      acc(last, nbr1,nbr2,nbr4,carry2,carry4);
      acc(lastL,nbr1,nbr2,nbr4,carry2,carry4);
      acc(currR,nbr1,nbr2,nbr4,carry2,carry4);
      acc(currL,nbr1,nbr2,nbr4,carry2,carry4);
      acc(nextR,nbr1,nbr2,nbr4,carry2,carry4);
      acc(next, nbr1,nbr2,nbr4,carry2,carry4);
      acc(nextL,nbr1,nbr2,nbr4,carry2,carry4);
      
      // "fix" the current line
      uint32_t *line = lineStarts[y];
      andLine(nbr2,line); // kill any cells without two neighbors
      andLine(nbr2,nbr1); // create mask for cells with three neighbors
      orLine(nbr1,line); // turn them on
      andNotLine(nbr4,line); // turn off cells with four or more neighbors
   }
}

void handle_button_causing_wakeup();

void main_app_init() {
   pulse_blank_canvas();
   pulse_oled_set_brightness(100);
    pulse_update_power_down_timer(20000);
    pulse_register_callback(ACTION_WOKE_FROM_BUTTON, &handle_button_causing_wakeup);
   initGrid();
   resetGrid();
   drawGrid();
}

void handle_button_causing_wakeup() {
   pulse_oled_set_brightness(100);
   pulse_update_power_down_timer(20000);
}

void main_app_handle_button_down() {
   resetGrid();
   pulse_update_power_down_timer(20000);
}

void main_app_handle_button_up() {
}

void main_app_loop() {
   nextGrid();
   drawGrid();
}

void main_app_handle_doz() {
    for (int i = 100; i >= 0; i-=6) {
        pulse_oled_set_brightness(i);
        pulse_mdelay(60);
    }
}

void main_app_handle_hardware_update(enum PulseHardwareEvent event) {

}

EDIT: minor change to better handle wakeup.

Craig · **Joined:** Sat Feb 19, 2011 3:01 pm **Posts:** 12

You know what would be pretty rad? Use a display of the time as the initial seed for the Game of Life. Then reset the Game's state every second with the new time, and let it run. That would look so amazing.

Duane · Posted: Wed Mar 02, 2011 4:49 pm

Actually, I have that more or less working exactly as you've described.

Unfortunately, it's not as exciting as you'd think it would be. I'm trying to find a way to spruce it up.

I've also found a way to add a little more interest to the basic graphics - there is a way to tell which cells are new and which cells died and they could be color coded.

Conway's Life

Who is online