Hexagonal cellular automata

squareNeumann

The four nearest neighbors (orange) around a cell (green) make the von Neumann neighborhood.

squareMoore

The first (orange) and second (red) nearest neighbor of a cell (green) are the Moore neighborhood.

Earlier I used a complicated cellular automaton to create images of snowflakes, see “Fake snowflakes“. It is based on a hexagonal grid in contrast to the well-known cellular automata such as Conway’s game of life, that use square grids. Here I want to show how to transfer these automata from the square grid to the hexagonal grid. Then, these automata could create new images.

In a square lattice a cell has four nearest neighbors, see the figure at the top left. If its state in the next generation depends only them, then we have a von Neumann neighborhood. It is not often used. Each cell has four second-nearest neighbors, see the figure at the top right. If all eight neighbors determine the state of the cell we use a Moore neighborhood. It gives more interesting automata, such as the game of life.

hexagonNeumann

The six nearest neighbors (orange) of a hexagonal cell (green) correspond to the von Neumann neighborhood.

hexagonSquareNeumann

The hexagon grid is distorted to a square grid. The cells shown in orange are the von Neumann neighborhood of the cell in green.

In a hexagonal lattice each cell has six nearest neighbors, see the middle figure at the left. This corresponds to the Neumann neighborhood. To simplify programming we distort the lattice by shearing and compressing along the x-axis. The cells are then put on a square lattice. They still have six nearest neighbors, see the middle figure at the right. Note that this is not some mixture between the von Neumann and the Moore neighborhood. Instead they form the von Neumann neighborhood of the hexagonal lattice. In addition, boundaries of a region of cells are too distorted. Regular hexagons become irregular and have angles of 90 degrees and 135 degrees.

hexagonMoore

Moores neighborhood (orange and red) of a cell (green) in a hexagonal grid.

hexagonSquareMoore

Moores neighborhood in the distorted hexagonal grid.

To run something like Conway’s game of life on a hexagonal lattice we probably need the Moore neighborhood. It contains the nearest and second neighbors and is shown in the lowest figure at the left. Distorting the lattice as before, we get twelve neighboring cells in the square lattice, see the figure at the bottom right. Note that thinking of a hexagonal lattice the cells shown in orange are actually all nearest neighbors of the central cell (green) and the cells shown in red are all its second nearest neighbors.

Because of the complicated distorted boundaries, I do not use periodic boundary conditions. Instead, I assume that outside a finite region all cells have their state equal to zero at all times. This allows a fast calculation.

This entry was posted in Cellular automata and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s