logo标签列表

实现中的特定A*路径规划问题

c#unity-game-enginepath-findinga-star
3

我在A*算法实现中遇到了一些问题。有时它会做出奇怪的决定，比如忽略移动成本并穿过高成本区域，或者在回到正确路径之前朝错误方向移动一个格子。

我已经花费了太多时间，不想再继续浪费了，所以我想寻求新的帮助来解决这个问题。

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 ();
}
你已经尝试过什么了吗？你能够重现你的问题吗？如果可以，你是否尝试调试你的代码，至少试图找出哪里出了问题？ - PJvG
我已经尝试过调整路径成本和起始位置，但我使用的棋盘是随机生成的，因此很难确定确切的模式。最糟糕的情况是在可通过但移动成本高的瓷砖上。它不是绕过瓷砖，而是穿过它们。瓷砖成本是正确的，只是生成了错误的路径，因此我认为实现有误。 - Nick B.
1
你提到了“高成本瓷砖”，但是在你的代码示例中并没有明显体现。那么这个问题在CalculateDistance函数中是如何处理的呢？ - GWigWam
1
@NickB。您应该编辑您的问题并添加您的CalculateDistance方法。它太长了，无法适应评论区。请在此之后删除该评论。哦，当您编辑您的问题时，请还将oop标签从中删除，因为您的问题与面向对象编程无关（例如，您没有任何继承或抽象问题）。 - PJvG
我不确定你在CaluclateDistance()方法中想要做什么，但它只查看了瓦片的x和y位置，成本是如何实现的？ - John M
显示剩余3条评论
3个回答
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));
1
良好的分析和调试，但从技术上讲，这并不是一个答案。如果你能提出修复的方法，你将得到更高的分数。 - Bradley Uffner
@BradleyUffner 有道理。我加了一个简单的解决方案。请注意，OP寻求帮助调试，“这里有什么问题？”，并不一定需要完整的解决方案。也许这种问题形式在StackOverflow上不太适合。 - GWigWam
我已经更改为新的公式，但问题仍未解决。 - Nick B.
0

您没有说明是否允许对角线移动，但是这两个CalculateDistance函数中的一个应该足够：

    public static readonly int D = 1;
    public static readonly int D2 = 1;

    public static float CalculateDistance(Vector2 tileA_pos, Vector2 tileB_pos)
    {
        float dX = Math.Abs(tileB_pos.x - tileA_pos.x);
        float dY = Math.Abs(tileB_pos.y - tileA_pos.y);
        return D * (dX + dY);
    }

    public static float CalculateDistanceDiagonalsAllowed(Vector2 tileA_pos, Vector2 tileB_pos)
    {
        float dX = Math.Abs(tileB_pos.x - tileA_pos.x);
        float dY = Math.Abs(tileB_pos.y - tileA_pos.y);
        return D * (dX + dY) + (D2 - 2 * D) * (dX < dY ? dX : dY);
    }

其中D是垂直/水平移动的成本，D2是对角线移动的成本 - 您可能希望根据需要将其设置为1或Sqrt(2)。我假设currentTile.moveCost被用来定义高/低成本的瓷砖。

我尝试了这两种解决方案，但都没有解决问题。 - Nick B.
0
经过太多的时间（和一整晚的睡眠）后，我终于找到了解决方法。问题与CheckNeighbor函数有关。新的方法如下：
private void CheckNeighbor(ref Node neighborTile, ref Node currentTile, ref Node targetTile, ref List<Node> closedList, ref List<Node> openList, bool ignoreMoveCost = false){
    if (neighborTile != null) {
        if (!neighborTile.passable || closedList.Contains (neighborTile)) {
        } else {
            int newCostToNeighbor = (int)((ignoreMoveCost ? 1 : neighborTile.moveCost) + currentTile.GetGCost() + CalculateDistance (currentTile.position, neighborTile.position));
            if (!openList.Contains (neighborTile)) {
                openList.Add (neighborTile);
            } else if (newCostToNeighbor >= neighborTile.GetGCost ()) {
                return;
            }
            neighborTile.SetParent (currentTile);
            neighborTile.SetGCost (newCostToNeighbor);
            neighborTile.SetHCost (CalculateDistance (currentTile.position, neighborTile.position));
        }
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接