更换起点使用Dijkstra算法时Unity无响应问题求助

你在Unity 2019.1.14f1（Windows 10 Enterprise环境，硬件为Intel Xeon E5-1650 v4/32GB内存/GTX1080最新驱动）中，基于NavNodeProxy和NavLinkProxy实现Dijkstra路径生成时遇到了一个奇怪的问题：初始路径生成、修改终点都正常，但修改起点后Unity直接无响应，交换起点终点后问题依旧。结合你的代码，我梳理了核心问题和修复方案：

核心问题排查 #

从你的代码逻辑来看，导致无响应的最可能原因有两个：

1. 节点状态未在每次搜索前重置 #

第一次运行Dijkstra时，部分节点会被标记为Visited = true，且MinCostToStart会被设置为具体数值。当你修改起点重新搜索时，这些旧状态没有被清除：

• 被标记为Visited的节点会被直接跳过，导致算法无法完整遍历路径，甚至陷入逻辑死循环
• 残留的MinCostToStart值会打乱优先级队列的判断逻辑，可能让队列无法正常清空，导致程序假死

2. 优先级队列的存在性检查效率极低 #

你用pQueue.heapList.Contains(connectingNode)判断节点是否在队列中，而普通List的Contains是O(n)复杂度。当场景中节点数量较多时，这个操作会急剧拖慢性能，最终表现为Unity无响应。

具体修复步骤 #

步骤1：每次搜索前重置所有节点状态 #

在调用DijkstraSearch方法前，必须遍历所有NavNodeProxy，重置它们的核心状态：

// 假设你在VenueManager中维护了所有节点的集合_AllNavNodes
foreach(var node in venueManager._AllNavNodes)
{
    node._NavNodeInfo.Visited = false;
    node._NavNodeInfo.MinCostToStart = Mathf.Infinity;
    node._NavNodeInfo.NearestToStart = null;
}
// 然后再调用DijkstraSearch
DijkstraSearch(venueManager, newStart, end);

如果没有全局节点集合，也可以从_ActiveNavLinks中提取所有关联节点进行重置。

步骤2：优化优先级队列的存在性检查 #

替换List.Contains的低效判断，改用HashSet<NavNodeProxy>跟踪队列中的节点，把检查复杂度降到O(1)：

private static void DijkstraSearch(VenueManager venueManager, NavNodeProxy start, NavNodeProxy end) {
 var pQueue = new BinaryHeap<NavNodeProxy>();
 var inQueue = new HashSet<NavNodeProxy>(); // 新增：跟踪队列中的节点

 // 重置起点状态（全局重置后可简化）
 start._NavNodeInfo.MinCostToStart = 0;
 start._NavNodeInfo.Visited = false;
 start._NavNodeInfo.NearestToStart = null;

 pQueue.Add(start);
 inQueue.Add(start);

 do {
 var node = pQueue.Remove();
 inQueue.Remove(node);

 // 替换FindAll：如果提前构建了节点-链接字典，这里可以更高效（见步骤3）
 List<NavLinkProxy> nodeLinks = venueManager._ActiveNavLinks.FindAll(result => (result._NavLinkInfo.n1 == node) || (result._NavLinkInfo.n2 == node));
 for (int i = 0; i < nodeLinks.Count; i++) {
 NavNodeProxy connectingNode = nodeLinks[i]._NavLinkInfo.n1 == node ? nodeLinks[i]._NavLinkInfo.n2 : nodeLinks[i]._NavLinkInfo.n1;

 if (connectingNode._NavNodeInfo.Visited) continue;

 float newCost = node._NavNodeInfo.MinCostToStart + nodeLinks[i]._NavLinkInfo.horizontalLength;
 if (newCost < connectingNode._NavNodeInfo.MinCostToStart) {
 connectingNode._NavNodeInfo.MinCostToStart = newCost;
 connectingNode._NavNodeInfo.NearestToStart = node;

 if (!inQueue.Contains(connectingNode)) {
 pQueue.Add(connectingNode);
 inQueue.Add(connectingNode);
 }
 }
 }
 node._NavNodeInfo.Visited = true;
 if (node == end) return;
 } while (pQueue.heapList.Any());
}

步骤3：优化节点链接的查找方式 #

当前用FindAll遍历所有链接找当前节点的关联链接，也是O(n)复杂度。可以提前在VenueManager中构建一个字典，把节点映射到它的所有链接：

// 在VenueManager中添加字典
public Dictionary<NavNodeProxy, List<NavLinkProxy>> NodeToLinks;

// 在初始化方法（如Start/Awake）中构建字典
private void InitNavLinksMapping()
{
    NodeToLinks = new Dictionary<NavNodeProxy, List<NavLinkProxy>>();
    foreach(var link in _ActiveNavLinks)
    {
        // 给n1添加链接
        if(!NodeToLinks.ContainsKey(link._NavLinkInfo.n1))
            NodeToLinks[link._NavLinkInfo.n1] = new List<NavLinkProxy>();
        NodeToLinks[link._NavLinkInfo.n1].Add(link);

        // 给n2添加链接
        if(!NodeToLinks.ContainsKey(link._NavLinkInfo.n2))
            NodeToLinks[link._NavLinkInfo.n2] = new List<NavLinkProxy>();
        NodeToLinks[link._NavLinkInfo.n2].Add(link);
    }
}

// 然后在DijkstraSearch中替换FindAll
List<NavLinkProxy> nodeLinks = venueManager.NodeToLinks[node];

这会进一步降低算法的时间复杂度，避免大量重复遍历操作。

验证建议 #

1. 先添加全局节点状态重置的代码，测试修改起点的场景，看是否还会无响应
2. 如果仍有性能问题，再逐步添加后面的优化步骤

内容的提问来源于stack exchange，提问作者Calvin Dsouza