Defining coordinates and directions on hexagonal/triangular grids
Posted: April 22nd, 2021, 9:18 pm
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?
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?