A* Pathfinding in a hexagonal grid

问题:

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:

if (!Array.prototype.remove) {
    Array.prototype.remove = function(from, to) {
        var rest = this.slice((to || from) + 1 || this.length);
        this.length = from < 0 ? this.length + from : from;
        return this.push.apply(this, rest);
    };
}

var astar = {
    init: function(grid) {
        for(var x = 0; x < grid.length; x++) {
            for(var y = 0; y < grid[x].length; y++) {
                grid[x][y].f = 0;
                grid[x][y].g = 0;
                grid[x][y].h = 0;
				//grid[x][y].content = false;
                grid[x][y].visited = false;
                grid[x][y].closed = false;
                grid[x][y].debug = "";
                grid[x][y].parent = null;
				console.log([grid[x][y].coords[0],grid[x][y].coords[1]])
            }
        }
    },
    search: function(grid, start, end, heuristic) {
        this.init(grid);
        heuristic = heuristic || this.manhattan;

        var openList = [];
		
		//// find the start and end points in the grid ////
		start = grid[start.pos[0]][start.pos[1]];
		end =  grid[end.pos[0]][end.pos[1]];
		
		console.log( start, end )
		
        openList.push(start);
		
        while(openList.length > 0) {
			
            // Grab the lowest f(x) to process next
            var lowInd = 0;
            for(var i=0; i<openList.length; i++) {
                if(openList[i].f < openList[lowInd].f) { lowInd = i; }
            }
            var currentNode = openList[lowInd];

            // End case -- result has been found, return the traced path
            if( currentNode == end ) {
                var curr = currentNode;
                var ret = [];
                while(curr.parent) {
                    ret.push(curr);
                    curr = curr.parent;
                }
                return ret.reverse();
            }

            // Normal case -- move currentNode from open to closed, process each of its neighbors
            openList.remove( lowInd );
            currentNode.closed = true;

            var neighbors = this.neighbors(grid, currentNode);
            for(var i=0; i<neighbors.length;i++) {
                var neighbor = neighbors[i];

                if( neighbor.closed || neighbor.content == 2 ) { // not a valid node to process, skip to next neighbor
                    continue;
                }

                // g score is the shortest distance from start to current node, we need to check if
                //   the path we have arrived at this neighbor is the shortest one we have seen yet
                var gScore = currentNode.g + 1; // 1 is the distance from a node to it's neighbor
                var gScoreIsBest = false;

                if(!neighbor.visited) {
                    // This the the first time we have arrived at this node, it must be the best
                    // Also, we need to take the h (heuristic) score since we haven't done so yet
                    gScoreIsBest = true;
                    neighbor.h = heuristic(neighbor.coords, end.coords);
                    neighbor.visited = true;
                    openList.push(neighbor);
                }
                else if(gScore < neighbor.g) {
                    // We have already seen the node, but last time it had a worse g (distance from start)
                    gScoreIsBest = true;
                }

                if(gScoreIsBest) {
                    // Found an optimal (so far) path to this node.  Store info on how we got here and just how good it really is. ////
                    neighbor.parent = currentNode;
                    neighbor.g = gScore;
                    neighbor.f = neighbor.g + neighbor.h;
                    neighbor.debug = "F: " + neighbor.f + "<br />G: " + neighbor.g + "<br />H: " + neighbor.h;
                }
            }
        }

        // No result was found -- empty array signifies failure to find path
        return [];
    },
    manhattan: function(pos0, pos1) { //// heuristics : use manhattan distances  ////
        var dx = pos1[0] - pos0[0];
        var dy = pos1[1] - pos0[1];
		
        return  Math.abs (dx + dy);
    },
    neighbors: function(grid, node) {
        var ret = [];
        var x = node.coords[0];
        var y = node.coords[1];
		
        if(grid[x-1] && grid[x-1][y] ) {
            ret.push(grid[x-1][y]);
        }
        if( grid[x+1] && grid[x+1][y] ) {
            ret.push(grid[x+1][y]);
        }
        if( grid[x][y-1] && grid[x][y-1] ) {
            ret.push(grid[x][y-1]);
        }
        if( grid[x][y+1] && grid[x][y+1] ) {
            ret.push(grid[x][y+1]);
        }
        return ret;
    }
};

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

回答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.

回答2:

As already mentioned by someone here, the way I was generating the grid, and also the coordinates were incorrect.

I have another read through Amit Patel's implementation guide and I used his way to generate the grid and also the coordinates system including the coord. conversions.

generate: function(){
        var n_hex = null; 
        var row = 0, col = 0;
        for (var q = -this.grid_r; q <= this.grid_r; q++) {
            var r1 = Math.max(-this.grid_r, -q - this.grid_r);
            var r2 = Math.min(this.grid_r, -q + this.grid_r);
            col = q + this.grid_r;
            this.hexes[ col ] = [];
            for (var r = r1; r <= r2; r++) {
                row = r - r1;
                n_hex = new Hex( [q, r], [col, row], this.layout );
                this.hexes[ col ][ row ] = n_hex;
            }
        }
    },

As I started using the cube coordinates , the only thing I had to change in the a* pathfinding algorithm was the distance calculation:

return Math.max(Math.abs(a.x - b.x), Math.abs(a.y - b.y), Math.abs(a.z - b.z))

now the path-finding is working on both "pointy" and "flat" layouts :

回答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 chose the wrong coordinate system. Using a Cube coordinate system implementing the A* algorithm is quite simple. See the live demo on the above link.

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

回答4:

The "classic" path finding algorithm works as follows:

• Initialize all cells with zero.
• Start at the starting point and mark this point with the number 1.
• Loop start with n = 1:
• Take all cells with number n and mark all adjacent cells, which contains a zero, with number (n+1). If any of these adjacent cells is the exit, leave loop. If no adjacent cell with number zero found, there's no path to exit.
• Increment n and goto loop

If exit found then:

• Start loop at exit:
• Search adjacent cell with number n and remember this cell.
• Decrement n and goto loop

All remembered cells builds up the result path (in reverse order).

Cheerz

Hennes