A cellular automaton is a grid of cells, each one having a state, and a rule for determining what state a cell transitions to based on the state of it and its neighborhood. All cells have the same ruleset, but they may be in different states. All state transitions take place at the same time; everything looks at its neighbors and decides what to change to, then everything changes state at the same time.
The grid may be of any dimension (e.g. a line or a cube of cells). More complex examples are possible: Biome implements spiral cellular automata which consists of a number of orbits rotating at different periods where each orbit holds a different number of cells: neighbours include the leading and trailing cells, as well as whichever cells are currently adjacent in the next inner and outer orbits.
Note that this is a general description, there may be exceptions. There are methods that, instead of calculating everything at the same time, randomly pick points and update those points one at a time. Usually the update rule is a finite state machine with inputs, but not always. Some rules consider cells to move across the grid, or to swap state with adjacent cells. Examples of this include the Togetherness automata given in Five Cellular Automata: Algorithms.
Many automata have a characteristic feel to them, even if the grid is initialized with random noise it will converge to look like it was generated with the ruleset. This would be the teleological approach. Many simulate processes, the current state looks like a later version of the previous state. These could be used for an ontogenetic approach.
Cellular automata are often used for dungeon generation especially caves because they often create organic looking patterns. A more complex cave generation routine may use one or two passes of a cellular automata in order to remove isolated single point pillars and otherwise smooth the resulting map. There are also examples of cellular automata which make maze-like maps, such as the Maze CA.
Code Examples
—The following Javascript code implements a simple cellular automata using the rules from Conway's Game of Life.
— (dead link)
Nature of Code has a good tutorial on implementing CA, see http://natureofcode.com/book/chapter-7-cellular-automata/
Alternatively, you can look at notes in New Kind of Science: https://www.wolframscience.com/nks/notes-2-1--implementing-cellular-automata/
PCG Wiki References
External Links
- [http://tpnca.bravesites.com] - TPN's website about his cellular automata
- LiveWiki - A resource on cellular automata related to Conway's Game of Life.
- Cellular Automata - Wikipedia article on Cellular Automata.
- Five Cellular Automata: Algorithms
- Cellular Automata Method for Generating Random Cave-Like Levels - cave generation using Cellular Automata on RogueBasin
- Realtime Procedural Terrain Generation - cellular automata used for erosion.
- C# automata-based cave generation for rouge-likes - A C# implementation of automata-based cave generation.
Flickr Stream
The following images on Flickr have been generated using Cellular Automata:
