c# - 实现中的特定 A* 寻路问题

Question

我的 A* 实现有一些问题。它偶尔会决定在我的网格上做一些奇怪的事情，比如忽略移动成本并穿过高成本区域，或者在回到正轨之前朝错误的方向移动一个方 block 。

我已经正式在上面花了太多时间，然后我想承认，所以我正在伸出手寻找一双新鲜的眼睛。

private List<Vector2> PathFromTo(Vector2 startID, Vector2 targetID){
    List<Vector2> path = new List<Vector2> ();
    List<Node> closedList = new List<Node> ();
    List<Node> openList = new List<Node> ();
    Node startNode = nodeList.Find (tgt => tgt.nodeID == new Vector2 (startID.x, startID.y));
    if (startNode == null)
        return path;
    Node targetNode = nodeList.Find (tgt => tgt.nodeID == new Vector2 (targetID.x, targetID.y));
    if (targetNode == null)
        return path;

    openList.Add (startNode);

    while (openList.Count > 0) {
        Node current = openList [0];
        for (int i = 1; i < openList.Count; i++) 
            if (openList [i].GetFCost () <= current.GetFCost () && openList [i].GetHCost () < current.GetHCost ()) 
                current = openList [i];

        openList.Remove (current);
        closedList.Add (current);

        if (current == targetNode) {
            RetracePath (startNode, targetNode, ref path);
            return path;
        }

        foreach(Vector2 neighbour in current.neighbors) {
            Node neighbourNode = nodeList.Find (tgt => tgt.nodeID == new Vector2 (neighbour.x, neighbour.y));
            CheckNeighbor(ref neighbourNode, ref current, ref targetNode, ref closedList, ref openList);
        }
    }
    return path;
}

private void CheckNeighbor(ref Node neighborTile, ref Node currentTile, ref Node targetTile, ref List<Node> closedList, ref List<Node> openList){
    if (neighborTile != null) {
        if (!neighborTile.passable || closedList.Contains (neighborTile)) {
        } else {
            int newCostToNeighbor = (int)(currentTile.moveCost + CalculateDistance (currentTile.position, neighborTile.position));
            if (newCostToNeighbor < neighborTile.GetGCost() || !openList.Contains (neighborTile)) {
                neighborTile.SetGCost (newCostToNeighbor);
                neighborTile.SetHCost (CalculateDistance (neighborTile.position, targetTile.position));
                neighborTile.SetParent (currentTile);

                if (!openList.Contains (neighborTile)) 
                    openList.Add (neighborTile);
            }
        }
    }
}

public float CalculateDistance(Vector2 tileA_pos, Vector2 tileB_pos){ 
    float dX = Mathf.Abs (tileB_pos.x - tileA_pos.x); 
    float dY = Mathf.Abs (tileB_pos.y - tileA_pos.y); 
    float shift1 = -(tileA_pos.x + tileA_pos.y); 
    float shift2 = -(tileB_pos.x + tileB_pos.y); 
    float dZ = Mathf.Abs (shift2 - shift1); 
    return Mathf.Max (dX, dY, dZ); 
}

private void RetracePath(Node start, Node end, ref List<Vector2> pathInfo){
    pathInfo = new List<Vector2> ();
    Node current = end;
    while (current != start) {
        pathInfo.Add (current.nodeID);
        current = current.GetParent ();
    }
    pathInfo.Reverse ();
}

Answer 1

鉴于您在评论中显示的 CalculateDistance 方法，我编写了以下测试程序:(假设您的 Mathf 类似于 System.Math )

for (int y = -4; y < 5; y++)
{
    for (int x = -4; x < 5; x++)
    {
        var dst = CalculateDistance(new Vector2(x, y), new Vector2());
        Console.Write($"{((int)dst):D1} ");
    }
    Console.WriteLine();
}

测试程序测试(-4,-4)和(4, 4)之间的所有坐标，并计算它们到(0,0)的距离输出:

8 7 6 5 4 4 4 4 4
7 6 5 4 3 3 3 3 4
6 5 4 3 2 2 2 3 4
5 4 3 2 1 1 2 3 4
4 3 2 1 0 1 2 3 4
4 3 2 1 1 2 3 4 5
4 3 2 2 2 3 4 5 6
4 3 3 3 3 4 5 6 7
4 4 4 4 4 5 6 7 8

如您所见，输出完全古怪，您希望右下角与 (0,0) 的距离与右上角的距离一样远，但事实并非如此。也许您需要重写您的 CalculateDistance 方法。

您似乎计算了 dX、dY 和 dZ，这是不可能的，因为您只有 2 个坐标 (Vector2)。

---

编辑:如果没有记录“权重”，您可以简单地使用毕达哥拉斯算出两点之间的距离:

var dist = Math.Sqrt(Math.Pow(point1.x - point2.x, 2) + Math.Pow(point1.y - point2.y, 2));