如何限制A*中的路径长度？

Question

我的移动点数量和在迷宫中传送的能力有限，并且希望找到最佳路径。唯一的问题是 A* 不允许路径限制，这意味着在此示例中导航可能太长。

最佳路径是尝试使用最多移动点和最少传送动作到达目标的路径。

迷宫

['o', 'S', 'o']
['o', 'o', 'o']
['o', 'o', 'o']
['o', 'o', 'o']
['o', 'o', 'o']
['o', 'o', 'o']
['o', 'T', 'o']
['o', 'o', 'o']
['o', 'o', 'o']

• o

  -- 空单元格

• S

  ——开始

• T

  ——目标

^{为简洁起见，未包括障碍。}

规则

• 特工只有5个移动点
• 允许传送正好2格

图表

• 每个相邻单元格的连接成本为 10（步行）
• 距当前单元格 2 个单元格的每个单元格设置为 22（传送时每个单元格成本 11）

当前行为

算法将尝试使用 6 个移动点，因为这是最便宜的路径。

最优路径

• 向南跳2格
• 向南走 4 个小区

^{反过来也有效}

代码

启发式代码不会暴露整个路径，这意味着我无法在它走得太远之前阻止它。

astar(
    from_position,
    |point| get_connections_for_point(point),
    |point| point.distance_to(to_position),
    |point| point == to_position,
);

我尝试将隐形传态成本设置得较低，但这会导致算法使用常规步行，这是不正确的，因为隐形传态的成本更高。

我尝试将隐形传态成本设置为与步行成本相同，但算法也更喜欢隐形传态，因为它在返回的 Vec 中产生更少的单元。

Answer 1

我发现的一种可能的解决方案是将两种成本设置为相同的值，并迭代 A* 算法返回的所有路径，并根据可用的移动点和找到具有最少隐形传送的路径和到达目标的路径使用过。

// get a collection of paths
astar_bag(
    from_position,
    |point| get_connections_for_point(point),
    |point| point.distance_to(to_position),
    |point| point == to_position,
);