A* (A-star) - Implementierung in AS3

Bin ich setzen gemeinsam ein Projekt für eine Klasse, die verlangt von mir, legte AI in einem top-down-Taktik-und Strategiespiel in Flash AS3.

Habe ich beschlossen, dass ich mit einem Knoten Weg finden Ansatz, denn das Spiel basiert auf einer kreisförmigen Bewegung, Regelung. Wenn ein Spieler eine Einheit, die er im wesentlichen zeichnet eine Reihe von Linien, die verbinden, dass ein Spieler Gerät Folgen.

Ich versuche, um gemeinsam eine ähnliche operation für die KI-Einheiten, die im Spiel durch die Schaffung einer Liste der Knoten zu Durchlaufen, um zu einem Ziel-Knoten. Daher meine Verwendung des Astar (der resultierende Pfad kann verwendet werden, um erstellen dieser Zeile).

Hier ist mein Algorithmus

function findShortestPath (startN:node, goalN:node)
{
 var openSet:Array = new Array();
 var closedSet:Array = new Array();
 var pathFound:Boolean = false;


 startN.g_score = 0;
 startN.h_score = distFunction(startN,goalN);
 startN.f_score = startN.h_score;
 startN.fromNode = null;
 openSet.push (startN);
 var i:int = 0


 for(i= 0; i< nodeArray.length; i++)
 {
  for(var j:int =0; j<nodeArray[0].length; j++)
  {
   if(!nodeArray[i][j].isPathable)
   {
    closedSet.push(nodeArray[i][j]);
   }
  }
 }

 while (openSet.length != 0)
 {
  var cNode:node = openSet.shift();
  if (cNode == goalN)
  {
   resolvePath (cNode);
   return true;
  }
  closedSet.push (cNode);

  for (i= 0; i < cNode.dirArray.length; i++)
  {
   var neighborNode:node = cNode.nodeArray[cNode.dirArray[i]];

   if (!(closedSet.indexOf(neighborNode) == -1))
   {
    continue;
   }

   neighborNode.fromNode = cNode;

   var tenativeg_score:Number = cNode.gscore + distFunction(neighborNode.fromNode,neighborNode);

   if (openSet.indexOf(neighborNode) == -1)
   {


    neighborNode.g_score = neighborNode.fromNode.g_score + distFunction(neighborNode,cNode);

    if (cNode.dirArray[i] >= 4)
    {
     neighborNode.g_score -= 4;
    }
    neighborNode.h_score=distFunction(neighborNode,goalN);
    neighborNode.f_score=neighborNode.g_score+neighborNode.h_score;

    insertIntoPQ (neighborNode, openSet);
     //trace(" F Score of neighbor: " + neighborNode.f_score + " H score of Neighbor: " + neighborNode.h_score + "  G_score or neighbor: " +neighborNode.g_score);
   }

   else if (tenativeg_score <= neighborNode.g_score)
   {
    neighborNode.fromNode=cNode;
    neighborNode.g_score=cNode.g_score+distFunction(neighborNode,cNode);
    if (cNode.dirArray[i]>=4)
    {
     neighborNode.g_score-=4;
    }
    neighborNode.f_score=neighborNode.g_score+neighborNode.h_score;
    openSet.splice (openSet.indexOf(neighborNode),1);
    //trace(" F Score of neighbor: " + neighborNode.f_score + " H score of Neighbor: " + neighborNode.h_score + "  G_score or neighbor: " +neighborNode.g_score);
    insertIntoPQ (neighborNode, openSet);
   }
  }
 }
 trace ("fail");
 return false;
}

Gerade jetzt diese Funktion erstellt auf Wege, die oft nicht optimale oder ganz unrichtig angesichts der Ziel-und das passiert meist dann, wenn ich Knoten, die nicht Weg können, und ich bin nicht ganz sicher, was ich falsch mache, gerade jetzt.

Wenn mir jemand helfen könnte dies korrigieren, ich würde es sehr begrüßen.

Einige Hinweise

Meine OpenSet ist im wesentlichen eine Priority-Queue, so das ist, wie ich Sortiere meine Knoten von den Kosten.
Hier ist die Funktion

function insertIntoPQ (iNode:node, pq:Array)
{
 var inserted:Boolean=true;
 var iterater:int=0;
 while (inserted)
 {
  if (iterater==pq.length)
  {
   pq.push (iNode);
   inserted=false;
  }
  else if (pq[iterater].f_score >= iNode.f_score)
  {
   pq.splice (iterater,0,iNode);
   inserted=false;
  }

  ++iterater;
 }
}

Dank!