The Game of Life

Índice

Come back to davidam.com

1 Introduction

This is a simple game loved by the hacker culture. The game made its first public appearance in the October 1970 issue of Scientific American, by Comway's attempting to drastically simplify von Neumann's ideas about find a hypothetical machine that could build copies of itself.

Life provides an example of emergence and self-organization. It is interesting for computer scientists, physicists, biologists, biochemists, economists, mathematicians, philosophers, generative scientists and others to observe the way that complex patterns can emerge from the implementation of very simple rules.

A visual example about the implementation of life is the programs to generate fractals, but you can find life in your GNU/Emacs too, typing M-x life.

In this article we explain a simple implementation in emacs lisp.

2 Data Structure

The data structure is a table (array 2x2), I've implemented this idea with lists. For instance:

(setq table-example '((1 1 0 1) 
                      (0 1 0 1) 
                      (0 0 0 0) 
                      (0 1 0 0)))

I've implemented a small function to print it:

(defun print-matrix (matrix)
  (interactive)
  (setq size (length matrix))
  (insert "\n")
  (dotimes (i size)
    (if (/= i 0) (insert "\n"))
    (dotimes (j size)
      (insert (format "%d " (elt (elt matrix i) j)))))
  (insert "\n"))

3 Neighborhoods

A core function to implement the game of life is neighborhoods, this function receives the position and the matrix and returns how many neighborhoods there are.

(defun neighborhoods (i j matrix)
"Receives the position and the matrix and returns how many neighborhoods there are"
  (interactive)
  (let ((size (length matrix)))
    (cond 
     ;; corners
     ((and (= i 0) (= j 0)) (+ 0 (elt (elt matrix 0) 1) (elt (elt matrix 1) 0) (elt (elt matrix 1) 1)))
     ((and (= i 0) (= j (- size 1))) (+ 0 (elt (elt matrix 0) (- size 2)) (elt (elt matrix 1) (- size 2)) (elt (elt matrix 1) (- size 1))))
     ((and (= i (- size 1)) (= j 0)) (+ 0 (elt (elt matrix (- size 2)) 0) (elt (elt matrix (- size 2)) 1) (elt (elt matrix (- size 1)) 1)))
     ((and (= i (- size 1)) (= j (- size 1))) (+ 0 (elt (elt matrix (- i 1)) (- j 1)) (elt (elt matrix (- i 1)) j) (elt (elt matrix i) (- j 1))))
     ;; awns
     ((and (= i 0) (> j 0) (not (= j (- size 1)))) (+ (elt (elt matrix 0) (+ j 1)) (elt (elt matrix 0) (- j 1)) (elt (elt matrix 1) (+ j 1)) (elt (elt matrix 1) j) (elt (elt matrix 1) (- j 1)))) ;; superior probada
     ((and (not (= i (- size 1))) (> i 0) (= j 0)) (+ (elt (elt matrix (+ i 1)) 0) (elt (elt matrix (- i 1)) 0) (elt (elt matrix (+ i 1)) 1) (elt (elt matrix i) 1) (elt (elt matrix (- i 1)) 1))) ;; izquierda probada
     ((and (= i (- size 1)) (> j 0) (not (= j (- size 1)))) (+ (elt (elt matrix (- i 1)) (- j 1)) (elt (elt matrix (- i 1)) j) (elt (elt matrix (- i 1)) (+ j 1)) (elt (elt matrix i) (- j 1)) (elt (elt matrix i) (+ j 1)))) ;; inferior (probada)
     ((and (not (= i (- size 1))) (> i 0) (= j (- size 1))) (+ (elt (elt matrix (- i 1)) (- j 1)) (elt (elt matrix (- i 1)) j) (elt (elt matrix i) (- j 1)) (elt (elt matrix (+ i 1)) j))) ;; derecha (probada)
     ;; rest
     ((and (not (= i 0)) (not (= j 0)) (not (= i (- size 1))) (not (= j (- size 1)))) (+ 0 (elt (elt matrix (- i 1)) (- j 1)) (elt (elt matrix (- i 1)) j) (elt (elt matrix (- i 1)) (+ j 1)) (elt (elt matrix i) (- j 1)) (elt (elt matrix i) (+ j 1)) (elt (elt matrix (+ i 1)) (- j 1)) (elt (elt matrix (+ i 1)) j) (elt (elt matrix (+ i 1)) (+ j 1))))
     )))

4 Life

In life game we've a matrix with cells in two states (live or dead) and there are the next rules for change from the state live to dead.

  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overcrowding.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

An implementation of this rules in emacs lisp are:

(defun comway-rules (i j table)
  (interactive)
  (cond ((and (= 1 (elt (elt table i) j)) (< 2 (neighborhoods i j table)) 0))
                            ((and (= 1 (elt (elt table i) j)) (or (= 2 (neighborhoods i j table)) (= 3 (neighborhoods i j table)))) 1)
                            ((and (= 1 (elt (elt table i) j)) (< 3 (neighborhoods i j table))) 0)
                            ((and (= 0 (elt (elt table i) j)) (= 3 (neighborhoods i j table))) 1)
                            (t (elt (elt table i) j))
                            ))

Now, a function to apply this rules in a table:

(defun apply-comway-rules-list (table)
  (interactive)
  (setq table-res nil)
  (dotimes (i (length table))
     (setq list-res nil)
     (dotimes (j (length (elt table i)))
       (setq list-res (cons (comway-rules i j table) list-res)))
     (setq table-res (cons list-res table-res)))
  table-res
)

Now finally, we can write the full game of life:

(defun comway-life(table gen)
  (interactive "NNumber of generations: \n" gen)
  (setq table-ej '((1 1 0 1) (0 1 0 1) (0 0 0 0) (0 1 0 0)))
  (if (eq table-ej nil)
      (setq table table-ej))
  (dotimes (i gen)
    (insert (format "\nGeneration %d\n-------------" i))
    (print-matrix table)
    (setq table (apply-comway-rules-list table))))

To execute it:

(comway-life table-example 14)

5 License

Copyright (C) 2014 David Arroyo Menéndez Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in GNU Free Documentation License.

gfdl.png

Autor: David Arroyo Menéndez

Created: 2014-08-24 dom 21:08

Emacs 24.3.1 (Org mode 8.3beta)

Validate