无法实现有限转弯的基于网格的寻路

Question

我正在制作一个基于网格的2D游戏，并且由于具有挑战性的代码而陷入停滞状态。如果可能的话，我需要从网格中的一个单元格导航到另一个单元格，但最多需要2个回合。

红球是目标，绿色路径是有效的，“转弯”由蓝色圆圈突出显示。

没有粗暴的强迫问题，并检查每个可能的路径怎么可能这样做？我已经尝试了一些想法和一个*实现，但到目前为止没有运气。任何想法，使用统一的API或其他任何想法，都非常感谢。

Answer 1

这可以使用普通A *通过从原始网格创建专门设计的定向加权图来解决。

诀窍是创建一个包含多个“图层”的图形。层0表示到目前为止已经形成0匝，层1表示形成1匝，层2表示2匝。如果节点可以在没有转弯的情况下到达，则节点连接到同一层上的邻居，如果它们需要转弯，则它在下一层上的邻居。

希望这是您创建图表的足够信息，但如果没有，明确的步骤将是：

1. 创建6个图表，Layer_0_Horizontal，Layer_0_Vertical，Layer_1_Horizontal，Layer_1_Vertical，Layer_2_Horizontal，Layer_2_Vertical。
2. 对于Horizontal层中的每个节点，将其边缘移除到其垂直邻居，并将其替换为下一层中的节点的边缘，例如。 Layer_1_Vertical低于Layer_0_Horizontal。 Layer_2的边缘将不会被替换。对Vertical图层/水平边做同样的事情。
3. 创建一个虚假的“开始”节点，并将其连接到两个Layer_0节点，这两个节点表示具有0权重边的相同网格方块。如果您的A *实现仅支持一个目标节点，请对目标执行相同操作。

如果你想要更长的路径，在较短路径上具有较少的转弯且具有更多的转弯（即使只有两圈也是如此），给予层之间的边缘极大的重量。