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

Question

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

这是它正在做的事情：

所以我们从 0,0（橙色）开始，想要到达 1,2（绿色）。首先，它计算橙色方块的两个选项，北和东，并针对 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是一个无效的正方形，但是移动到1,1的f值被保存为3，所以它再次被忽略，让我们在0之间没有有效路径， 0 和 1,2。我错过了什么？

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

PCell：保存单元格坐标
PPair：将细胞坐标保存为PCell和F值
FVectorInt: 3-D整数向量
FPathCell：保存父坐标，以及 f、g 和 h 值。
cellDetails 是 FPathCell
closedMap 是 <key, value> 作为 <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 向量换成适当的动作。

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.

这一定是你的错误。这些选项不应是 'ignored'，而是 'delayed till they are the next-best options'。这样做的方式是，在 A* 的每次迭代中，您应该 select 具有最低 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++ 没有它们。您可以在网上找到实现这些功能的库。

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

A-Star Search Algorithm won't find a valid path

c++

algorithm

path-finding

a-star