Я собираю проект для класса, который требует, чтобы я поместил ИИ в игру Tactical Strategy сверху вниз во Flash AS3.
Я решил, что буду использовать метод поиска путей на основе узлов, потому что игра основана на схеме кругового движения. Когда игрок перемещает юнит, он, по существу, рисует серию линейных сегментов, которые соединяют, за которыми будет следовать юнитовый блок.
Я пытаюсь собрать аналогичную операцию для ИИ в нашей игре, создав список узлов для перехода к целевому узлу. Следовательно, я использую 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;
}
}
Спасибо!