Алгоритм * работает нормально, но не идеально. В чем дело? - PullRequest
Новая
       20

Алгоритм * работает нормально, но не идеально. В чем дело?

2 голосов
/ 19 мая 2010

Это моя сетка узлов:

альтернативный текст http://img168.imageshack.us/img168/7536/astartwrong.jpg

Я перемещаю объект вокруг него, используя алгоритм поиска пути A *. Обычно он работает нормально, но иногда действует неправильно:

  • При переходе с 3 на 1 он корректно проходит через 2. При переходе с 1 на 3 он проходит через 4.
  • При перемещении между 3 и 5 он проходит через 4 в любом направлении, а не более коротким путем через 6

Что может быть не так? Вот мой код (AS3): 

    public static function getPath(from:Point, to:Point, grid:NodeGrid):PointLine {

        // get target node
        var target:NodeGridNode = grid.getClosestNodeObj(to.x, to.y);

        var backtrace:Map = new Map();
        var openList:LinkedSet = new LinkedSet();
        var closedList:LinkedSet = new LinkedSet();

        // begin with first node
        openList.add(grid.getClosestNodeObj(from.x, from.y));

        // start A*
        var curNode:NodeGridNode;
        while (openList.size != 0) {

            // pick a new current node
            if (openList.size == 1) {
                curNode = NodeGridNode(openList.first);
            }
            else {
                // find cheapest node in open list
                var minScore:Number = Number.MAX_VALUE;
                var minNext:NodeGridNode;
                openList.iterate(function(next:NodeGridNode, i:int):int {
                    var score:Number = curNode.distanceTo(next) + next.distanceTo(target);
                    if (score < minScore) {
                        minScore = score;
                        minNext = next;
                        return LinkedSet.BREAK;
                    }
                    return 0;
                });
                curNode = minNext;
            }

            // have not reached
            if (curNode == target) break;
            else {
                // move to closed
                openList.remove(curNode);
                closedList.add(curNode);

                // put connected nodes on open list
                for each (var adjNode:NodeGridNode in curNode.connects) {
                    if (!openList.contains(adjNode) && !closedList.contains(adjNode)) {
                        openList.add(adjNode);
                        backtrace.put(adjNode, curNode);
                    }
                }
            }
        }

        // make path
        var pathPoints:Vector.<Point> = new Vector.<Point>();
        pathPoints.push(to);
        while(curNode != null) {
            pathPoints.unshift(curNode.location);
            curNode = backtrace.read(curNode);
        }
        pathPoints.unshift(from);
        return new PointLine(pathPoints);

    }

NodeGridNode :: distanceTo () 

    public function distanceTo(o:NodeGridNode):Number {
        var dx:Number = location.x - o.location.x;
        var dy:Number = location.y - o.location.y;
        return Math.sqrt(dx*dx + dy*dy);
    }

Ответы [ 2 ]

1 голос
/ 19 мая 2010

Проблема, которую я вижу здесь, это строка 

if (!openList.contains(adjNode) && !closedList.contains(adjNode))

Может случиться так, что adjNode может быть легче (короче) достичь через текущий узел, хотя он был достигнут с другого узла ранее, что означает, что он находится в openList.

0 голосов
/ 19 мая 2010

Нашли ошибку: 

                openList.iterate(function(next:NodeGridNode, i:int):int {
                    var score:Number = curNode.distanceTo(next) + next.distanceTo(target);
                    if (score < minScore) {
                        minScore = score;
                        minNext = next;
                        return LinkedSet.BREAK;
                    }
                    return 0;
                });

return LinkedSet.BREAK (который действует как оператор break в обычном цикле) не должно быть там. Это заставляет всегда выбирать первый узел в открытом списке вместо самого дешевого.

...