c

codeye

V1

2022/10/09阅读:17主题:默认主题

广度优先搜索:多个起始点

广度优先搜索:多个起始点

用多个起点运行广义第一搜索可以做一些很酷的事情。如果你还没有读过我的关于广义第一搜索的页面,那么在阅读本页面之前,你可以从那里开始。这里的想法是对那里的算法的一种修改。请注意,尽管本页的演示使用的是方形网格,但这些算法都不限于方形网格,甚至不限于网格。

到最近的障碍物的距离

Nairou在StackExchange上问,如何一次性计算出到最近的障碍物的距离。一个答案是广度优先搜索。通常在寻路中,我们用一个起点来初始化开放集,但在计算到最近的障碍物的距离时,我们把每个障碍物都视为一个起点。这里有一个快速的演示。点击在开放空间(蓝色)、起始点(紫色)和墙(灰色)之间循环。

这里有一些Python代码。它类似于我的 "广度优先搜索 "页面上的代码,但我们没有单一的起点,而是有很多。

frontier = Queue()
cost_so_far = {}

#将所有起始点的距离设为0

for s in start:
   frontier.put(s)
   cost_so_far[s] = 0

#从现有的点向外扩展

while not frontier.empty():
   current = frontier.get()
   for next in current.neighbors():
      if next not in cost_so_far:
         cost_so_far[next] = cost_so_far[current] + 1
         frontier.put(next)

到最近的交叉点的距离

下面是一个使用相同算法的不同例子。吃豆人安全地图告诉你到最近的十字路口的距离。将十字路口标记为起点(紫色)。在这个演示中,我还标记了左边大房间的入口,但可以尝试标记任何你想要的东西。

到最近的墙的距离# 下面是同样的算法,以墙为起点。它不仅告诉你房间的大小,还告诉你如何向中心移动或远离中心。点击切换墙壁。

墙壁、交叉点、敌人、盟友、资源、老板、宝藏--你可能用这个做很多类型的地图分析。例如,走廊是1,但门洞和其他瓷砖也有1。如果你把所有为1且周围为0或1的瓦片都标出来,这些就是走廊了。

区域增长# 除了距离之外,我们还可以跟踪这个距离是基于哪个起始点(种子)。我们最终会得到一张地图,告诉我们哪一个起点离基于旅行距离的其他各点最近。选择起始点。

frontier = Queue()
cost_so_far = {}
started_at = {}

# Set the distance to 0 at all start points,
# and each start point started at itself
for s in start:
   frontier.put(s)
   cost_so_far[s] = 0
   started_at[s] = s

# Expand outwards from existing points
while not frontier.empty():
   current = frontier.get()
   for next in current.neighbors():
      if next not in cost_so_far:
         cost_so_far[next] = cost_so_far[current] + 1
         started_at[next] = started_at[current]
         frontier.put(next)

将所有起点的距离设为0。 每个开始点都从自己开始

for s in start:
   frontier.put(s)
   cost_so_far[s] = 0
   started_at[s] = s

#从现有的点向外扩展

while not frontier.empty():
   current = frontier.get()
   for next in current.neighbors():
      if next not in cost_so_far:
         cost_so_far[next] = cost_so_far[current] + 1
         started_at[next] = started_at[current)
         frontier.put(next)

距离的计算是在同一过程中进行的,并告诉你任何一个瓦片离起始点(也许是首都)有多远,以及到该点的路径。

第二次运行广度优先搜索,这次以国家边界为起点,你可以找到距离边界的距离,以及到最近的边界的路径。最高的距离是离边界最远的那一点。

岛屿连通性#

前面的想法的一个变种是穿越地图,把每个地点都作为区域的起点,如果它还没有被分配到一个区域的话。这在图论中被称为连接部件。它在地图中对于识别岛屿很有用。我们将从每一个陆地点进行广度优先搜索,但不允许移动到水中。在地图上切换水/陆,可以看到岛屿的标签。

那不是有很多 "广度优先搜索 "吗?是的,在理论上。在实践中,我们可以在一次 "宽度优先搜索 "中完成所有的工作,每次队列清空时,我们都会将另一个节点插入队列中。下面是一个粗略的草图(但我还没有测试这段代码)。


frontier = Queue()
start_at = {}。

# 运行广度优先搜索来寻找岛屿。而不是在队列为空时停止
# 当队列是空的时候,我们将寻找一个还没有
# 还没有被访问过的瓷砖,并将其添加到队列中。
for location in all_land_tiles: # 不包括水砖
   if location in started_at:
      继续 # 已经分配给一个岛屿,跳过它

   # 这个位置在陆地上,但还没有被分配到
   # 一个岛屿,所以它将成为新的岛屿ID
   frontier.put(location)
   started_at[location] = location

   while not frontier.empty():
      current = frontier.get()
      for next in current.neighbors(): # 排除水
         if next not in started_at:
            started_at[next] = started_at[current)
            frontier.put(next)

为了找到与海岸的距离,第二次运行宽度优先搜索,以所有陆地瓷砖为起点

在广度优先搜索的邻居循环中,如果当前节点和邻居节点来自两个不同的岛屿,这就是一个潜在的桥的地方。你可以把它看作是一个新的图:岛屿是节点,潜在的桥是边。最简单的方法(如图所示)是将它们全部连接起来。如果你只想连接一些,生成树将把所有岛屿连接在一起。最小生成树将使桥的长度最小化。但可能有许多数学上同样短的桥,你可能需要添加启发式方法来选择你认为最吸引人的桥。

更多想法# 同样的算法在多边形网格上也适用。切换到Dijkstra算法来扩展这个算法,使之适用于可变移动成本。看一下这篇文章,了解更多的想法。

还有其他的算法,其中一些比宽度优先搜索更容易并行化或GPU友好。请看维基百科上的距离变换。对于欧氏距离而不是曼哈顿距离,见2D欧氏距离变换。A Comparative Study (PDF)

在一个地图生成实验中,我从海岸线开始,使用带有一些随机性的广度优先搜索来生成河流。

河流生长

广度优先搜索,从海岸线生长河流 在Mapgen4中,我不仅对河流而且对气候也使用了广度优先搜索。

地图上的河流

广度优先搜索,针对河流和生物群落 在这个地牢生成器中,我在所有的种子中连续而不是平行地运行广度优先搜索,而且我还对它的生长距离作了限制。我用它来生成地牢的房间。

实例

广度优先搜索,一次一个房间 广度优先搜索可以以每秒约100万个节点的速度运行。

分类:

后端

标签:

后端

作者介绍

c
codeye
V1