Defining coordinates and directions on hexagonal/triangular grids

[muzik]

Awful Introduction Section that you can probably skip
The majority of cellular automata explored today take place on the square grid {4,4}. Without a doubt due to its ease to draw and picture, it was used for the founding rules which went on to shape the modern cellular automata community. More recent efforts have resulted in the investigation of analogous cellular automata on other grids, notably the other two regular proper tilings of the plane: hexagonal {6,3} and triangular {3,6}. Modern software support for rules on these grids has removed any need for mental visualising and illustration, however to this day flaws remain in almost all general-purpose simulation programs, likely due to how cell positions are stored.

On the square grid, any cell's position (relative to an origin) can be described with simply two numbers (the Cartesian coordinate system). For both simulation and external manipulation, this system works flawlessly, and has been a staple since the very first simulation programs.

When simulating hexagonal and triangular patterns, the square grid and coordinates can also be used, as is seen in Golly's implementation. Subsequent visual manipulation can be used to make such patterns appear on true hexagonal and triangular grids, as is done by LifeViewer and (excluding triangular) Catagolue. All of this works fine for viewing and simulation, however, for editing, much of the assumptions that were made with the square grid in mind break down when applied to either grid.

For example:
- Rotation of patterns always assumes the use of a square grid and applies transformations based on that, which for non-square grids results in arbitrary and meaningless scrambling of the pattern (except for 180-degree rotations, due to these being shared between p4 and p6).
- Flipping of patterns across orthogonal lines also assumes that said orthogonal lines would be symmetric, which for hexagonal grids is not the case
- Selections of regions are derived using two points, which are then used to trace out a square - again this becomes arbitrary and meaningless for grids that do not support the existence of squares symmetrically
- In the case of triangular grids, which, for simulation on a square grid invert the neighbourhood vertically for positions of odd parity, the translation of a pattern by an odd amount results in a completely different pattern, which tends to be problematic when copying RLEs.

----
OK, Here's The Important Bit
As was described terribly by me above, it's clear that while cells on hexagonal and triangular grids can be described just fine via two numbers, they cannot be described "symmetrically" by it, which arises quite a lot when editing such patterns. As a result, for at least some cases, it may be a better idea to just forget about describing cells via Cartesian coordinates and use a dedicated coordinate system for each tiling that respects its symmetry.

Figure 1 of this paper describes two such coordinate systems that can be applied to the grids. While each cell, as a result, now requires three values to specify instead of two, and that we abandon the convention that all combinations of integers correspond to a valid cell, these systems do nonetheless obey the symmetries of their respective grids where Cartesian coordinates did not. However, they do obey new potentially useful rules: the coordinates of all valid hexagonal cells will always sum to 0, and triangular cells will sum to either 0 or 1 depending on their "direction".

Coupled with This Post I Made Earlier, we can now define orthogonal and diagonal directions on both hexagonal and triangular grids using these coordinate systems:
- orthogonal motion will be a displacement containing a 0, a -n and a n, and
- diagonal motion will be displacement containing a 2n and two -ns, or a -2n and two ns.

