没有对角线移动

我目前正在试图实现在C++中使用A * A *寻路：http://www.policyalmanac.org/games/aStarTutorial.htm 没有对角线移动

不过，对于第一个版本，我决定不包括对角线移动。

在C点的总结部分，在那里它循环检查当前点的邻居：

for each neighbour of the current square (above, below, left, right) 
    if neighbour on closed list or not walkable { 
     continue 
    } 

    if neighbour not in open list { 
     add to open list 
     set parent of neighbour to current square 
     update F, G, H values 
    } else if neighbour is on open list { 
     check to see if this path to that square is better, 
     using G cost as the measure. A lower G cost means that this is a better path. 
     If so, change the parent of the square to the current square, 
     and recalculate the G and F scores of the square. 
    }

如果我只允许4方向的运动，我仍然需要检查G值，看是否该广场的路径更好？例如，从起点开始，起点的所有4个邻居将具有相同的g。

来源

2016-12-05 PrimateJunkie

如果我没有记错，所有的直接邻居都有相同的g成本，但是如果你的目标位于你所在位置的西北斜向，那么从西或北邻居开始的路径的g成本将低于g成本如果你是从东方或南方邻居开始的话。 – mrogers

@NicoSchertler那么我应该检查具有最低g成本的邻居吗？然后将该平方的父元素设置为当前平方并重新更新值？ – PrimateJunkie

A *算法的步骤不会根据集合中的项目数量（当前单元格的邻居）而改变。你甚至可以在地图上有邻居清除的虫洞/传送器（除了相邻的单元格外），A *仍然可以工作。 –

检查较低G成本的重点是为该方块设置一条新路径，前提是找到更好的路径。您最初可能会找到从A到C的路径，但稍后搜索时，您会发现到C的邻居的不同路径。如果C不在封闭列表中，则新路径C的G成本可能会低于第一个，所以你想用更好的G（因此F）值来更新C.

来源

2016-12-05 19:16:20 aah

这是我陷入困境的地方。因此，在查看每个邻居时，我应该检查一下，看看该邻居是否具有比该节点的父节点+邻居与父节点之间的距离更低的g成本？@aah – PrimateJunkie

如果一个邻居在打开的列表中，但没有关闭的列表，这意味着它有一个以前的父母。因此，您正在计算基于新父母的G成本，并将其与旧父母的G成本进行比较，并使用两者中的较小者。您不会将父母的G成本与邻居进行比较。 – aah

@PrimateJunkie为了说明，将邻居相对于旧父代的G代价与邻居相对于新父代的G代价进行比较。因此，如果相邻方块之间的权重为W（*，*），并且旧父项为P1，新项为P2，则比较G（P1）+ W（P1，C）与G（P2）+ W P2，C），其中C是邻居平方。 – aah

我们来分析一下情况。基本点是图中的每个边都具有相同的权重。

假设您目前在顶点c并且分析了邻居n。那么邻居n的更新距离将是distance(c) + w，其中w是统一的边缘长度。现在的问题是如果n可以有比通过不同的路径更大的距离。

假设以前的父母p为n这将导致更长的路径。那么，n的距离是distance(p) + w。为了该表达式比从c更新的成本较大，下面需要持有：

distance(p) + w > distance(c) + w 
distance(p) > distance(c)

所以p将不得不远离开始比c。如果你使用Dijkstra算法，这是不可能的，因为这意味着p将在c之后被修复。但是你使用A *并用启发式确定顺序。因此，以下两个条件需要保留：

distance(p) > distance(c) 
distance(p) + heuristic(p) <= distance(c) + heuristic(c) 
<=> heuristic(p) <= heuristic(c) - (distance(p) - distance(c))

所以它归结为您的启发式。广泛使用的曼哈顿距离启发式允许这样做。所以如果你使用这种启发式，你必须检查一个更低的成本。如果你的启发式不允许上述条件（例如Dijkstra案例中的恒定启发式），那么你就不会。

来源

2016-12-05 19:28:33

没有对角线移动

回答

相关问题