[This feature takes a look at cellular automation, an algorithmic simulation useful in games, and discusses its use in titles like Minecraft and Dwarf Fortress, as well as other examples, and explains how it can be useful in the context of a game in development.]

What is cellular automation?

My name is John Harris, and I am working on a game called In Profundis (Kickstarter project), that simulates a large cavern world using what is called cellular automation. It allows water to flow, gases to spread, boulders to fall, and other systems propagate and change over time. To perform these feats, it runs a complex system that, each frame, decides on the contents of each cell of a grid-based game world.

Cellular automation is a generally overlooked tool in the game designer's toolbox, but a number of very interesting games have made use of it in one way or another. A partial list: Boulder Dash, SimCity, ADOM, Falling Sand, Dwarf Fortress and Minecraft.

Note those last two, currently darlings of the indie community; both games are popular, at least in part, due to their complex world simulations.

In Profundis uses it in a matter somewhat similar to Dwarf Fortress, although not as complex and in 2D space, as opposed to 3D. (N.B.: I interviewed Tarn Adams, programmer of Dwarf Fortress, for Gamasutra about some of the game's implementation details, including its fluid dynamics.)

By the widest possible definition, cellular automation is a simulation technique that involves performing some operation on the contents of the cells of a regular grid, repeatedly, the results for each cell replacing the previous contents on each pass.

It is a generally overlooked tool for game development for various reasons (we'll get to its drawbacks shortly), but it's been around for some time. The beginning of cellular automation is generally considered to be mathematician John Horton Conway's Game of Life. Life considers the fates of a number of counters on a board who live and die according to a small number of rules.

The player runs the board, seeded with a starting configuration, through a sequence of turns. On each turn, empty spaces with exactly three neighbors experience a birth, and receive a new counter by the next turn. Counters with fewer than two or more than three neighboring counters experience death, and are removed by the next turn. Neighboring spaces are those adjacent either orthogonally or diagonally, thus each space has eight neighbors. And that is all there is to Life.

Okay, that is far from all there is to Life. Those are the rules, but cellular automation is an excellent vehicle for illustrating the principle of emergent complexity. Simple patterns with small numbers of counters can explode, over many calculations, and create huge tableaus filling thousands of cells.

Life's rules are simple, but their consequences have, to this day, yet to be fully explored. (For more information on Life, a good place to start is the Wikipedia page. Also of note are the installments of Martin Gardner's Mathematical Games column in Scientific American, that first publicized the game to the general public. To play around with it yourself, I heartily suggest looking into the open source CA simulator Golly, available for most current platforms.)

While Life can be played without a computer, all the recent discoveries in Life behavior have depended on computer Life simulators. Some of the earliest entertainment software programs written were Life sims.

Not all cellular automation is as deep as Conway's Life. In fact you'd be hard-pressed to come up with a better behavioral-richness to calculation-time ratio. But we don't need elegance of Life's caliber, or anywhere close to it, in order to make good use of cellular automation.

For a game developer, what is useful about cellular automation?

• It is great at creating dynamically-changing systems. Flowing liquid is a particularly excellent example. Simulating the spread of lifeforms across a world is another. The spread of fires across a field of fuel is also well suited to CA-driven simulation; both Dwarf Fortress and Minecraft implement interesting (and dangerous) fire spreading behavior.

• If designed well, cellular automation takes care of its simulation tasks unobtrusively. You can fairly easily overlay other systems, like a platformer engine, upon the world sim. With a little extra work you could devote the CA process to its own thread, possibly allowing it to be run by its own processor.

• Tile-based games are already hosted on a regular, square grid, which naturally suggests a use in cellular automation. In particular, consoles that use hardware tile schemes are well-suited to displaying cellular automation.