Finding shortest path on a hexagonal grid

Posted by Timothy Mayes on Game Development See other posts from Game Development or by Timothy Mayes
Published on 2012-12-02T02:31:13Z Indexed on 2012/12/02 5:24 UTC
Read the original article Hit count: 400

Filed under:

path-finding

|

hexagon

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, each turn, move 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 its 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 wierd coordinate system needed.

Thanks in advance Tim

© Game Development or respective owner

Related posts about path-finding

Do I need path finding to make AI avoid obstacles?

as seen on Game Development - Search for 'Game Development'
How do you know when a path-finding algorithm is really needed? There are contexts, where you just want to improve AI navigation to avoid an object, like a space -ship that won't crash on a planet or a car that already knows where to steer, but needs small corrections to avoid a road bump. As I've… >>> More
Why is Reinforcement Learning so rarely used in pathfinding?

as seen on Game Development - Search for 'Game Development'
The venerable shortest-path graph theoretic algorithm A* and subsequent improvements (e.g., Hierarchical Annotated A*) is clearly the technique of choice for pathfinding in game development. Instead, it just seems to me that RL is a more natural paradigm to move a character around a game space. And… >>> More
Pathfinding Algorithm For Pacman

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I wanted to implement the game Pacman. For the AI, I was thinking of using the A* algorithm, having seen it on numerous forums. However, I implemented the Breadth First Search for some simple pathfinding (going from point a to point b with certain obstacles in between) and found it gave the optimum… >>> More
Graphical sandbox for pathfinding

as seen on Stack Overflow - Search for 'Stack Overflow'
If you needed a clean and consistent sandbox for pathfinding what would you use? I want to experiment with different pathfinding algorithms by sending virtual units (robots) around obstacles on a geometric plane. But I don't need a feature overkill like a game engine or Flash might have, just an… >>> More
method for specialized pathfinding?

as seen on Stack Overflow - Search for 'Stack Overflow'
I am working on a roguelike in my (very little) free time. Each level will basically be a few rectangular rooms connected together by paths. I want the paths between rooms to be natural-looking and windy, however. For example, I would not consider the following natural-looking: B … >>> More

Related posts about hexagon

3D terrain map with Hexagon Grids

as seen on Game Development - Search for 'Game Development'
I'm working on a hobby project (I'm a web/backend developer by day) and I want to create a 3D Tile (terrain) engine. I'm using XNA, but I can use MonoGame, OpenGL, or straight DirectX, so the answer does not have to be XNA specific. I'm more looking for some high level advice on how to approach this… >>> More
3D terrain map with Hexagon Grids (XNA)

as seen on Game Development - Search for 'Game Development'
I'm working on a hobby project (I'm a web/backend developer by day) and I want to create a 3D Tile (terrain) engine. I'm using XNA, but I can use MonoGame, OpenGL, or straight DirectX, so the answer does not have to be XNA specific. I'm more looking for some high level advice on how to approach this… >>> More
How to draw/manage a hexagon grid?

as seen on Stack Overflow - Search for 'Stack Overflow'
I've read this article: generating/creating hexagon grid in C . But look like both the author and answerer have already abandoned it. v(hexagonSide - hexagonWidth * hexagonWidth): What's hexagonSide and hexagonWidth? Isn't it will < 0 (so square root can't be calculated). And, can I put a hexagon… >>> More
Collision detection on a 2D hexagonal grid

as seen on Game Development - Search for 'Game Development'
I'm making a casual grid-based 2D iPhone game using Cocos2D. The grid is a "staggered" hex-like grid consisting of uniformly sized and spaced discs. It looks something like this. I've stored the grid in a 2D array. Also I have a concept of "surrounding" grid cells. Namely the six grid cells surrounding… >>> More
Is it better to hard code data or find an algorithm?

as seen on Game Development - Search for 'Game Development'
I've been working on a boardgame that has a hex grid as the board (the upper right grid in the image below) Since the board will never change and the spaces on the board will always be linked to the same other spaces around it, should I just hard code every space with the values that I need? Or… >>> More