A *六边形网格中的寻路-Java 学习之路

任何人都可以指向一个简单的例子，在 hexagonal 网格上实现A* path-finding algorithm（在JS中） . 我已经使它在正方形网格上工作，但是我在六边形网格上工作的所有尝试都失败了 .

这就是我的网格的样子：

enter image description here

我使用相同的技术绘制网格并生成坐标，如topic所示 .

这是网格坐标数据以及开始，结束坐标：

[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]

将曼哈顿距离计算更新为：

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;

我得到这个结果：

enter image description here

以及我计算最短路径的方式：

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 + "
G: " + neighbor.g + "
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;
    }
};

试图在互联网上寻找一些好的例子或文件，但实际上找不到任何有用的东西 .

4 回答

0
问题在于你的 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]);
    }
```
Regarding your updated manhattan method: 这是对的 . 下图使用颜色显示从当前中央十六进制（红色的[0：0]）到每个其他十六进制的距离 . 例如，橙色六角形瓷砖从红色移动一（1）个 . 黄色是红色的两（2）次移动 . 等等 .

您可能会注意到模式：如果x坐标和y坐标共享相同的符号，则距离等于最大坐标的大小 . 否则，距离是其绝对值的总和 . 这正是您在 updated manhattan 方法中计算距离的方式 . 所以你在那里很好 .

Regarding heuristic search in general: 这里'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'不是一个启发式问题 - 这是一个算法问题 .
回复于 2024-05-07T13:11:26+08:00

-1

正如这里有人提到的那样，我生成网格的方式，以及坐标都不正确 .

我通过Amit Patel的实现再次阅读guide并且我用他的方式生成网格以及包括坐标的坐标系统 . 转换 .

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;
            }
        }
    },

当我开始使用立方体坐标时，我在a *寻路算法中唯一需要改变的是距离计算：

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

现在路径查找正在处理“尖”和“平”布局：

enter image description here

回复于 2024-05-07T13:11:26+08:00

14

这是一个已经解决的问题，有很多文献可以支持它 . 我所知道的最好的资源是Red Blob Games：https://www.redblobgames.com/grids/hexagons/ .

简而言之，最可能的原因是您选择了错误的坐标系 . 使用实现A *算法的立方体坐标系非常简单 . 请参阅上面链接中的现场演示 .

如果你真的想使用其他系统，那么在需要时转换为 .

回复于 2024-05-07T13:11:26+08:00
2
“经典”路径寻找算法的工作原理如下：
- 用零初始化所有单元格 .
- 从起点开始，用数字1标记此点 .
- 循环启动，n = 1：
- 获取编号为n的所有单元格，并标记包含零的所有相邻单元格，编号为（n 1） . 如果这些相邻单元格中的任何一个是出口，则离开循环 . 如果没有找到数字为零的相邻单元格，则没有退出路径 .
- 递增n和goto循环
如果退出，则：
- 退出时启动循环：
- 搜索编号为n的相邻单元格并记住此单元格 .
- 减少n和goto循环
所有记住的单元格构建结果路径（以相反的顺序） .

Cheerz

亨尼斯
回复于 2024-05-07T13:11:26+08:00

A *六边形网格中的寻路

4 回答

相关问题