sw1nn

Adventures. Stories. Code.

Game of Life Pt 2

| Comments

This post is a continuation of the previous post at the London clojure dojo.

When we left the story, we had generated a HTML table with id attributes related to the (x,y) co-ordinates and CSS classes to determine the colour.

We have some methods on the client side relevant to updating the table

1
2
3
4
5
6
7
8
9
10
11
12
13
14

(defn fill-random []
     (map  #(if (< 0.6 (rand 1)) :alive) (range (* WIDTH HEIGHT))

(defn set-cell-state [x y state]
  (if-let [e (by-id (str x "-" y))]
    (if state
      (.setAttribute e "class" (name state))
      (.removeAttribute e "class"))))

(defn update-view [grid]
     (doall (map-indexed (fn [index state]
                            (let [x (mod index WIDTH)
                                  y (Math/floor (/ index WIDTH))]
                               (set-cell-state x y state)) grid))))

The first method fill-random creates a sequence of values, one for each entry in the grid. The possible values are either :alive or nil

The update-view method, which is a callback when the grid data has changed, maps across the grid sequence and calls set-cell-state for each entry. Note that we use map-indexed instead of map to get both the index and the state and then infer the (x,y) co-ordinates from the index. The other point to note here is that, since map-indexed produces a lazy sequence we need to force the evaluation with doall or we never see the side effects (i.e. the calls to set-cell-state).

So now we have a data representation and a call back that updates the grid with new values. The final piece of the puzzle is the code that creates the next generation based on the current one. i.e. applies the rules of game of life. Let’s remind ourselves what the rules are:

  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.

We first we need a method to find adjacent cells then we can count the values in those adjacent cells and apply the rules above. There seem to be many ways to skin this cat. A simple implementation might be to calculate multiple offsets from the current index. The juxt function lets you do something like this, but it doesn’t quite work as expected…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

(defn adjacent-indices [i]
    (filter #(>= % 0)
       ((juxt #(- % (inc WIDTH))    ; north-west  
              #(- % WIDTH)          ; north
              #(- % (dec WIDTH))    ; north-east
              dec                   ; west
              inc                   ; east
              #(+ % (dec WIDTH))    ; south-west
              #(+ % WIDTH)          ; south
              #(+ % (inc WIDTH)))   ; south-east
         i)))

    ; works fine, as long as you are not in an edge square.

    ; with a 5x5 grid
    ;=> (adjacent-indices 12)
    (6 7 8 11 13 16 17 18)

    ; but at 0, we get an unwanted value 4
    ;=> (adjacent-indices 0)
    (1 6 5 4)

a different approach is needed.

Consider these two examples. In each case we’d like to find the indices adjacent to the number highlighted in red. i.e. the squares highlighted in blue.

Example 1: center square
-c1
-r1
c0
c1
c2
c3
c4
c5
r0
0001020304
r1
0506070809
r2
1011121314
r3
1516171819
r4
2021222324
r5
      
Example 2: corner square
-c1
-r1
c0
c1
c2
c3
c4
c5
r0
0001020304
r1
0506070809
r2
1011121314
r3
1516171819
r4
2021222324
r5
      

Note that in the second example, some of the adjacent squares are off the board - we shouldn’t return indices related to those squares. If we alter our representation from a single sequence to a sequence of sequences we can then operate on the elements in each row. By discarding rows (highlighted in green) and columns (highlighted in pink) we should be left with the required values. Discarding from the front of a sequence is easily achieved with the drop function and discarding from the end of a sequence via drop-last. There’s also a useful feature of those functions that if you pass a negative index nothing happens. This means we don’t need to worry about validating the count passed to drop or drop-last

1
2
3
4
5
6
7
8

;=> (drop 3 [ 0 1 2 3 4 5])
(3 4 5)
;=> (drop-last 3 [0 1 2 3 4 5])
(0 1 2)
;=> (drop -2 [0 1 2 3 4 5])
(0 1 2 3 4 5)
;=>> (drop-last -4 [0 1 2 3 4 5])
(0 1 2 3 4 5)

So by combining that all together we can drop rows before and after those we’re interested in and similarly with columns. This is what I came up with

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

(defn adjacent-indices [i]
  (let [indices  (partition WIDTH (range (* WIDTH HEIGHT)))
        x        (mod i WIDTH)
        y        (Math/floor (/ i WIDTH)) ; int function not implement in cljs yet :-(
        n        (dec y)                  ; #rows to drop from north
        e        (- WIDTH x 2)            ; #cols to drop from east
        s        (- HEIGHT y 2)           ; #rows to drop from south
        w        (dec x)]                 ; #cols to drop from west

    (remove #(= % i)                      ; remove supplied index
            (mapcat #(->> % (drop w) (drop-last e))
                    (->> indices (drop n) (drop-last s))))))

 ; with a 5x5 grid
 ;=> (adjacent-indices 12)
 (8 9 14 19 18 17 12 7)
 ;=> (adjacent-indices 0)
 (1 5 6)

Great! we solved the adjacency problem……or have we? Lets check the performance characteristics of the two approaches.

1
2
3
4
5
6
7

;=> (time (adjacent-indices-orig 12))
"Elapsed time: 0.047 msecs"
(6 7 8 11 13 16 17 18)

;=> (time (adjacent-indices-new 12))
"Elapsed time: 0.158 msecs"
(6 7 8 11 13 16 17 18)

Quite a difference and since we’re applying this function once for each cell, this difference can easily accumulate. But since the adjacent indices are static values for a particular grid we can easily memoize the adjacent-indices function to avoid recalculating known values…

1
2
3
4
5
6
7
8

(def adjacent-indices (memoize adjacent-indices-internal))

; warm up memoization
;=> (for [n (range (* WIDTH HEIGHT))] (adjacent-indices n))
([1 5 6] [0 2 5 6 7] [1 3 6 7 8] [2 4 7 8 9] [3 8 9] [0 1 6 10 11] [0 1 2 5 7 10 11 12] [1 2 3 6 8 11 12 13] [2 3 4 7 9 12 13 14] [3 4 8 13 14] [5 6 11 15 16] [5 6 7 10 12 15 16 17] [6 7 8 11 13 16 17 18] [7 8 9 12 14 17 18 19] [8 9 13 18 19] [10 11 16 20 21] [10 11 12 15 17 20 21 22] [11 12 13 16 18 21 22 23] [12 13 14 17 19 22 23 24] [13 14 18 23 24] [15 16 21] [15 16 17 20 22] [16 17 18 21 23] [17 18 19 22 24] [18 19 23])
;=> (time (adjacent-indices 12))
"Elapsed time: 0.044 msecs"
[6 7 8 11 13 16 17 18]

Having solved the adjacency problem, if should be fairly simple to calculate the states of each cell in the next generation by applying the rules.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

(defn- next-gen-state
  "Main logic routine. Applies the rules of Conway's game of life.

   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.
cl
  See http://en.wikipedia.org/wiki/Conway's_Game_of_Life for full details "
  [grid index alive?]
  (let [n (count (keep grid (adjacent-indices index)))]
    (cond
      (or (> n 3) (< n 2)) nil
      (= n 3) :alive
      (and (= n 2) alive?) :alive
      :else nil)))

(defn update-model []
  (let [grid @*grid*]
    (swap! grid #(vec (map-indexed (partial next-gen-state grid) %))))

The final piece is to add a watch to the *grid* atom so that the update-view callback is fired everytime the grid updates and also to update the model regularly using a timer

1
2
3
4
5
6
7
8
9
10
11
12
13
14

; called by the view to register the update-view callback on the model
(defn add-listener
  "Allows interested view to register interest in model changes. TODO: only supports a single listener, should maintain a list."
  [f]
  (add-watch *grid* nil
             (fn [k r o n]
               (f n))))

; creates a time using google closure support.
(defn start-timer []
  (let [timer (goog.Timer. 1000)]
    (update-model)
    (. timer (start))
    (events/listen timer goog.Timer/TICK update-model)))

See the final version in action here

All code on github details in the README

Comments