A* Ошибка реализации поиска пути

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

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

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


person Elliot Bonneville    schedule 01.04.2012    source источник
comment
Я не думаю, что вы могли бы опубликовать образец ввода?   -  person Matt Esch    schedule 02.04.2012
comment
Конечно, это должно выглядеть так: FindPath(new Vector2(10, 10), new Vector2(15, 15));, где Vector2 — класс позиции.   -  person Elliot Bonneville    schedule 02.04.2012
comment
Я имею в виду, не могли бы вы создать полный тестовый пример, который ломается? Я уверен, что мог бы настроить один, но он у вас уже должен быть. Избавляет меня от хлопот :) - Было бы проще, если бы мы могли видеть, как он пытается работать   -  person Matt Esch    schedule 02.04.2012
comment
Конечно, зайдите сюда: www.saege.bonfx.com/0.1.3. Откройте консоль и нажмите Shift-T, чтобы проверить поиск пути, который вызывает сбой. Я включил всю свою среду, чтобы вы могли просмотреть исходный код, если хотите увидеть остальные сценарии.   -  person Elliot Bonneville    schedule 02.04.2012
comment
Примечание: потрясающая игра на данный момент   -  person aaaidan    schedule 02.04.2012
comment
Как мне быть в курсе?   -  person aaaidan    schedule 03.04.2012
comment
@aaaidan: Вскоре у меня должен быть сайт для него - как видите, он все еще находится на начальной стадии. Тем временем я создал страницу на Roguelike Wiki (эта игра является roguelike), которую вы можете найти здесь: www.roguebasin.roguelikedevelopment.org/index.php/Saege. К сожалению, эта страница также немного устарела, так как я добился большого прогресса с тех пор, как последний раз обновлял ее неделю или около того назад. Тем не менее, я обновлю его в какой-то момент в ближайшем будущем. Цените интерес!   -  person Elliot Bonneville    schedule 03.04.2012


Ответы (2)


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

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

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

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

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

person Matt Esch    schedule 01.04.2012
comment
Это потому, что я зацикливаюсь только тогда, когда open_list.length() больше 0. - person Elliot Bonneville; 02.04.2012
comment
Да, но вы хотите выйти, как только найдете путь. Вот почему алгоритм A* использует эвристику; добиться быстрой сходимости. - person Matt Esch; 02.04.2012
comment
Тем не менее алгоритм должен работать. Но я изменю это. - person Elliot Bonneville; 02.04.2012
comment
Тест будет работать с оператором return в нем. Я на самом деле получаю выход из этого. Если вы забываете проверить закрытый список, вы можете следовать круговым путям, что, очевидно, и происходит здесь. - person Matt Esch; 02.04.2012

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

person Neil    schedule 01.04.2012
comment
Я не забыл, я просто удалил этот код, потому что он ссылался на некоторые конструкции, которые я не хотел включать сюда, прежде всего потому, что они были довольно длинными. Извините, что не разъяснил. - person Elliot Bonneville; 02.04.2012
comment
@ElliotBonneville Ну, это довольно важная часть кода, особенно закрытые узлы, которые необходимы, чтобы избежать бесконечной рекурсии. - person Neil; 02.04.2012