John Horton Conway’s Game Of Life

April 20, 2012

We steal the screen-handling code from a prior exercise:

(define esc (integer->char 27))
(define (cls)
  (display esc) (display #\[)
  (display #\2) (display #\J))
(define (hide-cursor)
  (display esc) (display #\[) (display #\?)
  (display #\2) (display #\5) (display #\l))
(define (show-cursor)
  (display esc) (display #\[) (display #\?)
  (display #\2) (display #\5) (display #\h))
(define (goto r c)
  (display esc) (display #\[) (display r)
  (display #\;) (display c) (display #\H))
(define max-r 24) (define max-c 39)

(define (show grid)
  (for (r 0 max-r)
    (for (c 0 max-c)
      (when (matrix-ref grid r c)
        (goto r (+ c c 1)) (display #\*)))))

The neighbors function counts the number of occupied cells that adjoin the given cell, wrapping around at the edges:

(define (neighbors grid r c)
  (define (cell rc)
    (if (matrix-ref grid (modulo (+ r (car rc)) max-r)
          (modulo (+ c (cadr rc)) max-c))
      1 0))
  (apply + (map cell
    '((-1 -1) (-1 0) (-1 1) (0 -1) (0 1) (1 -1) (1 0) (1 1)))))

The Game of Life is implemented using two grids, so that all the assignments happen simultaneously; the input grid, init, is read at each step as the output grid, next is built one cell at a time, then the output grid replaces the input grid at the recursive call of the function. The Scheme idiom for <= allows us to use three operands to implement a between operator:

(define (life init)
  (cls) (hide-cursor) (show init)
  (let ((next (make-matrix max-r max-c)))
    (for (r 0 max-r)
      (for (c 0 max-c)
        (matrix-set! next r c
          (or (and (matrix-ref init r c)
                   (<= 2 (neighbors init r c) 3))
              (and (not (matrix-ref init r c))
                   (= (neighbors init r c) 3))))))
    (life next)))

A function to generate a random initial population is shown below. Some populations quickly die, others churn for a long time, all eventually become stable. You can watch what happens to a random population by saying (life (rand-init)):

(define (rand-init)
  (let ((grid (make-matrix max-r max-c #f)))
    (for (r 0 max-r)
      (for (c 0 max-c)
        (if (< (rand) 1/2) (matrix-set! grid r c #t))))
    grid))

One of the most famous Life patterns is the glider, which keeps moving endlessly along the infinite grid:

(define glider
  (let ((grid (make-matrix max-r max-c #f)))
    (matrix-set! grid 0 1 #t)
    (matrix-set! grid 1 2 #t)
    (matrix-set! grid 2 0 #t)
    (matrix-set! grid 2 1 #t)
    (matrix-set! grid 2 2 #t)
    grid))

We used the matrix functions, the for macro, and the random number generator from the Standard Prelude. You can see the complete program at http://programmingpraxis.codepad.org/l6ExmA3j.

Pages: 1 2

6 Responses to “John Horton Conway’s Game Of Life”

  1. ardnew said

    Pulled a lot of code from the Voters exercise.. This isn’t really implemented as an infinite two-dimensional grid, as the generations just wrap around the edges and persist in the same finite space, but here’s a solution in perl:

    use strict;
    use warnings;
    
    our $NROWS = 20;
    our $NCOLS = 20;
    our $DELAY = 0.1; # seconds
    
    sub gen_grid
    {
      my ($r, $c, $d, @g) = @_;
     
      push @g, [map {int(rand($d + 1))} (1 .. $c)] for (1 .. $r);
      return @g;
    }
    
    sub print_grid
    {
      print "\033[2J";
      print +(join '', @$_).$/ foreach @_;
      select undef, undef, undef, $DELAY;
    }
     
    sub neighbors
    {
      my ($y, $m, $x, $n, $g) = @_;
      
      return grep 
        { 
          $$g[($y + $$_[0]) % $m][($x + $$_[1]) % $n] 
        }
        ([-1,-1],[-1, 0],[-1, 1],[ 0,-1],
         [ 0, 1],[ 1,-1],[ 1, 0],[ 1, 1])
    }
    
    sub main
    {
      my ($rows, $cols) = @_;
      my @grid = gen_grid($rows, $cols, 1);
    
      while (1)
      {
        my @next = gen_grid($rows, $cols, 0);    
        print_grid(@grid);
        
        foreach my $r (0 .. $rows - 1)
        {
          foreach my $c (0 .. $cols - 1)
          {
            my $n = neighbors($r, $rows, $c, $cols, \@grid);
            $next[$r][$c] = $grid[$r][$c] & ($n == 2) | ($n == 3);
          }
        }        
        @grid = @next;
      }
    }
    
    main($NROWS, $NCOLS);
    
  2. stungeye said

    Here’s a test-driven game of life I wrote in Ruby last year:

    Tests (Minitest Specs): http://stungeye.github.com/tdd_game_of_life/test_life.html
    Game of Life Code: http://stungeye.github.com/tdd_game_of_life/
    Simple GUI: http://stungeye.github.com/tdd_game_of_life/shoes_life.html

  3. Kwiatki said

    I came across the Game of Life in One Hundred Computer Programming Problems by Newey. I got hooked, spent a lot of time with a pencil and an eraser, used the Go board too. But I think I only learned about the glider when I saw one as a screensaver on a Sun workstation years later.

  4. [...] John Horton Conway’s Game Of Life « Programming Praxis [...]

  5. Reblogged this on Jamison White's Blog and commented:
    I completed a rough text only version of it. I tried to limit myself to declarative Python statements (no for loops).

  6. Dennis Smith said

    The September 1985 issue of Nibble magazine published my “One-Liner” version of John Conway’s Game Of Life. The rules for the contest were simple; no more than 256 characters could be used and all had to be on one line. The program allows for the entry of the starting live cells and will run until CtrlC is pressed. Because of the program size restriction the board is limited to 9 x 9 (to allow 10 or above would have made the program one character too long.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 616 other followers

%d bloggers like this: