A Random Walk Through Idea Space: Asynchronous Game Of Life

I had the idea to do an asynchronous Game Of Life in the browser using clojurescript’s core.async. I thought it would be fun if there was no global state, no external time and no datastructures - have the cells be channels just signalling to their neighbours when they transitioned between dead and alive.

Go take a look at it here

I will assume you have seen my other post with resources to learn CSP and core.async

I think the implementation is true to the idea of Asynchronous cellular automata but fear it has bugs as the steady state often settles on something that is not a valid GoL position (in particular I often see clumps of alive cells with too many neighbours, all surviving)

The code is on github, you can play with it in cljsfiddle and see a full page version of it.

As it is only 100 lines I may as well walk through them here.

Fairly uninteresting initialisation, prob is the probability a cell is alive/dead at the beginning. I made width height and cell-size atoms because I reset them all on calling init later.

(def line-colour "#cdcdcd")
(def alive "#666")
(def dead "#eee")
(def width (atom nil))
(def height (atom nil))
(def cell-size (atom nil))
(def canvas (.getElementById js/document "world"))
(def context (.getContext canvas "2d"))
(def prob 0.5)

Standard canvas drawing stuff

(defn fill_sq [x y colour]
  (let [cell-size @cell-size]
    (set! (.-fillStyle context) colour)
    (set! (.-strokeStyle context) line-colour)
    (.fillRect context
               (* x cell-size)
               (* y cell-size)
               cell-size
               cell-size)
    (.strokeRect context
                 (* x cell-size)
                 (* y cell-size)
                 cell-size
                 cell-size)))

I thought it neat to have the draw function as a channel too, the timeout here sets the velocity of the simulation via backpressure on the unbuffered channels

(def draw
  (let [c (chan)]
    (go (loop []
          (let [[x y colour] (<! c)]
            (<! (timeout 10))
            (fill_sq x y colour)
            (recur))))
    c))

The hardest bit to explain (and probably where the remaining bugs are…)

cell takes an [x y] position and returns 2 channels, one for input that neighbours can use to inform it about their alive/dead transitions and one to be told of new neighbours, via passing in their input channel, so it’s a channel of channels :-)

Each cell creates a single go block that listens for new neighbours and state transitions from neighbours on it’s input channels. Whenever something comes from a neighbour (either 1 or -1 to signal it becoming alive or dead) it updates it’s neighbour count, works out if it’s state transitions and tells it’s neighbours if it did and also sends draw a signal too. It is all kicked off by the alive cells telling their new neighbours they are alive as they connect.

There is an asymmetry in the alive/dead transitions, 3 neighbours

(defn cell [[x y]]
  (let [new-neighbour (chan)
        input (chan)
        neighbours #{}
        initial-state (if (< (rand) prob) :alive :dead)]
    (if (= initial-state :alive)
      (fill_sq x y alive))
    (go (loop [neighbour-count 0
               state initial-state
               neighbours neighbours]
          (let [[val chan] (alts! [new-neighbour input])]
            (cond (= chan new-neighbour)
                  (do (if (= state :alive)
                        (>! val 1))
                      (recur neighbour-count state (conj neighbours val)))
                  :else
                  (let [neighbour-count (+ val neighbour-count)
                        new-state (if (or (= neighbour-count 3)
                                          (and (= neighbour-count 2) (= state :alive)))
                                    :alive
                                    :dead)
                        draw? (not= new-state state)
                        delta (if (= new-state :alive) 1 (- 1))
                        colour (if (= new-state :alive) alive dead)]
                    (if draw?
                      (do (doseq [n neighbours]
                            (>! n delta))
                          (>! draw [x y colour])))
                    (recur neighbour-count new-state neighbours))))))
    [input new-neighbour]))

Getting neighbours for a position

(defn neighbours [[x y] grid]
  (filter (comp not nil?)
          (for [dx [-1 0 1]
                dy (if (zero? dx)
                     [-1 1]
                     [-1 0 1])]
            (let [x' (+ dx x)
                  y' (+ dy y)]
              (get grid [x' y'])))))

This is the loop that kicks everything off (OK I cheat and have a collection here). We loop through the [x y] positions and create a cell (ie an [input new-neighbour] pair) for each and store the result in the cells map. Then we look up the neighbours for each cell and then pass into their new-neighbour channel it’s input channel. This starts our cascade.

(defn draw-loop []
  (let [xys (for [x (range @width)
                  y (range @height)]
              [x y])
        cells (zipmap xys (map cell xys))]
    (doseq [[xy [input _]] cells]
      (go
       (doseq [[_ nn] (neighbours xy cells)]
         (>! nn input))))))

The init function just sets the atoms, grows the canvas to fill the space it is given, draws the empty grid then kicks off draw-loop

(defn ^:export init []
  (set! (.-width canvas) (.-clientWidth canvas))
  (set! (.-height canvas) (.-clientHeight canvas))
  (reset! width 75)
  (reset! cell-size (/ (.-clientWidth canvas) @width))
  (reset! height (/ (.-clientHeight canvas) @cell-size))
  (doseq [y (range @height)
          x (range @width)]
    (fill_sq x y dead))
  (draw-loop))

Hope you enjoyed it, let me know if I can clear up anything (and if you spot a bug).

Menu