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
过了一会儿,我脑海中浮现出一些想法和相似之处。
这与微型机器人需要解决的问题非常接近,大多数情况下使用泛洪填充算法。
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