Unity 2D网格游戏寻路问题：目标占据多Tile时的路径计算缺陷

核心解决方案思路 #

针对多Tile目标的寻路需求，核心是将寻路终点从目标区域内的单个Tile，改为目标区域周围的可行走相邻Tile，同时调整A*的启发式函数和终止条件，确保找到最优路径且不与目标重叠：

• 把目标区域的所有Tile标记为不可行走，避免路径规划到目标身上
• 启发式函数（HCost）计算当前节点到目标区域中最近Tile的距离，引导路径向最近的目标区域靠近
• 终止条件改为：当当前节点是目标区域的相邻可行走Tile时，停止寻路并返回路径

代码修改步骤 #

1. 调整寻路方法的输入参数 #

将FindPath的目标参数从单个Vector3Int改为目标区域的Tile集合IEnumerable<Vector3Int>，支持传入任意大小的目标区域：

public List<Vector3Int> FindPath(Vector3Int start, IEnumerable<Vector3Int> targetArea)

2. 修改终止条件 #

当当前节点是目标区域的相邻可行走Tile时，即视为到达终点：

// 替换原有的if (currentNode.Position == target)
if (IsAdjacentToTargetArea(currentNode.Position, targetArea))
{
    return RetracePath(startNode, currentNode);
}

3. 重写启发式距离计算 #

计算当前节点到目标区域中所有Tile的最小曼哈顿距离，替代原有的单个目标Tile距离：

private int GetMinManhattanDistanceToTarget(Vector3Int pos, IEnumerable<Vector3Int> targetArea)
{
    int minDistance = int.MaxValue;
    foreach (var targetPos in targetArea)
    {
        int distance = Mathf.Abs(pos.x - targetPos.x) + Mathf.Abs(pos.y - targetPos.y);
        if (distance < minDistance)
        {
            minDistance = distance;
        }
    }
    return minDistance;
}

4. 添加相邻判断方法 #

判断当前节点是否与目标区域相邻，且自身是可行走Tile：

private bool IsAdjacentToTargetArea(Vector3Int pos, IEnumerable<Vector3Int> targetArea)
{
    foreach (var targetPos in targetArea)
    {
        // 检查上下左右四个方向是否相邻
        if (Mathf.Abs(pos.x - targetPos.x) + Mathf.Abs(pos.y - targetPos.y) == 1)
        {
            return _region.IsWalkable(pos);
        }
    }
    return false;
}

5. 排除目标区域Tile的寻路 #

在遍历邻居时，额外排除目标区域内的Tile，避免路径规划到目标身上：

// 替换原有的邻居判断条件
if (closedSet.Contains(neighborPos) || !_region.IsWalkable(neighborPos) || targetArea.Contains(neighborPos))
    continue;

修改后的完整代码 #

using UnityEngine;
using System.Collections.Generic;
using System.Linq;

public class AStarPathfinder
{
    private NavigationRegion _region;

    public AStarPathfinder(NavigationRegion region)
    {
        _region = region;
    }

    // 修改目标参数为目标区域的Tile集合
    public List<Vector3Int> FindPath(Vector3Int start, IEnumerable<Vector3Int> targetArea)
    {
        Dictionary<Vector3Int, Node> nodes = new Dictionary<Vector3Int, Node>();
        List<Node> openList = new List<Node>();
        HashSet<Vector3Int> closedSet = new HashSet<Vector3Int>();

        Node startNode = new Node(start);
        startNode.GCost = 0;
        // 计算到目标区域的最小距离作为初始HCost
        startNode.HCost = GetMinManhattanDistanceToTarget(start, targetArea);
        nodes[start] = startNode;
        openList.Add(startNode);

        while (openList.Count > 0)
        {
            // 优化：用OrderByDescending或者PriorityQueue提升效率，这里保留原有逻辑
            Node currentNode = openList.OrderBy(x => x.FCost).First();

            openList.Remove(currentNode);
            closedSet.Add(currentNode.Position);

            // 终止条件：当前节点是目标区域的相邻可行走Tile
            if (IsAdjacentToTargetArea(currentNode.Position, targetArea))
            {
                return RetracePath(startNode, currentNode);
            }

            foreach (Vector3Int neighborPos in GetNeighbors(currentNode.Position))
            {
                // 排除目标区域内的Tile
                if (closedSet.Contains(neighborPos) || !_region.IsWalkable(neighborPos) || targetArea.Contains(neighborPos))
                    continue;

                int tentativeGCost = currentNode.GCost + 1;
                Node neighbor;

                if (!nodes.TryGetValue(neighborPos, out neighbor))
                {
                    neighbor = new Node(neighborPos);
                    nodes[neighborPos] = neighbor;
                }

                if (tentativeGCost < neighbor.GCost)
                {
                    neighbor.GCost = tentativeGCost;
                    // 更新HCost为到目标区域的最小距离
                    neighbor.HCost = GetMinManhattanDistanceToTarget(neighborPos, targetArea);
                    neighbor.Parent = currentNode;

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

        return null;
    }

    private List<Vector3Int> RetracePath(Node start, Node end)
    {
        List<Vector3Int> path = new List<Vector3Int>();
        Node currentNode = end;

        while (currentNode != start)
        {
            path.Add(currentNode.Position);
            currentNode = currentNode.Parent;
        }

        path.Reverse();
        return path;
    }

    // 计算到目标区域的最小曼哈顿距离
    private int GetMinManhattanDistanceToTarget(Vector3Int pos, IEnumerable<Vector3Int> targetArea)
    {
        int minDistance = int.MaxValue;
        foreach (var targetPos in targetArea)
        {
            int distance = Mathf.Abs(pos.x - targetPos.x) + Mathf.Abs(pos.y - targetPos.y);
            if (distance < minDistance)
            {
                minDistance = distance;
            }
        }
        return minDistance;
    }

    // 判断当前节点是否与目标区域相邻且可行走
    private bool IsAdjacentToTargetArea(Vector3Int pos, IEnumerable<Vector3Int> targetArea)
    {
        foreach (var targetPos in targetArea)
        {
            if (Mathf.Abs(pos.x - targetPos.x) + Mathf.Abs(pos.y - targetPos.y) == 1)
            {
                return _region.IsWalkable(pos);
            }
        }
        return false;
    }

    private List<Vector3Int> GetNeighbors(Vector3Int pos)
    {
        return new List<Vector3Int>
        {
            new Vector3Int(pos.x + 1, pos.y, pos.z),
            new Vector3Int(pos.x - 1, pos.y, pos.z),
            new Vector3Int(pos.x, pos.y + 1, pos.z),
            new Vector3Int(pos.x, pos.y - 1, pos.z)
        };
    }
}

// 保留原有的Node类（假设你已有这个定义）
public class Node
{
    public Vector3Int Position;
    public int GCost;
    public int HCost;
    public Node Parent;

    public int FCost => GCost + HCost;

    public Node(Vector3Int position)
    {
        Position = position;
        GCost = int.MaxValue;
        HCost = 0;
        Parent = null;
    }
}

额外优化建议 #

• 使用PriorityQueue替代List作为openList：原代码中OrderBy(x => x.FCost).First()的时间复杂度较高，改用PriorityQueue<Node, int>可以将每次获取最小FCost节点的操作从O(n)降到O(logn)，提升寻路效率
• 缓存目标区域的相邻Tile：如果目标区域不频繁移动，可以提前计算并缓存目标区域的所有相邻可行走Tile，避免每次寻路都遍历目标区域判断相邻关系

内容的提问来源于stack exchange，提问作者Lucas Duran