XNA A *アルゴリズムの実装に時間がかかりすぎる

Question

私のXNAゲームでは、自分のジェネリックPriorityQueueクラスを使ってA *を敵の動作の一部として実装しています。しかし、実装はあまりにも時間がかかります - ゲーム時間の1秒未満がリアルタイムの約5秒かかるところまで。正確に何が時間がかかり、それをどう変えるのですか？

優先度は浮動小数点数ではなくintとして表されます。浮動小数点数を使って試したときに試合が開始されないためです。

操作の数が問題であると思われます。最後のフレームの最後に、（100,100）から（0,0）までの経路を障害物なしで見つけるための評価されたノードの数は、グリッドの正方形のサイズを変更した後に〜800または305でしたサイズが1から5になりました。これによりフレームレートの低下が改善されましたが、まだまだ滑らかにはなりませんでした。

この件に関するほとんどの記事とスタック交換の質問では、タイブレーカーを実装することを提案しています。私はh（）スコアに1.1,1.01,1.0001を乗算しようとしました。おそらく私が誤解しているものがあります。

別の可能性のあるオプションは、私のPriorityQueueが十分に効率的でないということです。確かに、私はそれをより効率的にする方法や提案がほしいと思う方法を知らない。

敵のメンバーとチェイス方法：

#region data 
    private IFocusable Target { get; set; } 
    private Map WorldMap { get; set; } 
    #endregion 

    #region methods 
    protected void Chase(GameTime gameTime) 
    { 
     PriorityQueue<Vector2> openSet = new PriorityQueue<Vector2>(); 
     List<Vector2> closedSet = new List<Vector2>(); 
     Dictionary<Vector2, Vector2> cameFrom = new Dictionary<Vector2, Vector2>(); 
     Dictionary <Vector2, int> gScores = new Dictionary<Vector2, int>(); 
     openSet.Enqueue(Heuristic(Position, Target.Position), Tools.RoundDown(Position)); 
     gScores.Add(Position, 0); 
     while(openSet.Count != 0) 
     { 
      Vector2 current = openSet.Dequeue(); 
      if (current == Tools.RoundDown(Target.Position)) 
      { 
       Position = ReconstructPath(cameFrom, current); 
       break; 
      } 
      closedSet.Add(current); 
      List<Vector2> neighbours = WorldMap.GetNeighbours(current, Speed); 
      foreach (Vector2 neighbour in neighbours) 
      { 
       if (closedSet.Contains(neighbour)) 
        continue; 
       int tenativeGScore = gScores[current] + (int)Vector2.Distance(current, neighbour); 
       if (openSet.Contains(neighbour) == -1 || tenativeGScore < gScores[neighbour]) 
       { 
        cameFrom[neighbour] = current; 
        gScores[neighbour] = tenativeGScore; 
        int fScore = tenativeGScore + Heuristic(neighbour, Target.Position); 
        openSet.Enqueue(fScore, neighbour); 
       } 
      } 
     } 
    } 

    private Vector2 ReconstructPath(Dictionary<Vector2, Vector2> cameFrom, Vector2 currentNode) 
    { 
     if (cameFrom[currentNode] == Position) 
      return currentNode; 
     else 
      return ReconstructPath(cameFrom, cameFrom[currentNode]); 
    } 

    //Heuristic: distance between neighbour and target, rounded down. 
    private int Heuristic(Vector2 current, Vector2 goal) 
    { 
     return (int)Vector2.Distance(current, Tools.RoundDown(goal)); 
    } 
    #endregion 
} 

優先度つきキュー：

public class PriorityQueue<T> where T : IEquatable<T> 
{ 
    #region data 
    private List<Tuple<int, T>> Items { get; set; } 
    public int Count {get{return Items.Count;}} 
    private bool Sorted { get; set; } 
    #endregion 

    #region c'tor 
    public PriorityQueue() 
    { 
     this.Items = new List<Tuple<int,T>>(); 
     this.Sorted = true; 
    } 
    #endregion 