----
Stuff I Want To Know
I doubt that any of the major CA simulators will ever adopt these coordinate systems (as much as I'd encourage it), but learning and using these coordinate systems in common parlance to describe features of CA that use these grids should end up being a massive boon to the exploration of these rule families. However, there are some things that I'm still not completely certain of:

- For spaceship and other moving object displacements, how would the canonical displacement be written? While they'd definitely still be listed in descending order, I'm torn between "make as many of the values as possible positive" and "make the value with the highest absolute value positive". And since the coordinates will always sum to 0 for hexagonal ships, would it be a good idea to always omit one insignificant value for brevity, or not?
- Would using these coordinate systems imply the existence of "optimal"/"canonical" selection options? Square selections obviously don't work very good for hexagonal and triangular grids, so it might be better to use hexagon and/or triangle shaped selections on said grids. Similarly to how a rectangle can be described using two sets of coordinates which have two values, is it possible to define a good bounding triangle or hexagon using two sets of coordinates which have three values?
- Are there any other advantages I haven't mentioned here? And are there any disadvantages (outside of being harder to code or taking up a bit more space) to using these instead of square coordinates?

[bprentice]

A related issue is pattern editing. Square Cell, Hexagonal Cell and Triangular Cell do not use rubber banding or the clip board to perform pattern editing. Rather, a group of cells may be selected by clicking the display with the control key depressed. The first click marks a corner of the selection area and the second click marks the diagonally opposite corner. A third click clears the selection. When selected a group of cells may be manipulated by several of the toolbar buttons. Selections may be rotated, flipped, written to a file, set to a random state and moved or copied by dragging. The inside or outside of a selection may also be cleared. 90 degree rotations are performed by Square Cell and 60 degree rotations are performed by Hexagonal Cell and Triangular Cell. Selected cells do not participate when the simulation is run and thus selections may be used for temporary storage and pattern synchronization.

The following patterns were constructed from a single cell using only the selection, move, copy, clear, rotate and flip operations.

S.png (242.58 KiB) Viewed 826 times

H.png (1 MiB) Viewed 826 times

T.png (1.17 MiB) Viewed 826 times

Using the simulator of your choice do the same thing.

See:

https://www.conwaylife.com/wiki/LifeWik ... n_Software

Brian Prentice

[muzik]

Another thing related to this: how exactly would bounded grids be made to work?

Currently, the bounded grids we use for hexagonal and triangular patterns are clearly based on the square grid, giving us a rhombus for hexagonal grids and a weird rectangle on triangular grids, identically to selections:

Code: Select all

x = 2, y = 2, rule = B12/SH:T30,30
2o$2o!

Code: Select all

x = 2, y = 2, rule = B12/SL:T30,30
2o$2o!

For the hexagonal case, it's easy to cut this rhombus down to a hexagon geometrically:

Code: Select all

x = 30, y = 30, rule = B12/SH:T30,30
16b14o$17b13o$18b12o$19b11o$20b10o$21b9o$22b8o$23b7o$24b6o$25b5o$26b4o
$27b3o$28b2o$29bo3$o$2o$3o$4o$5o$6o$7o$8o$9o$10o$11o$12o$13o$14o!
[[ VIEWONLY COLOR BOUNDED 128 128 128 COLOR ALIVE 128 128 128 COLOR DEAD 0 0 0 ]]

The big question is what manifolds should be allowed. Hexagons support a wider array of possible gluings than a rectangle does (and we don't even have the full set of square manifolds either so far - finite cylinders and mobius strips, anyone?). And also note that this is a regular hexagon - what irregular bounded grid parameters should be supported given that we accept rectangles? And of those irregular hexagons, how would we notate them?

----

Back on the topic of selections (although this could still very well apply to bounded grids), there are two possible hexagon shapes for selections on a hexagonal grid. The following is the closest analogue to our current rectangle selection:

Code: Select all

x = 65, y = 65, rule = B123456/S0123456H
33o$34o$35o$36o$37o$38o$39o$40o$41o$42o$43o$44o$45o$46o$47o$48o$49o$
50o$51o$52o$53o$54o$55o$56o$57o$58o$59o$60o$61o$62o$63o$64o$65o$b64o$
2b63o$3b62o$4b61o$5b60o$6b59o$7b58o$8b57o$9b56o$10b55o$11b54o$12b53o$
13b52o$14b51o$15b50o$16b49o$17b48o$18b47o$19b46o$20b45o$21b44o$22b43o$
23b42o$24b41o$25b40o$26b39o$27b38o$28b37o$29b36o$30b35o$31b34o$32b33o!
[[ VIEWONLY GRID ]]

This is more analogous to a "von Neumann selection", which no program currently supports:

Code: Select all

x = 89, y = 89, rule = B23456/S0123456H
22bo$21b4o$20b7o$19b10o$18b13o$17b16o$16b19o$15b22o$14b25o$13b28o$12b
31o$11b34o$10b37o$9b40o$8b43o$7b46o$6b49o$5b52o$4b55o$3b58o$2b61o$b64o
$67o$b66o$b67o$2b66o$2b67o$3b66o$3b67o$4b66o$4b67o$5b66o$5b67o$6b66o$
6b67o$7b66o$7b67o$8b66o$8b67o$9b66o$9b67o$10b66o$10b67o$11b66o$11b67o$
12b66o$12b67o$13b66o$13b67o$14b66o$14b67o$15b66o$15b67o$16b66o$16b67o$
17b66o$17b67o$18b66o$18b67o$19b66o$19b67o$20b66o$20b67o$21b66o$21b67o$
22b66o$22b67o$24b64o$26b61o$28b58o$30b55o$32b52o$34b49o$36b46o$38b43o$
40b40o$42b37o$44b34o$46b31o$48b28o$50b25o$52b22o$54b19o$56b16o$58b13o$
60b10o$62b7o$64b4o$66bo!
[[ VIEWONLY GRID ]]

There are also four triangular options for the hex grid, two Moore-like and two von Neumann:

Code: Select all

x = 72, y = 32, rule = B23456/S0123456H
o39b32o$2o39b31o$3o39b30o$4o39b29o$5o39b28o$6o39b27o$7o39b26o$8o39b25o
$9o39b24o$10o39b23o$11o39b22o$12o39b21o$13o39b20o$14o39b19o$15o39b18o$
16o39b17o$17o39b16o$18o39b15o$19o39b14o$20o39b13o$21o39b12o$22o39b11o$
23o39b10o$24o39b9o$25o39b8o$26o39b7o$27o39b6o$28o39b5o$29o39b4o$30o39b
3o$31o39b2o$32o39bo!
[[ VIEWONLY GRID ]]

Code: Select all

x = 132, y = 63, rule = B23456/S0123456H
o99bo$b2o96b2o$b4o93b4o$2b5o90b5o$2b7o87b7o$3b8o84b8o$3b10o81b10o$4b
11o78b11o$4b13o75b13o$5b14o72b14o$5b16o69b16o$6b17o66b17o$6b19o63b19o$
7b20o60b20o$7b22o57b22o$8b23o54b23o$8b25o51b25o$9b26o48b26o$9b28o45b
28o$10b29o42b29o$10b31o39b31o$11b32o36b32o$11b34o33b34o$12b35o30b35o$
12b37o27b37o$13b38o24b38o$13b40o21b40o$14b41o18b41o$14b43o15b43o$15b
44o12b44o$15b46o9b46o$16b47o6b47o$16b46o9b46o$17b44o12b44o$17b43o15b
43o$18b41o18b41o$18b40o21b40o$19b38o24b38o$19b37o27b37o$20b35o30b35o$
20b34o33b34o$21b32o36b32o$21b31o39b31o$22b29o42b29o$22b28o45b28o$23b
26o48b26o$23b25o51b25o$24b23o54b23o$24b22o57b22o$25b20o60b20o$25b19o
63b19o$26b17o66b17o$26b16o69b16o$27b14o72b14o$27b13o75b13o$28b11o78b
11o$28b10o81b10o$29b8o84b8o$29b7o87b7o$30b5o90b5o$30b4o93b4o$31b2o96b
2o$31bo99bo!
[[ VIEWONLY GRID ]]

Again, the question of how "irregular" versions of these would be supported remains.