我的A *尋路實現有問題嗎？

Question

所以我試圖在LibGDX中實現一個A * PathFinding算法，這樣我就可以理解它是如何工作的。我基於我的實現寫在它上面：http://www.policyalmanac.org/games/aStarTutorial.htm

目前，我已經得到算法來計算路徑，甚至返回一個路徑作爲非存在，如果目標不可訪問，但找到的路由路徑需要的是真正不尋常的，如果有牆壁部分阻斷目標，你可以在這裏看到：

所以想什麼，我找出什麼是錯我的執行，看看爲什麼關閉列表正在生成這樣的路徑，或者如果我錯過了一個步驟。

這些都是在路徑查找器類的變量：

public class PathFinder { 
private Array<Array<GridNode>> grid = new Array<Array<GridNode>>(); 
private Array<GridNode> openPath = new Array<GridNode>(); 
private Array<GridNode> closedPath = new Array<GridNode>(); 
private int GridX, GridY; 
private int StartX = -1, StartY = -1; 
private int EndX = -1, EndY = -1; 

public static int Found = 1; 
public static int NonExistant = 2; 

這裏的路徑探路者類查找代碼：

public int findPath() 
{ 
    //Clear current path 
    openPath.clear(); 
    closedPath.clear(); 

    //Reset all F, G and H values to 0 
    for (int y = 0; y < grid.size; y++) 
    { 
     for (int x = 0; x < grid.get(y).size; x++) 
     { 
      grid.get(y).get(x).Reset(); 
     } 
    } 

    //If no Start or End nodes have been set, quit the findPath. 
    if (StartX == -1 || StartY == -1 || EndX == -1 || EndY == -1) 
    { 
     return NonExistant; 
    } 
    else if (StartX == EndX && StartY == EndY) // If Start = End, return found. 
    { 
     return Found; 
    } 
    else 
    { 
     openPath.add(grid.get(StartY).get(StartX)); //Add Start node to open 
     SetOpenList(StartX, StartY); //Set neighbours. 

     closedPath.add(grid.get(StartY).get(StartX)); //Add Start node to closed. 
     openPath.removeValue(grid.get(StartY).get(StartX),true); //Remove Start Node from open. 

     while (closedPath.get(closedPath.size - 1) != grid.get(EndY).get(EndX)) 
     { 
      //Set Neighbours for parent 
      SetOpenList(closedPath.get(closedPath.size-1).X/GridX, closedPath.get(closedPath.size-1).Y/GridY); 

      if (openPath.size != 0) 
      { 
       int bestF = 10000; 
       int bestFIndex = -1; 

       //Get node with lowest F in open. 
       for (int i = 0; i < openPath.size; i++) 
       { 
        if (openPath.get(i).F < bestF) 
        { 
         bestF = openPath.get(i).F; 
         bestFIndex = i; 
        } 
       } 

       if (bestFIndex != -1) 
       { 
        closedPath.add(openPath.get(bestFIndex)); //Add node to closed list 
        openPath.removeIndex(bestFIndex); //remove from open list 
       } 
       else 
        return NonExistant; 
      } 
      else 
      { 
       return NonExistant; 
      } 
     } 
    } 

    return Found; 
} 

public void CompareParentwithOpen(GridNode Parent, GridNode Open) 
{ 
    //If the G value of open is smaller than the G value in Parent, recalculate F, G and H. 
    if (Open.G < Parent.G) 
    { 
     openPath.get(
       openPath.indexOf(Open, true)).CalculateNode(
         Parent, 
         grid.get(StartY).get(StartX), 
         grid.get(EndY).get(EndX)); 
    } 
} 

public void SetOpenList(int X, int Y) 
{ 
    //Check position of X and Y to avoid IndexOutofBounds. 
    Boolean ignoreLeft = (X - 1 < 0); 
    Boolean ignoreRight = (X + 1 >= grid.get(Y).size); 
    Boolean ignoreUp = (Y - 1 < 0); 
    Boolean ignoreDown = (Y + 1 >= grid.size); 

    tempOpen = new Array<GridNode>(); 

    //For each check, if the checked grid is not an unpassable type and not in the closed list, continute checking. 
    //If checked grid is already in Open List, go to Compare parent with open. 
    if (!ignoreLeft && !ignoreUp) 
    { 
     if (grid.get(Y-1).get(X-1).type != GridNode.GridType.UNPASSABLE && 
       !closedPath.contains(grid.get(Y-1).get(X-1), true)) 
     { 
      if (!(openPath.contains(grid.get(Y-1).get(X-1), true) || openPath.contains(grid.get(Y-1).get(X-1), false))) 
      { 
       grid.get(Y-1).get(X-1).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX)); 
       openPath.add(grid.get(Y-1).get(X-1)); 
      } 
      else 
      { 
       CompareParentwithOpen(grid.get(Y).get(X), 
         openPath.get(openPath.indexOf(grid.get(Y-1).get(X-1), true))); 
      } 
     } 
    } 

    if (!ignoreUp) 
    { 
     if (grid.get(Y-1).get(X).type != GridNode.GridType.UNPASSABLE && 
       !closedPath.contains(grid.get(Y-1).get(X), true)) 
     { 
      if (!(openPath.contains(grid.get(Y-1).get(X), true) || openPath.contains(grid.get(Y-1).get(X), false))) 
      { 
       grid.get(Y-1).get(X).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX)); 
       openPath.add(grid.get(Y-1).get(X)); 
      } 
      else 
      { 
       CompareParentwithOpen(grid.get(Y).get(X), 
         openPath.get(openPath.indexOf(grid.get(Y-1).get(X), true))); 
      } 
     } 
    } 

    if (!ignoreRight && !ignoreUp) 
    { 
     if (grid.get(Y-1).get(X+1).type != GridNode.GridType.UNPASSABLE && 
       !closedPath.contains(grid.get(Y-1).get(X+1), true)) 
     { 
      if (!(openPath.contains(grid.get(Y-1).get(X+1), true) || openPath.contains(grid.get(Y-1).get(X+1), false))) 
      { 
       grid.get(Y-1).get(X+1).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX)); 
       openPath.add(grid.get(Y-1).get(X+1)); 
      } 
      else 
      { 
       CompareParentwithOpen(grid.get(Y).get(X), 
         openPath.get(openPath.indexOf(grid.get(Y-1).get(X+1), true))); 
      } 
     } 
    } 

    if (!ignoreLeft) 
    { 
     if (grid.get(Y).get(X-1).type != GridNode.GridType.UNPASSABLE && 
       !closedPath.contains(grid.get(Y).get(X-1), true)) 
     { 
      if (!(openPath.contains(grid.get(Y).get(X-1), true) || openPath.contains(grid.get(Y).get(X-1), false))) 
      { 
       grid.get(Y).get(X-1).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX)); 
       openPath.add(grid.get(Y).get(X-1)); 
      } 
      else 
      { 
       CompareParentwithOpen(grid.get(Y).get(X), 
         openPath.get(openPath.indexOf(grid.get(Y).get(X-1), true))); 
      } 
     } 
    } 

    if (!ignoreRight) 
    { 
     if (grid.get(Y).get(X+1).type != GridNode.GridType.UNPASSABLE && 
       !closedPath.contains(grid.get(Y).get(X+1), true)) 
     { 
      if (!(openPath.contains(grid.get(Y).get(X+1), true) || openPath.contains(grid.get(Y).get(X+1), false))) 
      { 
       grid.get(Y).get(X+1).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX)); 
       openPath.add(grid.get(Y).get(X+1)); 
      } 
      else 
      { 
       CompareParentwithOpen(grid.get(Y).get(X), 
         openPath.get(openPath.indexOf(grid.get(Y).get(X+1), true))); 
      } 
     } 
    } 

    if (!ignoreLeft && !ignoreDown) 
    { 
     if (grid.get(Y+1).get(X-1).type != GridNode.GridType.UNPASSABLE && 
       !closedPath.contains(grid.get(Y+1).get(X-1), true)) 
     { 
      if (!(openPath.contains(grid.get(Y+1).get(X-1), true) || openPath.contains(grid.get(Y+1).get(X-1), false))) 
      { 
       grid.get(Y+1).get(X-1).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX)); 
       openPath.add(grid.get(Y+1).get(X-1)); 
      } 
      else 
      { 
       CompareParentwithOpen(grid.get(Y).get(X), 
         openPath.get(openPath.indexOf(grid.get(Y+1).get(X-1), true))); 
      } 
     } 
    } 

    if (!ignoreDown) 
    { 
     if (grid.get(Y+1).get(X).type != GridNode.GridType.UNPASSABLE && 
       !closedPath.contains(grid.get(Y+1).get(X), true)) 
     { 
      if (!(openPath.contains(grid.get(Y+1).get(X), true) || openPath.contains(grid.get(Y+1).get(X), false))) 
      { 
       grid.get(Y+1).get(X).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX)); 
       openPath.add(grid.get(Y+1).get(X)); 
      } 
      else 
      { 
       CompareParentwithOpen(grid.get(Y).get(X), 
         openPath.get(openPath.indexOf(grid.get(Y+1).get(X), true))); 
      } 
     } 
    } 

    if (!ignoreRight && !ignoreDown) 
    { 
     if (grid.get(Y+1).get(X+1).type != GridNode.GridType.UNPASSABLE && 
       !closedPath.contains(grid.get(Y+1).get(X+1), true)) 
     { 
      if (!(openPath.contains(grid.get(Y+1).get(X+1), true) || openPath.contains(grid.get(Y+1).get(X+1), false))) 
      { 
       grid.get(Y+1).get(X+1).CalculateNode(grid.get(Y).get(X), grid.get(StartY).get(StartX), grid.get(EndY).get(EndX)); 
       openPath.add(grid.get(Y+1).get(X+1)); 
      } 
      else 
      { 
       CompareParentwithOpen(grid.get(Y).get(X), 
         openPath.get(openPath.indexOf(grid.get(Y+1).get(X+1), true))); 
      } 
     } 
    } 

    for (GridNode c : closedPath) //incase any nodes in closed are in open, remove closed nodes. 
    { 
     openPath.removeValue(c, true); 
    } 
} 

