javascript - 实现A-Star算法。请帮忙？

Question

我正在尝试用 JavaScript 为我的寻路机器人实现 A* 算法。唯一的问题是我不明白找到所有相邻的正方形是什么意思。我正在使用曼哈顿距离公式，因为我不能让我的机器人斜着走。这是我的代码（现在）：

var open = new Array();
var closed = new Array();
start = [9,18]; //do not take this literally
goal = [1,0]; //again don't
open.push(start);
while (open.length != 0) {
    for(var x = 0; x < open.length; x++) {
        heuristicValue[x] = computeHeuristicV(maplayout, start[0], start[1], open[x][0], open[x][1], goal[0], goal[1]);
    }
    minimum = Math.min(100000,heuristicValue[0]);
    for(var x = 1; x < open.length; x++) {
        minimum = Math.min(minimum, heuristicValue[x]);
    }
    for(var x = 0; x < open.length; x++) {
        if (minimum == heuristicValue[x]) {
            current = [open[x][0], open[x][1]];
        }
    }
    closed.push(current);
    //INCOMPLETE
}

computeHeuristicV 函数计算上面代码中的启发式值。

Answer 1

“所有相邻方格”是指路径上每个可能的下一跳。

Answer 2

A* is a great algorithm to master and use. The two key elements are finding neighbors and the heuristic. A heuristic is used to estimate the distance between your current location, and the end. Also, the statement "find all adjacent squares" is referencing a neighbors function. For example, you might have the following:

var heuristic = function(state) {
    var endLocation = MyGame.getEndLocation();
    return Math.abs(state.x - endLocation.x) + Math.abs(state.y - endLocation.y)
}

var neighbors = function(state){
    var neighborStates = [];
    MyGame.setPlayer({
        x: state.x,
        y: state.y
    });
    neighborStates.push(MyGame.moveUp.getState());
    neighborStates.push(MyGame.moveRight.getState());
    neighborStates.push(MyGame.moveDown.getState());
    neighborStates.push(MyGame.moveLeft.getState());
    return neighborStates;
}

So, getting the "adjacent squares" is just asking you for the neighboring states or options. Personal plug: I just authored a simple a-star algorithm here: https://github.com/tssweeney/async-astar. Reading the description might help you to better understand the problem.