The Game of Life

When Conway introduced "the Game of Life" in the mathematical column of Scientific American it immediately had an enormous success. The game itself is simple: there is an infinite grid of cells and cells live or die according to a bunch of simple rules.

The game roots are far less than trivial, as in those times Conway was interested in a problem which is still actual today (introduced by von Neuman, according to Wikipedia). The idea was building a machine able to copy itself (in which von Neuman succeeded, but Life is just simpler). Later, the game was proved to have the same computational power of a Turing machine. Anyway, the rules are:

• if a living cell has just two living neighbours, it dies.
• if a living cell has two or three living neighbours, it remains alive
• if a living cell has four or more living neighbours, it dies.
• if a dead cell has exactly three living neighbours, it becomes alive

Every self-respecting computer geek has tried to implement the game at least once. Indeed, the variant usually implemented is placed on a thorus (that is to say, finite width, finite height, wraparound). This greatly simplifies the implementation (which becomes trivial) and holds much of the nice properties "game-wise".

I have no idea how many times I implemented the thing in different languages. Indeed, it is a very nice problem to implement idiomatically. I have to admit that I still have the idea of proposing this as an exercise for the programming lab of a course here at the University. Still, I'm not sure students would find it as amusing as I do and perhaps it would be just a hard exercise for them (depending on how much exercise they did on holiday). So I decided not to give it. Moreover, they would have to do it in C++, which is far less amusing than doing it in Lisp (the last language in which I did it).

I somewhat feel lot of freedom in Lisp. I don't feel I'm forced to a careful and formal object oriented design: things usually feel better if they are simpler. And usually code remains decently organized nonetheless. For example, in an OOL the "board topology" would probably be a class. From another point of view, there is nothing suggesting that a very simple GOL implementation needs such generality. Probably, it we would like to have different boards (especially considering questions about very large boards and efficiently storing and manipulating data) different visiting strategies (cell for cell) should be used. In fact just iterating over the alive cells, does not account for the 4th rule. Detecting a cluster of three alive cells (starting from an alive cell) around the dead one may not be efficient. In fact, I have not thought about the algorithms that should be used in those cases, not I wanted to. I did not want to develop an industrial strong GOL implementation: I just wanted to toy with Lisp. Over-engineering is just around the corner. Beware!

By the way, here the toy implementation.

	(proclaim '(optimize (speed 3) (space 0) (debug 0)))
	(defparameter *width* 80)
	(defparameter *height* 23)
	(defparameter *length* (* *width* *height*))
	(defun neighbours (pos)
	(mapcar (lambda (x) (mod x *length*))
	(delete pos
	(mapcan (lambda (pos)
	(list (1- pos)
	pos
	(1+ pos)))
	(list pos
	(+ pos *width*)
	(- pos *width*))))))
	(defun alive-neighbours (board pos)
	(reduce #'+
	(mapcar (lambda (pos) (sbit board pos))
	(neighbours pos))))
	(defun evolve (board)
	(let ((new-board (make-array (array-dimensions board)
	:element-type 'bit)))
	(loop for pos from 0 below (array-total-size board)
	do (let ((alive-neighbours (alive-neighbours board pos))
	(alive-cell (= (sbit board pos) 1)))
	(cond
	((and alive-cell (< alive-neighbours 2))
	(setf (sbit new-board pos) 0))
	((and alive-cell (< alive-neighbours 4))
	(setf (sbit new-board pos) 1))
	((and alive-cell (>= alive-neighbours 4))
	(setf (sbit new-board pos) 0))
	((and (not alive-cell)
	(= alive-neighbours 3))
	(setf (sbit new-board pos) 1))
	(t (setf (sbit new-board pos)
	(sbit board pos))))))
	new-board))
	(defun print-board (board &optional (stream *standard-output*))
	(loop for j from 0 below *height*
	do (loop for i from 0 below *width*
	do (write-char
	(if (= (sbit board (+ i (* j *width*))) 1) #\* #\space)
	stream)
	finally (write-char #\newline stream))))
	(defun make-board (lst)
	(let ((board (make-array (list *length*)
	:element-type 'bit
	:initial-element 0)))
	(loop for pair in lst
	do (setf (sbit board (+ (car pair)
	(* (cdr pair) *width*))) 1))
	board))
	(defun make-random-pairs (p)
	(loop for j from 0 below *height*
	append (loop for i from 0 below *width*
	when (= (random p) 0)
	collect (cons i j))))
	(defun evolution (board)
	(print-board board)
	(unless (char= (read-char) #\q)
	(evolution (evolve board))))
	(defun game ()
	(evolution (make-board (make-random-pairs 12))))

view raw life.lisp hosted with ❤ by GitHub