UE4中基于路点的寻路函数无限循环问题求助

嘿，我帮你揪出了导致无限循环的核心问题，还有几个影响寻路逻辑的小bug，咱们一个个说清楚：

1. 最致命的循环诱因：插入错误的节点 #

你的for循环最后一行写的是：

openList.insert(startNode);

这完全错了！你应该把当前遍历到的**node**插入openList，而不是把startNode（当前正在处理的节点）重新塞回去。这就导致每次循环都往openList里加同一个节点，永远清不空，直接造成无限循环。正确的写法是：

openList.insert(node);

2. OpenList的逻辑不符合A*要求 #

你用了set<UWaypoint*>来存openList，但set是按指针地址排序的，而A*需要每次从openList中取出f值（你的distance变量，即g+h）最小的节点。用set的话，openList.begin()拿到的不一定是最优节点，不仅逻辑错误，还可能导致寻路卡死。

建议换成priority_queue，或者每次遍历openList找到f值最小的节点。这里先给你用遍历找最小值的修正方案（容易理解），后续可以优化成优先队列。

3. ClosedList的效率优化 #

用vector存closedList，每次find都是线性扫描，节点多了会非常慢。换成unordered_set<UWaypoint*>可以把查找时间降到O(1)。

4. 完善OpenList中已有节点的处理逻辑 #

原代码里如果节点已经在openList里就直接跳过，但A*的正确逻辑是：如果当前路径到这个节点的g值比之前记录的更小，应该更新节点的previous和distance（f值）。

修正后的完整代码 #

TArray<FVector> UWaypointsPathfinding::GetPath(UWaypoint* startNode, UWaypoint* goalNode) {
    if (!startNode || !goalNode) {
        return TArray<FVector>(); // 空值判断，避免崩溃
    }

    UWaypoint* currentNode = startNode;
    unordered_set<UWaypoint*> openSet;
    unordered_set<UWaypoint*> closedSet;
    openSet.insert(startNode);

    // 初始化起始节点：f = g + h，g初始为0
    startNode->previous = nullptr;
    float startToGoalDist = FVector::Dist(startNode->GetOwner()->GetActorLocation(), goalNode->GetOwner()->GetActorLocation());
    startNode->distance = 0 + startToGoalDist;

    while (!openSet.empty()) {
        // 从openSet中找到f值最小的节点
        currentNode = *openSet.begin();
        for (UWaypoint* node : openSet) {
            if (node->distance < currentNode->distance) {
                currentNode = node;
            }
        }

        // 移除当前节点到closedSet
        openSet.erase(currentNode);
        closedSet.insert(currentNode);

        // 到达目标节点，退出循环
        if (currentNode == goalNode) {
            break;
        }

        // 遍历相邻节点
        for (UActorComponent* comp : currentNode->nearest) {
            UWaypoint* neighbor = comp->FindComponentByClass<UWaypoint>();
            if (!neighbor) {
                continue; // 空值判断，避免崩溃
            }

            // 如果邻居在closedSet里，跳过
            if (closedSet.find(neighbor) != closedSet.end()) {
                continue;
            }

            // 计算当前路径的g值和新的f值
            float currentG = currentNode->distance - FVector::Dist(currentNode->GetOwner()->GetActorLocation(), goalNode->GetOwner()->GetActorLocation());
            float newG = currentG + FVector::Dist(neighbor->GetOwner()->GetActorLocation(), currentNode->GetOwner()->GetActorLocation());
            float newF = newG + FVector::Dist(neighbor->GetOwner()->GetActorLocation(), goalNode->GetOwner()->GetActorLocation());

            // 如果邻居不在openSet，或者新路径更优则更新
            if (openSet.find(neighbor) == openSet.end() || newF < neighbor->distance) {
                neighbor->previous = currentNode;
                neighbor->distance = newF;

                if (openSet.find(neighbor) == openSet.end()) {
                    openSet.insert(neighbor);
                }
            }
        }
    }

    // 回溯生成从起点到终点的路径
    TArray<FVector> path;
    UWaypoint* tempNode = goalNode;
    while (tempNode != nullptr) {
        path.Insert(tempNode->GetOwner()->GetActorLocation(), 0);
        tempNode = tempNode->previous;
    }

    return path;
}

额外说明 #

• 我加了空值判断，避免空指针崩溃；
• 拆分了g值和f值的计算，让逻辑更清晰；
• 补充了路径回溯的代码，原代码里这部分是空的；
• 如果要进一步优化，可以把openSet换成priority_queue，自定义排序规则按f值从小到大，这样不用每次遍历找最小值，效率更高。

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