One-Dimensional Cellular Automata

First, a teaser with an aweful gif!

After watching the first couple minutes of The Coding Train's awesome video on Cellular Automata, I decided to try and write my own. I've written many versions of Conway's Game of Life before, but have never written a 1D CA. This is my first attempt at making one. I'm going to make a color version after this, but I want to make sure the simple version is optimal before moving on.

I'm fairly happy with how this turned out, although there's a couple aspects that I'm sure could be improved:

1. When generating new generations, I'm relying on indexing the generation constantly. The code that creates a new generation is

(mapv #(next-state-of generation % rule-set) (range (count generation))))

The fact that I'm relying on (range (count generation)) worries me, as that's often a smell.

2. I wasn't sure how to handle out-of-bounds cells. I opted for just treating any cell that's out-of-bounds as a 0, but I'm not sure if this is "correct", or if there's a cleaner way. I'm also disappointed with my current way of handling OOB cells in general. OOB cells are substituted with a namespaces keyword, then replaced with a 0.

3. In my main, I'm not thrilled with how the x's and y's are calculated for each block and generation. For the x's, each generation is given to xs-for-boxes, which returns a range of x values. Those values are then zipped with the generation (via (map vector...)), and fed into a doseq. It's the same for the y's. This seems clumsy to me. Is there a cleaner way?

4. It's also pretty slow when I crank up the generation size. Generations of 100 blocks across are pretty smooth, but anything over ~200 begins to lag pretty hard (at least on my M3 Surface Pro 4). Any performance suggestions would be appreciated.

5. Anything else at all! I'm open to any criticism!

Requires the Quil graphics library. Essentially a Clojure wrapper over Processing.

(ns cellular-automata.one-dim.generation)

(def neighborhood-range 1)

; TODO: Is all the indexing necessary?

; TODO: Necessary? Immedietely replace with the filler?
(def out-of-bounds-cell ::oob)
(def out-of-bounds-filler 0)

(defn new-generation
"Returns an empty generation of cells."
[starting-val num-of-cells]
(vec (repeat num-of-cells starting-val)))

(defn- inbounds? [generation-size cell-i]
(< -1 cell-i generation-size))

(defn- neighborhood-indices-of
"Returns the indices cof the ells immedietely surrounding the cell at index cell-i.
Any out of bounds indices are replaced by out-of-bounds-cell."
[generation-size cell-i]
(map #(if (inbounds? generation-size %) % out-of-bounds-cell)
(range (- cell-i neighborhood-range)
(inc (+ neighborhood-range cell-i)))))

(defn- neighborhood-of
"Returns the cells immedietely surrounding the cell at index cell-i.
Any out of bounds cells will be replaced by out-of-bounds-filler."
[generation cell-i]
(let [gen-size (count generation)
neigh-indices (neighborhood-indices-of gen-size cell-i)]

(map #(if (= out-of-bounds-cell %)
out-of-bounds-filler
(generation %))
neigh-indices)))

(defn- next-state-of
"Replaces the cell at cell-i with it's new state based on the given rule-set."
[generation cell-i rule-set]
(let [neighborhood (neighborhood-of generation cell-i)]
; TODO: Do checking to ensure that the neighborhood
;  is actually in the ruleset?
(rule-set (vec neighborhood))))

(defn next-generation
"Returns the next generation according to the rule-set.
rule-set can either be a map mapping a neighborhood to a value, or a plain
function that accepts a neighborhood and returns the new cell."
[generation rule-set]
(mapv #(next-state-of generation % rule-set)
(range (count generation))))


(ns cellular-automata.one-dim.rule-sets)

(defn odd-set [neighb]
(if (even? (apply - neighb))
0
1))


(ns cellular-automata.one-dim.main
(:require [quil.core :as q]
[quil.middleware :as m]

[cellular-automata.one-dim.generation :as gen]
[cellular-automata.one-dim.rule-sets :as rs]))

; TODO: Allow cells states from 0 to 255^3, and color accordingly?

(defrecord State [generations])

(def screen-width 1000)
(def screen-height 1000)

(def fps 100)

(def generation-size 100)
(def box-width (/ screen-width generation-size))
(def max-generations (int (inc (/ screen-height box-width))))

(def rule-set rs/odd-set)
(def initial-generation (assoc (gen/new-generation 0 generation-size)
(int (/ generation-size 2)) 1))

(update state :generations
#(conj %
(gen/next-generation (last %) rule-set))))

(defn fix-overflow
"Removes the oldest generations in the event of an overflow."
[state]
(update state :generations
#(if (> (count %) max-generations)
(subvec % 1)
%)))

(defn xs-for-boxes
"Returns the x-values each box in the generation should be drawn at."
[generation]
(range 0 screen-width box-width))

(defn ys-for-generations
"Returns the y-values each generation should be drawn at."
[generations]
(let [neg-width (- box-width)]
(range (- screen-height box-width) neg-width neg-width)))

(defn draw-block [x y cell-state]
(let [c (if (zero? cell-state) [0 0 0] [255 255 255])]
(q/with-fill c
(q/rect x y box-width box-width))))

(defn draw-generation [generation y]
(let [x-boxes (map vector generation (xs-for-boxes generation))]
(doseq [[box-state x] x-boxes]
(draw-block x y box-state))))

(defn setup-state []
(q/frame-rate fps)

(let [starting-gens [initial-generation]]
(->State starting-gens)))

(defn update-state [state]
(-> state
(fix-overflow)))

(defn draw-state [state]
(let [{gens :generations} state
y-gens (map vector (ys-for-generations gens) gens)]

(doseq [[y gen] y-gens]
(draw-generation gen y))))

(defn -main []
(q/defsketch One-D-CA
:size [screen-width screen-height]

:setup setup-state
:update update-state
:draw draw-state

:middleware [m/fun-mode]))


You invent special values for the out-of-bounds index (out-of-bounds-cell) and its value (out-of-bounds-filler): nil would be idiomatic for both. Using the local keyword ::oob for the out-of-bounds index does no harm, but using 0 for the out-of-bounds value restricts the way that the rule can treat it.

Your next-generation function implies that the next generation is the same size as this one, hence all generations are the same size, whatever the rule-set. So you can pre-compute the index sets for neighbours, as a vector or (slower) a map. Doing so would speed up your program considerably. You could at the same time accommodate a variable neighbourhood-range.

From now on we assume that we can ignore out-of-bounds values.

We could represent the neighbourhoods as ranges, which are optimised for integer arguments. We can capture this in a function like ...

(defn trimmed-ranges [neighbourhood-range size]
(let [tr (fn [i] (range (max 0 (- i neighbourhood-range)) (min size (+ i neighbourhood-range 1))))]
(mapv tr (range size))))


For example,

(trimmed-ranges 2 10)
=> [(0 1 2) (0 1 2 3) (0 1 2 3 4) (1 2 3 4 5) (2 3 4 5 6)
(3 4 5 6 7) (4 5 6 7 8) (5 6 7 8 9) (6 7 8 9) (7 8 9)]


This enables us to write next-generation as

(defn next-generation [neighbours generation rule]
(mapv
(fn [i] (->> i neighbours (map generation) rule))
(range (count generation))))


... where the neighbours function is an explicit argument.

We can tie this up neatly by returning a lazy sequence of the generations.

(defn generations [neighbours first-generation rule]
(iterate #(next-generation neighbours % rule) first-generation))


... where

• neighbours is a function returning the indexes of the neighbours of its index argument.
• first-generation is the initial generation vector.
• rule is a function that turns the values of the neighbours of an element into its new value.

(def generation-size 10)

(def neighbours-v (trimmed-ranges 1 generation-size))

(defn odd-set [neighb]
(mod (apply - neighb) 2))

(def initial-generation (assoc (new-generation 0 generation-size)
(quot generation-size 2) 1))


Then

(take 5 (generations neighbours-v initial-generation odd-set))
=>  ([0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 1 1 1 0 0 0]
[0 0 0 1 0 1 0 1 0 0]
[0 0 1 1 0 1 0 1 1 0]
[0 1 0 0 0 1 0 0 0 1])

• Only as much of this sequence is generated as is called for.
• Elements that are no longer referred to are forgotten.
• You could, for instance, use partition to window the sequence.
• Awesome, thanks for the suggestions. I actually ended up doing away with the whole OOB problem by just wrapping the cells, but it's still good to see another perspective. – Carcigenicate Sep 15 '17 at 18:29
• Another approach would be to pad the generation vector with empty (nil ?) cells at either end. The neighbours are then a straight subvec. The rule has to be adapted to deal with empty cells, but I think that's how it should be - position sensitive rules are then possible. I think this would be faster. – Thumbnail Sep 15 '17 at 20:51