TIL: Triangle grids
I’ve been jamming on a little game prototype with a friend that uses a triangle grid. Figuring out how to set up the coordinate system has been a bit of a nightmare; triangles are super weird! We’ve currently got it set up so that each row of triangles shares a y coordinate, and then the x coordinates are a bit wonky depending on which y you’re at. Like this:
This is handy for storing the map in memory, but not very nice at all for answering questions like “how far away are these two triangles from one another” or “what triangle did the player click” or even just “where do I draw this triangle”. In this coordinate system, (0,0) and (2,1) have two other triangles between them, but (1,0) and (3,1) share a common point. So figuring out what’s adjacent to a triangle depends on the particular place that triangle is.
Amit Patel, of course, has thought about this problem. He suggests a coordinate system like a skewed square grid, where you divide each square in two across its diagonal. In this system, there are three coordinates: x, y, and R. The x and y coordinates tell you which rhombus you’re in, and the R coordinate tells you whether you’re in the lower-left triangle half of the rhombus or the upper-right one, so it’s just a binary 0 or 1. (Amit labels the two options L and R, but that seems a little confusing because the name of the 3rd coordinate is also R.)
The sheared-square coordinate system is a lot easier to work with for figuring out where the player clicked, because it’s just a little matrix math to un-shear the world and then you can use regular square grid math to figure out the x and y, and then you just need to figure out whether you’re in the bottom-left or top-right half of the square (i.e. unsheared rhombus), and that gets you your R value. The (x, y, R) system isn’t so great for computing distances, though, so Amit wrote another article about that.
The idea with this system is that the distance between any two triangles is the number of lines you’d need to cross when walking from one to the other. It’s a little like the Manhattan distance on square grids.
The (a, b, c) system I drew above is a little redundant, though: for any (a, b) pair, there’s only two possible values for c. For example, if a = 0 and b = 0, then c must be either 0 or 1. This is pretty much the same thing as the R coordinate in the (x, y, R) system, but instead of always being 0 or 1, it’s one of two adjacent numbers depending on where in the grid you are. In the system I drew above, the c coordinate is always equal to either (–a – b) or
(–a – b + 1).
None of these three systems seems quite natural to me. The square-packed system uses just two coordinates, which seems right for a two-dimensional grid, where the others use three coordinates, with one of them being restricted to one of two values. The sheared-square system has a weird binary third coordinate whose geometric meaning is somewhat opaque. The (a, b, c) system’s coordinates are all clearly geometrically meaningful, but its third coordinate is oddly constrained, like the sheared-square system. It’s a little surprising to me that hex grids work out to be much simpler, and are amenable to storing just two coordinates.
