在塔防游戏中,有很多敌人都是向着同一目标前进的。在众多塔防游戏当中,有一条或几条预定好的路径。在一些塔防游戏中,比如经典的《Desktop Tower Defense》,你可以将塔放在地图上的任何地方,把他们作为阻碍敌人通往预定路径的障碍。试着点击地图来切换或移动墙壁:
我们将如何实现?
图搜索算法例如A*这样的算法经常被用来搜索两点之间的最短路径。你可以用这个来找到每一个敌人前往的目标的路径。有很多不同的图搜索算法可以用在这种类型的游戏。这些都是经典的算法:
单源,单目标:
- 贪心搜索算法
- A*算法 – 在游戏当中常使用
单源多目标或多源单目标
- 广度优先搜索算法-无加权边缘
- Dijkstra算法-有加权边缘
- Bellman-Ford算法-支持负权重
多源多目标
- Floyd-Warshall算法
- Johnson’s算法
像《Desktop Tower Defense》这样的游戏会有很多个敌人的位置(源)和一个共同的目的地。这使得它被归为多源单目标这一类。我们可以执行一个算法,一次性算出所有敌人的路径,而不是为每个敌人执行一次A*算法。更好的是,我们可以计算出每个位置的最短路径,所以当敌人挤在一起或者新的敌人被创建出来时,他们的路径已经被预先计算好了。
我们先来看看广度优先算法,有时也被称作“洪水填充法”(FIFO的变种)。虽然图搜索算法是适用于任何由节点和边构成的网格图,但是我还是使用方形网格来说明这些例子。网格是图的一个特例。每个网格瓦片是图节点,网格瓷砖之间的边界是图的边。我会在另一篇文章当中探讨非网格图。
广度优先搜索从一个节点开始,并访问邻居节点。关键的概念是“边界”,它在已探索和未开发的区域之间的边界。边界从原来的节点向外扩展,直到探索了整张图。
边界队列是一个图节点(网格瓦片)是否需要被分析的列表/数组。它最开始仅仅包含一个元素,起始节点。每个节点上的访问标志追踪我们是否采访过该节点。开始的时候除了起始节点都标志为FALSE。使用滑块来查看边界是如何扩展的:
![170533jwa8cnw2476n7a4c.jpg](https://di.gameres.com/attachment/forum/201510/30/170533jwa8cnw2476n7a4c.jpg)
这个算法是如何运行的?每走一步,获得一个元素的边界,把它命名为current。然后寻找current的每个邻居,next。如果他们还没有被访问过,将他们都添加到边界队列里面。下面是一些python代码:
- frontier = Queue()
- frontier.put(start)
- visited = {}
- visited[start] = True
-
- while not frontier.empty():
- current = frontier.get()
- for next in graph.neighbors(current):
- if next not in visited:
- frontier.put(next)
- visited[next] = True
如果你需要距离,你可以在起始节点将一个计数器设置为0,并在每次访问邻居节点的时候将它加一个邻居节点。让我们把visitd重命名为distance,并且用它来存储一个计数器:
- frontier = Queue()
- frontier.put(start)
- distance = {}
- distance[start] = 0
-
- while not frontier.empty():
- current = frontier.get()
- for next in graph.neighbors(current):
- if next not in distance:
- frontier.put(next)
- distance[next] = 1 + distance[current]
- frontier.put(next)
- if next not in distance:
- for next in graph.neighbors(current):
- current = frontier.get()
-
- distance[start] = 0
- distance = {}
- frontier.put(start)
如果你想同时计算路径和距离,你可以使用两个变量。
这就是广度优先检索算法。对于塔防风格的游戏,我用它来搜寻所有位置到一个指定位置的路径,而不是重复使用A*算法为每个敌人计算路径。我用它来寻找每一个移动的怪物的指定行动距离内所有的位置。我也是用它来进行程序化地生成地图。Minecraft使用它来进行可见性剔除。这是一个好的算法。
接下来的步骤:
我有实现python和c++代码。
如果你想要找到从一个点出发而不是到达一个点的路径,只需要在检索路径的时候翻转came_from指针。
如果你想要多个点路径而不是一个点的路径,你可以在图的边缘为你的每个目标点添加一个额外的点。额外的点不会出现在网格中,但是它会表示在图中的目标位置。
提前退出:如果你是在寻找一个到达某一点或从某一点出发,。我在A*算法的文章当中描述了这种情况。
加权边:如果你需要不同的移动成本,广度优先搜索可以替换为为Dijkstra算法。我在A*算法的文章当中描述了这种情况。
启发:如果你要添加一种指导搜索目标的方法,广度优先算法可以替换为最佳优先算法。我在A*算法的文章当中描述了这种情况。
如果你从广度优先算法,并且加上了提前退出,加权的边缘和启发,你会得到A*。正如你所想,我在A*算法的文章当中描述了这样的情况。
相关阅读:开放世界游戏中的大地图的实现——程序技术篇
游资网编译
![锐亚教育](http://www.insideria.cn/files/default/2017/03-19/164933d4e4bd117214.jpg)
锐亚教育,游戏开发论坛|游戏制作人|游戏策划|游戏开发|独立游戏|游戏产业|游戏研发|游戏运营| unity|unity3d|unity3d官网|unity3d 教程|金融帝国3|8k8k8k|mcafee8.5i|游戏蛮牛|蛮牛 unity|蛮牛
- 还没有人评论,欢迎说说您的想法!