2D配列にA *経路探索を実装する

Question

2Dタイルマップを作成中です。私は現在、A *経路探索を実装しようとしています。私はthe Wikipedia pseudocode for A*に従っています。

アルゴリズムによって行われた決定にいくつか奇妙な振る舞いがあることを除いて、すべてがうまくいっています。

これまでの私のコード：

void Pathfinding(Point from, Point destination) { 

    goalNode = new Node(destination, 0, 0); 
    startNode = new Node(from, 0, ManhattanDistance(from, destination)); 

    open = new List<Node>();   //list of nodes 
    closed = new List<Node>(); 
    open.Add(startNode);    //Add starting point 

    while(open.Count > 0) { 

     node = getBestNode();     //Get node with lowest F value 
     if(node.position == goalNode.position) { 
      Debug.Log("Goal reached"); 
      getPath(node); 
      break; 
     } 
     removeNode(node, open); 
     closed.Add(node); 

     List<Node> neighbors = getNeighbors(node); 
     foreach(Node n in neighbors) { 
      float g_score = node.G + 1; 
      float h_score = ManhattanDistance(n.position, goalNode.position); 
      float f_score = g_score + h_score; 

      if(isValueInList(n, closed) && f_score >= n.F) 
       continue; 

      if(!isValueInList(n, open) || f_score < n.F) { 
       n.parent = node; 
       n.G = g_score; 
       n.G = h_score; 
       if(!isValueInList(n, open)) { 
        map_data[n.position.x, n.position.y] = 4; 
        open.Add(n); 
       } 
      } 
     } 
    } 
} 

このコードの実行結果：

ブルーが開いてリストからノードで、緑がゴールノードに選択されたパスであります。

SOLUTION： - 順序付けがありません、あなたのコードにしながら、

void Pathfinding(Point from, Point destination) { 

    goalNode = new Node(destination, 0, 0); 
    startNode = new Node(from, 0, ManhattanDistance(from, destination)); 

    open = new List<Node>();   //list of nodes 
    closed = new List<Node>(); 
    open.Add(startNode);    //Add starting point 

    while(open.Count > 0) { 

     node = getBestNode();     //Get node with lowest F value 
     if(node.position == goalNode.position) { 
      Debug.Log("Goal reached"); 
      getPath(node); 
      break; 
     } 
     removeNode(node, open); 
     closed.Add(node); 

     List<Node> neighbors = getNeighbors(node); 
     foreach(Node n in neighbors) { 
      float g_score = node.G + 1; 
      float h_score = ManhattanDistance(n.position, goalNode.position); 
      float f_score = g_score + h_score; 

      if(isValueInList(n, closed) && f_score >= n.F) 
       continue; 

      if(!isValueInList(n, open) || f_score < n.F) { 
       n.parent = node; 
       n.G = g_score; 
       n.H = h_score; 
       if(!isValueInList(n, open)) { 
        map_data[n.position.x, n.position.y] = 4; 
        open.Add(n); 
       } 
      } 
     } 
    } 
} 

Answer 1

まず、開いているノードは、降順でをソートする必要があります。距離（g）と経験則（h）を計算しますが、実際にはそれを使用することはありません。あなたは

セカンド（各反復でリストをソートすることは効率的ではないであろうと）リストの代わりに注文したコンテナをを使用することを検討すべきである、あなたはする必要があります

n.G = h_score; 

としてノードでヒューリスティック値を格納しません。

n.H = h_score;