“Cellular Automata” (CA) sounds like a nasty technical term. In reality CA is one of the easiest mathematical models to grasp and implement in computers, and specifically in games. Some CAs also exhibit very interesting behavior over time and can create interesting patterns, so it is definitely worthwhile learning a bit about them.

[TIP: This tutorial was written for the beginner. If you know what CAs are and you are looking for their specific application to games, have a look at the other documents on this site under the heading “Cellular Automata”.]

There are many reasons why game designers and developers should know about cellular automata. First, because they can be used in terrain generation, a topic I will discuss in depth. Second, they can be used to create objects that look “alive” i.e. they reproduce, cluster around each other and move about in interesting ways. Third, CAs, when assigned to control particles, provide really interesting dynamic graphics (simulated clouds anyone?) There are many other places to use cellular automata within games, and I will try to provide all kinds of info on them in the future.

OK, so you got interested in our topic. But what are CA’s really? You might have noticed that Cellular Automata is the plural for Cellular Automaton. An automaton is defined as a mathematical operator that has a memory to remember its current state, and a number of inputs, which it then uses to update its state. The Turing Machine (along with its infinitely long band of paper is one example of an automaton. Humans are automatons in a way. For example John might be in an angry, sad or content state. Let’s say he is sad right now. He might then receive a call that he has won the lottery. His state changes to happy. That is really automaton behavior.

Figure 1

Figure 1 shows an automaton that is in state A at the time t=n, and then changes its state to B at time t=n+1, due to the inputs it received (i and j) and its previous state (A). Now there are a bunch of simplifications here. First of all, the number of inputs can be anything from one input to any countable number of inputs (like 54433 of them). Secondly, the same inputs will also be acting on the automaton at t=n+1…so they might change its state to another state at that time. Thirdly, in some cases, the state might not change at all, because the new state calculated from i and j and A at time n+1 might be A again. In addition, we only showed the automata in states A and B…it might be able to change into any number of states (generally any whole number below infinity are allowed), so there might be a state C and D or X that the automaton can change into.