第4章 Unity引擎中A*寻路算法的深度解析与高级应用实践

4.1 游戏寻路系统的架构设计思想

在商业级游戏开发中，寻路系统是人工智能模块的核心组成部分，它直接决定了非玩家角色（NPC）在虚拟世界中的移动智能和表现真实性。一个高效、可靠的寻路系统不仅需要提供从起点到终点的最优路径，更要考虑游戏世界的动态性、角色行为的多样性以及系统性能的平衡性。

从系统架构的角度看，现代游戏寻路解决方案通常采用分层设计。最底层是空间表示层，负责将连续的三维游戏世界离散化为计算机可处理的导航数据结构；中间层是算法核心层，实现路径搜索和优化的具体逻辑；最上层是应用接口层，为游戏逻辑提供简洁易用的寻路功能调用。这种分层设计保证了系统的可维护性和扩展性，允许开发团队根据不同场景需求调整各层实现。

在Unity引擎的生态中，寻路系统的实现需要考虑引擎特有的技术特性。Unity的导航网格系统提供了基础的寻路功能，但在复杂游戏场景中往往需要更精细的控制。商业项目中的寻路系统必须处理多种复杂情况：动态障碍物的实时避让、多角色协同移动的路径协调、不同地形对移动速度的影响、以及敌人AI的战术路径选择等。这些需求推动开发者超越基础的A*算法实现，构建更加智能的寻路解决方案。

性能考量是寻路系统设计中的关键因素。在开放世界游戏或大规模多人在线游戏中，可能有成百上千的AI角色同时进行路径计算。传统的同步寻路计算会迅速耗尽CPU资源，导致游戏帧率下降。因此，现代寻路系统通常采用异步计算、路径缓存、空间分区等优化技术，确保在大规模场景下仍能保持流畅的游戏体验。

本专题将从A寻路算法的基础原理出发，逐步深入到商业项目中的高级应用实践。我们将探讨三种不同的导航图构建方式，分析A算法的工作机制与优化策略，实现战术寻路系统，并最终构建一个完整的、可用于生产环境的寻路解决方案。所有代码实现均采用Allman风格和驼峰命名法，确保在Unity 2021.3.8f1c1环境中能够稳定运行。

4.2 导航图构建的三种核心技术路径

4.2.1 寻路系统的基本概念体系

在深入技术实现之前，我们需要建立统一的术语体系。寻路系统中的核心概念包括：

1. 节点（Node）：寻路计算的基本单元，代表游戏世界中的一个可通行位置。节点的粒度决定了寻路的精度和计算复杂度。

2. 边（Edge）：连接两个节点的通路，代表角色可以从一个位置移动到另一个位置。边通常带有权重，表示移动的代价（如距离、时间、危险程度等）。

3. 导航图（Navigation Graph）：由节点和边构成的图结构，抽象表示游戏世界的可通行区域。导航图的质量直接决定了寻路结果的合理性。

4. 启发函数（Heuristic Function）：用于估计从当前节点到目标节点代价的函数，是A*算法高效性的关键。良好的启发函数能够显著减少搜索范围。

5. 开放列表（Open List）和关闭列表（Closed List）：A*算法中用于管理待探索节点和已探索节点的数据结构。

在Unity中实现寻路系统时，还需要考虑与引擎现有系统的集成。Unity的NavMesh系统已经提供了基础的导航功能，但自定义寻路系统能够提供更精细的控制和更复杂的功能。以下是一个基础寻路节点的实现，作为我们后续实现的基石：

using UnityEngine;
using System.Collections.Generic;

public class PathNode : System.IComparable<PathNode>
{
    // 节点在导航图中的位置
    private Vector3 worldPosition;
    private int gridX;
    private int gridY;
    
    // A*算法所需的核心数据
    private int gCost; // 从起点到当前节点的实际代价
    private int hCost; // 从当前节点到终点的启发式估计代价
    private int fCost; // 总代价 (f = g + h)
    
    // 节点状态和关系
    private bool isWalkable;
    private PathNode parentNode;
    private List<PathNode> neighborNodes;
    
    // 地形属性
    private float terrainPenalty;
    private NodeType nodeType;
    
    public enum NodeType
    {
        Normal,
        DifficultTerrain,
        DangerousArea,
        RestrictedZone
    }
    
    public PathNode(Vector3 position, int x, int y, bool walkable)
    {
        worldPosition = position;
        gridX = x;
        gridY = y;
        isWalkable = walkable;
        
        gCost = int.MaxValue;
        hCost = 0;
        fCost = int.MaxValue;
        
        parentNode = null;
        neighborNodes = new List<PathNode>();
        terrainPenalty = 0f;
        nodeType = NodeType.Normal;
    }
    
    // 计算总代价
    public void CalculateFCost()
    {
        fCost = gCost + hCost;
    }
    
    // 实现IComparable接口用于优先队列排序
    public int CompareTo(PathNode otherNode)
    {
        if (otherNode == null) return 1;
        
        // 首先比较fCost
        int compare = fCost.CompareTo(otherNode.fCost);
        if (compare == 0)
        {
            // 如果fCost相同，比较hCost（倾向于更接近目标的节点）
            compare = hCost.CompareTo(otherNode.hCost);
        }
        return compare;
    }
    
    // 重置节点状态（用于新的寻路计算）
    public void Reset()
    {
        gCost = int.MaxValue;
        hCost = 0;
        fCost = int.MaxValue;
        parentNode = null;
    }
    
    // 属性访问器
    public Vector3 WorldPosition
    {
        get { return worldPosition; }
    }
    
    public int GridX
    {
        get { return gridX; }
    }
    
    public int GridY
    {
        get { return gridY; }
    }
    
    public int GCost
    {
        get { return gCost; }
        set { gCost = value; }
    }
    
    public int HCost
    {
        get { return hCost; }
        set { hCost = value; }
    }
    
    public int FCost
    {
        get { return fCost; }
    }
    
    public bool IsWalkable
    {
        get { return isWalkable; }
        set { isWalkable = value; }
    }
    
    public PathNode ParentNode
    {
        get { return parentNode; }
        set { parentNode = value; }
    }
    
    public List<PathNode> NeighborNodes
    {
        get { return neighborNodes; }
    }
    
    public float TerrainPenalty
    {
        get { return terrainPenalty; }
        set { terrainPenalty = Mathf.Max(0f, value); }
    }
    
    public NodeType Type
    {
        get { return nodeType; }
        set { nodeType = value; }
    }
    
    // 计算到另一个节点的移动代价（考虑地形惩罚）
    public int GetMovementCostTo(PathNode targetNode)
    {
        // 基础代价为节点间的曼哈顿距离
        int baseCost = Mathf.Abs(gridX - targetNode.gridX) + Mathf.Abs(gridY - targetNode.gridY);
        
        // 应用地形惩罚
        float penaltyMultiplier = 1f + (terrainPenalty + targetNode.terrainPenalty) / 2f;
        
        return Mathf.RoundToInt(baseCost * penaltyMultiplier);
    }
    
    // 添加相邻节点
    public void AddNeighbor(PathNode neighbor)
    {
        if (neighbor != null && !neighborNodes.Contains(neighbor))
        {
            neighborNodes.Add(neighbor);
        }
    }
    
    // 移除相邻节点（用于动态障碍物）
    public void RemoveNeighbor(PathNode neighbor)
    {
        if (neighbor != null)
        {
            neighborNodes.Remove(neighbor);
        }
    }
    
    // 检查是否为同一位置
    public bool IsSamePosition(PathNode otherNode)
    {
        if (otherNode == null) return false;
        return gridX == otherNode.gridX && gridY == otherNode.gridY;
    }
    
    public override string ToString()
    {
        return $"Node({gridX},{gridY}) at {worldPosition} - Walkable: {isWalkable}, FCost: {fCost}";
    }
}

4.2.2 基于网格单元的导航图构建技术

网格导航图是最直观、最易于实现的寻路空间表示方法。它将游戏世界划分为均匀的网格单元，每个单元对应一个节点。这种方法特别适合策略游戏、回合制游戏或基于瓦片的地图。

网格导航图的优势在于实现简单、计算高效，且易于处理规则地形。然而，它的缺点也很明显：内存消耗与网格分辨率成正比，对于大型开放世界可能产生巨大的内存开销；同时，对角移动的代价计算需要特殊处理，以避免"锯齿状"路径。

以下是网格导航图的完整实现，包含动态障碍物支持和多层级地形处理：

using UnityEngine;
using System.Collections.Generic;

public class GridBasedNavigationGraph : MonoBehaviour
{
    [Header("网格配置")]
    [SerializeField] private Vector2 gridWorldSize = new Vector2(50, 50);
    [SerializeField] private float nodeRadius = 0.5f;
    [SerializeField] private LayerMask unwalkableMask = ~0;
    [SerializeField] private TerrainType[] walkableRegions;
    
    [Header("高级配置")]
    [SerializeField] private bool useHeightDifference = true;
    [SerializeField] private float maxWalkableHeight = 1.0f;
    [SerializeField] private bool allowDiagonalMovement = true;
    [SerializeField] private bool cutCorners = false;
    
    private float nodeDiameter;
    private int gridSizeX, gridSizeY;
    private PathNode[,] nodeGrid;
    private LayerMask walkableMask;
    private Dictionary<int, int> walkableRegionsDictionary;
    
    [System.Serializable]
    public class TerrainType
    {
        public LayerMask terrainMask;
        public int terrainPenalty;
    }
    
    void Awake()
    {
        InitializeNavigationGrid();
    }
    
    public void InitializeNavigationGrid()
    {
        nodeDiameter = nodeRadius * 2;
        gridSizeX = Mathf.RoundToInt(gridWorldSize.x / nodeDiameter);
        gridSizeY = Mathf.RoundToInt(gridWorldSize.y / nodeDiameter);
        
        // 初始化可通行区域字典
        walkableRegionsDictionary = new Dictionary<int, int>();
        walkableMask = 0;
        
        foreach (TerrainType region in walkableRegions)
        {
            walkableMask.value |= region.terrainMask.value;
            int layer = (int)Mathf.Log(region.terrainMask.value, 2);
            walkableRegionsDictionary.Add(layer, region.terrainPenalty);
        }
        
        CreateNodeGrid();
        BuildNeighborConnections();
        
        Debug.Log($"导航网格初始化完成: {gridSizeX}x{gridSizeY} 个节点");
    }
    
    private void CreateNodeGrid()
    {
        nodeGrid = new PathNode[gridSizeX, gridSizeY];
        Vector3 worldBottomLeft = transform.position - 
            Vector3.right * gridWorldSize.x / 2 - 
            Vector3.forward * gridWorldSize.y / 2;
        
        for (int x = 0; x < gridSizeX; x++)
        {
            for (int y = 0; y < gridSizeY; y++)
            {
                Vector3 worldPoint = worldBottomLeft + 
                    Vector3.right * (x * nodeDiameter + nodeRadius) + 
                    Vector3.forward * (y * nodeDiameter + nodeRadius);
                
                bool walkable = CheckNodeWalkability(worldPoint);
                PathNode newNode = new PathNode(worldPoint, x, y, walkable);
                
                // 设置地形惩罚
                if (walkable)
                {
                    ApplyTerrainPenalty(newNode, worldPoint);
                }
                
                nodeGrid[x, y] = newNode;
            }
        }
    }
    
