A * Ошибка реализации Pathfinding

Question

Кажется, у меня есть ошибка в следующей реализации поиска пути A *, которую я реализовал на основе найденного psuedocode здесь .

function NodeList() {
    this.nodes = [];

    this.add = function(givenNode) {
        for(var i = 0; i<this.nodes.length; i++) {
            if(this.nodes[i].f <= givenNode.f) {
                this.nodes.splice(i, 0, givenNode);
                return;
            }
        }

        this.nodes.push(givenNode);
    }

    this.pop = function() {
        return this.nodes.splice(this.nodes.length-1, 1)[0];
    }

    this.getNode = function(givenNode) {
        for (var i = 0; i < this.nodes.length; i++) {
            if (this.nodes[i].pos.x == givenNode.pos.x && this.nodes[i].pos.y == givenNode.pos.y) {
                return this.nodes.splice(i, 1)[0];
            }
        }

        return -1;
    }

    this.hasNode = function(givenNode) {
        for (var i = 0; i < this.nodes.length; i++) {
            if (this.nodes[i].pos.x == givenNode.pos.x && this.nodes[i].pos.y == givenNode.pos.y) {
                return true;
            }
        }

        return false;
    }

    this.length = function() {
        return this.nodes.length;
    }
}

function PathNode(pos, f, g, h) {
    this.pos = pos;
    this.f = f;
    this.g = g;
    this.h = h;
}

function FindPath(start, goal) {
    var x_array = [0, -1, -1, -1, 0, 1, 1, 1];
    var y_array = [1, 1, 0, -1, -1, -1, 0, 1];

    var open_list = new NodeList();
    open_list.add(new PathNode(start, start.Manhattan(goal) * 10, 0, start.Manhattan(goal) * 10));
    var closed_list = new NodeList();

    while(open_list.length() > 0) {     
        var currentNode = open_list.pop();

        if(currentNode.pos.x == goal.x && currentNode.pos.y == goal.y) {
            var path = [];
            var curNode = currentNode;

            while(true) {
                path.push(curNode);
                curNode = curNode.parent;
                if(curNode == undefined) break;
            }

            return(path);
        }

        closed_list.add(currentNode);

        for(var i=0; i<8; i++) {
            var neighbor = new PathNode(new Vector2(currentNode.pos.x + x_array[i], currentNode.pos.y + y_array[i]), 0, 0, 0);

            if(map.tiles[neighbor.pos.x][neighbor.pos.y].blocked == true) {
            canContinue = false;
        }

        for(var j=0; j<objects.length; j++) {
            if(objects[j].blocks == true && objects[j].position.x == neighbor.pos.x && objects[j].position.y == neighbor.pos.y) canContinue = false;
        }

        if(closed_list.hasNode(neighbor)) continue;
        if(!canContinue) continue;

            if(open_list.hasNode(neighbor)) { // if open_list contains neighbor, do this:
                neighbor = open_list.getNode(neighbor);
                neighbor.parent == currentNode;
                neighbor.g = currentNode.g + 10;
                neighbor.h = neighbor.pos.Manhattan(goal) * 10;
                neighbor.f = neighbor.g + neighbor.h;
                open_list.add(neighbor);
            } else { // otherwise it's not on the open list, do this:
                if(neighbor.g < currentNode.g) {
                    neighbor.parent = currentNode;
                    neighbor.g = currentNode.g + 10;
                    neighbor.f = neighbor.g + neighbor.h;
                }

                open_list.add(neighbor);
            }
        }   
    }
}

Я, должно быть, делаю что-то не так, потому что код закручивается в бесконечный цикл и вылетает из браузера при каждом запуске. Может ли кто-нибудь указать мои ошибки?

Answer 1

Я дополню этот ответ точками по мере их нахождения.

• Прежде всего, я не вижу способа избежать внешнего цикла в вашей среде.У вас есть console.log вместо оператора return, который вы в своем примере разместили здесь.console.log(path); вместо return path;

• Вы не проверяете закрытый список на наличие узлов, которые были закрыты.Поэтому, как только вы оценили состояние узла в открытом списке, он помещается в закрытый список, но вы ничего не делаете с этим списком.Ничто не мешает вам снова добавить узел из закрытого списка в открытый список.Вы только проверяете открытый список, чтобы предотвратить добавление одного и того же узла более одного раза.(Хотя ваш пример кода, размещенный здесь, показывает, что вы есть)

Комбинация этих вещей выглядит так, как будто она будет производить один и тот же путь бесконечно много раз.обратите внимание, ваш пример кода имеет неправильный отступ, поэтому похоже, что большая часть этого кода не находится в цикле проверки 8 соседей.

Answer 2

Вы, похоже, забыли исключить из поиска невидимые и закрытые узлы.