[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Conway's Game of Life (cellular automata)



I wrote Conway's Game of Life in what I thought was good TLS style,
but I wondered if HTDP would recommend something different.  There's
some talk of object-oriented design in HTDP which I didn't
follow. This seems like a good thing for HTDP; it's fun & easy.

In more detail, Ian Stewart's book "The Collapse of Chaos" describes
Conway's Game of Life and claims that a "glider gun" is periodic with
period 30, with the additional feature that the "glider gun" shoots
out a stream of pulses diagonally (down & to the right).  I was
intrigued by this & code it up below, and indeed it's 30-periodic!
The basic cellular automata rule is very simple:

   If a cell is white, and exactly 3 of it's neighbors are black, then
   the cell becomes black.  Otherwise the cell remains white.

   If a cell is black, and either 2 or 3 of it's neighbors are black,
   then the cell remains black; otherwise the cell becomes white.

This is easy in C, represent a game by a matrix of 1s & 0s, copy the
matrix and mutate the copy.  Writing it as a functional program was a
challenge for me, but I don't believe it was hard.  But I wondered if
HTDP doesn't recommend an OOP approach: think of each cell as an
object, and pass messages between the nearest neighbors...

-Bill

(define glider-gun 
  (map string->list 
       (list
        "                                                                  "
        "                                      x                           "
        "                                   xxxx                           "
        "                          x       xxxx         xx                 "
        "                         x x      x  x         xx                 "
        "             xx         x   xx    xxxx     x                      "
        "             xx         x   xx     xxxx    x                      "
        "                        x   xx        x                           "
        "                         x x                                      "
        "                          x                                       "
        "                                                                  "
        "                                                                  "
        "                                                                  "
        "                                                                  "
        "                                                                  "
        "                                                                  "
        "                                                                  "
        "                                                                  "
        "                                                                  "
        "                                                                  "
        "                                                                  ")))

(define (iterate-life game)
  ;; takes a Conway game of life and produces the next iteration,
  ;; by the following rule:
  ;; If a cell is white (#\space), and exactly 3 of it's neighbors are black (#\x),
  ;; then the cell becomes black.  
  ;; If a cell is black, and either 2 or 3 of it's neighbors are black, then
  ;; the cell remains black; otherwise the cell becomes white.
  ;;
  ;; A game is normally represented as a matrix of 0s and 1s.   
  ;; We use  a  list (rows) of lists (columns) of characters, so each "matrix entry" 
  ;; is either #\space or #\x. 
  ;;
  ;; We first pad the game with #\space on all sides, then call 
  ;; iterate-life-real, which does the real work.
  (let ((padded-game (make-padded-game game)))
    (iterate-life-real padded-game)))


(define (make-padded-game game)
  (letrec ((make-blank-list 
    ;; returns a list full of spaces of same length as list 
            (lambda (list) 
              (if (null? list) 
                  `()
                  (cons #\space 
                        (make-blank-list (cdr list)))))))
    (let* ((make-padded-row (lambda (row) 
                              (cons #\space 
                                    (append row 
                                            (list #\space)))))
           (game-padded-by-rows 
            ;; the game with each row padded by a SPC on both ends
            (map make-padded-row game))
           (padded-blank-row (make-blank-list (car game-padded-by-rows))))
      (cons padded-blank-row 
            (append game-padded-by-rows 
                    (list padded-blank-row))))))


(define (iterate-life-real padded-game)
  ;; Returns the next iteration of Conway game of life on the middle,
  ;; so returns a game missing the padded frame of SPCs.
  (if (null? (cddr padded-game))
      `()
      (cons (fix-middle-row (car padded-game)
                            (cadr padded-game)
                            (caddr padded-game))
            (iterate-life-real (cdr padded-game)))))


(define (fix-middle-row top row bot)
  ;; take 3 lists (rows) of the same length and play Life on the middle row, 
  ;; minus the 1st & last elements, which initially are padded SPCs.
  (if (null? (cddr row))
      '()
      (cons (Conway (car top) (cadr top) (caddr top)
                    (car row) (cadr row) (caddr row)
                    (car bot) (cadr bot) (caddr bot))
            (fix-middle-row (cdr top) 
                            (cdr row) 
                            (cdr bot)))))


(define (Conway nw n ne
                w here e
                sw s se)
  ;; performs the Conway iteration on the cell whose value is `here'.
  ;; If here is white (#\space), and exactly 3 of it's neighbors are black (#\x),
  ;; we return black.  
  ;; If here is black, and if the number of black neighbors is not 2 or 3, 
  ;; we return white (#\space).
  ;; Otherwise, the cell is unchanged, so we return here.
      (let* ((black->1 (lambda (cell)
                         (if (char=? cell #\x)
                             1
                             0)))
             (numblack (apply + (map black->1 (list nw n ne
                                                    w    e
                                                    sw s se)))))        
        (cond ((and (char=? here #\space) 
                    (= numblack 3)) 
               #\x)
              ((and (char=? here #\x)
                    (not (or (= numblack 2)
                             (= numblack 3)))) 
               #\space)
              (else here))))


(define 60-iterations-of-glider-gun 
  (do ((i 0 (+ i 1))
       (picturelist '() (cons (map list->string picture) 
                              (cons i picturelist)))
       (picture glider-gun (iterate-life picture)))
    ((> i 60) (reverse picturelist))))

60-iterations-of-glider-gun 


;; Code below has the feature that after selecting the output with
;; Meta-a and pasting it into a file and deleting the top lines, you
;; can `lpr' the file printing 3 iterations per page.    

;; Still need to implement error checking:  if we ever get 3
;; consecutive black cells on the bounding frame (an outer row or
;; column), then the grid is too small, and must be enlarged.