'shortest path' 与行走代理的算法

Question

我正在寻找一种最短路径算法，其中代理（必须从头到尾移动的东西）在可行走区域上只有有限的视野。假设我们有一个迷宫，其起点和目标是基于图块的。是这样的：然后代理可能 只能在每个方向（上、下、左、右）看到一个 但具有 无限内存 。作为衡量标准，我希望 尽可能少的步骤 来达到目标。有算法吗？

如果有的话，是否有解决更一般问题的算法。比方说：一个图表、多个目标和起点以及一个 returns 看到节点和有限内存的函数？

使用具有全视野的恒星的解决方案：

Answer 1

过了一会儿，我想到了一些想法和相似之处。

接近问题的是Micromouse has to solve most use Flood Fill

Flood-fill (node, target-color, replacement-color):
 1. If target-color is equal to replacement-color, return.
 2. ElseIf the color of node is not equal to target-color, return.
 3. Else Set the color of node to replacement-color.
 4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
 5. Return.

Answer 2

由于能见度有限，您不能真正指望找到最短路径，因为您要么可以看到通往目标的路径，要么不能，除非您足够幸运地看到多条路径。

但是，您可以使用试探法来改进搜索。例如，您会想要探索未探索的图块，优先考虑目标附近的图块，从最近的图块开始。能见度仅为 1 时，您基本上是盲人，但如果您的能见度稍高，您可以优先探索目标周围，直到找到连接到您已经探索过的事物的路径。

这让我想起了双向路径追踪，这是一种渲染技术，您可以追踪相机和灯光的路径，直到它们连接起来。 http://www.pbr-book.org/3ed-2018/Light_Transport_III_Bidirectional_Methods/Bidirectional_Path_Tracing.html

Answer 3

一个非常简单的替代方法是：

walk to an undiscovered tile using a star
if it is the goal stop
if not repeat
if there aren't any undiscovered tiles stop and fail

Answer 4

基本上 A* 仍然可以工作，但您需要找到一个新的启发式方法，我建议您包括瓷砖之间的旅行时间。

'shortest path' 与行走代理的算法

Algorithm for 'shortest path' with walking agent

algorithm

path-finding