我正在实施一个机器人能够解决任何迷宫（机器人只有前传感器，但我让它扫描周围的环境），我能够让它将迷宫变成一个 Map ，其中0代表墙壁， 1代表道路，可能是倾斜的道路 . 现在，机器人不是快速转弯，而是沿着直线向下移动相当快 . 因此，通过稍微倾斜的走廊的正常最短路径算法将是缓慢的，尽管路径足够宽 .
例如，我们发现
0001111111000
0011111110000
0111111100000
1111111000000
1111110000000
作为一个可能的 Map . 我希望机器人能够识别出它可以对角地行走，或者甚至只是直接然后向右然后向右移动，而不是每次都用正常的最短路径算法转动 .
有任何想法吗？此外，欢迎完整的算法更改 - 我对此很新 .
1 回答
我前段时间遇到过类似的问题 .
您可以为周围单元格分配权重，为前单元格分配较小的权重，从而生成在移动过程中生成的权重图 .
我使用Dijkstra算法，周围单元格的权重为2，前单元格的权重为1，你必须将机器人的方向传递给Dijkstra，并在将它们添加到优先级队列时，并且当从队列中提取单元格时，添加相对于方向保存在提取的单元格中 .
然后进行移动，然后重新计算修改后的Dijkstra，以找到最近的看不见的单元格 .