Playing with cellular automaton

While thumbing through a copy of Ian Millington’s Artificial Intelligence for Games recently, I discovered a section on cellular automaton. I had encountered cellular automaton before, but was only familiar with John Conway’s Game of Life version, in which the state of a cell is modelled as “on” or “off” depending on the states of its neighbours.

As Millington points out, other variations of cellular automaton can be used to create decision-making systems for games and other simulations. Genre-defining city-builder SimCity, for instance, uses a cellular automata to develop and degrade buildings based on the properties of their neighbours - albeit as one system among many that determined how prosperous the player’s city will become.¹

Welcome to cellular city

The simple simulation that runs on this page is a somewhat contrived example of a base-building AI in a strategy simulation. Let’s say the objectives of this simulation is to create a settlement with a balance of different building types - houses, farms, markets and theatres. Construction of these buildings relies on natural resources (forests), and access to resources is secured by the placement of defensive towers.

Successful settlements are resilient to attacks if they avoid locating buildings of the same type next to each other, and have a good ratio of defensive towers to other buildings - within reason, of course, as the placement of a defensive tower occupies a cell that could perhaps be used by another, more valuable building.

We can implement a cellular automata system that broadly adheres to these objectives with the following ruleset:

1. A cell near a forest can be used to build a defensive tower, up to a maximum of two defensive towers.
2. A cell bounded two defensive towers can become either a small house, small market or small farm.
3. A cell bordering two basic buildings (of any type) should become a large building of another type, to prevent locating the same types of buildings next to each other.
4. Theatres can only be built in a space that borders two large buildings of different types.

Due to the random initial placement of trees (which you can control if you pause the simulation), as well as the random allocation of the basic buildings as per rule 2, this simulation produces a nice diversity of settlement layouts.²

I have diverged from traditional cellular automaton in a couple ways in this simulation. For instance, I’ve limited the system to generating only one building per generation. In Conway’s Game of Life, the entire next generation of cells are calculated based on the current generation and updated at the same time. Using that approach here however, would result in the forest cells immediately being surrounded on all sides by defence towers.

I have also randomised the order in which the system picks the next cell to evaluate against the ruleset. This is to prevent the system from constructing ‘strips’ of buildings, as it would if simply cycling from the top-left to the bottom-right of the grid.

That said, a more advanced approach might be to identify zones in which the system has started to generate a ‘critical mass’ of buildings and focus more on developing these areas. This could actually be achieved with a separate cellular automata system, perhaps based on a larger grid, to identify and mark areas as good candidates for settlement enlargement.

The complete code for the simulation is available on GitHub.