# Learning Haskell with Venu: Cellular automata

·
*
Reading time:
4 mins
*

Lately I've been experimenting a lot with a number of CG and procedural content
generation algorithms, and began feeling the need for mathematical rigour over
the practical, "real life situation" style I've been used to by writing
Javascript day in, day out. I got to a point where simple simulations required
way more boilerplate code than I was willing to write, and the usage of native
numeric constructs began getting in the way of performance. For example, I was
working on an image processing algorithm, representing the pixels as
plain 1D arrays, and I discovered that wrapping the aforementioned array
inside a native `Uint32Array`

produced an impressive performance boost, cutting
the execution time from ~46ms to ~1.5ms at the expense of adding a little
boilerplate code. Which is great in and of itself, but not so great in terms of
code cleanliness, and code cleanliness is fundamental when I'm trying to
represent somewhat complex mathematical ideas.

So I decided to look into functional programming. After reading about it for a bit, I began working my way through the Ninety-nine Haskell Problems to get comfortable with the new paradigm, and then decided to prototype something a bit more challenging.

### Cellular automata

I chose to implement a simple cellular automaton. A *cellular automaton* is a
discrete computation model defined over a grid of cells, each one having a
state. Each step of the computation, called *generation*, involves computing
a new state for each cell that depends upon the previous states of the cell
and of a chosen subset of neighboring cells. The criteria with which the new
state is computed are called *rules* and are, basically, a function of those
previous states.

Let's choose a neighborhood in the form of the Moore neighborhood. Let denote the 2D matrix representing the automaton. The Moore neighborhood for a generic cell is defined as

Let be the matrix at the th generation. We could say that

Finally, we could decide our rule function to be a simplified version of the one described in this nice article about cellular automata which I suggest you read, too.

I decided to represent the automaton's grid as a plain 1D array. The `generation`

function is defined inductively with great ease; being `vec`

the array containing
the grid, the generation 0 is the array itself, and each subsequent generation
is defined as the `step`

function mapped over the values of the previous
generation. `step`

corresponds to the defined before, and the sum over the
neighborhood is represented as the fold of the sum operation over the cell values
extracted by the `getCell`

function.

generation :: Int -> [Int] -> [Int] generation 0 vec = vec generation i vec = map step [0 .. length vec] where vec' = generation (i-1) vec step :: Int -> Int step i = if (neighSum > 4) then 1 else 0 where x = i `mod` 32 y = i `div` 32 neighSum = foldr (+) 0 [getCell (x + x') (y + y') vec' | x' <- [-1..1], y' <- [-1..1], not (x' == 0 && y' == 0) ]

Coupled with Haskell's `System.Random`

, we get a nice looking dungeon after a few generations:

You can read the whole code here: https://gist.github.com/veeenu/8dbba3e53f94d7142c63.

Surely this could have been done a lot better, and it will be, as I keep studying the language and getting better at it. Meanwhile, please feel free to criticize and comment whatever you feel like to! :)

**ERRATA CORRIGE**. My friend Roberto pointed out that the 2-tuple wasn't supposed
to be part of the Moore neighborhood, and, besides that, its status was already taken into
account for (but not used in this particular case) in the form of in the rule
function anyway. This has now been corrected both in the code and in the mathematical
expression.