game-of-life

Game of Life in Hexagonal, Pentagonal and Other Tessellations

That game of life is hard to play
I’m gonna lose it anyway
The losing card I’ll someday lay
So this is all I have to say

~ M.A.S.H

Started to read The Recursive Universe [1], once again, I got amazed by this Conway’s toy. I tried to make just another implementation of Conway’s Game of Life, with a decent copypasta from Rob Tomlin’s tutorial [2] and fair algorithm and code optimization. Real fun starts when you try it on various tile shapes (squares, triangles, hexagons, pentagons,…)

Rules

millions of dollars in valuable computer time may have already been wasted by the game’s growing horde of fanatics

~ Time 1974

Carter Bays [4] stated a notation for game rules with values E1, E2,../F1, F2,.. of environment and fertility rates. The original Conway’s rules for squares are 2,3/3, which means cells with 2 or 3 neighbors preserve in the same state, while if a dead cell has 3 neighbors, cell will live in next generations.

We call a game of life (GL) rule if it satisfies the criteria below.

  1. When counting the neighbors of a cell, all touching neighbors are considered and treated the same.
  2. At least one glider exists. (An oscillator that translates is called a glider.)
  3. Start with a finite wrapped universe that is completely filled with a random pattern. Then after a finite number of generations, all such patterns eventually must either disappear, or decompose into one or more oscillators. Rules exhibiting this property are said to be stable. [4]

Orthogonal - the original [Live demo]

The original Conway’s rules [1] (2,3/3, [4]) are, if for a given cell:

  1. the number of live neighbours is exactly 2, the cell maintains its status quo into the next generation; (0 -> 0), (1 -> 1)
  2. the number of live neighbours is exactly 3, the cell will live in the next generation; (0 -> 1), (1 -> 1)
  3. the number of live neighbours is 1, 4,…, the cell won’t live in the next generation; (0 -> 0), (1 -> 0)

Live demo of regular Game of life.

Hexagonal [Live demo]

The game of life on hexagons is bit different as each cell has six neighbors. In order to preserve existence of gliders, the rule 3,5/2 satisfies all three criteria [4], if for a given cell:

  1. the number of live neighbours is exactly 2 and the cell lives, the cell will live in the next generation; (0 -> 1), (1 -> 0)
  2. the number of live neighbours is 3 or 5, the cell maintains its status quo into the next generation ; (0 -> 0), (1 -> 1)
  3. otherwise, the cell won’t live in the next generation; (0 -> 0), (1 -> 0)

Live demo of hexagonal Game of life.

Pentagonal [Live demo]

Each cell on the “Cairo tiling” pentagonal tessellation has seven neighbors, which is nice as it is between orthogonal and hexagonal variants. A rule 2,3/3,4,6 seems to be the only rule satisfies all criteria [4], if for a given cell:

  1. the number of live neighbours is exactly 3, 4, 6 and the cell lives, the cell will live in the next generation; (0 -> 1), (1 -> 0)
  2. the number of live neighbours is 2 or 3, the cell maintains its status quo into the next generation ; (0 -> 0), (1 -> 1)
  3. otherwise, the cell won’t live in the next generation; (0 -> 0), (1 -> 0)

Live demo of pentagonal Game of life on Cairo tiling.


A :fried_shrimp: example of pentagonal glider on 2,3/3,4,6, it has period 48 and moves 6 units up.

Rhomboidal [Live demo]

Rhomboidal tiling is formed by dividing each hexagon in regular hexagonal tilings into 3 regular rhombi [8]. Such grid has high connectivity as each rhombus has 10 neighbours, which is called Q*bert neighborhood [8]. We can use the original 2,3/3 rule as in orthogonal grid, if for a given cell:

  1. the number of live neighbours is exactly 2, the cell maintains its status quo into the next generation; (0 -> 0), (1 -> 1)
  2. the number of live neighbours is exactly 3, the cell will live in the next generation; (0 -> 1), (1 -> 1)
  3. the number of live neighbours is 1, 4,…, the cell won’t live in the next generation; (0 -> 0), (1 -> 0)

Interestingly, we can find plenty of still lifes and infinite growth generators, but very little of gilders and oscillators. On a picture below, we can see a small fraction of still lifes.

Live demo of Rhomboidal Game of Life :diamonds:.

Sphinxonal [Live demo]

A sphinx polygon consists of six equilateral triangles and its simplest periodic tiling [9] where two sphinxes fit into a parallelogram. In such periodic tiling, each cell has 12 neighbours (highest among all previously listed tilings). We can use the original 2,3/3 rule as in orthogonal grid, if for a given cell:

  1. the number of live neighbours is exactly 2, the cell maintains its status quo into the next generation; (0 -> 0), (1 -> 1)
  2. the number of live neighbours is exactly 3, the cell will live in the next generation; (0 -> 1), (1 -> 1)
  3. the number of live neighbours is 1, 4,…, the cell won’t live in the next generation; (0 -> 0)

This tiling is rich on oscillators.

Live demo of Sphinxonal Game of Life :cat2:.

Much more interesting tiling using _sphinx is used by Lee and Mood in [10]._

Advent of Code 2020 - Seating System [Part 1], [Part 2]

A variation of Cellular Automata was used as a puzzle in Advent of Code 2020 on Day 13. The idea was to simulate occupation of seats in waiting area as more and more people arrive, with given rules:

Fortunately, people are entirely predictable and always follow a simple set of rules. All decisions are based on the number of occupied seats adjacent to a given seat (one of the eight positions immediately up, down, left, right, or diagonal from the seat). The following rules are applied to every seat simultaneously:

Here is a live demo for my puzzle: Part 1, Part 2

Usage

Feel more that free to use, modify and copy the code, just follow the licence and cite it:

@misc{Kerekrety2020,
  author = {Kerekrety, M},
  title = {Game of Life in Hexagonal, Pentagonal and Other Tessellations},
  year = {2020},
  publisher = {GitHub},
  journal = {GitHub repository},
  howpublished = {\url{https://github.com/matejker/game-of-life}}
}

References

[1] William Poundstone (1985), The Recursive Universe, NTC Publishing Group ISBN:978-0-8092-5202-2
[2] Rob Tomlin (2020), The Game of Life Using JavaScript,
https://medium.com/javascript-in-plain-english/the-game-of-life-using-javascript-fc1aaec8274f
[3] James Tauber (?), CSS Hexagon Tutorial. https://jtauber.github.io/articles/css-hexagon.html
[4] Carter Bays (2005) A Note on the Game of Life in Hexagonal and Pentagonal Tessellations. https://content.wolfram.com/uploads/sites/13/2018/02/15-3-4.pdf
[5] Teruhisa Sugimoto, Tohru Ogawa (2000), Tiling Problem of Convex Pentagon. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.1383&rep=rep1&type=pdf
[6] Eric Wastl (2020), Advent of Code 2020, https://adventofcode.com/2020
[7] Peter Taylor (2014), Implement the Game of Life on Anything but a Regular Grid > Rhombille, https://codegolf.stackexchange.com/a/36176
[8] Wikimedia (?), Rhombille tiling, https://en.wikipedia.org/wiki/Rhombille_tiling
[9] Wikimedia (?), Sphinx tiling, https://en.wikipedia.org/wiki/Sphinx_tiling
[10] Lee, J. Y. and Moody, R. V. (2001), Lattice substitution systems and model sets., Discrete Comput. Geom. 2001, 25, 2, pp. 173–201, MR1811757, or https://tilings.math.uni-bielefeld.de/substitution/sphinx/

This site is open source. Improve this page.