AS3中的A *(A-star)实现
问题描述:
我正在为一个需要我将AI放在Flash AS3中的自上而下的战术策略游戏中的课程组建一个项目。AS3中的A *(A-star)实现
我决定使用基于节点的路径查找方法,因为游戏基于循环移动方案。当一个玩家移动一个单位时,他基本上会画出一系列连接玩家单位的连线。
我想通过创建一个节点列表来遍历目标节点,尝试在我们的游戏中为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;
}
}
谢谢!
答
你能不能解释一下什么是这些行的目的:
if (cNode.dirArray[i] >= 4)
{
neighborNode.g_score -= 4;
}
A *对于其中成本始终为正,即路径成本是单调递增的问题。
另一件需要检查的问题是关于最优性,distFunction()总是返回一个小于或等于达到目标的实际成本的值(即启发式要求被允许,所以A *可以保证它将找到最佳解决方案)。
我对AS3一无所知 - 所以我不能评论优先级队列的使用情况。
答
试用http://script3.blogspot.com/2010/04/star-path-finding-algorthim-in.html 你可以找到有强大的具有平滑路径搜索选项A *寻路类。