Gamasutra: The Art & Business of Making Gamesspacer
An Intro to Cellular Automation

Printer-Friendly VersionPrinter-Friendly Version
View All     RSS
April 25, 2014
arrowPress Releases
April 25, 2014
PR Newswire
View All





If you enjoy reading this site, you might also want to check out these UBM TechWeb sites:


 
An Intro to Cellular Automation

May 4, 2011 Article Start Page 1 of 3 Next
 

[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.

Article Start Page 1 of 3 Next

Related Jobs

Nexon America, Inc.
Nexon America, Inc. — El Segundo , California, United States
[04.24.14]

Web Designer - Temporary - 3 month
Darkside Game Studios
Darkside Game Studios — Sunrise, Florida, United States
[04.24.14]

Mid-Senior Graphics Programmer
Digital Extremes
Digital Extremes — LONDON, Ontario, Canada
[04.24.14]

UI ARTIST/DESIGNER
Digital Extremes
Digital Extremes — LONDON, Ontario, Canada
[04.24.14]

UI ARTIST/DESIGNER






Comments


Robert Boyd
profile image
Thanks for the great article!



Thanks to you, I now want to make a 2D water flow based puzzle game. :)

Carlo Delallana
profile image
Some of the more interesting applications of CA i've used is in generative music. When married with audio and a set scale of notes (Chromatic, Lydian, etc) the system is able to produce some really interesting compositions.

Bart Stewart
profile image
Something to bear in mind is that thinking in terms of cellular automata is not like regular procedural programming.



Rather than directly coding specific behaviors for a specific object type that is both complex and unique, you have to think indirectly -- you're setting up a few simple rules for a large number of identical small objects and saying, "Go!" Becoming effective at this style of coding is similar to the mental shift that's required when switching from a procedural language like C or Java to a declarative language such as Prolog or LISP. For the best results, you need to be able to "think" in each style.



In the case of cellular automata, the thinking style is more exploratory than imperative. Instead of telling one complex object exactly how to behave, with zero tolerance for undefined or unexpected behaviors (which are treated as bugs), you win by thinking in terms of turning the key on a bunch of wind-up toys and seeing what happens.



In other words, the behavior of masses of cellular automata is less predictable than that of procedurally-defined individual objects, and it's necessary to be OK with that. Rather than thinking "this is the exact behavior I expect to see; anything else is a bug," programming CAs needs thinking more like, "as long as the mass behavior is within certain bounds of behavior and performance, the specific ruleset is irrelevant."



So to anyone thinking of trying this: jump in, let go, and have fun seeing what happens!

John Harris
profile image
Yes, this is exactly the way to think of it.

Jean-Michel Vilain
profile image
Cool to see someone comparing the life game with Prolog :-)

Ted Brown
profile image
Articles like this are dangerous to my spare time! =) Thanks for posting!

Robert Boyd
profile image
No kidding. Now I want to try making a system based on this when I really should be working on something else instead.

Carlo Delallana
profile image
so many ideas, so little time

Arnaud Clermonté
profile image
There's an simpler way than setting a "do not calculate" flag:

Instead of processing all the cells in order,

process all the even cells, then all the odd cells.

In the case of a 2d grid, see the world as a checkers board:

Process all the whites, then all the blacks.

That way, assuming there are no diagonal moves, a moving block will only be able to move by 2 tiles in 1 simulation tick.

( you can even do the 2 steps on separate simulation ticks )

John Harris
profile image
That's such a clever idea I may end up using it myself! I wish you were around when I was working on the Commodore so long ago....

ignace saenen
profile image
You can recode diagonal moves as a move in 2 steps, e.g. first horizontal and then vertical. [You'll briefly need to be able to store more than 1 object per cell, until the second pass ticks.]

Will Hendrickson
profile image
Wow, a very insightful optimization, Arnaud, since if the frames are close enough together a player is unlikely to notice that diagonals are not calculated. Of course, this means that if they do notice, it might change the gameplay. A good example would be the miasma in Dwarf Fortress, which is not calculated diagonally, so many players use diagonal entrances to refuse piles indoors to take advantage of this.



Cellular automation is a very cool technique that can accomplish a lot, I would love to read more ideas people have about possible uses for it, especially in a 3D environment.

Andrew Baker
profile image
You should probably take a look at this article regarding the currently most optimal (speed, not memory) way of doing fast CA calculations: http://drdobbs.com/high-performance-computing/184406478

Abstract: Using a quad-tree and memoization leads to extraordinarily performant CA calculations on arbitrarily large sets.

John Harris
profile image
Thanks for the tip! Since I wrote the article I discovered that MathWorld has a number of articles on CA, which makes sense now that I think of it since it's Stephen Wolfram's site. Might be some interesting reading to be done there as well. And as I mentioned, hobbyists have been working on worldsim CA, in the form of Falling Sand clones, for a few years now.

John Harris
profile image
Recognizing the name "HashLife" from Golly, I did a search for the pattern your article mentions, "metacatacryst," put it into Golly and started running it.



At first it didn't seem to be extraordinarily fast. That was because the pattern defaulted, it turns out, to QuickLife. I turned on HashLife. Again, I didn't notice must of a speedup.



Then I noticed an option in the menu, "Hyperspeed." Interesting. I activated it.



Dear god!!!



I think I understand how HashLife works in principle, but it's going to take a few rereads to wrap my head around it. A most excellent and awesome algorithm!

Andrew Baker
profile image
I'm glad it's helpful. I'm looking forward to seeing your project completed.

raigan burns
profile image
Awesome article, great ideas presented well -- thanks!



I don't suppose you might be planning a follow-up where you detail your current system? I'm really curious about what changes you ended up making and why :)

Matthew Mouras
profile image
Great article. I have a friend who has been lost to experiments with CA for years... he seems happy, if not possessed. Now I have a better understanding of these systems. Thanks much.

Mika Luoma-aho
profile image
Great article!



About optimizations:

- Instead of looping through everything (in the screen space) each frame, you could have a simple list (sorted by y-axis values for example) of potentially changing cells that should be checked for changes in the next frame. Ofcourse things that change each frame should be in the list all the time (like gases) but more stationary things like boulders do not need to be checked every time, but only when there is change near them

- Using this kind of optimization with flowing water is harder but should be possible and could allow you to simulate the whole game world each frame (and maybe sacrifice simulation accurancy for things that are far away from the user point of view).

John Harris
profile image
I have indeed considered keeping a list of potentially-changing frames, and some other schemes like active rectangles and such. It's still very early in development and I'm following Knuth's edict about not optimizing too early, focusing more of getting it working at the moment. And in fact I believe water would optimize well this way; most of the action with water occurs on the surface.



There may well be a clever way optimize gases like this too. There is a lot of experimental work left to be done here.

Jeff Beaudoin
profile image
I really like this article, nice work.



One sort of cosmetic change you could make would be to have blocks of water that filled from the top display as a full block, but with one of eight (or however many units of water fit in one block) different colors of blue, depending on how full they are.

This would give you a solid stream running down but still show some difference between water levels.

John Harris
profile image
The current version shows fluid as a level even when unsupported for ease of understanding. It will definitely look different in the final version.


none
 
Comment: