# Finding shortest path on a hexagonal grid

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.

• A* gives you shortest path regardless of the shape of your graph (grid, hex, freeform..) – Jari Komppa Dec 3 '12 at 7:31

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.

• Thanks for the link to the A* search algorithm. The only way i can imagine being able to traverse nsew and nw / se is a tilted hex. Which looks weird in my head. Can you link me to an example of that? – Timothy Mayes Dec 2 '12 at 6:32
• I'm saying that your rendered image doesn't have to bear much resemblance to the internal structure. I'm suggesting that internally you use N S E W and NW/SE, but you display it to the user as if it were a grid. Attaching an explanatory diagram to the original reply :) – ZorbaTHut Dec 3 '12 at 7:27
• Interesting representation for a hex grid. I usually make a jagged pattern, so the adjacency is different for odd and even rows. This introduces an additional minimal complexity in the path search, but uses a bidimensional array more efficiently (supposing the entire play area is a rectangle. – Panda Pajama Dec 3 '12 at 8:46
• @PandaPajama: jagged does work nicer for efficiently storing rectangular maps; you can make the non-jagged coordinates work nicely with this trick – amitp Dec 3 '12 at 16:51
• @PandaPajama, there's another interesting trick you can use - you can use the non-jagged representation for coordinates, then abstract the backing for your data storage behind something that uses the "jagged" method. I've found the coordinate system of non-jagged is far easier to deal with but of course once it's abstracted away, the backend can do whatever it likes to make things efficient :) – ZorbaTHut Dec 3 '12 at 17:12

I have just postd a library of hex-grid utilites on CodePlex.com here: https://hexgridutilities.codeplex.com/ The library includes path-finding (using A-* a la Eric Lippert) and includes utilites for automated conversion between jagged (termed User) cordinates and non-jagged (termed Canonical) coordinates. The path-findingn 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 [edit: 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 (ie 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 assymmetry of jagged coordintes.

• Wow! Net one down-vote for posting a library of working code, with examples and documentation, that answers the question/problem posed by the OP. – Pieter Geerkens Feb 23 '13 at 1:11
• While I wasn't the downvoter (and etiquette generally suggests leaving a comment explaining a downvote), I suspect the downvote was because (a) the post comes off sounding of advertising, and (b) putting the bulk of an answer on the other side of a link is generally frowned upon because links have a tendency to rot and SE sites try to be self-contained. The information that's provided here is interesting, but it doesn't answer the user's question, and the only information that could answer the question is on the other side of the link. – Steven Stadnicki Feb 23 '13 at 2:25
• Good points; thank you. I have expanded the post with excerpts that address the question of how to efficiently maintain multiple hex grid coordinates. The posted code library is freeware – Pieter Geerkens Feb 23 '13 at 2:29
• Oops! The divide-by-2 only works fo positive integers. (Thank you again, K&R.) It should be replaced by a call to the Normalize() method in IntVector2D: – Pieter Geerkens Feb 26 '13 at 21:14
• public IntVector2D Normalize() { if (Z==1) return this; else { var x = (X >= 0) ? X : X - Z; var y = (Y >= 0) ? Y : Y - Z; return new IntVector2D(x/Z, y/Z); } } – Pieter Geerkens Feb 26 '13 at 21:16

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.