javascript - 将广度优先搜索移植到 Javascript

Question

我用 Python 为蛇创建了 AI。游戏运行良好。我最近开始学习 Javascript，并尝试编写与游戏等效的 Javascript。

游戏在 x*y 网格上进行(例如 30*20)。在 Python 中，我使用 (x, y) 元组表示游戏位置。在 JS 中，我使用我映射的整数:

function map(x, y) {
    return x + y * size.width;
}
function unmap(pos) {
    return {x: pos % size.width, y: Math.floor(pos/size.width)};
}

我的问题是搜索不起作用。当我尝试从中创建路径时，它会进入无限循环。搜索功能是:

function search(start, goal) {
    var frontier = new PriorityQueue({
        comparator: function(a, b) {
            return a.score - b.score;
        }
    });
    frontier.queue({value: start, score: 0});
    var cameFrom = {};
    cameFrom[start] = null;

    while (frontier.length !== 0) {
        var current = frontier.dequeue().value;
        if (current === goal) {
            break;
        }

        var nbs = neighbors(current);
        for(var i = 0; i < nbs.length; i++) {
            var next = nbs[i];
            if (Object.keys(cameFrom).indexOf(next) === -1) {
                var priority = heuristic(goal, next);
                frontier.queue({value: next, score: priority});
                cameFrom[next] = current;
            }
        }
    }
    return cameFrom;
}

我使用 this priority queue .

Python 中的搜索更面向对象，但我不想包含更多代码 - 问题已经很长了。但我会包括搜索:

def search(self, grid, start, goal):
    frontier = PriorityQueue()
    frontier.put(start, 0)
    came_from = {}
    came_from[start] = None

    while not frontier.empty():
        current = frontier.get()

        if current == goal:
            break

        for next in grid.neighbors(current):
            if next not in came_from:
                priority = self.heuristic(goal, next)
                frontier.put(next, priority)
                came_from[next] = current

    return came_from

如果还需要什么，请询问。我不擅长 JS。

Answer 1

问题出在这一行:

if (Object.keys(cameFrom).indexOf(next) === -1) {

我正在搜索整数，但键始终是字符串。您可以清楚地了解此示例中的行为:

var foo = {0: "fooBar", 1: "bar"};
console.log("keys", Object.keys(foo));
console.log("int", Object.keys(foo).indexOf(0)); // -1
console.log("string", Object.keys(foo).indexOf("0")); // 0

这更具可读性、更短且有效:

if (cameFrom[next] === undefined) {

感谢IVlad谁指出了错误的线路。