Моя реализация поиска пути A * не дает ожидаемых результатов - PullRequest
Новая
       13

Моя реализация поиска пути A * не дает ожидаемых результатов

2 голосов
/ 10 августа 2011

Мой AS3 A * реализация поиска пути иногда не возвращает наиболее эффективный маршрут, скорее всего так: 

[E][X][ ][ ][ ]
[.][X][.][.][ ]
[ ][.][ ][i][S]

(где. - пройденный узел, а X - стены. S = начало, E = конец, i = мой воображаемый маркер)

Проблема: у меня должен быть общий балл (расстояние до конца) 30 + (расстояние от начала) 10 = 40, в то время как у плитки выше у меня должен быть общий балл (расстояние до конца) 40+ (расстояние от начало) 14 = 54. Почему выбирается 54 вместо 40, я не знаю - я использую это, чтобы найти узел с наименьшим общим счетом в открытом списке: 

        var lowestTScore:int = 10000;
        var pointerTo:PathNode;
        for each (var Cur:PathNode in openList) {
            //loops through each node in openlist and finds the one with lowest total score.
            if (Cur.distS + Cur.distE < lowestTScore) {
                lowestTScore = Cur.distS + Cur.distE;
                pointerTo = Cur;
            }
        }

(с которыми я не вижу проблем).

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

theNode.distE = (Math.abs(theNode.xpos - endPts[0]) + Math.abs(theNode.ypos - endPts[1])) * 10;

(что, опять же, я не вижу никаких проблем с.)

Я действительно в замешательстве.

Main.as: http://pastebin.com/ZKQJwY4S PathSearcher: as: http://pastebin.com/KnmWGbQw

(я понимаю, что лучше отправлять непосредственно код проблемы, но я не знаю, где находится код проблемы :( Извините)

Спасибо за любую помощь!

1 Ответ

1 голос
/ 11 августа 2011

Нашел проблему! Я не добавил 

    theNode.distS = theNode.parentNode.distS + cost;

при смене родителей узла. Я изменил только parentNode, но не оценку distS.

...