六边形网格中的 A* 寻路 [英] A* Pathfinding in a hexagonal grid
问题描述
谁能告诉我一个简单的例子，它实现了
我使用相同的技术来绘制网格并生成坐标，如下所示
还有我计算最短路径的方式:
if (!Array.prototype.remove) {Array.prototype.remove = 函数(从，到){var rest = this.slice((to || from) + 1 || this.length);this.length = from <0 ?this.length + from : from;返回 this.push.apply(this, rest);};}var astar = {初始化:函数(网格){for(var x = 0; x 尝试在互联网上四处寻找一些好的示例或文档，但找不到任何有用的东西.
问题在于您的 neighbors 方法:尽管六边形有六个邻居 (6)，但您只需将四 (4) 推到ret.下图突出显示了该问题.浅灰色的十六进制表示当前节点(即 neighbor).ret 中添加了绿色六边形，但未添加红色六边形.
要解决此问题，请将以下两 (2) 个案例添加到您的 neighbors 方法中:
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]);}关于你更新的 manhattan 方法:它是正确的.下图使用颜色来显示从当前中心六边形(在 [0:0] 处为红色)到每隔一个六边形的距离.例如，橙色六角砖距红色一 (1) 步.黄色是从红色开始的两 (2) 次移动.等等.
您可能会注意到这种模式:如果 x 和 y 坐标的符号相同，则距离等于最大坐标的大小.否则，距离是它们的绝对值之和.这正是您在 updated manhattan 方法中计算距离的方式.所以你在那里很好.
关于启发式搜索的一般性:这里有一种简单的方法来检查次优解决方案是启发式实现中的错误的结果，还是算法实现中的错误.只需对所有值使用启发式值零 (0)，即使用平凡启发式.如果在使用平凡启发式时，路径不是最优的，那么您就知道这不是启发式问题——这是一个算法问题.
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.
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.
这篇关于六边形网格中的 A* 寻路的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
