在AS3 A *（A星）实施 [英] A* (A-star) implementation in AS3

问题描述

我组建了一个项目，需要我把AI在自上而下的战术策略游戏在Flash AS3类。

I am putting together a project for a class that requires me to put AI in a top down Tactical Strategy game in Flash AS3.

我决定，我会用一个节点，基于寻路的方法，因为游戏是基于一个圆周运动方案。当玩家移动一个单元，他基本上绘制一系列连接，一个播放器单元将遵循沿着线段。

I decided that I would use a node based path finding approach because the game is based on a circular movement scheme. When a player moves a unit he essentially draws a series of line segments that connect that a player unit will follow along.

我试图通过创建节点列表遍历到目标节点放在一起的AI单位在我们的游戏中类似的操作。因此，我使用阿斯达的（生成的路径可以被用来创建这条线）。

I am trying to put together a similar operation for the AI units in our game by creating a list of nodes to traverse to a target node. Hence my use of Astar (the resulting path can be used to create this line).

下面是我的算法

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

现在这个函数创建，往往不是最优的或完全不准确的给出了目标路径，而这通常发生在我有没有路能够节点，我不太知道我做错了，现在。

Right now this function creates paths that are often not optimal or wholly inaccurate given the target and this generally happens when I have nodes that are not path able, and I am not quite sure what I am doing wrong right now.

如果有人可以帮助我解决这个我会AP preciate它极大地。

If someone could help me correct this I would appreciate it greatly.

若干注记

我的OpenSet本质上是一个优先级队列，因此多数民众赞成我怎么按成本排序我的节点。 下面是功能

My OpenSet is essentially a Priority Queue, so thats how I sort my nodes by cost. Here is that function

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

谢谢！

推荐答案

你能解释什么是这些行的目的：

Could you explain what's the purpose of these lines:

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

A *是问题，即成本始终为正，即路径成本单调递增的。

A* is for problems where costs are always positive i.e. cost of paths is monotonically increasing.

另一件事是检查，对于最优化，是distFunction（）的返回总是一个值，该值小于等于比实际成本要达到的目标（如启发式要求予以受理所以A *能保证它会找到最优的解决方案）。

Another thing to check, regarding optimality, is that distFunction() is returning always a value which is lesser or equal than the actual cost to reach the goal (i.e. the heuristic is required to be admissible so A* can guarantee it will find optimal solutions).

我不知道AS3任何东西 - 这样我就可以不上优先级队列使用意见

I don't know anything about AS3 at all - so I can't comment on the priority queue usage.

这篇关于在AS3 A *（A星）实施的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！