在基于 2D 网格的 Unity 游戏中提高 A* 寻路效率

Question

public List<Node> FindPath(Vector2Int start, Vector2Int target)
{
    List<Node> openSet = new List<Node>();
    HashSet<Node> closedSet = new HashSet<Node>();
    Node startNode = grid.GetNode(start);
    Node targetNode = grid.GetNode(target);

    openSet.Add(startNode);

    while (openSet.Count > 0)
    {
        Node currentNode = openSet[0];
        for (int i = 1; i < openSet.Count; i++)
        {
            if (openSet[i].FCost < currentNode.FCost || (openSet[i].FCost == currentNode.FCost && openSet[i].HCost < currentNode.HCost))
            {
                currentNode = openSet[i];
            }
        }

        openSet.Remove(currentNode);
        closedSet.Add(currentNode);

        if (currentNode == targetNode)
        {
            return RetracePath(startNode, targetNode);
        }

        foreach (Node neighbor in grid.GetNeighbors(currentNode))
        {
            if (!neighbor.Walkable || closedSet.Contains(neighbor))
            {
                continue;
            }

            int newMovementCostToNeighbor = currentNode.GCost + GetDistance(currentNode, neighbor);
            if (newMovementCostToNeighbor < neighbor.GCost || !openSet.Contains(neighbor))
            {
                neighbor.GCost = newMovementCostToNeighbor;
                neighbor.HCost = GetDistance(neighbor, targetNode);
                neighbor.Parent = currentNode;

                if (!openSet.Contains(neighbor))
                {
                    openSet.Add(neighbor);
                }
            }
        }
    }

    return null;
}

int GetDistance(Node nodeA, Node nodeB)
{
    int dstX = Mathf.Abs(nodeA.GridX - nodeB.GridX);
    int dstY = Mathf.Abs(nodeA.GridY - nodeB.GridY);
    return dstX + dstY;
}

List<Node> RetracePath(Node startNode, Node endNode)
{
    List<Node> path = new List<Node>();
    Node currentNode = endNode;

    while (currentNode != startNode)
    {
        path.Add(currentNode);
        currentNode = currentNode.Parent;
    }
    path.Reverse();
    return path;
}

A*算法计算量大，网格大小增加了更多复杂性，游戏环境应该动态变化。

我尝试了路径捕获、简化网格和多线程来凑合，仍然无法做出明显的改进。请提出您改进游戏系统的建议。

Answer 1

尝试在网格中进行简洁的跟踪。这可以大大提高性能。