最短路径，但在物理迷宫上

Question

我正在实现一个能够解决任何迷宫的机器人(机器人只有前端传感器，但我让它扫描周围环境)，我能够让它将迷宫转换为地图，其中0代表墙壁，1代表道路，可能有倾斜的道路。现在，机器人在转弯方面并不快，但在直线上移动的速度相当快。因此，通过有点倾斜的走廊的正常最短路径算法将很慢，尽管路径足够宽。

例如，我们发现

0001111111000
0011111110000
0111111100000
1111111000000
1111110000000

作为可能的地图。我希望机器人能够识别出它可以沿对角线行走，甚至可以直接向上走，然后再右转，而不是在正常的最短路径算法中每次都转弯。

有什么想法吗？另外，一个完整的算法改变也是受欢迎的--我对此还是个新手。

Answer 1

前段时间我也遇到过类似的问题。

您可以将权重分配给周围的单元格，而将较少的权重分配给前面的单元格，从而制作一个在移动过程中生成的权重图。

我使用Dijkstra算法，周围单元的权重为2，前面的单元的权重为1，您必须将机器人的方向传递给Dijkstra，当将它们添加到优先级队列时，当从队列中提取单元时，添加与提取的单元中保存的方向相关的邻居。

然后进行移动，然后重新计算修改后的Dijkstra，以找到最近的不可见单元。