AS3中的A* (A-star)实现

Question

我正在为一个课程整理一个项目，这个项目需要我把AI放在Flash AS3中的一个自上而下的战术策略游戏中。

我决定使用基于节点的路径查找方法，因为游戏是基于循环移动方案的。当玩家移动一个单位时，他基本上绘制了一系列连接玩家单位的线段。

我正在尝试通过创建一个遍历到目标节点的节点列表，为我们游戏中的AI单元组合一个类似的操作。因此我使用了Astar (生成的路径可以用来创建这一行)。

这是我的算法

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

现在，这个函数创建的路径通常不是最优的，或者在给定目标的情况下完全不准确，这通常发生在我的节点无法路径时，而我不太确定我现在做错了什么。

如果有人能帮我改正这个错误，我将不胜感激。

一些注意事项

我的OpenSet本质上是一个优先级队列，所以这就是我按成本对节点进行排序的方式。下面是该函数

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

谢谢!

Answer 1

你能解释一下这些行的用途吗：

if (cNode.dirArray[i] >= 4)
{
 neighborNode.g_score -= 4;
}

A*表示成本始终为正的问题，即路径成本单调增加。

关于最优性，另一件需要检查的事情是，distFunction()总是返回一个小于或等于达到目标的实际成本的值(即，启发式需要是可接受的，所以A*可以保证它会找到最优解)。

我对AS3一无所知--所以我不能评论优先级队列的使用情况。

Answer 2

这里有一个快速的实现：https://github.com/tomnewton/AS3AStar

Answer 3

试试http://script3.blogspot.com/2010/04/star-path-finding-algorthim-in.html，你可以找到一个强大的*寻路类，带有流畅的寻路选项。