    private bool CheckNodeWalkability(Vector3 worldPoint)
    {
        // 基础碰撞检测
        bool hitCollider = Physics.CheckSphere(worldPoint, nodeRadius, unwalkableMask);
        
        if (hitCollider)
        {
            return false;
        }
        
        // 高度差检测
        if (useHeightDifference)
        {
            RaycastHit hit;
            if (Physics.Raycast(worldPoint + Vector3.up * 10, Vector3.down, out hit, 20, walkableMask))
            {
                float heightDifference = Mathf.Abs(worldPoint.y - hit.point.y);
                if (heightDifference > maxWalkableHeight)
                {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    private void ApplyTerrainPenalty(PathNode node, Vector3 worldPoint)
    {
        // 使用射线检测确定地形类型
        RaycastHit hit;
        if (Physics.Raycast(worldPoint + Vector3.up * 10, Vector3.down, out hit, 20, walkableMask))
        {
            int hitLayer = hit.collider.gameObject.layer;
            if (walkableRegionsDictionary.ContainsKey(hitLayer))
            {
                node.TerrainPenalty = walkableRegionsDictionary[hitLayer];
                
                // 根据地形类型设置节点类型
                if (node.TerrainPenalty > 50)
                {
                    node.Type = PathNode.NodeType.DifficultTerrain;
                }
            }
        }
    }
    
    private void BuildNeighborConnections()
    {
        for (int x = 0; x < gridSizeX; x++)
        {
            for (int y = 0; y < gridSizeY; y++)
            {
                PathNode currentNode = nodeGrid[x, y];
                
                if (!currentNode.IsWalkable) continue;
                
                // 添加相邻节点
                AddValidNeighbors(currentNode, x, y);
            }
        }
    }
    
    private void AddValidNeighbors(PathNode node, int x, int y)
    {
        // 四方向邻居
        AddNeighborIfValid(node, x, y + 1); // 上
        AddNeighborIfValid(node, x, y - 1); // 下
        AddNeighborIfValid(node, x - 1, y); // 左
        AddNeighborIfValid(node, x + 1, y); // 右
        
        if (allowDiagonalMovement)
        {
            // 对角线邻居
            bool upWalkable = IsNodeWalkable(x, y + 1);
            bool downWalkable = IsNodeWalkable(x, y - 1);
            bool leftWalkable = IsNodeWalkable(x - 1, y);
            bool rightWalkable = IsNodeWalkable(x + 1, y);
            
            // 左上
            if (upWalkable && leftWalkable)
            {
                if (!cutCorners || (IsNodeWalkable(x, y + 1) && IsNodeWalkable(x - 1, y)))
                {
                    AddNeighborIfValid(node, x - 1, y + 1);
                }
            }
            
            // 右上
            if (upWalkable && rightWalkable)
            {
                if (!cutCorners || (IsNodeWalkable(x, y + 1) && IsNodeWalkable(x + 1, y)))
                {
                    AddNeighborIfValid(node, x + 1, y + 1);
                }
            }
            
            // 左下
            if (downWalkable && leftWalkable)
            {
                if (!cutCorners || (IsNodeWalkable(x, y - 1) && IsNodeWalkable(x - 1, y)))
                {
                    AddNeighborIfValid(node, x - 1, y - 1);
                }
            }
            
            // 右下
            if (downWalkable && rightWalkable)
            {
                if (!cutCorners || (IsNodeWalkable(x, y - 1) && IsNodeWalkable(x + 1, y)))
                {
                    AddNeighborIfValid(node, x + 1, y - 1);
                }
            }
        }
    }
    
    private void AddNeighborIfValid(PathNode node, int neighborX, int neighborY)
    {
        if (IsInGridBounds(neighborX, neighborY))
        {
            PathNode neighbor = nodeGrid[neighborX, neighborY];
            if (neighbor.IsWalkable)
            {
                node.AddNeighbor(neighbor);
            }
        }
    }
    
    private bool IsNodeWalkable(int x, int y)
    {
        if (!IsInGridBounds(x, y)) return false;
        return nodeGrid[x, y].IsWalkable;
    }
    
    private bool IsInGridBounds(int x, int y)
    {
        return x >= 0 && x < gridSizeX && y >= 0 && y < gridSizeY;
    }
    
    // 将世界坐标转换为网格坐标
    public PathNode GetNodeFromWorldPoint(Vector3 worldPosition)
    {
        float percentX = (worldPosition.x + gridWorldSize.x / 2) / gridWorldSize.x;
        float percentY = (worldPosition.z + gridWorldSize.y / 2) / gridWorldSize.y;
        
        percentX = Mathf.Clamp01(percentX);
        percentY = Mathf.Clamp01(percentY);
        
        int x = Mathf.RoundToInt((gridSizeX - 1) * percentX);
        int y = Mathf.RoundToInt((gridSizeY - 1) * percentY);
        
        if (IsInGridBounds(x, y))
        {
            return nodeGrid[x, y];
        }
        
        return null;
    }
    
    // 动态更新节点通行性（用于处理动态障碍物）
    public void UpdateNodeWalkability(Vector3 worldPosition, bool walkable)
    {
        PathNode node = GetNodeFromWorldPoint(worldPosition);
        if (node != null)
        {
            node.IsWalkable = walkable;
            
            // 更新相邻节点的连接
            UpdateNeighborConnections(node);
        }
    }
    
    private void UpdateNeighborConnections(PathNode node)
    {
        int x = node.GridX;
        int y = node.GridY;
        
        // 清空当前节点的邻居列表
        node.NeighborNodes.Clear();
        
        // 如果节点不可通行，也要从邻居节点中移除
        if (!node.IsWalkable)
        {
            RemoveNodeFromNeighbors(node);
            return;
        }
        
        // 重新添加有效的邻居
        AddValidNeighbors(node, x, y);
        
        // 更新周围节点的连接
        UpdateSurroundingNodes(x, y);
    }
    
    private void RemoveNodeFromNeighbors(PathNode node)
    {
        int x = node.GridX;
        int y = node.GridY;
        
        // 从所有相邻节点中移除当前节点
        for (int i = -1; i <= 1; i++)
        {
            for (int j = -1; j <= 1; j++)
            {
                if (i == 0 && j == 0) continue;
                
                int neighborX = x + i;
                int neighborY = y + j;
                
                if (IsInGridBounds(neighborX, neighborY))
                {
                    PathNode neighbor = nodeGrid[neighborX, neighborY];
                    neighbor.RemoveNeighbor(node);
                }
            }
        }
    }
    
    private void UpdateSurroundingNodes(int centerX, int centerY)
    {
        // 更新周围3x3区域内的节点连接
        for (int x = -1; x <= 1; x++)
        {
            for (int y = -1; y <= 1; y++)
            {
                int currentX = centerX + x;
                int currentY = centerY + y;
                
                if (IsInGridBounds(currentX, currentY))
                {
                    PathNode currentNode = nodeGrid[currentX, currentY];
                    if (currentNode.IsWalkable)
                    {
                        // 清空并重新构建邻居连接
                        currentNode.NeighborNodes.Clear();
                        AddValidNeighbors(currentNode, currentX, currentY);
                    }
                }
            }
        }
    }
    
    // 获取网格中的所有可行走节点
    public List<PathNode> GetAllWalkableNodes()
    {
        List<PathNode> walkableNodes = new List<PathNode>();
        
        for (int x = 0; x < gridSizeX; x++)
        {
            for (int y = 0; y < gridSizeY; y++)
            {
                if (nodeGrid[x, y].IsWalkable)
                {
                    walkableNodes.Add(nodeGrid[x, y]);
                }
            }
        }
        
        return walkableNodes;
    }
    
    // 获取一定范围内的所有节点
    public List<PathNode> GetNodesInRadius(Vector3 center, float radius)
    {
        List<PathNode> nodesInRadius = new List<PathNode>();
        PathNode centerNode = GetNodeFromWorldPoint(center);
        
        if (centerNode == null) return nodesInRadius;
        
        int radiusInNodes = Mathf.CeilToInt(radius / nodeDiameter);
        
        for (int x = -radiusInNodes; x <= radiusInNodes; x++)
        {
            for (int y = -radiusInNodes; y <= radiusInNodes; y++)
            {
                int checkX = centerNode.GridX + x;
                int checkY = centerNode.GridY + y;
                
                if (IsInGridBounds(checkX, checkY))
                {
                    PathNode node = nodeGrid[checkX, checkY];
                    if (Vector3.Distance(center, node.WorldPosition) <= radius)
                    {
                        nodesInRadius.Add(node);
                    }
                }
            }
        }
        
        return nodesInRadius;
    }
    
    void OnDrawGizmosSelected()
    {
        Gizmos.DrawWireCube(transform.position, new Vector3(gridWorldSize.x, 1, gridWorldSize.y));
        
        if (nodeGrid != null)
        {
            foreach (PathNode node in nodeGrid)
            {
                Gizmos.color = node.IsWalkable ? Color.white : Color.red;
                
                // 根据节点类型调整颜色
                switch (node.Type)
                {
                    case PathNode.NodeType.DifficultTerrain:
                        Gizmos.color = Color.yellow;
                        break;
                    case PathNode.NodeType.DangerousArea:
                        Gizmos.color = new Color(1, 0.5f, 0); // 橙色
                        break;
                    case PathNode.NodeType.RestrictedZone:
                        Gizmos.color = Color.magenta;
                        break;
                }
                
                Gizmos.DrawCube(node.WorldPosition, Vector3.one * (nodeDiameter - 0.1f));
            }
        }
    }
    
    public int MaxGridSize
    {
        get { return Mathf.Max(gridSizeX, gridSizeY); }
    }
    
    public float NodeDiameter
    {
        get { return nodeDiameter; }
    }
    
    public Vector2 GridWorldSize
    {
        get { return gridWorldSize; }
    }
}

4.2.3 基于可视点的导航图构建方案

可视点导航图（也称为航点图）是另一种常见的寻路空间表示方法。与网格系统不同，它只在关键位置（如拐角、门口、开阔区域中心）放置节点。这种方法特别适用于室内场景或具有明显通道结构的环境。

可视点导航图的主要优势在于节点数量远少于网格系统，从而减少了内存占用和计算复杂度。同时，它生成的路径更加自然，避免了网格系统中的"锯齿"现象。然而，它的构建过程更为复杂，需要算法自动识别关键位置，或者依赖设计师手动放置航点。

以下是可视点导航图的实现，包含自动航点生成和动态连接更新：

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

public class VisibilityPointNavigationGraph : MonoBehaviour
{
    [Header("生成参数")]
    [SerializeField] private float pointSpacing = 2.0f;
    [SerializeField] private float connectionDistance = 5.0f;
    [SerializeField] private LayerMask obstacleMask = ~0;
    [SerializeField] private float agentRadius = 0.5f;
    
    [Header("自动生成")]
    [SerializeField] private bool autoGeneratePoints = true;
    [SerializeField] private Vector3 generationBounds = new Vector3(50, 10, 50);
    [SerializeField] private int maxGenerationAttempts = 1000;
    
    private List<VisibilityPoint> allPoints;
    private Dictionary<VisibilityPoint, List<VisibilityPoint>> connections;
    
    public class VisibilityPoint
    {
        public Vector3 Position { get; private set; }
        public int ID { get; private set; }
        public PointType Type { get; set; }
        
        public enum PointType
        {
            General,
            Corner,
            Doorway,
            StrategicPosition
        }
        
        public VisibilityPoint(Vector3 position, int id)
        {
            Position = position;
            ID = id;
            Type = PointType.General;
        }
        
        public override bool Equals(object obj)
        {
            if (obj is VisibilityPoint other)
            {
                return ID == other.ID;
            }
            return false;
        }
        
        public override int GetHashCode()
        {
            return ID.GetHashCode();
        }
    }
    
    void Awake()
    {
        InitializeVisibilityGraph();
    }
    
    private void InitializeVisibilityGraph()
    {
        allPoints = new List<VisibilityPoint>();
        connections = new Dictionary<VisibilityPoint, List<VisibilityPoint>>();
        
        if (autoGeneratePoints)
        {
            GenerateVisibilityPoints();
        }
        
        BuildPointConnections();
        
        Debug.Log($"可视点导航图初始化完成: {allPoints.Count} 个点");
    }
    
    private void GenerateVisibilityPoints()
    {
        Vector3 boundsMin = transform.position - generationBounds / 2;
        Vector3 boundsMax = transform.position + generationBounds / 2;
        
        int pointsGenerated = 0;
        int attempts = 0;
        
        while (pointsGenerated < maxGenerationAttempts && attempts < maxGenerationAttempts * 2)
        {
            Vector3 randomPosition = new Vector3(
                Random.Range(boundsMin.x, boundsMax.x),
                Random.Range(boundsMin.y, boundsMax.y),
                Random.Range(boundsMin.z, boundsMax.z)
            );
            
            // 检查位置是否可行走
            if (IsPositionWalkable(randomPosition))
            {
                // 检查是否与其他点太近
                bool tooClose = false;
                foreach (VisibilityPoint existingPoint in allPoints)
                {
                    if (Vector3.Distance(randomPosition, existingPoint.Position) < pointSpacing)
                    {
                        tooClose = true;
                        break;
                    }
                }
                
                if (!tooClose)
                {
                    VisibilityPoint newPoint = new VisibilityPoint(randomPosition, allPoints.Count);
                    DeterminePointType(newPoint, randomPosition);
                    
                    allPoints.Add(newPoint);
                    connections[newPoint] = new List<VisibilityPoint>();
                    pointsGenerated++;
                }
            }
            
            attempts++;
        }
        
        // 在边界和拐角处添加额外点
        AddStrategicPoints();
    }
    
    private bool IsPositionWalkable(Vector3 position)
    {
        // 检查地面
        if (!Physics.Raycast(position + Vector3.up * 5, Vector3.down, 10, obstacleMask))
        {
            return false;
        }
        
        // 检查周围空间
        Collider[] colliders = Physics.OverlapSphere(position, agentRadius, obstacleMask);
        return colliders.Length == 0;
    }
    
    private void DeterminePointType(VisibilityPoint point, Vector3 position)
    {
        // 分析周围环境来确定点类型
        int wallCount = CountNearbyWalls(position, pointSpacing * 1.5f);
        
        if (wallCount >= 2)
        {
            point.Type = VisibilityPoint.PointType.Corner;
        }
        else
        {
            // 检查是否是门口或狭窄通道
            RaycastHit hit;
            if (Physics.SphereCast(position, agentRadius * 0.5f, Vector3.forward, out hit, pointSpacing, obstacleMask) ||
                Physics.SphereCast(position, agentRadius * 0.5f, Vector3.right, out hit, pointSpacing, obstacleMask))
            {
                point.Type = VisibilityPoint.PointType.Doorway;
            }
        }
    }
    
    private int CountNearbyWalls(Vector3 position, float checkDistance)
    {
        int wallCount = 0;
        Vector3[] directions = {
            Vector3.forward, Vector3.back, Vector3.left, Vector3.right
        };
        
        foreach (Vector3 direction in directions)
        {
            RaycastHit hit;
            if (Physics.Raycast(position, direction, out hit, checkDistance, obstacleMask))
            {
                wallCount++;
            }
        }
        
        return wallCount;
    }
    
    private void AddStrategicPoints()
    {
        // 在边界处添加点
        AddBoundaryPoints();
        
        // 在已有点之间添加中间点（如果距离太远）
        AddIntermediatePoints();
    }
    
    private void AddBoundaryPoints()
    {
        Vector3 boundsMin = transform.position - generationBounds / 2;
        Vector3 boundsMax = transform.position + generationBounds / 2;
        
        // 在地图边界均匀分布点
        float boundarySpacing = pointSpacing * 2;
        
        // 添加X方向的边界点
        for (float x = boundsMin.x; x <= boundsMax.x; x += boundarySpacing)
        {
            AddPointIfValid(new Vector3(x, boundsMin.y, boundsMin.z));
            AddPointIfValid(new Vector3(x, boundsMin.y, boundsMax.z));
        }
        
        // 添加Z方向的边界点
        for (float z = boundsMin.z; z <= boundsMax.z; z += boundarySpacing)
        {
            AddPointIfValid(new Vector3(boundsMin.x, boundsMin.y, z));
            AddPointIfValid(new Vector3(boundsMax.x, boundsMin.y, z));
        }
    }
    
    private void AddPointIfValid(Vector3 position)
    {
        if (IsPositionWalkable(position))
        {
            VisibilityPoint newPoint = new VisibilityPoint(position, allPoints.Count);
            newPoint.Type = VisibilityPoint.PointType.StrategicPosition;
            allPoints.Add(newPoint);
            connections[newPoint] = new List<VisibilityPoint>();
        }
    }
    
    private void AddIntermediatePoints()
    {
        List<VisibilityPoint> pointsToAdd = new List<VisibilityPoint>();
        
        // 检查所有点对，如果距离太远则添加中间点
        for (int i = 0; i < allPoints.Count; i++)
        {
            for (int j = i + 1; j < allPoints.Count; j++)
            {
                VisibilityPoint pointA = allPoints[i];
                VisibilityPoint pointB = allPoints[j];
                
                float distance = Vector3.Distance(pointA.Position, pointB.Position);
                if (distance > connectionDistance * 1.5f)
                {
                    // 在中间位置添加点
                    Vector3 midPosition = (pointA.Position + pointB.Position) / 2;
                    
                    if (IsPositionWalkable(midPosition) && HasLineOfSight(pointA.Position, midPosition))
                    {
                        VisibilityPoint midPoint = new VisibilityPoint(midPosition, allPoints.Count + pointsToAdd.Count);
                        midPoint.Type = VisibilityPoint.PointType.General;
                        pointsToAdd.Add(midPoint);
                    }
                }
            }
        }
        
        // 添加新点到图中
        foreach (VisibilityPoint newPoint in pointsToAdd)
        {
            allPoints.Add(newPoint);
            connections[newPoint] = new List<VisibilityPoint>();
        }
    }
    
    private void BuildPointConnections()
    {
        // 重置所有连接
        foreach (var connectionList in connections.Values)
        {
            connectionList.Clear();
        }
        
        // 为每个点建立连接
        for (int i = 0; i < allPoints.Count; i++)
        {
            VisibilityPoint pointA = allPoints[i];
            
            for (int j = i + 1; j < allPoints.Count; j++)
            {
                VisibilityPoint pointB = allPoints[j];
                
                float distance = Vector3.Distance(pointA.Position, pointB.Position);
                
                // 如果点在连接距离内且有视线
                if (distance <= connectionDistance && HasLineOfSight(pointA.Position, pointB.Position))
                {
                    connections[pointA].Add(pointB);
                    connections[pointB].Add(pointA);
                }
            }
        }
        
        // 确保图的连通性
        EnsureGraphConnectivity();
    }
    
    private bool HasLineOfSight(Vector3 from, Vector3 to)
    {
        Vector3 direction = to - from;
        float distance = direction.magnitude;
        
        // 使用球体投射来考虑代理半径
        RaycastHit hit;
        if (Physics.SphereCast(from, agentRadius, direction.normalized, out hit, distance, obstacleMask))
        {
            return false;
        }
        
        return true;
    }
    
    private void EnsureGraphConnectivity()
    {
        if (allPoints.Count == 0) return;
        
        // 使用BFS检查图的连通性
        HashSet<VisibilityPoint> visited = new HashSet<VisibilityPoint>();
        Queue<VisibilityPoint> queue = new Queue<VisibilityPoint>();
        
        // 从第一个点开始
        queue.Enqueue(allPoints[0]);
        visited.Add(allPoints[0]);
        
        while (queue.Count > 0)
        {
            VisibilityPoint current = queue.Dequeue();
            
            foreach (VisibilityPoint neighbor in connections[current])
            {
                if (!visited.Contains(neighbor))
                {
                    visited.Add(neighbor);
                    queue.Enqueue(neighbor);
                }
            }
        }
        
        // 如果图不连通，添加必要连接
        if (visited.Count < allPoints.Count)
        {
            ConnectDisconnectedComponents(visited);
        }
    }
    
    private void ConnectDisconnectedComponents(HashSet<VisibilityPoint> mainComponent)
    {
        List<VisibilityPoint> disconnectedPoints = new List<VisibilityPoint>();
        
        // 找出不在主组件中的点
        foreach (VisibilityPoint point in allPoints)
        {
            if (!mainComponent.Contains(point))
            {
                disconnectedPoints.Add(point);
            }
        }
        
        // 为每个孤立点寻找最近的主组件点并建立连接
        foreach (VisibilityPoint isolatedPoint in disconnectedPoints)
        {
            VisibilityPoint nearestMainPoint = FindNearestPointInSet(isolatedPoint, mainComponent);
            
            if (nearestMainPoint != null)
            {
                // 添加连接（即使没有视线，我们也强制连接）
                connections[isolatedPoint].Add(nearestMainPoint);
                connections[nearestMainPoint].Add(isolatedPoint);
                
                // 现在这个点也在主组件中了
                mainComponent.Add(isolatedPoint);
            }
        }
    }
    
    private VisibilityPoint FindNearestPointInSet(VisibilityPoint point, HashSet<VisibilityPoint> pointSet)
    {
        VisibilityPoint nearest = null;
        float minDistance = float.MaxValue;
        
        foreach (VisibilityPoint candidate in pointSet)
        {
            float distance = Vector3.Distance(point.Position, candidate.Position);
            if (distance < minDistance && HasLineOfSight(point.Position, candidate.Position))
            {
                minDistance = distance;
                nearest = candidate;
            }
        }
        
        return nearest;
    }
    
    // 手动添加点（用于设计师放置关键点）
    public VisibilityPoint AddManualPoint(Vector3 position, VisibilityPoint.PointType type = VisibilityPoint.PointType.General)
    {
        if (!IsPositionWalkable(position))
        {
            Debug.LogWarning($"无法在位置 {position} 添加点，该位置不可行走");
            return null;
        }
        
        VisibilityPoint newPoint = new VisibilityPoint(position, allPoints.Count);
        newPoint.Type = type;
        
        allPoints.Add(newPoint);
        connections[newPoint] = new List<VisibilityPoint>();
        
        // 更新与新点的连接
        UpdateConnectionsForPoint(newPoint);
        
        return newPoint;
    }
    
    private void UpdateConnectionsForPoint(VisibilityPoint newPoint)
    {
        foreach (VisibilityPoint existingPoint in allPoints)
        {
            if (existingPoint == newPoint) continue;
            
            float distance = Vector3.Distance(newPoint.Position, existingPoint.Position);
            
            if (distance <= connectionDistance && HasLineOfSight(newPoint.Position, existingPoint.Position))
            {
                connections[newPoint].Add(existingPoint);
                connections[existingPoint].Add(newPoint);
            }
        }
    }
    
    // 移除点及其所有连接
    public void RemovePoint(VisibilityPoint point)
    {
        if (point == null || !allPoints.Contains(point)) return;
        
        // 从所有相邻点的连接列表中移除该点
        foreach (VisibilityPoint neighbor in connections[point])
        {
            connections[neighbor].Remove(point);
        }
        
        // 移除该点的连接记录
        connections.Remove(point);
        
        // 从点列表中移除
        allPoints.Remove(point);
        
        Debug.Log($"已移除点 {point.ID}");
    }
    
    // 动态更新连接（用于处理动态障碍物）
    public void UpdateConnectionsForArea(Vector3 center, float radius)
    {
        List<VisibilityPoint> affectedPoints = GetPointsInRadius(center, radius);
        
        foreach (VisibilityPoint point in affectedPoints)
        {
            // 临时移除所有连接
            List<VisibilityPoint> oldConnections = new List<VisibilityPoint>(connections[point]);
            connections[point].Clear();
            
            // 重新评估与所有其他点的连接
            foreach (VisibilityPoint otherPoint in allPoints)
            {
                if (otherPoint == point) continue;
                
                float distance = Vector3.Distance(point.Position, otherPoint.Position);
                
                if (distance <= connectionDistance && HasLineOfSight(point.Position, otherPoint.Position))
                {
                    connections[point].Add(otherPoint);
                    
                    // 确保双向连接
                    if (!connections[otherPoint].Contains(point))
                    {
                        connections[otherPoint].Add(point);
                    }
                }
                else
                {
                    // 移除另一端的连接（如果存在）
                    connections[otherPoint].Remove(point);
                }
            }
        }
        
        // 再次确保图的连通性
        EnsureGraphConnectivity();
    }
    
    public List<VisibilityPoint> GetPointsInRadius(Vector3 center, float radius)
    {
        List<VisibilityPoint> pointsInRadius = new List<VisibilityPoint>();
        
        foreach (VisibilityPoint point in allPoints)
        {
            if (Vector3.Distance(center, point.Position) <= radius)
            {
                pointsInRadius.Add(point);
            }
        }
        
        return pointsInRadius;
    }
    
    public List<VisibilityPoint> GetAllPoints()
    {
        return new List<VisibilityPoint>(allPoints);
    }
    
    public List<VisibilityPoint> GetConnectedPoints(VisibilityPoint point)
    {
        if (connections.ContainsKey(point))
        {
            return new List<VisibilityPoint>(connections[point]);
        }
        return new List<VisibilityPoint>();
    }
    
    public VisibilityPoint GetNearestPoint(Vector3 position)
    {
        if (allPoints.Count == 0) return null;
        
        VisibilityPoint nearest = allPoints[0];
        float minDistance = Vector3.Distance(position, nearest.Position);
        
        for (int i = 1; i < allPoints.Count; i++)
        {
            float distance = Vector3.Distance(position, allPoints[i].Position);
            if (distance < minDistance)
            {
                minDistance = distance;
                nearest = allPoints[i];
            }
        }
        
        return nearest;
    }
    
    void OnDrawGizmosSelected()
    {
        if (allPoints == null) return;
        
        // 绘制所有点
        foreach (VisibilityPoint point in allPoints)
        {
            // 根据点类型设置颜色
            Color pointColor = Color.white;
            switch (point.Type)
            {
                case VisibilityPoint.PointType.Corner:
                    pointColor = Color.yellow;
                    break;
                case VisibilityPoint.PointType.Doorway:
                    pointColor = Color.cyan;
                    break;
                case VisibilityPoint.PointType.StrategicPosition:
                    pointColor = Color.magenta;
                    break;
            }
            
            Gizmos.color = pointColor;
            Gizmos.DrawSphere(point.Position, 0.3f);
            
            // 绘制连接线
            if (connections.ContainsKey(point))
            {
                Gizmos.color = Color.gray;
                foreach (VisibilityPoint connectedPoint in connections[point])
                {
                    if (point.ID < connectedPoint.ID) // 避免重复绘制
                    {
                        Gizmos.DrawLine(point.Position, connectedPoint.Position);
                    }
                }
            }
        }
        
        // 绘制生成边界
        Gizmos.color = Color.green;
        Gizmos.DrawWireCube(transform.position, generationBounds);
    }
}

4.2.4 导航网格的高级应用技术

导航网格（NavMesh）是现代游戏开发中最常用的寻路空间表示方法。它将可行走区域划分为凸多边形集合，比网格系统更节省内存，比可视点系统更精确。Unity内置的NavMesh系统提供了强大的功能，但在复杂项目中，我们仍需要扩展其能力。

以下是在Unity NavMesh基础上实现的增强型导航系统，包含动态障碍物处理、区域代价计算和多层导航支持：

using UnityEngine;
using UnityEngine.AI;
using System.Collections.Generic;

public class EnhancedNavMeshSystem : MonoBehaviour
{
    [Header("NavMesh配置")]
    [SerializeField] private float agentRadius = 0.5f;
    [SerializeField] private float agentHeight = 2.0f;
    [SerializeField] private float maxSlope = 45.0f;
    [SerializeField] private int areaMask = NavMesh.AllAreas;
    
    [Header("动态障碍物")]
    [SerializeField] private bool enableDynamicObstacles = true;
    [SerializeField] private float obstacleUpdateInterval = 0.5f;
    
    [Header("区域代价")]
    [SerializeField] private NavMeshCostArea[] costAreas;
    
    private NavMeshData navMeshData;
    private List<NavMeshBuildSource> buildSources;
    private Dictionary<int, float> areaCostDictionary;
    private Dictionary<GameObject, NavMeshObstacle> dynamicObstacles;
    private float obstacleUpdateTimer;
    
    [System.Serializable]
    public class NavMeshCostArea
    {
        public int areaType;
        public float costMultiplier = 1.0f;
        public Color debugColor = Color.white;
    }
    
    void Awake()
    {
        InitializeEnhancedNavMesh();
    }
    
    void Update()
    {
        if (enableDynamicObstacles)
        {
            UpdateDynamicObstacles();
        }
    }
    
    private void InitializeEnhancedNavMesh()
    {
        // 初始化区域代价字典
        areaCostDictionary = new Dictionary<int, float>();
        foreach (NavMeshCostArea area in costAreas)
        {
            areaCostDictionary[area.areaType] = area.costMultiplier;
        }
        
        // 初始化动态障碍物字典
        dynamicObstacles = new Dictionary<GameObject, NavMeshObstacle>();
        
        // 收集场景中的所有可导航几何体
        CollectBuildSources();
        
        // 构建导航网格
        BuildNavMesh();
        
        Debug.Log("增强型导航网格系统初始化完成");
    }
    
    private void CollectBuildSources()
    {
        buildSources = new List<NavMeshBuildSource>();
        
        // 收集所有网格渲染器和地形作为导航源
        MeshFilter[] meshFilters = FindObjectsOfType<MeshFilter>();
        foreach (MeshFilter filter in meshFilters)
        {
            if (filter.sharedMesh != null && IsWalkableSurface(filter.gameObject))
            {
                NavMeshBuildSource source = new NavMeshBuildSource();
                source.shape = NavMeshBuildSourceShape.Mesh;
                source.sourceObject = filter.sharedMesh;
                source.transform = filter.transform.localToWorldMatrix;
                source.area = GetAreaTypeForObject(filter.gameObject);
                
                buildSources.Add(source);
            }
        }
        
        // 处理地形
        Terrain[] terrains = FindObjectsOfType<Terrain>();
        foreach (Terrain terrain in terrains)
        {
            if (terrain.terrainData != null)
            {
                NavMeshBuildSource source = new NavMeshBuildSource();
                source.shape = NavMeshBuildSourceShape.Terrain;
                source.sourceObject = terrain.terrainData;
                source.transform = Matrix4x4.TRS(
                    terrain.transform.position, 
                    Quaternion.identity, 
                    Vector3.one
                );
                source.area = GetAreaTypeForObject(terrain.gameObject);
                
                buildSources.Add(source);
            }
        }
    }
    
    private bool IsWalkableSurface(GameObject obj)
    {
        // 检查对象是否有NavMeshModifier组件
        NavMeshModifier modifier = obj.GetComponent<NavMeshModifier>();
        if (modifier != null && modifier.ignoreFromBuild)
        {
            return false;
        }
        
        // 检查对象是否在可导航层
        if (((1 << obj.layer) & areaMask) == 0)
        {
            return false;
        }
        
        // 检查最大坡度
        if (obj.GetComponent<Terrain>() == null) // 地形有特殊处理
        {
            // 对于普通网格，检查表面法线
            MeshFilter filter = obj.GetComponent<MeshFilter>();
            if (filter != null && filter.sharedMesh != null)
            {
                // 简化的坡度检查 - 实际项目可能需要更精确的方法
                return true;
            }
        }
        
        return true;
    }
    
    private int GetAreaTypeForObject(GameObject obj)
    {
        // 检查NavMeshModifier
        NavMeshModifier modifier = obj.GetComponent<NavMeshModifier>();
        if (modifier != null)
        {
            return modifier.area;
        }
        
        // 根据材质或标签确定区域类型
        Renderer renderer = obj.GetComponent<Renderer>();
        if (renderer != null)
        {
            // 这里可以根据材质名称或其他属性分配区域类型
            // 例如：草地=1，沙地=2，沼泽=3等
        }
        
        // 默认区域（可通行）
        return 0;
    }
    
    private void BuildNavMesh()
    {
        NavMeshBuildSettings buildSettings = NavMesh.GetSettingsByID(0);
        buildSettings.agentRadius = agentRadius;
        buildSettings.agentHeight = agentHeight;
        buildSettings.agentSlope = maxSlope;
        
        Bounds buildBounds = CalculateBuildBounds();
        
        NavMeshData newNavMeshData = NavMeshBuilder.BuildNavMeshData(
            buildSettings,
            buildSources,
            buildBounds,
            Vector3.zero,
            Quaternion.identity
        );
        
        if (newNavMeshData != null)
        {
            if (navMeshData != null)
            {
                NavMesh.RemoveNavMeshData(navMeshData);
            }
            
            navMeshData = newNavMeshData;
            NavMesh.AddNavMeshData(navMeshData);
            
            Debug.Log($"导航网格构建完成，包含 {buildSources.Count} 个源");
        }
        else
        {
            Debug.LogError("导航网格构建失败");
        }
    }
    
    private Bounds CalculateBuildBounds()
    {
        Bounds bounds = new Bounds();
        bool hasBounds = false;
        
        foreach (NavMeshBuildSource source in buildSources)
        {
            Bounds sourceBounds;
            
            switch (source.shape)
            {
                case NavMeshBuildSourceShape.Mesh:
                    Mesh mesh = source.sourceObject as Mesh;
                    if (mesh != null)
                    {
                        sourceBounds = mesh.bounds;
                        sourceBounds = TransformBounds(sourceBounds, source.transform);
                    }
                    else
                    {
                        continue;
                    }
                    break;
                    
                case NavMeshBuildSourceShape.Terrain:
                    TerrainData terrainData = source.sourceObject as TerrainData;
                    if (terrainData != null)
                    {
                        sourceBounds = terrainData.bounds;
                        sourceBounds = TransformBounds(sourceBounds, source.transform);
                    }
                    else
                    {
                        continue;
                    }
                    break;
                    
                default:
                    continue;
            }
            
            if (!hasBounds)
            {
                bounds = sourceBounds;
                hasBounds = true;
            }
            else
            {
                bounds.Encapsulate(sourceBounds);
            }
        }
        
        if (!hasBounds)
        {
            bounds = new Bounds(Vector3.zero, Vector3.one * 10);
        }
        
        // 扩大边界以确保完全包含所有几何体
        bounds.Expand(5.0f);
        
        return bounds;
    }
    
    private Bounds TransformBounds(Bounds bounds, Matrix4x4 transform)
    {
        Vector3 center = transform.MultiplyPoint(bounds.center);
        Vector3 extents = bounds.extents;
        
        // 计算变换后的边界框
        Vector3[] corners = new Vector3[8];
        corners[0] = transform.MultiplyPoint(new Vector3(bounds.min.x, bounds.min.y, bounds.min.z));
        corners[1] = transform.MultiplyPoint(new Vector3(bounds.min.x, bounds.min.y, bounds.max.z));
        corners[2] = transform.MultiplyPoint(new Vector3(bounds.min.x, bounds.max.y, bounds.min.z));
        corners[3] = transform.MultiplyPoint(new Vector3(bounds.min.x, bounds.max.y, bounds.max.z));
        corners[4] = transform.MultiplyPoint(new Vector3(bounds.max.x, bounds.min.y, bounds.min.z));
        corners[5] = transform.MultiplyPoint(new Vector3(bounds.max.x, bounds.min.y, bounds.max.z));
        corners[6] = transform.MultiplyPoint(new Vector3(bounds.max.x, bounds.max.y, bounds.min.z));
        corners[7] = transform.MultiplyPoint(new Vector3(bounds.max.x, bounds.max.y, bounds.max.z));
        
        Vector3 min = corners[0];
        Vector3 max = corners[0];
        
        for (int i = 1; i < 8; i++)
        {
            min = Vector3.Min(min, corners[i]);
            max = Vector3.Max(max, corners[i]);
        }
        
        return new Bounds((min + max) * 0.5f, max - min);
    }
    
    private void UpdateDynamicObstacles()
    {
        obstacleUpdateTimer += Time.deltaTime;
        if (obstacleUpdateTimer >= obstacleUpdateInterval)
        {
            // 查找新添加的动态障碍物
            GameObject[] potentialObstacles = GameObject.FindGameObjectsWithTag("DynamicObstacle");
            
            foreach (GameObject obstacleObj in potentialObstacles)
            {
                if (!dynamicObstacles.ContainsKey(obstacleObj))
                {
                    AddDynamicObstacle(obstacleObj);
                }
            }
            
            // 移除已销毁的障碍物
            List<GameObject> toRemove = new List<GameObject>();
            foreach (var kvp in dynamicObstacles)
            {
                if (kvp.Key == null || kvp.Value == null)
                {
                    toRemove.Add(kvp.Key);
                }
            }
            
            foreach (GameObject removedObj in toRemove)
            {
                dynamicObstacles.Remove(removedObj);
            }
            
            obstacleUpdateTimer = 0f;
        }
    }
    
    private void AddDynamicObstacle(GameObject obstacleObj)
    {
        NavMeshObstacle obstacle = obstacleObj.GetComponent<NavMeshObstacle>();
        if (obstacle == null)
        {
            obstacle = obstacleObj.AddComponent<NavMeshObstacle>();
            
            // 根据对象尺寸设置障碍物参数
            Renderer renderer = obstacleObj.GetComponent<Renderer>();
            if (renderer != null)
            {
                Bounds bounds = renderer.bounds;
                obstacle.shape = NavMeshObstacleShape.Box;
                obstacle.size = bounds.size;
                obstacle.center = obstacleObj.transform.InverseTransformPoint(bounds.center);
            }
            else
            {
                // 默认设置
                obstacle.shape = NavMeshObstacleShape.Capsule;
                obstacle.radius = 1.0f;
                obstacle.height = 2.0f;
            }
            
            obstacle.carving = true;
            obstacle.carveOnlyStationary = false;
        }
        
        dynamicObstacles[obstacleObj] = obstacle;
        Debug.Log($"添加动态障碍物: {obstacleObj.name}");
    }
    
    // 寻路方法（考虑区域代价）
    public bool FindPathWithCost(Vector3 start, Vector3 end, out NavMeshPath path, out float totalCost)
    {
        path = new NavMeshPath();
        totalCost = 0f;
        
        if (!NavMesh.CalculatePath(start, end, areaMask, path))
        {
            return false;
        }
        
        if (path.corners.Length < 2)
        {
            return false;
        }
        
        // 计算路径总代价（考虑区域类型）
        for (int i = 0; i < path.corners.Length - 1; i++)
        {
            Vector3 segmentStart = path.corners[i];
            Vector3 segmentEnd = path.corners[i + 1];
            
            float segmentLength = Vector3.Distance(segmentStart, segmentEnd);
            float segmentCost = segmentLength;
            
            // 获取路径段的区域类型
            int areaType = GetAreaTypeForPathSegment(segmentStart, segmentEnd);
            if (areaCostDictionary.ContainsKey(areaType))
            {
                segmentCost *= areaCostDictionary[areaType];
            }
            
            totalCost += segmentCost;
        }
        
        return true;
    }
    
    private int GetAreaTypeForPathSegment(Vector3 start, Vector3 end)
    {
        // 采样路径中点以确定区域类型
        Vector3 midpoint = (start + end) * 0.5f;
        
        NavMeshHit hit;
        if (NavMesh.SamplePosition(midpoint, out hit, 1.0f, areaMask))
        {
            return hit.mask;
        }
        
        return 0; // 默认区域
    }
    
    // 获取最近的可通行点
    public bool GetNearestWalkablePoint(Vector3 position, out Vector3 result, float maxDistance = 10.0f)
    {
        NavMeshHit hit;
        if (NavMesh.SamplePosition(position, out hit, maxDistance, areaMask))
        {
            result = hit.position;
            return true;
        }
        
        result = position;
        return false;
    }
    
    // 检查点是否在导航网格上
    public bool IsPointOnNavMesh(Vector3 position, float maxDistance = 0.1f)
    {
        NavMeshHit hit;
        return NavMesh.SamplePosition(position, out hit, maxDistance, areaMask);
    }
    
    // 获取导航网格上的随机点
    public bool GetRandomPointOnNavMesh(Vector3 center, float radius, out Vector3 result)
    {
        for (int i = 0; i < 30; i++) // 尝试30次
        {
            Vector3 randomDirection = Random.insideUnitSphere * radius;
            randomDirection += center;
            
            NavMeshHit hit;
            if (NavMesh.SamplePosition(randomDirection, out hit, radius, areaMask))
            {
                result = hit.position;
                return true;
            }
        }
        
        result = center;
        return false;
    }
    
    // 重建部分导航网格（用于动态地形变化）
    public void PartialNavMeshUpdate(List<NavMeshBuildSource> updatedSources)
    {
        if (updatedSources == null || updatedSources.Count == 0) return;
        
        // 收集当前所有源
        List<NavMeshBuildSource> allSources = new List<NavMeshBuildSource>(buildSources);
        
        // 更新或添加修改的源
        foreach (NavMeshBuildSource updatedSource in updatedSources)
        {
            bool found = false;
            for (int i = 0; i < allSources.Count; i++)
            {
                // 这里需要根据实际情况判断是否为同一源
                // 简化实现：假设源已经更新
                allSources[i] = updatedSource;
                found = true;
                break;
            }
            
            if (!found)
            {
                allSources.Add(updatedSource);
            }
        }
        
        buildSources = allSources;
        
        // 重新构建导航网格
        BuildNavMesh();
        
        Debug.Log($"部分导航网格更新完成，更新了 {updatedSources.Count} 个源");
    }
    
    // 获取区域代价
    public float GetAreaCost(int areaType)
    {
        if (areaCostDictionary.ContainsKey(areaType))
        {
            return areaCostDictionary[areaType];
        }
        return 1.0f; // 默认代价
    }
    
    // 设置区域代价
    public void SetAreaCost(int areaType, float costMultiplier)
    {
        areaCostDictionary[areaType] = Mathf.Max(0.1f, costMultiplier);
    }
    
    void OnDrawGizmos()
    {
        if (costAreas == null) return;
        
        // 绘制区域代价信息
        foreach (NavMeshCostArea area in costAreas)
        {
            // 在实际项目中，这里可以绘制区域边界或标记
        }
    }
}

4.3 A*寻路算法的核心原理与优化实现

4.3.1 A*算法的理论基础与实现细节

A*算法是一种在图形平面上寻找从起点到终点的最低成本路径的算法。它结合了最佳优先搜索的启发式方法和Dijkstra算法的保证性，通过评估函数f(n) = g(n) + h(n)来决定搜索方向，其中g(n)是从起点到节点n的实际成本，h(n)是从节点n到终点的估计成本。

以下是A*算法的完整实现，包含多种启发函数选择和性能优化：

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

public class AStarPathfinder
{
    // 寻路统计
    private class PathfindingStats
    {
        public int nodesExplored;
        public int pathLength;
        public float searchTime;
        public bool pathFound;
        
        public PathfindingStats()
        {
            nodesExplored = 0;
            pathLength = 0;
            searchTime = 0f;
            pathFound = false;
        }
    }
    
    // 启发函数类型
    public enum HeuristicType
    {
        Manhattan,
        Euclidean,
        Chebyshev,
        Diagonal,
        Custom
    }
    
    // 寻路请求
    public class PathRequest
    {
        public Vector3 startPosition;
        public Vector3 targetPosition;
        public System.Action<List<Vector3>, bool> callback;
        public HeuristicType heuristicType;
        public float heuristicWeight;
        public bool allowDiagonal;
        public bool cutCorners;
        
        public PathRequest(Vector3 start, Vector3 target, System.Action<List<Vector3>, bool> callback,
                          HeuristicType heuristic = HeuristicType.Euclidean, float weight = 1.0f,
                          bool diagonal = true, bool corners = false)
        {
            startPosition = start;
            targetPosition = target;
            this.callback = callback;
            heuristicType = heuristic;
            heuristicWeight = Mathf.Clamp(weight, 1.0f, 2.0f);
            allowDiagonal = diagonal;
            cutCorners = corners;
        }
    }
    
    // 优先队列实现（最小堆）
    private class PriorityQueue<T> where T : System.IComparable<T>
    {
        private List<T> data;
        
        public int Count
        {
            get { return data.Count; }
        }
        
        public PriorityQueue()
        {
            data = new List<T>();
        }
        
        public void Enqueue(T item)
        {
            data.Add(item);
            int childIndex = data.Count - 1;
            
            while (childIndex > 0)
            {
                int parentIndex = (childIndex - 1) / 2;
                
                if (data[childIndex].CompareTo(data[parentIndex]) >= 0)
                {
                    break;
                }
                
                // 交换
                T temp = data[childIndex];
                data[childIndex] = data[parentIndex];
                data[parentIndex] = temp;
                
                childIndex = parentIndex;
            }
        }
        
        public T Dequeue()
        {
            if (data.Count == 0)
            {
                return default(T);
            }
            
            int lastIndex = data.Count - 1;
            T frontItem = data[0];
            data[0] = data[lastIndex];
            data.RemoveAt(lastIndex);
            
            lastIndex--;
            int parentIndex = 0;
            
            while (true)
            {
                int childIndex = parentIndex * 2 + 1;
                if (childIndex > lastIndex)
                {
                    break;
                }
                
                int rightChild = childIndex + 1;
                if (rightChild <= lastIndex && data[rightChild].CompareTo(data[childIndex]) < 0)
                {
                    childIndex = rightChild;
                }
                
                if (data[parentIndex].CompareTo(data[childIndex]) <= 0)
                {
                    break;
                }
                
                T temp = data[parentIndex];
                data[parentIndex] = data[childIndex];
                data[childIndex] = temp;
                
                parentIndex = childIndex;
            }
            
            return frontItem;
        }
        
        public bool Contains(T item)
        {
            return data.Contains(item);
        }
        
        public void UpdateItem(T item)
        {
            // 当项目代价变化时，重新排序
            int index = data.IndexOf(item);
            if (index >= 0)
            {
                // 简化实现：移除并重新添加
                data.RemoveAt(index);
                Enqueue(item);
            }
        }
        
        public void Clear()
        {
            data.Clear();
        }
    }
    
    // 同步寻路方法
    public static List<Vector3> FindPathSync(PathNode startNode, PathNode targetNode, 
                                            HeuristicType heuristicType = HeuristicType.Euclidean,
                                            float heuristicWeight = 1.0f, out PathfindingStats stats)
    {
        stats = new PathfindingStats();
        System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
        stopwatch.Start();
        
        if (startNode == null || targetNode == null || !startNode.IsWalkable || !targetNode.IsWalkable)
        {
            stopwatch.Stop();
            stats.searchTime = (float)stopwatch.Elapsed.TotalSeconds;
            return new List<Vector3>();
        }
        
        // 如果起点和终点相同
        if (startNode.IsSamePosition(targetNode))
        {
            List<Vector3> singleNodePath = new List<Vector3> { startNode.WorldPosition };
            stopwatch.Stop();
            stats.searchTime = (float)stopwatch.Elapsed.TotalSeconds;
            stats.nodesExplored = 1;
            stats.pathLength = 1;
            stats.pathFound = true;
            return singleNodePath;
        }
        
        // 初始化开放列表和关闭列表
        PriorityQueue<PathNode> openSet = new PriorityQueue<PathNode>();
        HashSet<PathNode> closedSet = new HashSet<PathNode>();
        
        // 重置起始节点
        startNode.Reset();
        startNode.GCost = 0;
        startNode.HCost = CalculateHeuristic(startNode, targetNode, heuristicType);
        startNode.CalculateFCost();
        
        openSet.Enqueue(startNode);
        
        while (openSet.Count > 0)
        {
            // 获取FCost最小的节点
            PathNode currentNode = openSet.Dequeue();
            stats.nodesExplored++;
            
            // 检查是否到达目标
            if (currentNode.IsSamePosition(targetNode))
            {
                List<Vector3> path = RetracePath(startNode, currentNode);
                stopwatch.Stop();
                
                stats.searchTime = (float)stopwatch.Elapsed.TotalSeconds;
                stats.pathLength = path.Count;
                stats.pathFound = true;
                
                return path;
            }
            
            closedSet.Add(currentNode);
            
            // 探索邻居节点
            foreach (PathNode neighbor in currentNode.NeighborNodes)
            {
                if (!neighbor.IsWalkable || closedSet.Contains(neighbor))
                {
                    continue;
                }
                
                // 计算新的GCost
                int tentativeGCost = currentNode.GCost + currentNode.GetMovementCostTo(neighbor);
                
                if (tentativeGCost < neighbor.GCost || !openSet.Contains(neighbor))
                {
                    neighbor.ParentNode = currentNode;
                    neighbor.GCost = tentativeGCost;
                    neighbor.HCost = CalculateHeuristic(neighbor, targetNode, heuristicType, heuristicWeight);
                    neighbor.CalculateFCost();
                    
                    if (!openSet.Contains(neighbor))
                    {
                        openSet.Enqueue(neighbor);
                    }
                    else
                    {
                        openSet.UpdateItem(neighbor);
                    }
                }
            }
        }
        
        // 没有找到路径
        stopwatch.Stop();
        stats.searchTime = (float)stopwatch.Elapsed.TotalSeconds;
        stats.pathFound = false;
        
        return new List<Vector3>();
    }
    
    // 计算启发函数值
    private static int CalculateHeuristic(PathNode a, PathNode b, HeuristicType type, float weight = 1.0f)
    {
        int dx = Mathf.Abs(a.GridX - b.GridX);
        int dy = Mathf.Abs(a.GridY - b.GridY);
        
        switch (type)
        {
            case HeuristicType.Manhattan:
                return Mathf.RoundToInt((dx + dy) * weight);
                
            case HeuristicType.Euclidean:
                return Mathf.RoundToInt(Mathf.Sqrt(dx * dx + dy * dy) * weight);
                
            case HeuristicType.Chebyshev:
                return Mathf.RoundToInt(Mathf.Max(dx, dy) * weight);
                
            case HeuristicType.Diagonal:
                // 对角距离：D * max(dx, dy) + (D2 - 2*D) * min(dx, dy)
                int D = 1;  // 正交移动代价
                int D2 = 1; // 对角移动代价（假设与正交相同）
                return Mathf.RoundToInt((D * (dx + dy) + (D2 - 2 * D) * Mathf.Min(dx, dy)) * weight);
                
            default:
                return Mathf.RoundToInt(Mathf.Sqrt(dx * dx + dy * dy) * weight);
        }
    }
    
    // 回溯路径
    private static List<Vector3> RetracePath(PathNode startNode, PathNode endNode)
    {
        List<Vector3> path = new List<Vector3>();
        PathNode currentNode = endNode;
        
        while (currentNode != null && !currentNode.IsSamePosition(startNode))
        {
            path.Add(currentNode.WorldPosition);
            currentNode = currentNode.ParentNode;
        }
        
        path.Add(startNode.WorldPosition);
        path.Reverse();
        
        // 路径平滑（减少不必要的拐点）
        List<Vector3> smoothedPath = SmoothPath(path);
        
        return smoothedPath;
    }
    
    // 路径平滑
    private static List<Vector3> SmoothPath(List<Vector3> originalPath)
    {
        if (originalPath.Count <= 2)
        {
            return new List<Vector3>(originalPath);
        }
        
        List<Vector3> smoothedPath = new List<Vector3>();
        smoothedPath.Add(originalPath[0]);
        
        for (int i = 1; i < originalPath.Count - 1; i++)
        {
            Vector3 previous = smoothedPath[smoothedPath.Count - 1];
            Vector3 current = originalPath[i];
            Vector3 next = originalPath[i + 1];
            
            // 检查是否可以跳过当前点（三点是否近似共线）
            Vector3 dirToCurrent = (current - previous).normalized;
            Vector3 dirToNext = (next - previous).normalized;
            
            float dotProduct = Vector3.Dot(dirToCurrent, dirToNext);
            
            // 如果方向基本一致（夹角很小），跳过当前点
            if (dotProduct < 0.99f) // 约8度夹角
            {
                smoothedPath.Add(current);
            }
        }
        
        smoothedPath.Add(originalPath[originalPath.Count - 1]);
        
        return smoothedPath;
    }
    
    // 异步寻路支持
    public static System.Collections.IEnumerator FindPathAsync(PathRequest request, 
                                                              GridBasedNavigationGraph grid)
    {
        PathNode startNode = grid.GetNodeFromWorldPoint(request.startPosition);
        PathNode targetNode = grid.GetNodeFromWorldPoint(request.targetPosition);
        
        PathfindingStats stats;
        List<Vector3> path = FindPathSync(startNode, targetNode, 
                                         request.heuristicType, 
                                         request.heuristicWeight, 
                                         out stats);
        
        // 模拟异步延迟（实际项目中这里可能是真正的异步计算）
        yield return null;
        
        request.callback?.Invoke(path, stats.pathFound);
        
        Debug.Log($"异步寻路完成: 探索节点={stats.nodesExplored}, " +
                 $"路径长度={stats.pathLength}, 耗时={stats.searchTime:F4}秒");
    }
    
    // 批量寻路（用于RTS等多单位同时寻路）
    public static List<List<Vector3>> FindMultiplePaths(List<PathRequest> requests, 
                                                       GridBasedNavigationGraph grid,
                                                       int maxConcurrent = 4)
    {
        List<List<Vector3>> allPaths = new List<List<Vector3>>();
        List<System.Collections.IEnumerator> coroutines = new List<System.Collections.IEnumerator>();
        
        // 分批处理请求以避免性能峰值
        for (int i = 0; i < requests.Count; i += maxConcurrent)
        {
            int batchSize = Mathf.Min(maxConcurrent, requests.Count - i);
            List<PathRequest> batch = requests.GetRange(i, batchSize);
            
            // 同步处理每批请求
            foreach (PathRequest request in batch)
            {
                PathNode startNode = grid.GetNodeFromWorldPoint(request.startPosition);
                PathNode targetNode = grid.GetNodeFromWorldPoint(request.targetPosition);
                
                PathfindingStats stats;
                List<Vector3> path = FindPathSync(startNode, targetNode, 
                                                 request.heuristicType, 
                                                 request.heuristicWeight, 
                                                 out stats);
                
                allPaths.Add(path);
            }
        }
        
        return allPaths;
    }
    
    // 增量寻路（用于动态调整路径）
    public static List<Vector3> FindIncrementalPath(PathNode startNode, PathNode targetNode,
                                                   List<PathNode> previouslyExplored,
                                                   out List<PathNode> newlyExplored,
                                                   HeuristicType heuristicType = HeuristicType.Euclidean,
                                                   float heuristicWeight = 1.0f)
    {
        newlyExplored = new List<PathNode>();
        
        if (startNode == null || targetNode == null || 
            !startNode.IsWalkable || !targetNode.IsWalkable)
        {
            return new List<Vector3>();
        }
        
        PriorityQueue<PathNode> openSet = new PriorityQueue<PathNode>();
        HashSet<PathNode> closedSet = new HashSet<PathNode>(previouslyExplored);
        
        // 重用之前探索的节点
        foreach (PathNode node in previouslyExplored)
        {
            closedSet.Add(node);
        }
        
        startNode.Reset();
        startNode.GCost = 0;
        startNode.HCost = CalculateHeuristic(startNode, targetNode, heuristicType, heuristicWeight);
        startNode.CalculateFCost();
        
        openSet.Enqueue(startNode);
        
        while (openSet.Count > 0)
        {
            PathNode currentNode = openSet.Dequeue();
            
            if (currentNode.IsSamePosition(targetNode))
            {
                List<Vector3> path = RetracePath(startNode, currentNode);
                return path;
            }
            
            closedSet.Add(currentNode);
            newlyExplored.Add(currentNode);
            
            foreach (PathNode neighbor in currentNode.NeighborNodes)
            {
                if (!neighbor.IsWalkable || closedSet.Contains(neighbor))
                {
                    continue;
                }
                
                int tentativeGCost = currentNode.GCost + currentNode.GetMovementCostTo(neighbor);
                
                if (tentativeGCost < neighbor.GCost || !openSet.Contains(neighbor))
                {
                    neighbor.ParentNode = currentNode;
                    neighbor.GCost = tentativeGCost;
                    neighbor.HCost = CalculateHeuristic(neighbor, targetNode, heuristicType, heuristicWeight);
                    neighbor.CalculateFCost();
                    
                    if (!openSet.Contains(neighbor))
                    {
                        openSet.Enqueue(neighbor);
                    }
                    else
                    {
                        openSet.UpdateItem(neighbor);
                    }
                }
            }
        }
        
        return new List<Vector3>();
    }
}

4.3.2 A*算法工作流程的实例解析

为了深入理解A*算法的工作机制，让我们通过一个具体的实例来跟踪算法的执行过程。考虑一个5x5的网格，其中某些单元格不可通行：

起点S(0,0) -> 目标G(4,4)

网格布局（X为障碍物）：
S . . . .
. . X . .
. X . X .
. . . . .
. . . . G

算法执行步骤：

1. 初始化：将起点S加入开放列表，g(S)=0，h(S)=估算到G的距离，f(S)=g(S)+h(S)

2. 第一次迭代：从开放列表取出f值最小的节点（当前只有S）。检查S的邻居：右侧(1,0)和下侧(0,1)。计算它们的g、h、f值并加入开放列表。

3. 后续迭代：算法会持续从开放列表取出f值最小的节点进行扩展，避开障碍物，最终找到路径。

以下是带有详细日志的A*算法实现，可以帮助理解算法的工作过程：

public class AStarDebugPathfinder : AStarPathfinder
{
    // 带调试信息的寻路方法
    public static new List<Vector3> FindPathSync(PathNode startNode, PathNode targetNode,
                                                HeuristicType heuristicType = HeuristicType.Euclidean,
                                                float heuristicWeight = 1.0f,
                                                bool verboseLogging = false)
    {
        if (verboseLogging)
        {
            Debug.Log($"开始寻路: [{startNode.GridX},{startNode.GridY}] -> [{targetNode.GridX},{targetNode.GridY}]");
            Debug.Log($"使用启发函数: {heuristicType}, 权重: {heuristicWeight}");
        }
        
        if (startNode == null || targetNode == null || !startNode.IsWalkable || !targetNode.IsWalkable)
        {
            if (verboseLogging) Debug.Log("起点或终点不可通行");
            return new List<Vector3>();
        }
        
        if (startNode.IsSamePosition(targetNode))
        {
            if (verboseLogging) Debug.Log("起点和终点相同");
            return new List<Vector3> { startNode.WorldPosition };
        }
        
        PriorityQueue<PathNode> openSet = new PriorityQueue<PathNode>();
        HashSet<PathNode> closedSet = new HashSet<PathNode>();
        
        startNode.Reset();
        startNode.GCost = 0;
        startNode.HCost = CalculateHeuristic(startNode, targetNode, heuristicType, heuristicWeight);
        startNode.CalculateFCost();
        
        openSet.Enqueue(startNode);
        
        int iteration = 0;
        
        while (openSet.Count > 0)
        {
            iteration++;
            
            if (verboseLogging && iteration <= 10) // 只记录前10次迭代
            {
                Debug.Log($"\n迭代 #{iteration}");
                Debug.Log($"开放列表大小: {openSet.Count}");
            }
            
            PathNode currentNode = openSet.Dequeue();
            
            if (verboseLogging && iteration <= 10)
            {
                Debug.Log($"当前节点: [{currentNode.GridX},{currentNode.GridY}] " +
                         $"(g={currentNode.GCost}, h={currentNode.HCost}, f={currentNode.FCost})");
            }
            
            if (currentNode.IsSamePosition(targetNode))
            {
                if (verboseLogging)
                {
                    Debug.Log($"找到路径! 总迭代次数: {iteration}");
                    Debug.Log($"路径回溯...");
                }
                
                List<Vector3> path = RetracePath(startNode, currentNode);
                
                if (verboseLogging)
                {
                    Debug.Log($"路径长度: {path.Count} 个点");
                    LogPathDetails(path);
                }
                
                return path;
            }
            
            closedSet.Add(currentNode);
            
            if (verboseLogging && iteration <= 10)
            {
                Debug.Log($"关闭列表大小: {closedSet.Count}");
                Debug.Log($"探索邻居节点:");
            }
            
            foreach (PathNode neighbor in currentNode.NeighborNodes)
            {
                if (!neighbor.IsWalkable)
                {
                    if (verboseLogging && iteration <= 10)
                    {
                        Debug.Log($"  [{neighbor.GridX},{neighbor.GridY}]: 不可通行");
                    }
                    continue;
                }
                
                if (closedSet.Contains(neighbor))
                {
                    if (verboseLogging && iteration <= 10)
                    {
                        Debug.Log($"  [{neighbor.GridX},{neighbor.GridY}]: 已在关闭列表中");
                    }
                    continue;
                }
                
                int tentativeGCost = currentNode.GCost + currentNode.GetMovementCostTo(neighbor);
                bool isBetterPath = false;
                
                if (!openSet.Contains(neighbor))
                {
                    if (verboseLogging && iteration <= 10)
                    {
                        Debug.Log($"  [{neighbor.GridX},{neighbor.GridY}]: 新节点");
                    }
                    isBetterPath = true;
                }
                else if (tentativeGCost < neighbor.GCost)
                {
                    if (verboseLogging && iteration <= 10)
                    {
                        Debug.Log($"  [{neighbor.GridX},{neighbor.GridY}]: 发现更好路径 " +
                                 $"(原g={neighbor.GCost}, 新g={tentativeGCost})");
                    }
                    isBetterPath = true;
                }
                
                if (isBetterPath)
                {
                    neighbor.ParentNode = currentNode;
                    neighbor.GCost = tentativeGCost;
                    neighbor.HCost = CalculateHeuristic(neighbor, targetNode, heuristicType, heuristicWeight);
                    neighbor.CalculateFCost();
                    
                    if (!openSet.Contains(neighbor))
                    {
                        openSet.Enqueue(neighbor);
                    }
                    else
                    {
                        openSet.UpdateItem(neighbor);
                    }
                    
                    if (verboseLogging && iteration <= 10)
                    {
                        Debug.Log($"    更新: g={neighbor.GCost}, h={neighbor.HCost}, f={neighbor.FCost}");
                    }
                }
                else
                {
                    if (verboseLogging && iteration <= 10)
                    {
                        Debug.Log($"  [{neighbor.GridX},{neighbor.GridY}]: 不是更好路径");
                    }
                }
            }
        }
        
        if (verboseLogging)
        {
            Debug.Log($"未找到路径! 总迭代次数: {iteration}");
        }
        
        return new List<Vector3>();
    }
    
    private static void LogPathDetails(List<Vector3> path)
    {
        if (path == null || path.Count == 0)
        {
            Debug.Log("路径为空");
            return;
        }
        
        Debug.Log("完整路径:");
        for (int i = 0; i < path.Count; i++)
        {
            Debug.Log($"  {i}: {path[i]}");
        }
        
        // 计算路径总长度
        float totalLength = 0f;
        for (int i = 0; i < path.Count - 1; i++)
        {
            totalLength += Vector3.Distance(path[i], path[i + 1]);
        }
        
        Debug.Log($"路径总长度: {totalLength:F2} 单位");
    }
    
    // 可视化调试方法
    public static void VisualizePathfinding(GridBasedNavigationGraph grid, 
                                          Vector3 startPos, Vector3 targetPos,
                                          HeuristicType heuristicType = HeuristicType.Euclidean)
    {
        PathNode startNode = grid.GetNodeFromWorldPoint(startPos);
        PathNode targetNode = grid.GetNodeFromWorldPoint(targetPos);
        
        if (startNode == null || targetNode == null)
        {
            Debug.LogWarning("无法找到起点或终点的对应节点");
            return;
        }
        
        List<Vector3> path = FindPathSync(startNode, targetNode, heuristicType, 1.0f, true);
        
        // 在场景中绘制调试信息
        DrawDebugVisualization(grid, startNode, targetNode, path);
    }
    
    private static void DrawDebugVisualization(GridBasedNavigationGraph grid,
                                              PathNode startNode, PathNode targetNode,
                                              List<Vector3> path)
    {
        // 在实际项目中，这里可以使用Gizmos或Debug.DrawLine绘制可视化信息
        // 例如：起点绿色，终点红色，路径蓝色，障碍物灰色等
        
        Debug.Log($"调试可视化: 起点[{startNode.GridX},{startNode.GridY}], " +
                 $"终点[{targetNode.GridX},{targetNode.GridY}], 路径点数: {path.Count}");
    }
}

4.4 战术寻路系统的实现与应用

4.4.1 战术寻路的核心概念

战术寻路不仅考虑最短路径，还考虑路径的安全性、隐蔽性和战术优势。在射击游戏、策略游戏等类型中，战术寻路是AI智能的重要体现。战术寻路需要考虑以下因素：

1. 威胁区域：敌人视野、火力覆盖区域、陷阱区等
2. 隐蔽性：利用掩体、阴影、烟雾等提供隐蔽的路径
3. 战术位置：制高点、伏击点、撤退路线等
4. 动态变化：威胁区域的实时变化，队友位置的影响

以下是战术寻路系统的完整实现：

using UnityEngine;
using System.Collections.Generic;

public class TacticalPathfindingSystem : MonoBehaviour
{
    [System.Serializable]
    public class ThreatZone
    {
        public Vector3 center;
        public float radius;
        public float threatLevel; // 0-1，威胁程度
        public ThreatType type;
        
        public enum ThreatType
        {
            EnemyVision,
            EnemyFire,
            Trap,
            Hazard,
            Dynamic
        }
        
        public ThreatZone(Vector3 center, float radius, float threatLevel, ThreatType type)
        {
            this.center = center;
            this.radius = radius;
            this.threatLevel = Mathf.Clamp01(threatLevel);
            this.type = type;
        }
        
        public float GetThreatAtPosition(Vector3 position)
        {
            float distance = Vector3.Distance(center, position);
            if (distance > radius) return 0f;
            
            // 距离越近，威胁越大
            float normalizedDistance = 1f - (distance / radius);
            return threatLevel * normalizedDistance;
        }
    }
    
    [System.Serializable]
    public class CoverPoint
    {
        public Vector3 position;
        public float coverQuality; // 0-1，掩体质量
        public CoverType type;
        public float safeRadius; // 安全半径
        
        public enum CoverType
        {
            FullCover,
            HalfCover,
            Destructible,
            Moving
        }
        
        public CoverPoint(Vector3 position, float quality, CoverType type, float safeRadius = 2f)
        {
            this.position = position;
            this.coverQuality = Mathf.Clamp01(quality);
            this.type = type;
            this.safeRadius = safeRadius;
        }
        
        public bool IsPositionInCover(Vector3 position, Vector3 threatPosition)
        {
            float distance = Vector3.Distance(this.position, position);
            if (distance > safeRadius) return false;
            
            // 检查是否真正提供掩护（阻挡视线）
            Vector3 toThreat = threatPosition - position;
            RaycastHit hit;
            
            // 简化的掩护检查
            if (Physics.Raycast(position + Vector3.up * 1.5f, toThreat.normalized, out hit, toThreat.magnitude))
            {
                // 如果击中掩体点附近的物体，认为提供掩护
                if (Vector3.Distance(hit.point, this.position) < safeRadius * 2f)
                {
                    return true;
                }
            }
            
            return false;
        }
    }
    
    [Header("战术参数")]
    [SerializeField] private float threatAvoidanceWeight = 2.0f;
    [SerializeField] private float coverPreferenceWeight = 1.5f;
    [SerializeField] private float stealthMultiplier = 1.2f;
    [SerializeField] private float minSafeDistance = 5.0f;
    
    [Header("动态威胁")]
    [SerializeField] private bool updateThreatsInRealTime = true;
    [SerializeField] private float threatUpdateInterval = 0.3f;
    
    private List<ThreatZone> activeThreats;
    private List<CoverPoint> availableCovers;
    private float threatUpdateTimer;
    private GridBasedNavigationGraph navigationGrid;
    
    void Awake()
    {
        InitializeTacticalSystem();
    }
    
    void Update()
    {
        if (updateThreatsInRealTime)
        {
            UpdateDynamicThreats();
        }
    }
    
    private void InitializeTacticalSystem()
    {
        activeThreats = new List<ThreatZone>();
        availableCovers = new List<CoverPoint>();
        navigationGrid = GetComponent<GridBasedNavigationGraph>();
        
        if (navigationGrid == null)
        {
            navigationGrid = FindObjectOfType<GridBasedNavigationGrid>();
        }
        
        Debug.Log("战术寻路系统初始化完成");
    }
    
    // 添加威胁区域
    public void AddThreatZone(Vector3 center, float radius, float threatLevel, 
                             ThreatZone.ThreatType type = ThreatZone.ThreatType.EnemyVision)
    {
        ThreatZone newThreat = new ThreatZone(center, radius, threatLevel, type);
        activeThreats.Add(newThreat);
        
        Debug.Log($"添加威胁区域: {type} at {center}, 半径={radius}, 威胁等级={threatLevel}");
    }
    
    // 移除威胁区域
    public void RemoveThreatZone(Vector3 center, float radiusThreshold = 1.0f)
    {
        for (int i = activeThreats.Count - 1; i >= 0; i--)
        {
            if (Vector3.Distance(activeThreats[i].center, center) < radiusThreshold)
            {
                activeThreats.RemoveAt(i);
                Debug.Log($"移除威胁区域 at {center}");
            }
        }
    }
    
    // 添加掩体点
    public void AddCoverPoint(Vector3 position, float quality, 
                             CoverPoint.CoverType type = CoverPoint.CoverType.HalfCover)
    {
        CoverPoint newCover = new CoverPoint(position, quality, type);
        availableCovers.Add(newCover);
    }
    
    // 移除掩体点
    public void RemoveCoverPoint(Vector3 position, float radiusThreshold = 1.0f)
    {
        for (int i = availableCovers.Count - 1; i >= 0; i--)
        {
            if (Vector3.Distance(availableCovers[i].position, position) < radiusThreshold)
            {
                availableCovers.RemoveAt(i);
            }
        }
    }
    
    private void UpdateDynamicThreats()
    {
        threatUpdateTimer += Time.deltaTime;
        if (threatUpdateTimer >= threatUpdateInterval)
        {
            // 更新动态威胁（例如移动的敌人）
            UpdateMovingThreats();
            
            // 移除过期的威胁
            RemoveExpiredThreats();
            
            threatUpdateTimer = 0f;
        }
    }
    
    private void UpdateMovingThreats()
    {
        // 查找移动的敌人并更新其威胁区域
        GameObject[] enemies = GameObject.FindGameObjectsWithTag("Enemy");
        
        foreach (GameObject enemy in enemies)
        {
            // 检查是否已有该敌人的威胁区域
            bool found = false;
            foreach (ThreatZone threat in activeThreats)
            {
                if (threat.type == ThreatZone.ThreatType.Dynamic && 
                    Vector3.Distance(threat.center, enemy.transform.position) < 2f)
                {
                    // 更新位置
                    threat.center = enemy.transform.position;
                    found = true;
                    break;
                }
            }
            
            // 如果没有找到，添加新的威胁区域
            if (!found)
            {
                // 根据敌人类型确定威胁参数
                float threatRadius = 15f;
                float threatLevel = 0.7f;
                
                // 检查敌人是否正在开火
                AICombatController combat = enemy.GetComponent<AICombatController>();
                if (combat != null && combat.IsFiring())
                {
                    threatLevel = 1.0f;
                    threatRadius = 20f;
                }
                
                AddThreatZone(enemy.transform.position, threatRadius, threatLevel, 
                             ThreatZone.ThreatType.Dynamic);
            }
        }
    }
    
    private void RemoveExpiredThreats()
    {
        // 移除持续时间过长的动态威胁
        // 在实际项目中，可能需要更复杂的生命周期管理
    }
    
    // 战术寻路主方法
    public List<Vector3> FindTacticalPath(Vector3 start, Vector3 target, 
                                         out float pathSafetyScore)
    {
        pathSafetyScore = 0f;
        
        if (navigationGrid == null)
        {
            Debug.LogWarning("未找到导航网格");
            return new List<Vector3>();
        }
        
        PathNode startNode = navigationGrid.GetNodeFromWorldPoint(start);
        PathNode targetNode = navigationGrid.GetNodeFromWorldPoint(target);
        
        if (startNode == null || targetNode == null)
        {
            Debug.LogWarning("起点或终点不在导航网格上");
            return new List<Vector3>();
        }
        
        // 使用修改的A*算法进行战术寻路
        List<Vector3> path = FindTacticalPathAStar(startNode, targetNode, out pathSafetyScore);
        
        return path;
    }
    
    private List<Vector3> FindTacticalPathAStar(PathNode startNode, PathNode targetNode,
                                               out float safetyScore)
    {
        safetyScore = 0f;
        
        AStarPathfinder.PriorityQueue<PathNode> openSet = new AStarPathfinder.PriorityQueue<PathNode>();
        HashSet<PathNode> closedSet = new HashSet<PathNode>();
        
        startNode.Reset();
        startNode.GCost = 0;
        startNode.HCost = CalculateTacticalHeuristic(startNode, targetNode);
        startNode.CalculateFCost();
        
        openSet.Enqueue(startNode);
        
        while (openSet.Count > 0)
        {
            PathNode currentNode = openSet.Dequeue();
            
            if (currentNode.IsSamePosition(targetNode))
            {
                List<Vector3> path = AStarPathfinder.RetracePath(startNode, currentNode);
                safetyScore = CalculatePathSafetyScore(path);
                return path;
            }
            
            closedSet.Add(currentNode);
            
            foreach (PathNode neighbor in currentNode.NeighborNodes)
            {
                if (!neighbor.IsWalkable || closedSet.Contains(neighbor))
                {
                    continue;
                }
                
                // 计算战术移动代价
                int movementCost = currentNode.GetMovementCostTo(neighbor);
                float tacticalCost = CalculateTacticalCost(currentNode, neighbor);
                int totalCost = Mathf.RoundToInt(movementCost * tacticalCost);
                
                int tentativeGCost = currentNode.GCost + totalCost;
                
                if (tentativeGCost < neighbor.GCost || !openSet.Contains(neighbor))
                {
                    neighbor.ParentNode = currentNode;
                    neighbor.GCost = tentativeGCost;
                    neighbor.HCost = CalculateTacticalHeuristic(neighbor, targetNode);
                    neighbor.CalculateFCost();
                    
                    if (!openSet.Contains(neighbor))
                    {
                        openSet.Enqueue(neighbor);
                    }
                    else
                    {
                        openSet.UpdateItem(neighbor);
                    }
                }
            }
        }
        
        return new List<Vector3>();
    }
    
    private float CalculateTacticalCost(PathNode fromNode, PathNode toNode)
    {
        float baseCost = 1.0f;
        Vector3 nodePosition = toNode.WorldPosition;
        
        // 威胁代价
        float threatCost = CalculateThreatCost(nodePosition);
        baseCost += threatCost * threatAvoidanceWeight;
        
        // 隐蔽性代价（负代价，鼓励使用掩体）
        float coverBenefit = CalculateCoverBenefit(nodePosition);
        baseCost -= coverBenefit * coverPreferenceWeight;
        
        // 确保最小代价
        return Mathf.Max(0.1f, baseCost);
    }
    
    private float CalculateThreatCost(Vector3 position)
    {
        float totalThreat = 0f;
        
        foreach (ThreatZone threat in activeThreats)
        {
            float threatValue = threat.GetThreatAtPosition(position);
            totalThreat += threatValue;
            
            // 特别处理火力威胁
            if (threat.type == ThreatZone.ThreatType.EnemyFire)
            {
                totalThreat += threatValue * 0.5f; // 额外惩罚
            }
        }
        
        return totalThreat;
    }
    
    private float CalculateCoverBenefit(Vector3 position)
    {
        float bestCoverBenefit = 0f;
        
        // 检查是否在掩体保护下
        foreach (CoverPoint cover in availableCovers)
        {
            if (Vector3.Distance(position, cover.position) <= cover.safeRadius)
            {
                // 检查对每个威胁的掩护效果
                float coverEffectiveness = 0f;
                int coveredThreats = 0;
                
                foreach (ThreatZone threat in activeThreats)
                {
                    if (cover.IsPositionInCover(position, threat.center))
                    {
                        coverEffectiveness += cover.coverQuality;
                        coveredThreats++;
                    }
                }
                
                if (coveredThreats > 0)
                {
                    coverEffectiveness /= coveredThreats;
                    bestCoverBenefit = Mathf.Max(bestCoverBenefit, coverEffectiveness);
                }
            }
        }
        
        return bestCoverBenefit;
    }
    
    private int CalculateTacticalHeuristic(PathNode node, PathNode targetNode)
    {
        // 基础启发值（欧几里得距离）
        int baseHeuristic = AStarPathfinder.CalculateHeuristic(
            node, targetNode, 
            AStarPathfinder.HeuristicType.Euclidean, 
            1.0f
        );
        
        // 战术调整：鼓励使用安全路径
        float safetyFactor = 1.0f;
        
        // 如果目标点在高威胁区域，减少启发值以鼓励探索其他路径
        float targetThreat = CalculateThreatCost(targetNode.WorldPosition);
        if (targetThreat > 0.5f)
        {
            safetyFactor += targetThreat * 0.5f;
        }
        
        return Mathf.RoundToInt(baseHeuristic * safetyFactor);
    }
    
    private float CalculatePathSafetyScore(List<Vector3> path)
    {
        if (path == null || path.Count == 0) return 0f;
        
        float totalThreat = 0f;
        float maxSegmentThreat = 0f;
        
        for (int i = 0; i < path.Count; i++)
        {
            float pointThreat = CalculateThreatCost(path[i]);
            totalThreat += pointThreat;
            maxSegmentThreat = Mathf.Max(maxSegmentThreat, pointThreat);
        }
        
        float averageThreat = totalThreat / path.Count;
        
        // 安全评分：1.0表示完全安全，0.0表示极度危险
        float safetyScore = 1.0f - Mathf.Clamp01(averageThreat * 0.5f + maxSegmentThreat * 0.5f);
        
        return safetyScore;
    }
    
    // 寻找安全位置（用于撤退或重新定位）
    public bool FindSafePosition(Vector3 currentPosition, float searchRadius, 
                                out Vector3 safePosition, float minSafety = 0.7f)
    {
        safePosition = currentPosition;
        
        if (navigationGrid == null) return false;
        
        List<PathNode> nearbyNodes = navigationGrid.GetNodesInRadius(currentPosition, searchRadius);
        
        PathNode safestNode = null;
        float bestSafety = 0f;
        
        foreach (PathNode node in nearbyNodes)
        {
            if (!node.IsWalkable) continue;
            
            float nodeSafety = 1.0f - CalculateThreatCost(node.WorldPosition);
            
            // 检查是否靠近掩体
            float coverBonus = CalculateCoverBenefit(node.WorldPosition);
            nodeSafety = Mathf.Clamp01(nodeSafety + coverBonus * 0.3f);
            
            if (nodeSafety > bestSafety && nodeSafety >= minSafety)
            {
                bestSafety = nodeSafety;
                safestNode = node;
            }
        }
        
        if (safestNode != null)
        {
            safePosition = safestNode.WorldPosition;
            return true;
        }
        
        return false;
    }
    
    // 寻找伏击位置
    public bool FindAmbushPosition(Vector3 targetPosition, float maxDistance,
                                  out Vector3 ambushPosition, out float ambushQuality)
    {
        ambushPosition = targetPosition;
        ambushQuality = 0f;
        
        if (navigationGrid == null) return false;
        
        List<PathNode> candidateNodes = navigationGrid.GetNodesInRadius(targetPosition, maxDistance);
        
        PathNode bestAmbushNode = null;
        float bestScore = 0f;
        
        foreach (PathNode node in candidateNodes)
        {
            if (!node.IsWalkable) continue;
            
            // 评估伏击质量
            float score = EvaluateAmbushPosition(node, targetPosition);
            
            if (score > bestScore)
            {
                bestScore = score;
                bestAmbushNode = node;
            }
        }
        
        if (bestAmbushNode != null && bestScore > 0.3f)
        {
            ambushPosition = bestAmbushNode.WorldPosition;
            ambushQuality = bestScore;
            return true;
        }
        
        return false;
    }
    
    private float EvaluateAmbushPosition(PathNode ambushNode, Vector3 targetPosition)
    {
        float score = 0f;
        
        // 1. 视线检查
        if (HasLineOfSight(ambushNode.WorldPosition, targetPosition))
        {
            score += 0.4f;
        }
        
        // 2. 距离适中（不要太近也不要太远）
        float distance = Vector3.Distance(ambushNode.WorldPosition, targetPosition);
        float distanceScore = 1.0f - Mathf.Abs(distance - 15f) / 15f; // 理想距离15单位
        score += distanceScore * 0.3f;
        
        // 3. 隐蔽性
        float coverScore = CalculateCoverBenefit(ambushNode.WorldPosition);
        score += coverScore * 0.2f;
        
        // 4. 威胁程度（越低越好）
        float threatScore = 1.0f - CalculateThreatCost(ambushNode.WorldPosition);
        score += threatScore * 0.1f;
        
        return Mathf.Clamp01(score);
    }
    
    private bool HasLineOfSight(Vector3 from, Vector3 to)
    {
        Vector3 direction = to - from;
        RaycastHit hit;
        
        if (Physics.Raycast(from + Vector3.up * 1.5f, direction.normalized, out hit, direction.magnitude))
        {
            // 检查是否击中目标
            if (Vector3.Distance(hit.point, to) < 2f)
            {
                return true;
            }
            return false;
        }
        
        return true;
    }
    
    void OnDrawGizmosSelected()
    {
        // 绘制威胁区域
        Gizmos.color = new Color(1, 0, 0, 0.3f);
        foreach (ThreatZone threat in activeThreats)
        {
            Gizmos.DrawSphere(threat.center, 0.5f);
            Gizmos.DrawWireSphere(threat.center, threat.radius);
        }
        
        // 绘制掩体点
        Gizmos.color = new Color(0, 1, 0, 0.5f);
        foreach (CoverPoint cover in availableCovers)
        {
            Gizmos.DrawCube(cover.position, Vector3.one * 0.5f);
            Gizmos.DrawWireSphere(cover.position, cover.safeRadius);
        }
    }
}

4.4.2 复杂地形中的多层建筑寻路

多层建筑中的寻路需要处理楼梯、电梯、跳跃点等垂直移动。以下是多层寻路系统的实现：

public class MultiLevelPathfindingSystem : MonoBehaviour
{
    [System.Serializable]
    public class LevelConnection
    {
        public Vector3 connectionPoint;
        public ConnectionType type;
        public int fromLevel;
        public int toLevel;
        public float usageCost; // 使用代价（如爬楼梯比走平地慢）
        
        public enum ConnectionType
        {
            Staircase,
            Elevator,
            Ladder,
            Ramp,
            Teleport
        }
        
        public LevelConnection(Vector3 point, ConnectionType type, int fromLevel, int toLevel, float cost = 1.0f)
        {
            connectionPoint = point;
            this.type = type;
            this.fromLevel = fromLevel;
            this.toLevel = toLevel;
            usageCost = Mathf.Max(0.1f, cost);
        }
    }
    
    [System.Serializable]
    public class BuildingLevel
    {
        public int levelIndex;
        public float height;
        public GridBasedNavigationGraph levelGrid;
        public List<LevelConnection> connections;
        
        public BuildingLevel(int index, float height, GridBasedNavigationGraph grid)
        {
            levelIndex = index;
            this.height = height;
            levelGrid = grid;
            connections = new List<LevelConnection>();
        }
        
        public void AddConnection(LevelConnection connection)
        {
            connections.Add(connection);
        }
    }
    
    [Header("建筑配置")]
    [SerializeField] private List<BuildingLevel> buildingLevels;
    [SerializeField] private float levelHeight = 3.0f;
    
    [Header("连接点检测")]
    [SerializeField] private float connectionSearchRadius = 2.0f;
    [SerializeField] private LayerMask connectionMask = ~0;
    
    private Dictionary<int, BuildingLevel> levelDictionary;
    
    void Awake()
    {
        InitializeMultiLevelSystem();
    }
    
    private void InitializeMultiLevelSystem()
    {
        levelDictionary = new Dictionary<int, BuildingLevel>();
        
        // 初始化层级字典
        foreach (BuildingLevel level in buildingLevels)
        {
            levelDictionary[level.levelIndex] = level;
        }
        
        // 自动检测连接点
        if (buildingLevels.Count > 1)
        {
            AutoDetectConnections();
        }
        
        Debug.Log($"多层寻路系统初始化完成，{buildingLevels.Count} 个层级");
    }
    
    private void AutoDetectConnections()
    {
        // 自动检测楼梯、电梯等连接点
        // 在实际项目中，这里可以扫描场景中的特定对象
        
        for (int i = 0; i < buildingLevels.Count - 1; i++)
        {
            BuildingLevel currentLevel = buildingLevels[i];
            BuildingLevel nextLevel = buildingLevels[i + 1];
            
            // 查找可能的连接点（如楼梯顶部/底部）
            FindStairConnections(currentLevel, nextLevel);
            FindElevatorConnections(currentLevel, nextLevel);
        }
    }
    
    private void FindStairConnections(BuildingLevel fromLevel, BuildingLevel toLevel)
    {
        // 在实际项目中，这里会查找场景中的楼梯对象
        // 简化实现：假设每层都有预设的连接点
        
        Vector3 stairBottom = new Vector3(0, fromLevel.height, 0);
        Vector3 stairTop = new Vector3(0, toLevel.height, 0);
        
        LevelConnection bottomToTop = new LevelConnection(
            stairBottom, 
            LevelConnection.ConnectionType.Staircase,
            fromLevel.levelIndex,
            toLevel.levelIndex,
            1.5f // 爬楼梯代价更高
        );
        
        LevelConnection topToBottom = new LevelConnection(
            stairTop,
            LevelConnection.ConnectionType.Staircase,
            toLevel.levelIndex,
            fromLevel.levelIndex,
            1.2f // 下楼梯代价稍低
        );
        
        fromLevel.AddConnection(bottomToTop);
        toLevel.AddConnection(topToBottom);
    }
    
    private void FindElevatorConnections(BuildingLevel fromLevel, BuildingLevel toLevel)
    {
        // 电梯连接点
        Vector3 elevatorPosition = new Vector3(5, fromLevel.height, 0);
        
        LevelConnection elevatorUp = new LevelConnection(
            elevatorPosition,
            LevelConnection.ConnectionType.Elevator,
            fromLevel.levelIndex,
            toLevel.levelIndex,
            1.0f // 电梯代价与平地相似
        );
        
        LevelConnection elevatorDown = new LevelConnection(
            elevatorPosition + Vector3.up * (toLevel.height - fromLevel.height),
            LevelConnection.ConnectionType.Elevator,
            toLevel.levelIndex,
            fromLevel.levelIndex,
            1.0f
        );
        
        fromLevel.AddConnection(elevatorUp);
        toLevel.AddConnection(elevatorDown);
    }
    
    // 多层寻路主方法
    public List<Vector3> FindMultiLevelPath(Vector3 start, Vector3 target, out List<int> levelSequence)
    {
        levelSequence = new List<int>();
        
        // 确定起点和终点所在的层级
        int startLevel = GetLevelForPosition(start);
        int targetLevel = GetLevelForPosition(target);
        
        if (startLevel == -1 || targetLevel == -1)
        {
            Debug.LogWarning("起点或终点不在任何层级中");
            return new List<Vector3>();
        }
        
        if (startLevel == targetLevel)
        {
            // 同层寻路
            return FindSingleLevelPath(start, target, startLevel);
        }
        
        // 跨层寻路：使用层级图搜索
        List<LevelTransition> transitions = FindLevelTransitions(startLevel, targetLevel);
        
        if (transitions == null || transitions.Count == 0)
        {
            Debug.LogWarning("找不到层级间的连接路径");
            return new List<Vector3>();
        }
        
        // 构建完整路径
        List<Vector3> fullPath = BuildMultiLevelPath(start, target, transitions, out levelSequence);
        
        return fullPath;
    }
    
    private int GetLevelForPosition(Vector3 position)
    {
        float positionHeight = position.y;
        
        foreach (BuildingLevel level in buildingLevels)
        {
            float levelBottom = level.height - levelHeight / 2;
            float levelTop = level.height + levelHeight / 2;
            
            if (positionHeight >= levelBottom && positionHeight <= levelTop)
            {
                return level.levelIndex;
            }
        }
        
        return -1;
    }
    
    private List<Vector3> FindSingleLevelPath(Vector3 start, Vector3 target, int levelIndex)
    {
        if (!levelDictionary.ContainsKey(levelIndex))
        {
            return new List<Vector3>();
        }
        
        BuildingLevel level = levelDictionary[levelIndex];
        if (level.levelGrid == null)
        {
            return new List<Vector3>();
        }
        
        // 使用该层的导航网格进行寻路
        PathNode startNode = level.levelGrid.GetNodeFromWorldPoint(start);
        PathNode targetNode = level.levelGrid.GetNodeFromWorldPoint(target);
        
        if (startNode == null || targetNode == null)
        {
            return new List<Vector3>();
        }
        
        AStarPathfinder.PathfindingStats stats;
        List<Vector3> path = AStarPathfinder.FindPathSync(
            startNode, targetNode, 
            AStarPathfinder.HeuristicType.Euclidean, 1.0f, out stats);
        
        return path;
    }
    
    private class LevelTransition
    {
        public int fromLevel;
        public int toLevel;
        public Vector3 connectionPoint;
        public float transitionCost;
        public LevelConnection.ConnectionType connectionType;
        
        public LevelTransition(int from, int to, Vector3 point, float cost, 
                              LevelConnection.ConnectionType type)
        {
            fromLevel = from;
            toLevel = to;
            connectionPoint = point;
            transitionCost = cost;
            connectionType = type;
        }
    }
    
    private List<LevelTransition> FindLevelTransitions(int startLevel, int targetLevel)
    {
        // 使用图搜索算法（如BFS）查找层级间的连接路径
        Dictionary<int, LevelTransition> cameFrom = new Dictionary<int, LevelTransition>();
        Dictionary<int, float> costSoFar = new Dictionary<int, float>();
        
        PriorityQueue<int> frontier = new PriorityQueue<int>();
        frontier.Enqueue(startLevel, 0);
        
        cameFrom[startLevel] = null;
        costSoFar[startLevel] = 0;
        
        while (frontier.Count > 0)
        {
            int current = frontier.Dequeue();
            
            if (current == targetLevel)
            {
                break;
            }
            
            BuildingLevel currentLevel = levelDictionary[current];
            
            foreach (LevelConnection connection in currentLevel.connections)
            {
                int nextLevel = connection.toLevel;
                float newCost = costSoFar[current] + connection.usageCost;
                
                if (!costSoFar.ContainsKey(nextLevel) || newCost < costSoFar[nextLevel])
                {
                    costSoFar[nextLevel] = newCost;
                    float priority = newCost + HeuristicLevelDistance(nextLevel, targetLevel);
                    frontier.Enqueue(nextLevel, priority);
                    
                    cameFrom[nextLevel] = new LevelTransition(
                        current, nextLevel, 
                        connection.connectionPoint, 
                        connection.usageCost,
                        connection.type
                    );
                }
            }
        }
        
        // 重建转换序列
        if (!cameFrom.ContainsKey(targetLevel))
        {
            return null;
        }
        
        List<LevelTransition> transitions = new List<LevelTransition>();
        LevelTransition currentTransition = cameFrom[targetLevel];
        
        while (currentTransition != null)
        {
            transitions.Insert(0, currentTransition);
            currentTransition = cameFrom[currentTransition.fromLevel];
        }
        
        return transitions;
    }
    
    private float HeuristicLevelDistance(int levelA, int levelB)
    {
        // 简单的层级距离启发函数
        return Mathf.Abs(levelA - levelB) * 10f;
    }
    
    private List<Vector3> BuildMultiLevelPath(Vector3 start, Vector3 target, 
                                             List<LevelTransition> transitions,
                                             out List<int> levelSequence)
    {
        levelSequence = new List<int>();
        List<Vector3> fullPath = new List<Vector3>();
        
        Vector3 currentPosition = start;
        int currentLevel = GetLevelForPosition(start);
        
        levelSequence.Add(currentLevel);
        
        foreach (LevelTransition transition in transitions)
        {
            // 1. 从当前位置到连接点
            List<Vector3> toConnection = FindSingleLevelPath(
                currentPosition, transition.connectionPoint, currentLevel);
            
            if (toConnection.Count > 0)
            {
                fullPath.AddRange(toConnection);
            }
            
            // 2. 添加连接点本身
            fullPath.Add(transition.connectionPoint);
            
            // 3. 更新当前位置和层级
            currentPosition = transition.connectionPoint;
            currentLevel = transition.toLevel;
            levelSequence.Add(currentLevel);
            
            // 4. 如果是电梯，添加垂直移动段
            if (transition.connectionType == LevelConnection.ConnectionType.Elevator)
            {
                Vector3 verticalEnd = new Vector3(
                    currentPosition.x,
                    levelDictionary[currentLevel].height,
                    currentPosition.z
                );
                
                // 添加垂直移动的中间点（简化处理）
                for (float y = currentPosition.y; 
                     Mathf.Abs(y - verticalEnd.y) > 0.1f; 
                     y += Mathf.Sign(verticalEnd.y - currentPosition.y) * 0.5f)
                {
                    Vector3 verticalPoint = new Vector3(currentPosition.x, y, currentPosition.z);
                    fullPath.Add(verticalPoint);
                }
                
                currentPosition = verticalEnd;
            }
        }
        
        // 5. 最后一段路径到目标
        List<Vector3> toTarget = FindSingleLevelPath(currentPosition, target, currentLevel);
        if (toTarget.Count > 0)
        {
            fullPath.AddRange(toTarget);
        }
        
        // 6. 添加目标点
        fullPath.Add(target);
        
        return fullPath;
    }
    
    // 辅助类：带优先级的队列
    private class PriorityQueue<T>
    {
        private List<KeyValuePair<T, float>> elements = new List<KeyValuePair<T, float>>();
        
        public int Count
        {
            get { return elements.Count; }
        }
        
        public void Enqueue(T item, float priority)
        {
            elements.Add(new KeyValuePair<T, float>(item, priority));
        }
        
        public T Dequeue()
        {
            int bestIndex = 0;
            
            for (int i = 0; i < elements.Count; i++)
            {
                if (elements[i].Value < elements[bestIndex].Value)
                {
                    bestIndex = i;
                }
            }
            
            T bestItem = elements[bestIndex].Key;
            elements.RemoveAt(bestIndex);
            return bestItem;
        }
    }
    
    // 获取层级内的随机点
    public bool GetRandomPointInLevel(int levelIndex, out Vector3 randomPoint)
    {
        randomPoint = Vector3.zero;
        
        if (!levelDictionary.ContainsKey(levelIndex))
        {
            return false;
        }
        
        BuildingLevel level = levelDictionary[levelIndex];
        if (level.levelGrid == null)
        {
            return false;
        }
        
        List<PathNode> walkableNodes = level.levelGrid.GetAllWalkableNodes();
        if (walkableNodes.Count == 0)
        {
            return false;
        }
        
        int randomIndex = Random.Range(0, walkableNodes.Count);
        randomPoint = walkableNodes[randomIndex].WorldPosition;
        
        return true;
    }
    
    // 获取最近的连接点
    public bool GetNearestConnectionPoint(Vector3 position, int fromLevel, int toLevel, 
                                         out Vector3 connectionPoint)
    {
        connectionPoint = position;
        
        if (!levelDictionary.ContainsKey(fromLevel))
        {
            return false;
        }
        
        BuildingLevel level = levelDictionary[fromLevel];
        LevelConnection nearestConnection = null;
        float nearestDistance = float.MaxValue;
        
        foreach (LevelConnection connection in level.connections)
        {
            if (connection.toLevel == toLevel)
            {
                float distance = Vector3.Distance(position, connection.connectionPoint);
                if (distance < nearestDistance)
                {
                    nearestDistance = distance;
                    nearestConnection = connection;
                }
            }
        }
        
        if (nearestConnection != null)
        {
            connectionPoint = nearestConnection.connectionPoint;
            return true;
        }
        
        return false;
    }
    
    void OnDrawGizmosSelected()
    {
        if (buildingLevels == null) return;
        
        // 绘制层级
        foreach (BuildingLevel level in buildingLevels)
        {
            float y = level.height;
            
            Gizmos.color = new Color(0, 0.5f, 1, 0.3f);
            Gizmos.DrawCube(new Vector3(0, y, 0), new Vector3(20, 0.1f, 20));
            
            // 绘制连接点
            Gizmos.color = Color.yellow;
            foreach (LevelConnection connection in level.connections)
            {
                Gizmos.DrawSphere(connection.connectionPoint, 0.3f);
                
                // 绘制连接线
                if (levelDictionary != null && levelDictionary.ContainsKey(connection.toLevel))
                {
                    BuildingLevel targetLevel = levelDictionary[connection.toLevel];
                    Gizmos.DrawLine(
                        connection.connectionPoint,
                        new Vector3(
                            connection.connectionPoint.x,
                            targetLevel.height,
                            connection.connectionPoint.z
                        )
                    );
                }
            }
        }
    }
}

4.4.3 实时战略游戏中的小队寻路实现

RTS游戏中的小队寻路需要处理多个单位协同移动，避免拥挤，保持队形。以下是基于操控行为和A*寻路的小队寻路系统：

public class SquadPathfindingSystem : MonoBehaviour
{
    [System.Serializable]
    public class SquadFormation
    {
        public FormationType type;
        public float spacing;
        public float depth;
        
        public enum FormationType
        {
            Line,
            Column,
            Wedge,
            Box,
            Skirmish
        }
        
        public SquadFormation(FormationType type = FormationType.Line, float spacing = 2f, float depth = 1f)
        {
            this.type = type;
            this.spacing = spacing;
            this.depth = depth;
        }
        
        public List<Vector3> CalculateFormationPositions(Vector3 center, Vector3 forward, int unitCount)
        {
            List<Vector3> positions = new List<Vector3>();
            Vector3 right = Vector3.Cross(Vector3.up, forward).normalized;
            
            switch (type)
            {
                case FormationType.Line:
                    for (int i = 0; i < unitCount; i++)
                    {
                        float offset = (i - (unitCount - 1) / 2f) * spacing;
                        positions.Add(center + right * offset);
                    }
                    break;
                    
                case FormationType.Column:
                    for (int i = 0; i < unitCount; i++)
                    {
                        float offset = i * spacing * depth;
                        positions.Add(center - forward * offset);
                    }
                    break;
                    
                case FormationType.Wedge:
                    int rows = Mathf.CeilToInt(Mathf.Sqrt(unitCount));
                    int currentUnit = 0;
                    
                    for (int row = 0; row < rows; row++)
                    {
                        int unitsInRow = Mathf.Min(row + 1, unitCount - currentUnit);
                        float rowDepth = row * spacing * depth;
                        
                        for (int col = 0; col < unitsInRow; col++)
                        {
                            float colOffset = (col - (unitsInRow - 1) / 2f) * spacing;
                            positions.Add(center - forward * rowDepth + right * colOffset);
                            currentUnit++;
                        }
                    }
                    break;
                    
                case FormationType.Box:
                    int side = Mathf.CeilToInt(Mathf.Sqrt(unitCount));
                    for (int i = 0; i < unitCount; i++)
                    {
                        int row = i / side;
                        int col = i % side;
                        
                        float xOffset = (col - (side - 1) / 2f) * spacing;
                        float zOffset = (row - (side - 1) / 2f) * spacing * depth;
                        
                        positions.Add(center + right * xOffset - forward * zOffset);
                    }
                    break;
                    
                case FormationType.Skirmish:
                    for (int i = 0; i < unitCount; i++)
                    {
                        float angle = (i * 360f / unitCount) * Mathf.Deg2Rad;
                        float radius = spacing * Mathf.Sqrt(unitCount);
                        
                        Vector3 offset = new Vector3(
                            Mathf.Cos(angle) * radius,
                            0,
                            Mathf.Sin(angle) * radius
                        );
                        
                        positions.Add(center + offset);
                    }
                    break;
            }
            
            return positions;
        }
    }
    
    [Header("小队配置")]
    [SerializeField] private List<GameObject> squadUnits;
    [SerializeField] private SquadFormation currentFormation = new SquadFormation();
    [SerializeField] private float reformDistance = 5.0f;
    
    [Header("寻路参数")]
    [SerializeField] private float pathUpdateInterval = 0.5f;
    [SerializeField] private float separationWeight = 1.5f;
    [SerializeField] private float cohesionWeight = 1.0f;
    [SerializeField] private float alignmentWeight = 0.5f;
    
    private List<Vector3> formationPositions;
    private List<Vector3> currentPath;
    private int currentPathIndex;
    private float pathUpdateTimer;
    private Vector3 squadCenter;
    private Vector3 squadForward;
    private bool isMoving;
    
    void Awake()
    {
        InitializeSquad();
    }
    
    void Update()
    {
        UpdateSquadMovement();
        
        pathUpdateTimer += Time.deltaTime;
        if (pathUpdateTimer >= pathUpdateInterval && isMoving)
        {
            UpdateFormationPositions();
            pathUpdateTimer = 0f;
        }
    }
    
    private void InitializeSquad()
    {
        formationPositions = new List<Vector3>();
        currentPath = new List<Vector3>();
        
        if (squadUnits.Count > 0)
        {
            UpdateSquadCenter();
            formationPositions = currentFormation.CalculateFormationPositions(
                squadCenter, squadForward, squadUnits.Count);
        }
        
        Debug.Log($"小队初始化完成，{squadUnits.Count} 个单位");
    }
    
    private void UpdateSquadCenter()
    {
        if (squadUnits.Count == 0) return;
        
        Vector3 centerSum = Vector3.zero;
        Vector3 forwardSum = Vector3.zero;
        
        foreach (GameObject unit in squadUnits)
        {
            if (unit != null)
            {
                centerSum += unit.transform.position;
                forwardSum += unit.transform.forward;
            }
        }
        
        squadCenter = centerSum / squadUnits.Count;
        squadForward = forwardSum.normalized;
    }
    
    // 设置小队移动目标
    public void MoveSquadTo(Vector3 targetPosition)
    {
        if (squadUnits.Count == 0) return;
        
        // 寻找路径
        FindSquadPath(squadCenter, targetPosition);
        
        if (currentPath.Count > 1)
        {
            currentPathIndex = 0;
            isMoving = true;
            
            Debug.Log($"小队开始移动，路径长度: {currentPath.Count}");
        }
    }
    
    private void FindSquadPath(Vector3 start, Vector3 target)
    {
        // 使用A*寻路找到基本路径
        GridBasedNavigationGraph grid = FindObjectOfType<GridBasedNavigationGraph>();
        if (grid == null)
        {
            Debug.LogWarning("未找到导航网格");
            return;
        }
        
        PathNode startNode = grid.GetNodeFromWorldPoint(start);
        PathNode targetNode = grid.GetNodeFromWorldPoint(target);
        
        if (startNode == null || targetNode == null)
        {
            return;
        }
        
        AStarPathfinder.PathfindingStats stats;
        currentPath = AStarPathfinder.FindPathSync(
            startNode, targetNode, 
            AStarPathfinder.HeuristicType.Euclidean, 1.0f, out stats);
        
        // 为小队优化路径（加宽路径，考虑小队尺寸）
        OptimizePathForSquad();
    }
    
    private void OptimizePathForSquad()
    {
        if (currentPath.Count < 2) return;
        
        List<Vector3> optimizedPath = new List<Vector3>();
        
        // 简化路径，移除不必要的拐点
        optimizedPath.Add(currentPath[0]);
        
        for (int i = 1; i < currentPath.Count - 1; i++)
        {
            Vector3 prev = optimizedPath[optimizedPath.Count - 1];
            Vector3 current = currentPath[i];
            Vector3 next = currentPath[i + 1];
            
            Vector3 dirPrevCurrent = (current - prev).normalized;
            Vector3 dirCurrentNext = (next - current).normalized;
            
            // 如果方向变化显著，保留该点
            if (Vector3.Dot(dirPrevCurrent, dirCurrentNext) < 0.9f)
            {
                optimizedPath.Add(current);
            }
        }
        
        optimizedPath.Add(currentPath[currentPath.Count - 1]);
        currentPath = optimizedPath;
    }
    
    private void UpdateSquadMovement()
    {
        if (!isMoving || currentPath.Count == 0) return;
        
        UpdateSquadCenter();
        
        // 检查是否到达当前路径点
        float distanceToWaypoint = Vector3.Distance(squadCenter, currentPath[currentPathIndex]);
        
        if (distanceToWaypoint < reformDistance)
        {
            currentPathIndex++;
            
            if (currentPathIndex >= currentPath.Count)
            {
                // 到达最终目标
                StopSquad();
                return;
            }
        }
        
        // 计算小队前进方向
        Vector3 targetDirection = (currentPath[currentPathIndex] - squadCenter).normalized;
        
        // 更新小队朝向（平滑旋转）
        squadForward = Vector3.Slerp(squadForward, targetDirection, Time.deltaTime * 2f);
        
        // 更新每个单位的位置
        UpdateUnitPositions();
    }
    
    private void UpdateFormationPositions()
    {
        if (squadUnits.Count == 0) return;
        
        // 重新计算队形位置
        formationPositions = currentFormation.CalculateFormationPositions(
            squadCenter, squadForward, squadUnits.Count);
    }
    
    private void UpdateUnitPositions()
    {
        for (int i = 0; i < squadUnits.Count; i++)
        {
            if (squadUnits[i] == null) continue;
            
            GameObject unit = squadUnits[i];
            Vector3 targetPosition = formationPositions[i];
            
            // 应用操控行为
            Vector3 steeringForce = CalculateUnitSteering(unit, targetPosition, i);
            
            // 应用移动
            Rigidbody rb = unit.GetComponent<Rigidbody>();
            if (rb != null)
            {
                rb.AddForce(steeringForce, ForceMode.Acceleration);
            }
            else
            {
                unit.transform.position = Vector3.MoveTowards(
                    unit.transform.position, targetPosition, Time.deltaTime * 5f);
            }
            
            // 更新单位朝向
            if (steeringForce.magnitude > 0.1f)
            {
                Quaternion targetRotation = Quaternion.LookRotation(steeringForce.normalized);
                unit.transform.rotation = Quaternion.Slerp(
                    unit.transform.rotation, targetRotation, Time.deltaTime * 5f);
            }
        }
    }
    
    private Vector3 CalculateUnitSteering(GameObject unit, Vector3 targetPosition, int unitIndex)
    {
        Vector3 steeringForce = Vector3.zero;
        
        // 1. 前往目标位置
        Vector3 toTarget = targetPosition - unit.transform.position;
        if (toTarget.magnitude > 0.1f)
        {
            steeringForce += toTarget.normalized * 5f;
        }
        
        // 2. 分离（避免与队友碰撞）
        Vector3 separationForce = CalculateSeparation(unit, unitIndex);
        steeringForce += separationForce * separationWeight;
        
        // 3. 凝聚（保持在小队中心附近）
        Vector3 cohesionForce = CalculateCohesion(unit);
        steeringForce += cohesionForce * cohesionWeight;
        
        // 4. 对齐（与小队方向一致）
        Vector3 alignmentForce = CalculateAlignment(unit);
        steeringForce += alignmentForce * alignmentWeight;
        
        // 限制最大力
        if (steeringForce.magnitude > 10f)
        {
            steeringForce = steeringForce.normalized * 10f;
        }
        
        return steeringForce;
    }
    
    private Vector3 CalculateSeparation(GameObject unit, int unitIndex)
    {
        Vector3 separationForce = Vector3.zero;
        int neighborCount = 0;
        
        for (int i = 0; i < squadUnits.Count; i++)
        {
            if (i == unitIndex || squadUnits[i] == null) continue;
            
            Vector3 toNeighbor = unit.transform.position - squadUnits[i].transform.position;
            float distance = toNeighbor.magnitude;
            
            if (distance < currentFormation.spacing * 0.7f)
            {
                float strength = 1.0f - (distance / (currentFormation.spacing * 0.7f));
                separationForce += toNeighbor.normalized * strength;
                neighborCount++;
            }
        }
        
        if (neighborCount > 0)
        {
            separationForce /= neighborCount;
        }
        
        return separationForce;
    }
    
    private Vector3 CalculateCohesion(GameObject unit)
    {
        Vector3 toCenter = squadCenter - unit.transform.position;
        float distance = toCenter.magnitude;
        
        if (distance > currentFormation.spacing * 3f)
        {
            return toCenter.normalized * 3f;
        }
        
        return Vector3.zero;
    }
    
    private Vector3 CalculateAlignment(GameObject unit)
    {
        Vector3 currentForward = unit.transform.forward;
        Vector3 targetForward = squadForward;
        
        // 计算旋转轴和角度
        Vector3 rotationAxis = Vector3.Cross(currentForward, targetForward);
        
        if (rotationAxis.magnitude > 0.01f)
        {
            return rotationAxis.normalized * 2f;
        }
        
        return Vector3.zero;
    }
    
    public void StopSquad()
    {
        isMoving = false;
        currentPath.Clear();
        currentPathIndex = 0;
        
        Debug.Log("小队停止移动");
    }
    
    public void ChangeFormation(SquadFormation newFormation)
    {
        currentFormation = newFormation;
        UpdateFormationPositions();
        
        Debug.Log($"小队切换队形: {newFormation.type}");
    }
    
    public void AddUnitToSquad(GameObject newUnit)
    {
        if (newUnit != null && !squadUnits.Contains(newUnit))
        {
            squadUnits.Add(newUnit);
            UpdateFormationPositions();
            
            Debug.Log($"添加单位到小队，当前数量: {squadUnits.Count}");
        }
    }
    
    public void RemoveUnitFromSquad(GameObject unit)
    {
        if (unit != null && squadUnits.Contains(unit))
        {
            squadUnits.Remove(unit);
            UpdateFormationPositions();
            
            Debug.Log($"从小队移除单位，剩余数量: {squadUnits.Count}");
        }
    }
    
    public bool IsSquadMoving()
    {
        return isMoving;
    }
    
    public Vector3 GetSquadCenter()
    {
        return squadCenter;
    }
    
    public int GetSquadSize()
    {
        return squadUnits.Count;
    }
    
    void OnDrawGizmosSelected()
    {
        if (!isMoving || currentPath.Count == 0) return;
        
        // 绘制小队路径
        Gizmos.color = Color.blue;
        for (int i = 0; i < currentPath.Count - 1; i++)
        {
            Gizmos.DrawLine(currentPath[i], currentPath[i + 1]);
            Gizmos.DrawSphere(currentPath[i], 0.3f);
        }
        
        Gizmos.DrawSphere(currentPath[currentPath.Count - 1], 0.5f);
        
        // 绘制当前目标点
        if (currentPathIndex < currentPath.Count)
        {
            Gizmos.color = Color.red;
            Gizmos.DrawSphere(currentPath[currentPathIndex], 0.4f);
        }
        
        // 绘制队形位置
        Gizmos.color = Color.green;
        foreach (Vector3 pos in formationPositions)
        {
            Gizmos.DrawWireSphere(pos, 0.2f);
        }
        
        // 绘制小队中心和方向
        Gizmos.color = Color.cyan;
        Gizmos.DrawSphere(squadCenter, 0.5f);
        Gizmos.DrawRay(squadCenter, squadForward * 2f);
    }
}

4.5 寻路系统的性能优化与适用性分析

4.5.1 性能优化策略

在商业项目中，寻路系统的性能至关重要。以下是一些关键的优化策略：

1. 空间分区：使用网格、四叉树或八叉树对导航节点进行空间分区，减少搜索范围。

2. 层级细节（LOD）：根据AI角色与玩家的距离调整寻路精度。

3. 路径缓存：缓存常用路径，避免重复计算。

4. 异步计算：将寻路计算分配到多个帧或工作线程。

5. 增量寻路：当环境变化时，只重新计算受影响的部分路径。

public class OptimizedPathfindingManager : MonoBehaviour
{
    [System.Serializable]
    public class PathCacheEntry
    {
        public Vector3 start;
        public Vector3 end;
        public List<Vector3> path;
        public float timestamp;
        public float hitCount;
        
        public PathCacheEntry(Vector3 start, Vector3 end, List<Vector3> path)
        {
            this.start = start;
            this.end = end;
            this.path = new List<Vector3>(path);
            timestamp = Time.time;
            hitCount = 1;
        }
        
        public bool IsSimilar(Vector3 otherStart, Vector3 otherEnd, float tolerance = 1.0f)
        {
            return Vector3.Distance(start, otherStart) < tolerance && 
                   Vector3.Distance(end, otherEnd) < tolerance;
        }
    }
    
    [Header("缓存配置")]
    [SerializeField] private int maxCacheSize = 100;
    [SerializeField] private float cacheLifetime = 30.0f;
    
    [Header("异步配置")]
    [SerializeField] private int maxConcurrentRequests = 4;
    [SerializeField] private float asyncUpdateInterval = 0.1f;
    
    private List<PathCacheEntry> pathCache;
    private Queue<AStarPathfinder.PathRequest> requestQueue;
    private List<System.Collections.IEnumerator> activeCoroutines;
    private float asyncTimer;
    
    void Awake()
    {
        InitializeOptimizationSystem();
    }
    
    void Update()
    {
        UpdateAsyncProcessing();
        CleanupOldCache();
    }
    
    private void InitializeOptimizationSystem()
    {
        pathCache = new List<PathCacheEntry>();
        requestQueue = new Queue<AStarPathfinder.PathRequest>();
        activeCoroutines = new List<System.Collections.IEnumerator>();
        
        Debug.Log("优化寻路管理器初始化完成");
    }
    
    // 优化的寻路请求
    public void RequestOptimizedPath(Vector3 start, Vector3 end, 
                                    System.Action<List<Vector3>, bool> callback,
                                    GridBasedNavigationGraph grid)
    {
        // 1. 检查缓存
        List<Vector3> cachedPath = GetCachedPath(start, end);
        if (cachedPath != null)
        {
            callback?.Invoke(cachedPath, true);
            return;
        }
        
        // 2. 添加到请求队列
        AStarPathfinder.PathRequest request = new AStarPathfinder.PathRequest(
            start, end, (path, success) => 
            {
                if (success && path.Count > 0)
                {
                    AddToCache(start, end, path);
                }
                callback?.Invoke(path, success);
            }
        );
        
        requestQueue.Enqueue(request);
    }
    
    private List<Vector3> GetCachedPath(Vector3 start, Vector3 end, float tolerance = 1.0f)
    {
        foreach (PathCacheEntry entry in pathCache)
        {
            if (entry.IsSimilar(start, end, tolerance))
            {
                entry.hitCount++;
                entry.timestamp = Time.time;
                
                Debug.Log($"缓存命中! 使用缓存的路径 (命中次数: {entry.hitCount})");
                return new List<Vector3>(entry.path);
            }
        }
        
        return null;
    }
    
    private void AddToCache(Vector3 start, Vector3 end, List<Vector3> path)
    {
        // 移除旧缓存（如果超过最大大小）
        if (pathCache.Count >= maxCacheSize)
        {
            pathCache.Sort((a, b) => a.hitCount.CompareTo(b.hitCount));
            pathCache.RemoveAt(0);
        }
        
        PathCacheEntry newEntry = new PathCacheEntry(start, end, path);
        pathCache.Add(newEntry);
    }
    
    private void UpdateAsyncProcessing()
    {
        asyncTimer += Time.deltaTime;
        if (asyncTimer >= asyncUpdateInterval)
        {
            // 处理队列中的请求
            ProcessRequestQueue();
            asyncTimer = 0f;
        }
    }
    
    private void ProcessRequestQueue()
    {
        while (requestQueue.Count > 0 && activeCoroutines.Count < maxConcurrentRequests)
        {
            AStarPathfinder.PathRequest request = requestQueue.Dequeue();
            GridBasedNavigationGraph grid = FindObjectOfType<GridBasedNavigationGraph>();
            
            if (grid != null)
            {
                System.Collections.IEnumerator coroutine = 
                    AStarPathfinder.FindPathAsync(request, grid);
                
                StartCoroutine(coroutine);
                activeCoroutines.Add(coroutine);
            }
        }
        
        // 清理已完成的协程
        for (int i = activeCoroutines.Count - 1; i >= 0; i--)
        {
            if (!IsCoroutineRunning(activeCoroutines[i]))
            {
                activeCoroutines.RemoveAt(i);
            }
        }
    }
    
    private bool IsCoroutineRunning(System.Collections.IEnumerator coroutine)
    {
        // 简化的协程运行状态检查
        // 在实际项目中可能需要更精确的方法
        return coroutine != null;
    }
    
    private void CleanupOldCache()
    {
        for (int i = pathCache.Count - 1; i >= 0; i--)
        {
            if (Time.time - pathCache[i].timestamp > cacheLifetime)
            {
                pathCache.RemoveAt(i);
            }
        }
    }
    
    // 空间分区优化
    public class SpatialPartitioner
    {
        private Dictionary<Vector2Int, List<PathNode>> spatialGrid;
        private float cellSize;
        private int gridSize;
        
        public SpatialPartitioner(float cellSize, int gridSize)
        {
            this.cellSize = cellSize;
            this.gridSize = gridSize;
            spatialGrid = new Dictionary<Vector2Int, List<PathNode>>();
        }
        
        public void BuildSpatialGrid(PathNode[,] nodeGrid, int sizeX, int sizeY)
        {
            spatialGrid.Clear();
            
            for (int x = 0; x < sizeX; x++)
            {
                for (int y = 0; y < sizeY; y++)
                {
                    PathNode node = nodeGrid[x, y];
                    Vector2Int gridCoord = WorldToGrid(node.WorldPosition);
                    
                    if (!spatialGrid.ContainsKey(gridCoord))
                    {
                        spatialGrid[gridCoord] = new List<PathNode>();
                    }
                    
                    spatialGrid[gridCoord].Add(node);
                }
            }
        }
        
        public List<PathNode> GetNodesInRadius(Vector3 position, float radius)
        {
            List<PathNode> nodesInRadius = new List<PathNode>();
            Vector2Int centerCoord = WorldToGrid(position);
            
            int gridRadius = Mathf.CeilToInt(radius / cellSize);
            
            for (int dx = -gridRadius; dx <= gridRadius; dx++)
            {
                for (int dy = -gridRadius; dy <= gridRadius; dy++)
                {
                    Vector2Int gridCoord = new Vector2Int(
                        centerCoord.x + dx,
                        centerCoord.y + dy
                    );
                    
                    if (spatialGrid.ContainsKey(gridCoord))
                    {
                        foreach (PathNode node in spatialGrid[gridCoord])
                        {
                            if (Vector3.Distance(position, node.WorldPosition) <= radius)
                            {
                                nodesInRadius.Add(node);
                            }
                        }
                    }
                }
            }
            
            return nodesInRadius;
        }
        
        private Vector2Int WorldToGrid(Vector3 worldPosition)
        {
            int x = Mathf.FloorToInt(worldPosition.x / cellSize);
            int z = Mathf.FloorToInt(worldPosition.z / cellSize);
            
            return new Vector2Int(x, z);
        }
    }
    
    public int GetCacheSize()
    {
        return pathCache.Count;
    }
    
    public int GetQueueSize()
    {
        return requestQueue.Count;
    }
    
    public float GetCacheHitRate()
    {
        if (pathCache.Count == 0) return 0f;
        
        float totalHits = 0f;
        foreach (PathCacheEntry entry in pathCache)
        {
            totalHits += entry.hitCount;
        }
        
        return totalHits / pathCache.Count;
    }
}

4.5.2 A*寻路技术的适用性分析

A*寻路算法在不同游戏类型和场景中的适用性有所差异：

1. 策略游戏（RTS）：

   • 适合网格导航图
   • 需要小队寻路和队形保持
   • 性能要求高，需要优化算法

2. 角色扮演游戏（RPG）：

   • 适合导航网格
   • 需要复杂地形支持和多层建筑寻路
   • 可以接受较高的计算成本

3. 第一人称射击游戏（FPS）：

   • 需要战术寻路
   • 动态障碍物处理至关重要
   • 实时性能要求极高

4. 开放世界游戏：

   • 需要层级寻路（粗寻路+细寻路）
   • 必须支持动态世界变化
   • 内存优化是关键

5. 手机游戏：

   • 计算资源有限
   • 需要简化的寻路算法
   • 可以考虑预计算路径

选择寻路方案时需要考虑：

• 游戏世界的规模和复杂度
• AI角色的数量和行为复杂度
• 平台的性能限制
• 开发团队的技术能力
• 项目的开发周期和预算

总结

A*寻路算法是游戏AI开发中的核心技术之一。通过合理的导航图设计、算法优化和战术扩展，可以创建出适应各种游戏类型的智能寻路系统。在实际项目中，需要根据具体需求选择合适的实现方案，并在性能、精度和开发成本之间找到平衡点。

本专题详细介绍了A寻路算法的理论基础、多种实现方案以及高级应用技巧。通过网格导航图、可视点导航图和导航网格的对比分析，开发者可以根据项目需求选择最适合的导航表示方法。战术寻路、多层建筑寻路和小队寻路等高级功能则展示了A算法在实际游戏开发中的强大扩展能力。

在商业项目开发中，除了算法本身的正确性，还需要特别关注系统的性能优化、内存管理和动态更新能力。通过缓存、异步计算、空间分区等优化技术，可以确保寻路系统在复杂游戏场景中仍能保持高性能。

最后，寻路系统的成功不仅取决于技术实现，还需要与游戏设计紧密结合。一个好的寻路系统应该能够支持各种游戏玩法需求，为玩家创造流畅、自然的游戏体验。