First off, I'll briefly note the standard way to embed a hex neighborhood for cellular automata, which is to place cells at integer coordinates, and use the Moore neighbor minus two opposite diagonal corners, such as the lower left and upper right corner (in other words, compass points SW and NE). Let the remaining 6 neighbors be the location of adjacent hex cells. It's pretty easy to verify by eye that this works, and for many purposes, it's enough to work with a hex neighborhood. If you set up an mXn grid (m vertical, n horizontal), you get a parallelogram of cells in the hex grid that is m cells across and n cells down. I prefer to refer to positions as (i, j) with i increasing down, as rows, and j increasing to the right as columns. This is because I usually think of these as array indices rather than points (x, y) in the Euclidean plane.
If you just want a parallelogram of hex cells, it's that simple. You skew the coordinates for display, either with graphics or text. If you want a toroidally wrapped parallelogram, it's again not hard. For every (i, j) in an infinite grid, the position in the base parallelogram is (i mod m, j mod n) (with mod computed correctly to yield non-negative values, thankfully something Python does automatically with %).
But what if you want a different kind of wrapping? One that comes to mind and can be used to make tessellations with rotational symmetry is to rotate an nXn rhombus 120° or 240° and fit these together in hexagons. Note: one way to accomplish this is to keep track of the adjacency at boundaries. This is good enough for cellular automata that look only one neighbor away at a time. However, in my experience it's frustrating to get the adjacencies right. In addition, if you want to plot an arbitrary (i, j) as part of a tessellation, you have go through some extra mechanics crossing that boundary, since there is also a rotation involved. I have written code like this, and I find it hard to debug and even harder to understand a month later.
Here is an approach to handling tessellations based on rotations around corners of hexes (I'll get to centers of faces later). While it applies to any n, I am illustrating it with n=4. The left picture shows a hex grid with green, red, and blue rhombic clusters of 4x4 hex cells each. The green rhombuses are shown upright and red and blue are rotated 120° and 240° respectively. The right picture is simply a copy of the left with a skew I applied using Inkscape to show how all these cells map to a rectangular grid with integer positions (i, j). Each cell is labeled ij for values 0-3 in the base rhombus.
- Screen Shot 2021-01-27 at 6.33.50 PM.png (830.87 KiB) Viewed 875 times
A second symmetry operation consists of translations (derivable by composing rotations in two different places, but also visible in the picture). The green squares in the picture on the right lie along diagonals, and can be shifted along the same diagonal or to an adjacent diagonal. Moreover, any cell that lies in a green square can be mapped to its base position just by finding (i mod 4, j mod 4). To get from a green square to another green square, you can shift by any multiple of (-4, 4) to move along a diagonal, or by any multiple of (0, 12) to change diagonals. These both preserve the value of (⌈i/4⌉ + ⌈j/4⌉) mod 3, leading to a simple way to check if (i, j) is in a green square
It is not as simple to deal with the red and blue cells. While it's possible to subdivide them into triangles in the periodic squares, it gets hard to work with. If the goal is to go from (i, j) to its equivalence class in [0,3]X[0,3] it would be nice if everything were as simple as the green cells. So rather than analyze the hard case, just apply one or two 120° rotations until the cells are in a green square.
Fortunately, the skew that put all the hex centers at integer coordinates also changes the rotation matrix to integer values, so it's easy to carry out this rotation. Here is the algorithm in full (stated for general n, though illustrated for n=4):
While (⌈i/n⌉ + ⌈j/n⌉) mod 3 ≠ 0:
- Apply the rotation (i, j) → (j-i-1, -i-1)
This is simpler to implement than explain how it works, but hopefully the picture helps.
Until recently, I thought I was done, but there is a problem. When you rotate around corners, you always wind up with some triples of hex cells that are in the same equivalence class (and have the same state in a cellular automata) and all adjacent to each other. See the cells marked 00, 33, and 30 in the picture above.
This may be acceptable, but when working with coloring constraints that disallow adjacent hexes to have the same color, I found (obviously) that this kind of symmetry made any coloring impossible. In that case, it is better to use a face-centered rotation, i.e. one in which the cell labeled 00 stays at (0,0) instead of rotating through (0,0), (-1,-1), (-1,0) and back to (0,0).
The face centered case can be handled using the same kind of tessellation into rhombuses, but it is somewhat trickier. I was nearly despairing of getting it working till I found this approach:
- Screen Shot 2021-01-27 at 8.15.40 PM.png (363.68 KiB) Viewed 875 times
The plane is partitioned into 4x4 rhombuses as above, but look closer. They are not all numbered the same. The picture on the right is intended to illustrate which 4x4 sub-rhombus of a larger 5x5 rhombus is represented at each location.
To map this rotation to equivalence classes, do as follows. First apply algorithm used above, as if the rhombuses were for rotations around corners. Since we applied the rotation (j-i-1, -i-1), we do not keep (0,0) fixed as we would like it to be. So we simply correct it after the fact.
- If we applied one rotation, change (i, j) to (i+1, j+1), nudging (-1,-1) back to (0, 0).
- If we applied two rotations, change (i, j) to (i+1, j), nudging (-1, 0) back to (0, 0).
Finally, if the label is x0 with x>0 or 4x with x<4, then swap the order.
While this is more complicated than vertex rotation, it is a useful form of symmetry that I have implemented in this Python code used to generate SAT instances. I don't know if there is a simpler implementation.