Un algorithme A * fonctionne bien, mais pas parfaitement. Qu'est-ce qui ne va pas?

Question

Ceci est mon réseau de nœuds:

alt text http://img168.imageshack.us/img168/7536/astartwrong.jpg

Je me déplace un objet autour de l'aide de l'algorithme A * pathfinding. Il fonctionne généralement bien, mais il agit parfois à tort: ​​

• Lors d'un déplacement de 3 à 1, il passe correctement par 2. En allant de 1 à 3 cependant, il passe par 4.
• Lors d'un déplacement entre 3 et 5, il passe par 4 dans l'une ou l'autre direction au lieu du chemin le plus court via 6

Qu'est-ce qui ne va pas? Voici mon code (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); 
    } 

Answer 1

trouvé le bug:

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

Le return LinkedSet.BREAK (qui agit comme une déclaration de rupture dans une boucle régulière) ne devrait pas être là. Cela fait que le premier nœud de la liste ouverte est toujours sélectionné, au lieu du premier.

Answer 2

Le problème que je vois ici est la ligne

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

Il peut être le cas où un adjNode peut être plus facile (plus court) pour atteindre le nœud actuel, bien qu'il ait été atteint auparavant à partir d'un autre nœud, ce qui signifie qu'il se trouve dans la liste ouverte.