public void SetGridNode(int screenX, int screenY, GridNode.GridType Type) 
{ 
    int pointX = (int)(screenX/GridX); 
    int pointY = (int)(screenY/GridY); 

    if (pointY >= 0 && pointY < grid.size) 
    { 
     if (pointX >=0 && pointX < grid.get(pointY).size) 
     { 
      if (Type == GridNode.GridType.START || Type == GridNode.GridType.END) 
      { 
       for (int y = 0; y < grid.size; y++) 
       { 
        for (int x = 0; x < grid.get(y).size; x++) 
        { 
         if (grid.get(y).get(x).type == Type) 
         { 
          if (Type == GridNode.GridType.START) 
          { 
           StartX = -1; 
           StartY = -1; 
          } 
          else if (Type == GridNode.GridType.END) 
          { 
           EndX = -1; 
           EndY = -1; 
          } 

          grid.get(y).get(x).type = GridNode.GridType.NONE; 
         } 
        } 
       } 
      } 

      if (grid.get(pointY).get(pointX).type == Type) 
       grid.get(pointY).get(pointX).type = GridNode.GridType.NONE; 
      else 
      { 
       if (Type == GridNode.GridType.START) 
       { 
        StartX = pointX; 
        StartY = pointY; 
       } 
       else if (Type == GridNode.GridType.END) 
       { 
        EndX = pointX; 
        EndY = pointY; 
       } 

       grid.get(pointY).get(pointX).type = Type; 
      } 
     } 
    } 
} 