    #region methods 
    private int SortingMethod(Tuple<int, T> x, Tuple<int, T> y) 
    { 
     if (x == null || y == null) 
      throw new ArgumentNullException(); 
     return x.Item1 - y.Item1; 
    } 
    public void Enqueue(Tuple<int, T> item) 
    { 
     int index = Contains(item.Item2); 
     if (index == -1) 
     { 
      Items.Add(item); 
      Sorted = false; 
     } 
     else 
      Items[index] = item; 
    } 
    public void Enqueue(int key, T value) 
    { 
     Enqueue(new Tuple<int,T>(key, value)); 
    } 
    public T Dequeue() 
    { 
     if(!Sorted) 
     { 
      Items.Sort(SortingMethod); 
      Sorted = true; 
     } 
     Tuple<int, T> item = Items[0]; 
     Items.RemoveAt(0); 
     return item.Item2; 
    } 
    public int Contains(T value) 
    { 
     for (int i = 0; i < Items.Count; i++) 
      if (Items[i].Equals(value)) 
       return i; 
     return -1; 
    } 
    #endregion 
} 

地図の該当するメンバー（正方形のマップを表すクラスは、敵が上のナビゲートし、私は来ませんでした。 ）：

#region data 
    private int SquareSize { get; set; } 
    private List<Vector2> BlockedSquares { get; set; } 
    private Rectangle Bounds { get; set; } 
    #endregion 

    public List<Vector2> GetNeighbours(Vector2 vector, int speed) 
    { 
     Vector2[] directions = new Vector2[8]; 
     List<Vector2> neighbours = new List<Vector2>(); 
     directions[0] = Tools.RoundDown(Vector2.UnitX);//right 
     directions[1] = Tools.RoundDown(Vector2.UnitX);//left 
     directions[2] = Tools.RoundDown(Vector2.UnitY);//down 
     directions[3] = Tools.RoundDown(Vector2.UnitY);//up 
     directions[4] = Tools.RoundDown(Vector2.UnitX + Vector2.UnitY);//down right 
     directions[5] = Tools.RoundDown(-Vector2.UnitX + Vector2.UnitY);//down left 
     directions[6] = Tools.RoundDown(Vector2.UnitX - Vector2.UnitY);//up right 
     directions[7] = Tools.RoundDown(-Vector2.UnitX - Vector2.UnitY);//up left 
     for (int i = (int)vector.X - speed; i <= (int)vector.X + speed; i += SquareSize) 
     { 
      for(int j = (int)vector.Y - speed; j <= (int)vector.Y + speed; j += SquareSize) 
      { 
       Vector2 point = new Vector2(i, j); 
       if (point == vector) 
        continue; 
       else if (Vector2.Distance(vector, point) <= speed) 
        neighbours.Add(point); 
      } 
     } 
     return neighbours; 
    } 

    public Vector2 InSquare(Vector2 vector) 
    { 
     int x = (int)vector.X, y = (int)vector.Y; 
     x -= x % SquareSize; 
     y -= y % SquareSize; 
     return new Vector2(x, y); 
    } 

うまくいけばこの答えは私だけでなく、将来同様の質問に苦労する多くのプログラマーに役立つでしょう。

ありがとうございます。

Answer 1

減速の理由は、非効率な封じ込めチェックを使用していたためです。

：

List<Vector2> closedSet = new List<Vector2>(); 

に変更されます。closedSetの場合など

二分探索木、HashSets、のような高速の封じ込めをチェックし、使用したデータの種類は、私が代わりにHashSetの一覧を使用しました

HashSet<Vector2> closedSet = new HashSet<Vector2>(); 

closedSetについては、両方の型にAdd関数とContains関数があるため変更する必要はありません。

gスコアの場合、より効率的なTryGetValueの代わりにContainsKeyを使用するという問題があります。 this answerに基づいています。あなたが遅いかを知りたい場合は* *プロファイラを使用

float gScore;//Current gScores[neighbour] value, if there's any. 
if(gScores.TryGetValue(neighbour, out gScore) || tenativeGScore < gScore) 

Answer 2

Initialize()メソッドにthis.isFixedTimeStep = false;を入れてみてください。