Finding shortest path on a hexagonal grid

Question

I'm writing a turn based game that has some simulation elements. One task I'm hung up on currently is with path finding. What I want to do is move each turn an AI adventurer one tile closer to his target using his current x,y and his target x,y.

In trying to figure this out myself I can determine 4 directions no problem by using

dx = currentX - targetY
dy = currentY - targetY

but I'm not sure how to determine which of the 6 directions is actually the "best" or "shortest" route.

For example, the way it's setup currently, I use East, West, NE, NW, SE, SW but to get to the NE tile I move East then NW instead of just moving NW.

I hope this wasn't all rambling. Even just a link or two to get me started would be nice. Most of the info I've found is on drawing the grids and groking the weird coordinate system needed.

Answer 1

A few answers!

The coordinate system I've seen most often for hex-based traversal is one where the player can move in every normal NSEW direction, as well as NW and SE. Then you just render each row half-a-square offset. As an example, the location (2,7) is considered adjacent to (1,7), (3,7), (2,6), (2,8), and the weird ones: (1,6) and (3,8). Meanwhile, if we assume (2,7) is rendered at the center of the screen, (2,6) will be rendered up-and-to-the-right, (2,8) will be rendered down-and-to-the-left, (1,7) and (3,7) will bracket it to the left and right respectively, and (1,6) and (3,8) will place themselves top-left and bottom-right respectively.

A diagram of what I mean:

If you're doing it this way, finding the shortest direct path isn't difficult - travel the maximum NW/SE distance that you can without overshooting your target along a cardinal axis, then travel directly along that axis to the target.

But of course that will happily run you straight through mountains or other impassable terrain. To answer a question you haven't yet asked: The A* Search Algorithm is a common and reasonably good approach to pathfinding. It will handle not only weird non-grid layouts, but will happily deal with obstacles and even obstructed/slow ground.

Answer 2

I have just posted a library of hex-grid utilities.

The library includes path-finding (using A-* a la Eric Lippert) and includes utilities for automated conversion between jagged (termed User) coordinates and non-jagged (termed Canonical) coordinates. The path-finding algorithm allows the step cost for each node to vary both with the entry hex and te traversed hex-side (though the example provided is simpler). Also, elevated field-of-view using shadow-casting is provided, [edit: words removed].

Here is a code sample that converts readily between three hex-grid coordinate systems:

static readonly IntMatrix2D MatrixUserToCanon = new IntMatrix2D(2,1, 0,2, 0,0, 2);
IntVector2D VectorCanon {
  get { return !isCanonNull ? vectorCanon : VectorUser * MatrixUserToCanon / 2; }
  set { vectorCanon = value;  isUserNull = isCustomNull = true; }
} IntVector2D vectorCanon;
bool isCanonNull;

static readonly IntMatrix2D MatrixCanonToUser  = new IntMatrix2D(2,-1, 0,2, 0,1, 2);    
IntVector2D VectorUser {
  get { return !isUserNull  ? vectorUser 
             : !isCanonNull ? VectorCanon  * MatrixCanonToUser / 2
                            : VectorCustom * MatrixCustomToUser / 2; }
  set { vectorUser  = value;  isCustomNull = isCanonNull = true; }
} IntVector2D vectorUser;
bool isUserNull;

static IntMatrix2D MatrixCustomToUser = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
static IntMatrix2D MatrixUserToCustom = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
IntVector2D VectorCustom {
  get { return !isCustomNull ? vectorCustom : VectorUser * MatrixUserToCustom / 2; }
  set { vectorCustom  = value;  isCanonNull = isUserNull = true; }
} IntVector2D vectorCustom;
bool isCustomNull;

IntMatrix2D and IntVector2D are homogeneous integer implementations of affine2D Graphics Vector and Matrix. The final divide by 2 on the vector applications is to re-normalize the vectors; this could be buried in the IntMatrix2D implementation, but then the reason for the 7th argument to the IntMatrix2D constructors is less obvious. Note the combined caching and lazy-evaluation of non-current formulations.

These matrices are for the case:

• Hex grain vertical;
• Origin in upper-left for Canonical & User coordinates, lower-left for Custom coordnates;
• Y-axis vertically down;
• Rectangular X-axis horizontally across; and
• Canonical X-axis to the North-East (ie up and to the right, at 120 degrees CCW from Y-axis).

The code library mentioned above provides a similarly elegant mechanism for hex-picking (i.e. identifying the hex selected with a mouse click).

In canonical coordinates, the 6 cardinal direction-vectors are (1,0), (0,1), (1,1) and their inverses for all hexagons, without the asymmetry of jagged coordinates.

Answer 3

This is a solved problem, with much literature to back it up. The best resource I know is on Red Blob Games: https://www.redblobgames.com/grids/hexagons/.

In brief, the most likely reason is that you started with the wrong coordinate system. Using a Cube coordinate system implementing the A* algorithm is quite simple. See live demo on the above link.

If you really want to use some other system, then convert to and from when needed.