如何在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）

当前问题与期望目标 #

现有A*算法不支持路径长度限制，会生成需要6个移动点数的路径（因该路径总成本最低），超出可用移动点数限制。

期望的最优路径需满足以下优先级：

1. 优先耗尽全部5个移动点数
2. 尽可能减少传送操作

符合要求的最优路径示例：

• 向南传送2格
• 向南行走4格
  反向操作同样可行

代码现状与尝试调整 #

当前使用的A*算法实现未暴露完整路径，无法提前终止过长路径，代码片段如下：

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

尝试过调整传送成本，但未达到预期：

• 降低传送成本：算法优先选择传送，违背传送成本更高的设定
• 设传送成本与行走成本相同：算法仍偏好传送，因返回的路径单元格数量更少

内容的提问来源于stack exchange，提问作者cardiaque66