A *六边形网格中的寻路

问题描述 投票：18回答：4

任何人都可以指向一个简单的例子，在六边形网格上实现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 + "<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;
    }
};

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

javascript html5 canvas path-finding a-star
4个回答
15
投票

问题在于你的neighbors方法：虽然六边形有六个邻居（6），但你只将四（4）推到ret上。下图突出显示了该问题。浅灰色十六进制代表当前节点（即neighbor）。绿色六边形被添加到ret，但红色六边形不是。

IncludedOrNotIncluded

要解决此问题，请将以下两（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）次移动。等等。

Distance hex map

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

关于一般的启发式搜索：这是一种简单的方法来检查次优解是否是启发式实现中的错误的结果，或者是因为算法实现中的错误。只需对所有值使用启发式值零（0），即使用平凡启发式算法。如果在使用琐碎的启发式算法时，路径不是最优的，那么你知道它不是一个启发式问题 - 它是一个算法问题。

2
投票

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

我通过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

0
投票

“经典”路径寻找算法的工作原理如下：

  • 用零初始化所有单元格。
  • 从起点开始，用数字1标记此点。
  • 循环启动，n = 1：
  • 取所有数字为n的单元格，并标记所有相邻单元格，其中包含零，数字为（n + 1）。如果这些相邻单元格中的任何一个是出口，则离开循环。如果没有找到数字为零的相邻单元格，则没有退出路径。
  • 增加n和goto循环

如果退出，则：

  • 退出时启动循环：
  • 搜索数字为n的相邻单元格并记住此单元格。
  • 减少n和goto循环

所有记住的单元格构建结果路径（以相反的顺序）。

Cheerz

她的

0
投票

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

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

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

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.