A *路徑尋找算法不總是找到最短路由C＃XNA

Question

我正在創建一個簡單的XNA C＃自上而下的遊戲。在遊戲中，你會在地圖等迷宮附近遇到敵人。自動取款機我已經設置好了，所以當遊戲開始時，敵人會找到你最短的路徑（它會這樣做）。如果玩家已經移動，每秒都會找到一條新路徑。

遊戲總是找到一條路線給你，但似乎無法找到移動目標的最短路線，有時在你移動的時候進入一個循環，而當你停下來時，敵人會在地圖的半途中移動找到你，即使你只有幾步之遙。它似乎並不是啓發式的，因爲我刪除了它（使它成爲dijkstra），它似乎仍然存在相同的問題。我認爲這很簡單，我忽略了，但是我很難搞清楚什麼。

在此先感謝

class PathFinder 
{ 
    private Cell[,] map = Game1.cellArray; 


    public List<Cell> calculate(int currX, int currY, int destX, int destY) 
    { 
     resetMap(); 

     Debug.WriteLine("starting over"); 
     List<Cell> path = new List<Cell>(); 
     List<Cell> openList = new List<Cell>(); 
     List<Cell> closedList = new List<Cell>(); 

     Cell startPos = map[currY, currX]; 
     Cell endPos = map[destY, destX]; 
     startPos.closed = true; 
     closedList.Add(startPos); 


     Cell curPos = startPos; 

     while (!closedList.Contains(endPos)) 
     { 

      //add adjacent nodes to list, discover their scores 
      foreach (Cell v in getAdj(curPos)) 
      { 
       if (v.walkable == true && v.closed == false) 
       { 
        if (!openList.Contains(v)) 
        { 
         v.parent = curPos; 
         v.H = getH(v, endPos); 
         v.G = v.parent.G + 10; 

         v.F = v.G + v.H; 
         openList.Add(v); 


        } 
         //if square already on list would benefit from current tile being parent, make it so 
        else if (curPos.G + 10 < v.G) 
        { 
         v.parent = curPos; 
         v.G = v.parent.G + 10; 
         v.F = v.G + v.H; 
        } 
       } 
      } 
      if (openList.Count <= 1) {/*Console.WriteLine("Returned NULL");*/ return null; } 

      curPos = openList[1]; 

      curPos.closed = true; 
      closedList.Add(curPos); 
      openList[1] = openList[openList.Count - 1]; 
      openList.RemoveAt(openList.Count - 1); 

      openList.OrderBy(o => o.F); 
      openList.Reverse(); 

     } 

     //backtrack to discover path 
     Cell curNode = endPos; 
     path.Add(endPos); 
     while (curNode != startPos) 
     { 
      curNode = curNode.parent; 
      path.Add(curNode); 
      Debug.WriteLine("Path// X: " + curNode.xLocation + " Y: " + curNode.yLocation); 
     } 

     path.Reverse(); 
     return path; 
    } 
    //finds heuristic of current square by checking distance to destination ignoring walls 
    private int getH(Cell curPos, Cell endPos) 
    { 
     int diffX = curPos.xLocation - endPos.xLocation; 
     int diffY = curPos.yLocation - endPos.yLocation; 

     if (diffX < 0) 
     { 
      diffX *= -1; 
     } 
     if (diffY < 0) 
     { 
      diffY *= -1; 
     } 
     return ((diffX + diffY) * 10); 
    } 

    //get list of adjacent Cells 
    private List<Cell> getAdj(Cell curPos) 
    { 
     List<Cell> adjList = new List<Cell>(); 

     if (curPos.xLocation - 1 >= 0){ 
      adjList.Add(map[curPos.yLocation, curPos.xLocation - 1]); 
     } 
     if (curPos.xLocation < 19) 
     { 
      adjList.Add(map[curPos.yLocation, curPos.xLocation + 1]); 
     } 
     if (curPos.yLocation - 1 >= 0) 
     { 
      adjList.Add(map[curPos.yLocation - 1, curPos.xLocation]); 
     } 
     if (curPos.yLocation < 19) 
     { 
      adjList.Add(map[curPos.yLocation + 1, curPos.xLocation]); 
     } 


     return adjList; 
    } 

    private void resetMap() 
    { 
     //reset Cells to default values 
     for (int r = 0; r < map.GetLength(1); r++) 
     { 
      for (int c = 0; c < map.GetLength(0); c++) 
      { 
       map[r, c].reset(); 
      } 
     } 
    } 
} 

Answer 1

只是工作出了問題。在更改當前選定的圖塊之前未進行排序。我曾以爲我給他們錯誤的得分。