2

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

ありがとう！

4

3 に答える 3

2

これらの行の目的を説明していただけますか？

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

A *は、コストが常に正である、つまりパスのコストが単調に増加している問題用です。

最適性に関して確認するもう1つの点は、distFunction（）が常に目標に到達するための実際のコスト以下の値を返していることです（つまり、A *が最適なソリューションを見つけることを保証できるように、ヒューリスティックが許容される必要があります） ）。

AS3についてはまったく知りません。そのため、優先キューの使用法についてコメントすることはできません。

于 2010-05-17T09:40:40.080 に答える
1

ここに高速な実装があります: https://github.com/tomnewton/AS3AStar

于 2011-02-23T03:02:19.293 に答える
1

http://script3.blogspot.com/2010/04/star-path-finding-algorthim-in.htmlを試してみてください 。スムーズな経路検索オプションを備えた強力な*経路検索クラスが見つかります。

于 2011-03-19T20:38:34.170 に答える