Hexagonal Cellular Automata Techniques

By George Maydwell
June 2002
Revised June 2003

Introduction

Using Microsoft's DirectDraw interface made the display time negligible in comparison to the compute time when advancing a cellular automata by a generation. It also had the advantage of allowing color table animation, allowing for more visually interesting color cellular automata. Soon I had Collidoscope, but what I really needed was interesting sets of hexagonal cellular automata rules to put into it. This paper is an introduction to some of the techniques I developed in order to make interesting hexagonal cellular automata. Many of the same techniques can be used to advantage when attempting to define visually interesting rectangular cellular automata, as I demonstrate on my Modern Cellular Automata and Color Game Of Life Visual Exhibition web sites.

June 2003 Revisions

Where are the Interesting Hexagonal Cellular Automata?

So why has there been a historic paucity of visually interesting hexagonal cellular automata? First and foremost it seems that attempting to construct interesting hexagonal cellular automata with only six neighbors is a difficult undertaking. The vast majority of Collidoscope's decay rules are twelve neighbor rules. Very few of Collidoscope's rules are six neighbor rules.

Constructing interesting hexagonal cellular automata with less than four states also seems difficult. Collidoscope has no two state decay rules and only a handful of three state decay rules. Most of the interesting decay rules in Collidoscope have four or more states.

Traditionally, hexagonal cellular automata rules have been defined using the same methodology as is used for defining rule variants of Conway's Game of Life. Simply omitting two opposing corners from an eight cell neighborhood results in a six cell hexagonal neighborhood. Researchers using traditional techniques have thus usually been limited to rules with six neighbors and two states, making it difficult for them to discover the interesting hexagonal cellular automata rules which Collidoscope takes advantage of.

Animation-Reduction Cellular Automata

Hexagonal Superpixels

Hexagonal Neighborhoods

Most of Collidoscope's cellular automata are constructed using the twelve neighbor Star Of David neighborhood. The far and sar neighborhoods and variants are used for setting up grids on top of the hexagonal grid used for the cellular automata world. The far neighborhoods divide the universe into four partitions, whereas the sar neighborhoods divide the universe into three partitions. These are useful for adding cheap special effects to some cellular automata. Note that Collidoscope allows a rule to use a different neighborhood for each step.

Rule Compilers

	decay(eight + 3/23, 2)

Colorization

	red for birth with three neighbors
	green for stays alive with two neighbors
	blue for stays alive with three neighbors

Cellular automata which utilize refractory states provide additional opportunities for colorization. Collidoscope uses multiple colors for a rule's refractory states. A live cell's neighbors are already counted for the purposes of determining whether the live cell survives or becomes refractory. Collidoscope uses these neighbor counts to determine the color with with a cell with refractory or live state is displayed.

Canonical Weighted Form

The ultimate in control for a twelve cell neighborhood is achieved by using base seven weighted counting, where near neighbors count as seven and far neighbors count as one. This canonical form allows each combination of near and far neighbor to be colored differently, or indeed even to behave differently.

Consider a birth in Conway's Game of Life. If we use base five, counting adjacent (near) cells as five and diagonal (far) cells as one, then there are four different ways for this birth to occur:

	total = 15, three adjacent neighbors, no diagonal neighbors
	total = 11, two adjacent neighbors, one diagonal neighbor
	total = 7, one adjacent neighbor, two diagonal neighbors
	total = 3, no adjacent neighbors, three diagonal neighbors

Viewing the exact same cellular automata rule over and over can be boring. Its far more interesting if the rule changes and doesn't always act the same. Consider a variation of Conway's Game of Life in which cells with no adjacent neighbors and three diagonal neighbors die instead of living. A Variation such as this may exhibit differences from the original which vary from subtle to substantial. Collidoscope makes use of even subtle differences on the theory that subtle differences induce visual interest as the viewer's brain innately attempts recognition. Conversion of a rule to the canonical weighted form gives the maximum amount of control possible for effecting subtle variations.

Temporal Rules

Two step temporal cellular automata rules seem to be useful for creating cellular automata in which objects appear to move at two different speeds. Having both slow and fast objects in the same cellular automata adds to visual interest. Collidoscope's Silk cellular automata is an example. In its simplest form Silk is specified in Collidoscope as:

	decay(star(2,1) + 456/ + star(2,1) + 456/1, 4)

Silk is thus a four state cellular automata with two refractory states. It uses a star neighborhood and weighted counting with near neighbors counting as two and far neighbors counting as one. New cells are birthed in empty cells whose count is between four and six inclusive. On alternate steps, live cells with only a single far neighbor stay alive, otherwise they become refractory for two steps just like all other live cells. This kind of step alternation seems to favor the creation of objects that appear to move at half the speed of other objects.

Two or more cellular automata rules can also be combined using seasonal variation, in which one rule is repeated for a large number of steps before another rule is switched to. If the rules are closely related the effects can be subtle. When the number of steps between rule switches is reduced to a more moderate number the cellular automata can appear to have a rhythm or heartbeat.

Another temporal technique used by Collidoscope is transient induction: repeating a rule for a large number of steps, and then using a different rule for only a single step. Inducing a transient is useful for teasing out the dynamic behavior often inherent in a cellular automata. John Elliott's Hextenders is a good example. One of the few interesting six neighbor hexagonal cellular automata rules, it is even more interesting when perturbed by a transient once every hundred steps:

	decay(99 * (six + 23/1345) + six + 234/13456, 10)

Transients are also notably used in Collidoscope's George's Brain variants in which formations periodically stop and restart:

	decay(99 * (star + 34/5678) + six + 235/235, 3)

Collidoscope's variety of neighborhoods provides independent grid capabilities. Collidoscope's Phasers set of rules switches back and forth between using the far star and sar star neighborhoods.

Temporal techniques have not been widely used in cellular automata until Collidoscope, which makes extensive use of them. Use of these techniques substantially expands the number of visually interesting cellular automata which may be constructed.

Non-deterministic Rules

Non-deterministic specification is useful for defining classes of cellular automata rules with variations as described previously. It is also quite useful for specification of periods in temporal cellular automata, where different step periods can result in different emergent behaviors. Collidoscope only has on the order of a hundred different rule specifications, but these specify a combinatorial variety of cellular automata rules which is well beyond my capability to enumerate.

It should be noted that the traditional notion of a non-deterministic cellular automata rule is entirely different from Collidoscope's notion.

Conclusions

References