ExtendedSource checked

Cellular Automata

Updates grid cells from simple local rules.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Simulation
Difficulty: Beginner
Family: Discrete Simulation
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 4
Code example: Not ready
Visualization: Ready
Aliases: CA

Overview

Cellular Automata model complex behavior by applying the same rule to every cell based on neighboring cell states.

Core Concepts

simulated statecell state rulegrid frontierdiscrete simulationstate updatetime stepnumerical stability

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(t n)

Worst

O(t n)

Space

O(n)

When to Use

Use Cellular Automata when you need to store states on a grid.
Use it for pattern simulation with inputs like initial grid.
Use it when approximate behavior over time is more useful than a closed-form answer.
Use it when the Discrete Simulation tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when the time step, grid size, or sample count cannot support stable results.
Avoid it when the required output is not updated grid states.

What It Does

Stores states on a grid
Updates each cell from its neighborhood

Use Cases

Pattern simulation
Epidemic or fire spread models
Procedural cave generation

Inputs

Initial grid
Neighborhood rule
Step count

Outputs

Updated grid states

Key Formulas (1)

Cell update

state_next(cell) = rule(state(cell), neighbor_states)

state_next(cell) = rule(state(cell), neighbor_states)

Updates each grid cell from its current state and local neighborhood.

Pseudocode

1.Start with an initial grid
2.For each step, inspect each cell's neighbors
3.Compute the next state from the rule
4.Write updates into a new grid
5.Replace the old grid

Canonical Example

Input: position = 0, velocity = 2, time step = 0.5
Output: next simulated state
Explanation: Cellular Automata: The algorithm advances the system by applying its update rule over a small step.

Implementation Notes

Keep the input contract explicit: Initial grid; Neighborhood rule; Step count.
Use this step as the implementation spine: Start with an initial grid.
Then preserve the next state change: For each step, inspect each cell's neighbors.
Track units and invariants such as mass, energy, or count where they matter.

Common Pitfalls

Simple local rules can create surprisingly complex global behavior.
Using a time step that is convenient for rendering but unstable for the simulated system.
Returning updated grid states without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show grid cells changing from local neighbor counts.

Step 1 of 5: Start with an initial grid

cell-grid-rules

Notes

Cellular Automata operates in O(t n) time and O(n) space within the Discrete Simulation family. Key governing relation: state_next(cell) = rule(state(cell), neighbor_states). Often compared with Cellular Automata Cave Generation and Flood Fill.