通过没有障碍的迷宫路径搜寻

假设我们有以下 4 乘 4 格：

让我们假设这是一个迷宫。但是，没有墙壁/障碍物。我们只有一个起点（绿色方块）和一个终点（红色方块）。我们还假设为了从绿色变为红色，我们不能对角移动。所以，从绿色方块开始，让我们看看我们可以移动到哪个方块，然后用蓝色突出显示它们：

为了选择移动到下一个方格，我们需要考虑 2 个启发式：

1. g 值 - 这个节点离绿色方块有多远。
2. h 值 - 这是该节点离红色方块的距离。
3. f 值 - 这是 g 值和 h 值的总和。这是告诉我们要移动到哪个节点的最终数字。

为了计算这些启发式算法，我们将使用这个公式：distance = abs(from.x - to.x) + abs(from.y - to.y)

这被称为 曼哈顿距离 公式。

让我们计算绿色方块左边的蓝色方块的 g 值：abs(3 - 2) + abs(2 - 2) = 1

大！ 我们得到了价值：1。现在，让我们尝试计算 h 值：abs(2 - 0) + abs(2 - 0) = 4

完善。现在，让我们得到 f 值：1 + 4 = 5

因此，该节点的最终值为 5。

让我们对所有其他蓝色方块做同样的事情。每个正方形中心的大数字是 f 值，而左上角的数字是 g 值，右上角的数字是 h 值：

我们计算了所有蓝色节点的 g，h 和 f 值。现在，我们选哪个？

无论哪个具有最低的 f 值。

但是，在这种情况下，我们有 2 个具有相同 f 值的节点，5。我们如何在它们之间进行选择？

简单地说，要么随机选择一个，要么设置优先级。我通常喜欢这样的优先级：“右>上>下>左”

其中一个 f 值为 5 的节点将我们带入向下方向，另一个带我们向左。由于 Down 的优先级高于 Left，因此我们选择了 Down 的方块。

我现在标记我们计算启发式的节点，但没有移动到橙色，我们选择的节点为青色：

好的，现在让我们为青色节点周围的节点计算相同的启发式：

同样，我们选择从青色节点向下的节点，因为所有选项都具有相同的 f 值：

让我们计算青色节点唯一的邻居的启发式：

好吧，因为我们将遵循我们一直遵循的相同模式：

再一次，让我们计算节点邻居的启发式：

我们搬到那里：

最后，我们可以看到我们旁边有一个胜利的广场，所以我们搬到那里，我们就完成了。