A* Pathfinding in a hexagonal grid

Question

Can anyone point me to a simple example that implements A* path-finding algorithm on a hexagonal grid (in JS). I have made it working on a square grid, however all my attempts to make it work on a hexagonal grid have failed.

This is how my grid looks like:

I'm using the same technique to both draw the grid and generate coordinates as seen in this topic.

Here's the grid coords data along with the start, end coords:

        [0, 0] , [0, 1],  [0, 2],
    [1, 0],  [1, 1],  [1, 2],  [1, 3],
 [2, 0],  [2, 1],  [2, 2],  [2, 3],  [2, 4],
    [3, 0],  [3, 1], [3, 2],  [3, 3], 
        [4, 0], [4, 1],  [4, 2]


start_point: [0,2]
end_point: [4.0]

After updating the manhattan distance calculation to:

var dx = pos1[0] - pos0[0];
    var dy = pos1[1] - pos0[1];

    var dist;
    if ( Math.sign(dx) == Math.sign(dy) ){
        dist = Math.abs (dx + dy);
    }else{
        dist = Math.max(Math.abs(dx), Math.abs(dy))
    }

return dist;

I get this result:

and also the way I'm calculating the shortest path:

Tried looking around for some good examples or documents on the internet but couldn't really find anything of use.

Answer 1

The problem resides in your neighbors method: although a hexagon has six neighbors (6), you only push four (4) onto ret. The following figure highlights the issue. The light grey hex represents the current node (i.e. neighbor). The green hexagons are added to ret, but the red hexagons are not.

To fix this, add the following two (2) cases to your neighbors method:

    if( grid[x+1][y-1] && grid[x+1][y-1] ) {
        ret.push(grid[x][y-1]);
    }
    if( grid[x-1][y+1] && grid[x-1][y+1] ) {
        ret.push(grid[x][y+1]);
    }

Regarding your updated manhattan method: it is correct. The following figure uses colors to show the distance from the current central hex (at [0:0] in red) to every other hex. For example, the orange hex tiles are one (1) move from the red. The yellow are two (2) moves from the red. And so on.

You may notice the pattern: If the x- and y-coordinates share the same sign, the distance is equal to the magnitude of the largest coordinate. Otherwise, the distance is the sum of their absolute values. This is exactly the way you've calculated distance in your updated manhattan method. So you're good there.

Regarding heuristic search in general: Here's a simple way to check if a suboptimal solution is the result of a bug in the heuristic implementation or else because of a bug in the algorithm implementation. Just use the heuristic value zero (0) for all values, i.e. use the trivial heuristic. If, while using the trivial heuristic, the path is not optimal, then you know it's not a heuristic problem---it's an algorithm problem.