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

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

StackOverflow 文档

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

StackOverflow 文档

为了选择移动到下一个方格,我们需要考虑 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 值:

StackOverflow 文档

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

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

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

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

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

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

StackOverflow 文档

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

StackOverflow 文档

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

StackOverflow 文档

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

StackOverflow 文档

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

StackOverflow 文档

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

StackOverflow 文档

我们搬到那里:

StackOverflow 文档

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