'shortest path' 与行走代理的算法
Algorithm for 'shortest path' with walking agent
我正在寻找一种最短路径算法,其中代理(必须从头到尾移动的东西)在可行走区域上只有有限的视野。假设我们有一个迷宫,其起点和目标是基于图块的。是这样的:
然后代理可能 只能在每个方向(上、下、左、右)看到一个 但具有 无限内存 。作为衡量标准,我希望 尽可能少的步骤 来达到目标。
有算法吗?
如果有的话,是否有解决更一般问题的算法。比方说:一个图表、多个目标和起点以及一个 returns 看到节点和有限内存的函数?
使用具有全视野的恒星的解决方案:
过了一会儿,我想到了一些想法和相似之处。
接近问题的是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.
由于能见度有限,您不能真正指望找到最短路径,因为您要么可以看到通往目标的路径,要么不能,除非您足够幸运地看到多条路径。
但是,您可以使用试探法来改进搜索。例如,您会想要探索未探索的图块,优先考虑目标附近的图块,从最近的图块开始。能见度仅为 1 时,您基本上是盲人,但如果您的能见度稍高,您可以优先探索目标周围,直到找到连接到您已经探索过的事物的路径。
这让我想起了双向路径追踪,这是一种渲染技术,您可以追踪相机和灯光的路径,直到它们连接起来。 http://www.pbr-book.org/3ed-2018/Light_Transport_III_Bidirectional_Methods/Bidirectional_Path_Tracing.html
一个非常简单的替代方法是:
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
基本上 A* 仍然可以工作,但您需要找到一个新的启发式方法,我建议您包括瓷砖之间的旅行时间。
我正在寻找一种最短路径算法,其中代理(必须从头到尾移动的东西)在可行走区域上只有有限的视野。假设我们有一个迷宫,其起点和目标是基于图块的。是这样的:
如果有的话,是否有解决更一般问题的算法。比方说:一个图表、多个目标和起点以及一个 returns 看到节点和有限内存的函数?
使用具有全视野的恒星的解决方案:
过了一会儿,我想到了一些想法和相似之处。
接近问题的是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.
由于能见度有限,您不能真正指望找到最短路径,因为您要么可以看到通往目标的路径,要么不能,除非您足够幸运地看到多条路径。
但是,您可以使用试探法来改进搜索。例如,您会想要探索未探索的图块,优先考虑目标附近的图块,从最近的图块开始。能见度仅为 1 时,您基本上是盲人,但如果您的能见度稍高,您可以优先探索目标周围,直到找到连接到您已经探索过的事物的路径。
这让我想起了双向路径追踪,这是一种渲染技术,您可以追踪相机和灯光的路径,直到它们连接起来。 http://www.pbr-book.org/3ed-2018/Light_Transport_III_Bidirectional_Methods/Bidirectional_Path_Tracing.html
一个非常简单的替代方法是:
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
基本上 A* 仍然可以工作,但您需要找到一个新的启发式方法,我建议您包括瓷砖之间的旅行时间。