Saturday, October 8, 2011

Hyperbolic cellular automaton

Putting Conway Life to the hyperbolic plane.
Lightspeed glider in the unstable B2/S3 universe

Tessellations of the hyperbolic plane are cardinally different from the tessellations of the usual, euclidean plane. For example, for every regular plane tessellation, number of rank N neighbors grows as O(N2). However, on hyperbolic plane tessellation, it grows exponentially.
One of the simplest tessellations is {5;4}-tessellation, called here "pentagrid": covering of the plane by equal pentagons. Here is comparison chart of the pentagrid and rectangular grid:

Growth of the Nth order neighborhood on the hyperbolic (top) and euclidean (bottom) planes.
100th picture in this row would contain 39'601 cells in the bottom and tremendous 1'654'532'714'419'705'795'495'081'843'249'376’928’300’045’264’805’055’678’601 cells in the top.
So, what do Game Of Life looks like on pentagrid?
Here are some findings in the totalistic, 2-state cellular automations on the pentagrid.

Rule B3/S23

This rule is analog of the Conway Game of Life. However,the behavior it exhibits on the pentagrid is different.

Block (still life)5-honeycombAnalog of the beacon

Common still lifeNameless oscillatorComplex period-16 oscillator

Unfortunately, this rule (and all rules on pentagrid, that has no "1" or "2" in their B section), can not support spaceships. No cell configuration can outgrow its original bounds. It is class 2 by the Conway's classification.


This rule is unstable, almost any initial pattern will grow infinitely. However, some patterns demonstrate more interesting behavior. Most interestingly, this rule supports glider (picture at the top shows it in motion).
Glider (stop-frame)

Oscillator 1

Oscillator 2
Block evolves to 4 gliders2 cells replicating endlessly


Java application used to produce these simulations can be downloaded here (sources). The program lacks user interface, so if you really want to try it, read the README file first.

The most challenging problem in writing this application was developing a way to address cells on the pentagrid, and enumerating neighbors. While on the plane we can happily use 2 integers to address any cell, in the non-euclidean geometry it is absolutely not enough. Instead, tree structure can be used.

Coordinate tree for the pentagrid
Here, coordinate of each cell is not a pair, but a chain of numbers. The advantage of such approach is that it allows to calculate cell neighbors relatively easy.