塔防游戏的路径寻找算法分析

小篱

　　在塔防游戏中，有很多敌人都是向着同一目标前进的。在众多塔防游戏当中，有一条或几条预定好的路径。在一些塔防游戏中，比如经典的《Desktop Tower Defense》，你可以将塔放在地图上的任何地方，把他们作为阻碍敌人通往预定路径的障碍。试着点击地图来切换或移动墙壁：

　　我们将如何实现？

　　图搜索算法例如A*这样的算法经常被用来搜索两点之间的最短路径。你可以用这个来找到每一个敌人前往的目标的路径。有很多不同的图搜索算法可以用在这种类型的游戏。这些都是经典的算法：

　　单源，单目标:

• 贪心搜索算法
• A*算法 – 在游戏当中常使用
  

　　单源多目标或多源单目标

• 广度优先搜索算法-无加权边缘
• Dijkstra算法-有加权边缘
• Bellman-Ford算法-支持负权重
  

　　多源多目标

• Floyd-Warshall算法
• Johnson’s算法
  

　　像《Desktop Tower Defense》这样的游戏会有很多个敌人的位置（源）和一个共同的目的地。这使得它被归为多源单目标这一类。我们可以执行一个算法，一次性算出所有敌人的路径，而不是为每个敌人执行一次A*算法。更好的是，我们可以计算出每个位置的最短路径，所以当敌人挤在一起或者新的敌人被创建出来时，他们的路径已经被预先计算好了。

　　我们先来看看广度优先算法，有时也被称作“洪水填充法”（FIFO的变种）。虽然图搜索算法是适用于任何由节点和边构成的网格图，但是我还是使用方形网格来说明这些例子。网格是图的一个特例。每个网格瓦片是图节点，网格瓷砖之间的边界是图的边。我会在另一篇文章当中探讨非网格图。

　　广度优先搜索从一个节点开始，并访问邻居节点。关键的概念是“边界”，它在已探索和未开发的区域之间的边界。边界从原来的节点向外扩展，直到探索了整张图。

　　边界队列是一个图节点(网格瓦片)是否需要被分析的列表/数组。它最开始仅仅包含一个元素，起始节点。每个节点上的访问标志追踪我们是否采访过该节点。开始的时候除了起始节点都标志为FALSE。使用滑块来查看边界是如何扩展的：

　　这个算法是如何运行的？每走一步，获得一个元素的边界，把它命名为current。然后寻找current的每个邻居，next。如果他们还没有被访问过，将他们都添加到边界队列里面。下面是一些python代码：

1. frontier = Queue()
   
2. frontier.put(start)
   
3. visited = {}
   
4. visited[start] = True
   
5. 
   
6. while not frontier.empty():
   
7.    current = frontier.get()
   
8.    for next in graph.neighbors(current):
   
9.       if next not in visited:
   
10.          frontier.put(next)
    
11.          visited[next] = True

复制代码

　　现在你已经看见代码了，试着进入上面的动画。注意边界队列，关于current的代码，还有next节点的集合。在每一步中，有一个边界元素成为current节点，它的邻居节点会被标注，而且没有被拜访过的邻居节点会被添加到边界队列。有一些邻居节点可能已经被访问过，他们就不需要被添加到边界队列里面了。

　　这是一个相对简单的算法，并且对于包括AI在内的很多事情都是有用的。我有三种主要使用它的办法：

　　1.标记所有可达的点。这在你的图不是完全连接的，并且想知道哪些点是可达的时候是很有用的。这就是我再上面用visited这部分所做的。

　　2.找到从一个点到所有其他点或者所有点到一个点的路径。我在文章开头的动画demo里面使用了它。

　　3.测量从一个节点到所有其他节点的距离。这在预先知道一个移动中的怪物的距离时是很有用的。

　　如果你正在生成路径，你可能会想知道从每个节点移动的方向。当你访问一个邻居节点的时候，要记得你是从哪个节点过来的。让我们把visited重命名为came_from并且用它来记录之前位置的轨迹：

1. frontier = Queue()
   
2. frontier.put(start)
   
3. came_from = {}
   
4. came_from[start] = None
   
5. 
   
6. while not frontier.empty():
   
7.    current = frontier.get()
   
8.    for next in graph.neighbors(current):
   
9.       if next not in came_from:
   
10.          frontier.put(next)
    
11.          came_from[next] = current

复制代码

　　我们来看看它是这样的：

　　如果你需要距离，你可以在起始节点将一个计数器设置为0，并在每次访问邻居节点的时候将它加一个邻居节点。让我们把visitd重命名为distance，并且用它来存储一个计数器：

1. frontier = Queue()
   
2. frontier.put(start)
   
3. distance = {}
   
4. distance[start] = 0
   
5. 
   
6. while not frontier.empty():
   
7.    current = frontier.get()
   
8.    for next in graph.neighbors(current):
   
9.       if next not in distance:
   
10.          frontier.put(next)
    
11.          distance[next] = 1 + distance[current]

复制代码

　　我们来看看它是这样的：

　　如果你想同时计算路径和距离，你可以使用两个变量。

　　这就是广度优先检索算法。对于塔防风格的游戏，我用它来搜寻所有位置到一个指定位置的路径，而不是重复使用A*算法为每个敌人计算路径。我用它来寻找每一个移动的怪物的指定行动距离内所有的位置。我也是用它来进行程序化地生成地图。Minecraft使用它来进行可见性剔除。这是一个好的算法。

　　接下来的步骤：

　　我有实现python和c++代码。

　　如果你想要找到从一个点出发而不是到达一个点的路径，只需要在检索路径的时候翻转came_from指针。

　　如果你想要多个点路径而不是一个点的路径，你可以在图的边缘为你的每个目标点添加一个额外的点。额外的点不会出现在网格中，但是它会表示在图中的目标位置。

　　提前退出：如果你是在寻找一个到达某一点或从某一点出发，。我在A*算法的文章当中描述了这种情况。

　　加权边：如果你需要不同的移动成本，广度优先搜索可以替换为为Dijkstra算法。我在A*算法的文章当中描述了这种情况。

　　启发：如果你要添加一种指导搜索目标的方法，广度优先算法可以替换为最佳优先算法。我在A*算法的文章当中描述了这种情况。

　　如果你从广度优先算法，并且加上了提前退出，加权的边缘和启发，你会得到A*。正如你所想，我在A*算法的文章当中描述了这样的情况。

　　相关阅读：开放世界游戏中的大地图的实现——程序技术篇

游资网编译

1911

很有意思的帖子，谢谢分享

StarBeats

学习学习

chengchengccc

塔防游戏成品开发联系18141797029