A* Грешка при внедряване на Pathfinding

Изглежда, че имам грешка в следната реализация на A* pathfinding, която внедрих въз основа на псевдокода, намерен тук.

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 вместо израз за връщане, който имате във вашия пример, публикуван тук. 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