<分区>
我已经实现了 A 星算法来查找简单网格上两个节点之间的路径。我目前正在没有障碍物的网格上进行测试，它似乎正在寻找最短路径，但这不是“理想”的最短路径，我的意思是不会随机改变方向的路径。理想情况下，我希望它继续朝一个方向前进，这意味着它只会改变方向一次。
我该如何强制执行？我正在查看我考虑在打开列表中扩展哪个节点的代码部分，如果下一个图 block 有相同的 f 值，但不是很优雅。
<分区>
我已经实现了 A 星算法来查找简单网格上两个节点之间的路径。我目前正在没有障碍物的网格上进行测试，它似乎正在寻找最短路径，但这不是“理想”的最短路径，我的意思是不会随机改变方向的路径。理想情况下，我希望它继续朝一个方向前进，这意味着它只会改变方向一次。
我该如何强制执行？我正在查看我考虑在打开列表中扩展哪个节点的代码部分，如果下一个图 block 有相同的 f 值，但不是很优雅。
最佳答案
给定你的图 G=(V,E)，其中 V 中的每个 v 代表一个单元格，每条边 (u,v) 是可能的移动，您可以创建一个新的(加权)图 G'=(V',E')，如下所示:
V' = V_u U V_d U V_l U V_r - 每组代表您最后完成的移动类型，V_u = { v_u |对于 V 中的每个 v，对于 V_d,V_l,V_r
现在，对于 E 中的每条边 (u,v):
(u_l,v_l,1) 和 (u_r,v_l,1+eps),(u_u,v_l, 1+eps),(u_d,v_l,1+eps)。直觉上 - 你对“改变方向”给予小的惩罚 (eps)，如果保持相同的方向则没有惩罚。(u_u,v_u,1) 和 (u_r,v_u,1+eps),(u_l,v_u, 1+eps),(u_d,v_u,1+eps)。 (同样)确保 eps 足够小，只影响相同长度的路径。 1/(|V|+1) 应该这样做。
同时确保您现在有 4 个目标(t_u,t_d,t_l,t_r，其中 t 是原始目标)。
这为您提供了一个包含 4*|V| 个顶点的图，现在倾向于保持相同的方向而不是改变它。您可以坚持以前的启发式方法 - 如果它是可接受的，它将保持这种状态。
关于java - 不走视觉理想路线的星型算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23171524/