Unity战棋游戏A*算法的代码实现，带注释

Unity中的A*（A*搜索算法）是一种用于路径finding（寻路）的启发式搜索算法，常用于实时策略游戏中的单位移动。以下是基本的A*算法在C#中的简单实现，我将添加一些关键部分的注释以帮助理解：

using UnityEngine;

// 定义一个节点类，存储当前位置、目标位置、到起点的代价和到目标的估算代价
public class AStarNode : MonoBehaviour
{
    public Transform position;
    public int gCost; // 实际代价，从起点到当前点的实际步数
    public int fCost; // 估算代价，gCost + heuristic（启发式函数）
    public AStarNode parent; // 父节点

    // 启发式函数，这里常用曼哈顿距离或欧几里得距离，这里是曼哈顿距离
    private static int heuristic(Vector3 from, Vector3 to)
    {
        return Mathf.Abs(from.x - to.x) + Mathf.Abs(from.y - to.y);
    }

    // 计算两个节点之间的代价
    public float GetTotalCost(AStarNode other)
    {
        return gCost + Heuristic(position.position, other.position.position);
    }
}

// 搜索函数，返回从起点到终点的最佳路径
public List<AStarNode> FindPath(GameObject start, GameObject end)
{
    // 初始化开放列表和关闭列表
    Queue<AStarNode> openList = new Queue<AStarNode>();
    HashSet<AStarNode> closedList = new HashSet<AStarNode>();

    // 将起点加入开放列表，并设置其gCost和fCost
    AStarNode startNode = Instantiate(new AStarNode(), start.transform.position, Quaternion.identity);
    startNode.gCost = 0;
    startNode.fCost = heuristic(start.transform.position, end.transform.position);
    openList.Enqueue(startNode);

    while (openList.Count > 0)
    {
        // 选择fCost最小的节点作为当前节点
        AStarNode current = openList.Dequeue();

        // 如果找到终点，则回溯生成路径
        if (current == end.GetComponent<AStarNode>())
            return ReconstructPath(current);

        // 将当前节点加入关闭列表
        closedList.Add(current);

        // 遍历相邻节点，计算并更新它们的gCost和fCost
        foreach (Transform neighbor in current.transform.GetComponentsInChildren<Transform>())
        {
            AStarNode neighborNode = neighbor.gameObject.GetComponent<AStarNode>();

            if (closedList.Contains(neighborNode)) continue; // 已经访问过

            int tentativeGCost = current.gCost + current.GetTotalCost(neighborNode);

            if (!openList.Contains(neighborNode) || tentativeGCost < neighborNode.gCost)
            {
                // 更新邻居节点的状态
                neighborNode.parent = current;
                neighborNode.gCost = tentativeGCost;
                neighborNode.fCost = tentativeGCost + heuristic(neighborNode.position.position, end.transform.position);

                // 如果邻居不在开放列表中，加入；否则，如果新cost更优则替换
                if (!openList.Contains(neighborNode))
                    openList.Enqueue(neighborNode);
                else
                    openList.EnqueueOrRemove(neighborNode, tentativeGCost); // 使用自定义版本的EnqueueOrRemove操作，避免插入重复元素
            }
        }
    }

    // 没有找到路径，返回空列表
    return null;
}

// 重构路径函数，通过parent属性回溯到起点
private List<AStarNode> ReconstructPath(AStarNode node)
{
    List<AStarNode> path = new List<AStarNode>();
    path.Add(node);
    while (node.parent != null)
    {
        path.Insert(0, node.parent);
        node = node.parent;
    }
    return path;
}