Using Cellular Automata to Create a Random Map Generator

profile image

Matthew Bauer
blog post header image
map-generation world-building

Learn how to programmatically generate earth-like terrain using cellular automata.

Introduction to Cellular Automata

A cellular automaton consists of a grid of cells, each in one of a finite number of states, such as on and off. The grid can be in any finite number of dimensions. For each cell, a set of cells called its neighborhood is defined relative to the specified cell. An initial state is selected by assigning a state for each cell. A new generation is created, according to some fixed rule that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood.

The Game of Life

In the classic model of Cellular Automata (CA) Conway's Game of Life, the cells follow four simple rules.

  1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by overcrowding.
    4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

These simple rules ended up evolving complex patterns capable of motion and self-replication.So, if we take the ideas from this and apply them to map generation we should be able to create unique worlds for players to explore.

Applying CA to Map Generation

In Conway's Game of Life the cell is either alive or dead and always stays in one location (Although patterns can give the appearance of motion). For map generation we are going to create agents to move fromtheir current cell to one of the neighboring cells.

Creating Agents

Agents work with a given set of rules. The rules of an agent are determined by what you want that agent to accomplish. Maybe you want an agent that can create meandering rivers, lakes, or mountain ranges. Rules can be developed to create all of these things. For this example we are only going to create on set of rules for all of our tile types.

We want our agents to create groupings of tiles that are the same, while still having an element of randomness. To accomplish this we have 2 simple rules.

  • An agent can only move to a neighboring tile that is not the same type that the agent is creating.
  • An agent is more likely to move to a tile if that tile has more neighboring tiles of the agent's type.

Initial State

Initially I fill my map with one tile type, grass. Then I create a random number of Tree Agents, Mountain Agents, and Water Agents and place them randomly on the map.

Each agent is given a number of times they are allowed to move. When they run out of moves or they can't find a new place to move to, they are killed. The maps that are created can be varied by changing the number of agents that are used or by changing the number of times they are allowed to move. I start by filling a percentage of the map with agents and then give them a random number from a range to determine how far they can move.

Examples

Here are two example maps that my agents created. The larger map is 200x200 and the smaller map is 50x50.

Cell A cell is a location inside the Map that contains a cell type that is manipulated by an agent.

Cell Type The type of cell it is. Our cells have the following types Grass, Mountain, Water, and Tree.

Map The map is a 2-dimensional plane that is separated into an NxM matrix of cells.

Neighborhood/Neighbors The neighborhood of a cell consists of any cell that is touching or diagonal to the current cell.

Recommended posts

We have similar articles. Keep reading!