public Array<GridNode> GetPath() 
{ 
    return closedPath; 
} 

這些都是在GridNode類的變量：

public class GridNode { 
public int X = 0, Y = 0; 
public int Width = 10, Height = 10; 
public GridType type = GridType.NONE; 
public int F = 0, G = 0, H = 0; 

public static enum GridType 
{ 
    NONE, 
    UNPASSABLE, 
    START, 
    END 
} 

下面是計算GridNode類中F，G和H值的代碼：

public void CalculateNode(GridNode Parent, GridNode Start, GridNode End) 
{ 
    if (Parent != null) 
    { 
     if (Math.abs(X - Parent.X) != 0 && 
       Math.abs(Y - Parent.Y) != 0) 
     { 
      G = Parent.G + 14; 
     } 
     else 
     { 
      G = Parent.G + 10; 
     } 

     H = (int)((Math.abs(X-End.X)/Width) + (Math.abs(Y - End.Y)/Height)) * 10; 

     /*int xDistance = (Math.abs(X-End.X)/Width); 
     int yDistance = (Math.abs(Y - End.Y)/Height); 

     if (xDistance > yDistance) 
      H = 14*yDistance + 10*(xDistance-yDistance); 
     else 
      H = 14*xDistance + 10*(yDistance-xDistance);*/ 

     F = G + H; 
    } 
} 

public void Reset() 
{ 
    F = G = H = 0; 
} 

Answer 1

發現問題與@KommaKameleon在Twitter上的幫助。您可以查看GitHub Repo瞭解完整的工作代碼。

問題是我按照上面的寫法所有步驟。除了最後一步之外的所有內容，這要求您通過每個節點Parent從結束點到開始點。

因此，我所做的是添加GridNode類中的GridNode變量來存儲在計算F，G和H.

public class GridNode { 
public float X = 0, Y = 0; 
public int Width = 10, Height = 10; 
public GridType type = GridType.NONE; 
public float F = 0, G = 0, H = 0; 
public GridNode Parent = null; 
... 

public void CalculateNode(GridNode Parent, GridNode Start, GridNode End) 
{ 
    this.Parent = Parent; 

    if (Parent != null) 
    { 
... 

然後findPath內部（）方法中使用的父節點，後while循環，我做了另外一個while循環建立所謂finalPath一個新的Array屬性：

private Array<GridNode> finalPath = new Array<GridNode>(); 

這是我曾經經歷從終點每個父母到起點的algortithm。 （其中，端節點處於closedPath陣列的最後一個元素）

GridNode g = closedPath.peek(); 
finalPath.add(g); 

while (g != grid.get(StartY).get(StartX)) 
{ 
    g = g.Parent; 
    finalPath.add(g); 
} 

finalPath.reverse();