c++ - A-Star 搜索算法找不到有效路径

Question

我正尝试在我的 3D 网格中实现 A* 算法来寻路。我一直在学习教程，但没有找到有效的路径。我已经逐步查看我的代码以了解发生了什么，但我不知道如何解决问题。对于最基本的测试，我只使用 2-D 网格(它是 3-D，但只有一个 Z 选项，所以基本上是 2-D)。

这是它正在做的事情:

所以我们从 0,0(橙色)开始并希望到达 1,2(绿色)。首先，它计算橙色方 block 的两个选项，北和东，并针对 3 和 2.414 的 F 值获得 2 和 1.414 的距离。它移动到东广场 (0,1)。伟大的。但是现在它从 0,1 计算出两个空心正方形，即 1,1 和 0,2，它们的 g 值为 2，h 值(距离)为 1，因此它们的 F 值均为 3。

由于它们的 F 值为 3，而我们已经有一个 F 值为 3 的选项(从起点开始为 1,0)，因此这两个选项将被忽略，即使它们显然是最佳选项。

然后它继续前进并切换到移动到 1,0，然后再次将 1,1 计算为 3，将 2,0 计算为 4.236。 1,1 的 f 值并不大于我们当前的 f 值，因此它被忽略，我们向上移动到 2,0。

2,0 只能向右移动。

2,1 只能向下移动，因为 2,2 是一个无效方 block ，但是移动到 1,1 的 f 值被保存为 3，所以它再次被忽略，让我们在 0,0 和 0,0 之间没有有效路径1,2。我错过了什么？

这是我的路径循环的片段。这里有一堆自定义结构，我正在使用 Unreal Engine 中的 TMap 来存储我的封闭列表，但我认为这对问题并不重要。以下是关于这些结构的简要说明:

• PCell : 保存单元格坐标
• PPair : 将单元格坐标保存为 PCell 和 F 值
• FVectorInt : 3-D整数 vector
• FPathCell : 保存父坐标以及 f、g 和 h 值。
• cellDetails是 FPathCell 的 3D 动态数组
• closedMap是一个带有 <key, value> 的 TMap作为<IntVector, bool>

还有 locationIsWalkable(FVectorInt, StepDirection)只是检查玩家是否可以从某个方向走到一个单元格的代码。你可以忽略那部分。

    std::set<PPair> openList;
    PPair originPair = PPair();
    originPair.cell = PCell(i, j, k);
    originPair.f = 0.0;
    openList.insert(originPair);

    bool foundDestination = false;
    FPathCell destPair;
    FVectorInt destCell;

    while (!openList.empty() && !foundDestination)
    {
        iterations++;
        PPair p = *openList.begin();
        
        //Remove vertex
        openList.erase(openList.begin());

        //Add vertex to closed list
        i = p.cell.i;
        j = p.cell.j;
        k = p.cell.k;
        closedMap.Remove(FIntVector(i, j, k));
        closedMap.Add(FIntVector(i, j, k), true);

        double gNew, hNew, fNew;

        //Generate movement options
        //Option 1: NORTH (+X)
        //Process if valid movement
        if (locationIsWalkable(FVectorInt(i + 1, j, k), StepDirection::North))
        {
            FVectorInt check = FVectorInt(i + 1, j, k);

            //If this cell is the destination
            if (check == destination)
            {
                foundDestination = true;
                
                //Set the parent of the destination cell
                cellDetails[check.x][check.y][check.z].parent_i = i;
                cellDetails[check.x][check.y][check.z].parent_j = j;
                cellDetails[check.x][check.y][check.z].parent_k = k;
                destPair = cellDetails[check.x][check.y][check.z];
                destCell = check;
                break;
            }

            //Else if this cell is not in the closed list
            else if (!closedMap.FindRef(FIntVector(check.x, check.y, check.z)))
            {
                gNew = cellDetails[i][j][k].g + 1;
                hNew = calculateHValue(check, destination);
                fNew = gNew + hNew;

                if (cellDetails[check.x][check.y][check.z].f == FLT_MAX ||
                    cellDetails[check.x][check.y][check.z].f > fNew) {
                    
                    PPair cellPair = PPair();
                    cellPair.cell = PCell(check.x, check.y, check.z);
                    cellPair.f = fNew;
                    openList.insert(cellPair);

                    cellDetails[check.x][check.y][check.z].f = fNew;
                    cellDetails[check.x][check.y][check.z].g = gNew;
                    cellDetails[check.x][check.y][check.z].h = hNew;
                    cellDetails[check.x][check.y][check.z].parent_i = i;
                    cellDetails[check.x][check.y][check.z].parent_j = j;
                    cellDetails[check.x][check.y][check.z].parent_k = k;
                }
            }
        }

        //11 other movement options
    }

inline bool operator<(const PPair& lhs, const PPair& rhs)
{
    return lhs.f < rhs.f;
}

有 12 个移动选项(北、南、东、西、上+北、下+北等)，但它们基本上都使用相同的代码，只是换掉了 check。适当运动的 vector 。

Here's the tutorial I followed

Answer 1

Since their F values are 3 and we already have an option with an F value of 3 (1,0 from the starting point), these two options are ignored even though they are clearly the best options.

这一定是你的错误。这些选项不应被“忽略”，而是“延迟到它们成为下一个最佳选项”。这样做的方式是，在 A* 的每次迭代中，您应该选择 F 分数最低的开放单元格。

在您的示例中，展开0,1(以获得0,2 和1,1)后，您的开集应该看起来像:

(1,0):3   (1,1):3   (0,2):3

(也可以是这些的任何其他排列，因为它们具有相同的分数。)

现在假设它选择访问 1,0。它将 2,0 添加到队列中，但是 1,1 和 0,2 应该仍然存在:

(1,1):3   (0,2):3   (2,0):4.236

由于 2,0 的 F-score 高于 1,1 或 0,2，它不会尚未选择。相反，您的算法应在本次迭代中选择 1,1 或 0,2，从而到达目的地 1,2。

至于您的代码，您正在为 openList 使用 std::set，这可以防止队列中有多个具有相同分数的实例。您可以使用 multiset 或 priority_queue 来解决这个问题。然而，A* 可以降低开放集中节点的权重，并且两种数据结构都不允许在亚线性时间内进行该操作。通过多次插入同一个节点(每次它的分数降低)，并在它关闭后忽略任何弹出，您仍然会得到一个正确的算法，尽管不是最优的。

正确的 A* 实现通常使用二项式或斐波那契堆。不幸的是 C++ 没有它们。您可以在网络上找到实现这些功能的库。