Distances on a triangular grid

From Red Blob Games's Blog

As part of my article on grids, I'd like to provide basic algorithms for grids. I already know how to compute distances on square and hexagon grids, but I didn't know how to compute them on a triangle grid. I initially tried changing coordinate systems, inspired by Charles Fu's coordinate system. I normally use the coordinate system from my article on grids:

The first coordinate (which I will call u) is the position along the horizontal axis; the second (which I call v) is the position along the southwest/northeast diagonal. The Left/Right parity introduces some compliation; I let R be 1 and L be 0. This coordinate system is nice for storing maps in an array, but it's not as clean, because triangle grids have three axes but only two of them are expressed in the coordinates. For the horizontal axis I used 2u+R as the position; for the second axis I used 2v+R. I guessed that the position along the third axis would u-v. I drew some grids on paper, wrote down the u,v values, and then computed the three positional values. They behave properly for computing distances along the third axis, but the system falls apart when computing distances not on the three axes.

Frustrated, I decided to step back and approach this problem in a more principled manner. In Charles Fu's three-axis coordinate system, taking one step in the grid changes two of the coordinates and leaves the third alone. For a triangle grid, the dominating feature is the straight lines in three directions. I looked on the web for any articles describing distances on triangular grids, but didn't find any that satisfied me. This paper was promising but unfortunately gives an iterative algorithm and not a clean formula. However, it uses an interesting coordinate system, which is useful for computing distances. If you take one step in the grid, you will cross exactly one line. The distance between two locations will be the number of lines you have to cross. I wanted to use a coordinate system in which crossing a line changes a coordinate:

I want to map the u,v,R coordinates I normally use into the alternate coordinate system a,b,c, where exactly one of a,b,c changes when you cross a line. Here's where I decided to use algebra. In u,v,R space, the black triangle has coordinates 0,0,0; the triangle to the east of it has coordinates 0,0,1; to the west, -1,0,1; to the south, 0,-1,1. In a,b,c space, the black triangle is 0,0,0; the east triangle is 0,0,1; the west triangle is 0,-1,0; and the south triangle is -1,0,0.

I want a formula that computes a, and I expect it to be linear, so I write a = au*u + av*v + aR*R + constant. That's four unknowns, but we know the constant will be 0, so it's really three unknowns. To get three equations, I plug in the values for the east, west, and south triangles, then solve for the coefficients. Let's see what happens:

  For each s in (a, b, c), and each triangle i:
  si = su*u + sv*v + sR*R

  East triangle: u,v,R = 0,0,1
  s1 = su*0 + sv*0 + sR*1
  therefore: sR = s1
  
  West triangle: u,v,R = -1,0,1
  s2 = su*-1 + sv*0 + sR*1
  therefore: su = sR - s2
  
  South triangle: u,v,R = 0,-1,1
  s3 = su*0 + sv*-1 + sR*1
  therefore: sv = sR - s3

When s is axis a, we look at a for triangles 1 (east), 2 (west), and 3 (south), so a1 is 0, a2 is 0, and a3 is -1. The algebra tells us that aR = 0, au = 0, and av = 1. That means the formula is a = v. Pretty simple. Doing the same for b and c, I get b = u and c = u + v + R.

These results are simple enough that if I played with the grid enough, I would have come up with them. However the algebraic approach works for other constraints, not only the simple ones. I also used it to create a coordinate system with 2u+v+R, u+2v+R, v-u (this is 30 degrees rotated from the one above), which may be useful for other algorithms. Algebra and calculus also come in handy for defining movements (e.g., splines), growth rates, equilibria in interacting systems, and other types of interesting behaviors in games.

What is the distance between two locations in a triangular grid? Each step involves a line crossing, and we want to count steps, so we add up the line crossings along each axis (a, b, c): distance = abs(Δu) + abs(Δv) + abs(Δ(u+v+R)). This looks just like the Manhattan distance formula, but for triangles instead of squares.

Labels: grids , math , triangles