Unity学习记录-A星寻路

准备

路径排序

在A星寻路算法中，计算出组成路径的方格的关键是下面的等式：

$$F = G + H$$

其中：

• G是从起点A移动到该方格的移动代价
• H是从该方格移动到终点B的估算成本。H的值是乐观的，也就是说，H在计算时不会考虑障碍物、河流等地形因素。在这里，H的计算可以用Manhattan方法：横向移动的步数+纵向移动的步数
• F是方格的代价总和，F越低的方格越优先试探

数据结构准备

准备如下数据结构：

• List sortList：存储待试探的节点
• Dictionary cameFrom: 存储每个节点及其父节点(从哪里来的)

List<Vector2Int> sortList = new List<Vector2Int>();  //存储待试探的节点，可以用优先队列加快速度
Dictionary<Vector2Int, Vector2Int> cameFrom = new Dictionary<Vector2Int, Vector2Int>();  //存储每个节点及其父节点，用于找到路径后绘制路径 

开始搜索

我们可以从七点开始，检查其相邻的方格，然后向四周扩展，直到找到目标

1. 将起点加入sortList
2. 检查起点的相邻四个节点是否可以行走（非超出边界、河流、障碍物等），计算相邻合法节点的G、H、F，存入sortList中
3. 从sortList中取出代价F最小的节点，对此节点的相邻节点进行试探，如果有多个代价最小的节点，则取H较小的
4. 重复步骤3，直到找到终点

sortList.Add(start);  //起点入sortList
cameFrom[start] = new Vector2Int(-1, -1);  //起点入cameFrom
bool hasRoute = false;  //是否找到路径？开始自然还未找到

while (sortList.Count > 0)
{
    // 此处可以不排序，改为拿到最小值并移出即可
    sortList.Sort((Vector2Int a, Vector2Int b) =>
    {
        //拿出代价最小的
        if ((manhattan(start, a) + manhattan(end, a)) - (manhattan(start, b) + manhattan(end, b)) != 0)
            return (manhattan(start, a) + manhattan(end, a)) - (manhattan(start, b) + manhattan(end, b));
        else
            return manhattan(end, a) - manhattan(end, b); //此处如果两点代价相等，改为拿H值较小的
    });

    Vector2Int current = sortList[0];
    sortList.RemoveAt(0);
    
    // 找到目标位置
    if (current == end)
    {
        hasRoute = true;
        break;
    }
    
    // 四个相邻方向
    foreach (Vector2Int offset in offsets)
    {
        Vector2Int newPos = current + offset;
        // 超出边界
        if (newPos.x < 0 || newPos.y < 0 || newPos.x >= map.Count || newPos.y >= map[0].Count)
        {
            continue;
        }
        // 已经在队列中
        if (cameFrom.ContainsKey(newPos))
        {
            continue;
        }
        // 障碍物
        if (map[newPos.x][newPos.y].Find("Wallnut"))
        {
            continue;
        }
        
        // 把相邻方向格子加进队列
        sortList.Add(newPos);
        // newPos 是由于 current 添加进来的，因此current是newPos的父节点
        cameFrom[newPos] = current;
    }
}

绘制路径

找到路径后，进行路径的绘制

// 如果找到，就把路径渲染出来
if (hasRoute)
{
    Stack<Vector2Int> trace = new Stack<Vector2Int>();
    Vector2Int pos = end;
    while (cameFrom.ContainsKey(pos))
    {
        trace.Push(pos);
        pos = cameFrom[pos];
    }
    while (trace.Count > 0)
    {
        Vector2Int p = trace.Pop();
        // 通过mapComp修改sprite来进行表现
        mapComp.RenderRoute(p);
    }
}

整体代码

public IEnumerator IAStar(List<List<Transform>> map, Vector2Int start, Vector2Int end)
{
    // 此处可以用优先队列
    List<Vector2Int> sortList = new List<Vector2Int>();
    Dictionary<Vector2Int, Vector2Int> cameFrom = new Dictionary<Vector2Int, Vector2Int>();
    sortList.Add(start);
    
    cameFrom[start] = new Vector2Int(-1, -1);
    bool hasRoute = false;
    
    while (sortList.Count > 0)
    {
        // 此处可以不排序，改为拿到最小值并移出即可
        sortList.Sort((Vector2Int a, Vector2Int b) =>
        {
            if ((manhattan(start, a) + manhattan(end, a)) - (manhattan(start, b) + manhattan(end, b)) != 0)
                return (manhattan(start, a) + manhattan(end, a)) - (manhattan(start, b) + manhattan(end, b));
            else
                return manhattan(end, a) - manhattan(end, b); //此处如果两点权值相等，改为拿H值较小的
        });

        Vector2Int current = sortList[0];
        sortList.RemoveAt(0);
        // 找到目标位置
        if (current == end)
        {
            hasRoute = true;
            break;
        }
        // 四个相邻方向
        foreach (Vector2Int offset in offsets)
        {
            Vector2Int newPos = current + offset;
            // 超出边界
            if (newPos.x < 0 || newPos.y < 0 || newPos.x >= map.Count || newPos.y >= map[0].Count)
            {
                continue;
            }
            // 已经在队列中
            if (cameFrom.ContainsKey(newPos))
            {
                continue;
            }
            // 障碍物
            if (map[newPos.x][newPos.y].Find("Wallnut"))
            {
                continue;
            }
            // 把相邻方向格子加进队列
            sortList.Add(newPos);
            mapComp.RenderBox2(newPos);
            cameFrom[newPos] = current;
        }
    }
    // 如果找到，就把路径渲染出来
    if (hasRoute)
    {
        Stack<Vector2Int> trace = new Stack<Vector2Int>();
        Vector2Int pos = end;
        while (cameFrom.ContainsKey(pos))
        {
            trace.Push(pos);
            pos = cameFrom[pos];
        }
        while (trace.Count > 0)
        {
            Vector2Int p = trace.Pop();
            // 通过mapComp修改sprite来进行表现
            mapComp.RenderRoute(p);
        }
    }
}