塔防游戏的路径寻找算法分析
在塔防游戏中，众多敌人通常会朝着同一目标前进。在大多数塔防游戏里，会预设一条或多条路径。以经典的《Desktop Tower Defense》为例，玩家能够在地图的任意位置放置塔，这些塔会成为阻碍敌人沿预定路径行进的障碍物。你可以试着点击地图来切换或移动墙壁。
实现思路
图搜索算法常被用于搜索两点之间的最短路径，例如A*算法。借助这类算法，我们可以为每个敌人找到前往目标的路径。适用于此类游戏的图搜索算法有很多，以下是一些经典算法：
单源，单目标
- 贪心搜索算法
- A*算法：在游戏中较为常用
单源多目标或多源单目标
- 广度优先搜索算法：适用于无加权边缘的情况
- Dijkstra算法：适用于有加权边缘的情况
- Bellman - Ford算法：支持负权重
多源多目标
- Floyd - Warshall算法
- Johnson’s算法
像《Desktop Tower Defense》这类游戏，存在多个敌人位置（源）和一个共同的目的地，因此可归为多源单目标类别。我们可以执行一个算法一次性算出所有敌人的路径，而非为每个敌人单独执行一次A*算法。更优的做法是，预先计算出每个位置的最短路径，这样当敌人聚集在一起或新敌人出现时，其路径已提前确定。
广度优先搜索算法
广度优先搜索算法有时也被称作“洪水填充法”（FIFO的变种）。虽然图搜索算法适用于任何由节点和边构成的网格图，但为便于说明，我们以方形网格为例。网格是图的一个特例，每个网格瓦片对应图节点，网格瓷砖之间的边界对应图的边。非网格图的相关内容将在另一篇文章中探讨。
广度优先搜索从一个节点开始，逐步访问其邻居节点。其关键概念是“边界”，即已探索区域和未探索区域之间的界限。边界从起始节点向外扩展，直至整张图被完全探索。
边界队列是一个用于记录图节点（网格瓦片）是否需要被分析的列表/数组。初始时，队列仅包含起始节点。每个节点上的访问标志用于追踪该节点是否已被访问，除起始节点外，其他节点初始标志均为FALSE。你可以使用滑块查看边界的扩展过程。
算法运行原理
每一步，从边界队列中取出一个元素，将其命名为current。接着，寻找current的每个邻居节点next。若这些邻居节点尚未被访问过，则将它们添加到边界队列中。以下是Python代码示例：
# 此处应补充代码
现在，结合上述代码查看动画。注意边界队列、关于current的代码以及next节点的集合。每一步中，一个边界元素成为current节点，其邻居节点会被标记，未被访问过的邻居节点将被添加到边界队列，而已访问过的邻居节点则无需再次添加。
算法应用场景
广度优先搜索算法相对简单，在包括AI在内的诸多领域都有应用价值。主要应用场景如下：
- 标记所有可达的点：当图并非完全连通，且需要明确哪些点可达时，此应用场景十分有用。这也是前面使用visited标志的目的。
- 找到从一个点到所有其他点或所有点到一个点的路径：文章开头的动画demo便运用了该算法实现此功能。
- 测量从一个节点到所有其他节点的距离：在预先了解移动中怪物的距离时，这一应用场景非常实用。
路径和距离计算
若要生成路径，可能需要知道从每个节点移动的方向。访问邻居节点时，需记录是从哪个节点过来的。我们可以将visited重命名为came_from，用于记录之前位置的轨迹。代码示例如下：
# 此处应补充代码
若需要距离信息，可在起始节点将计数器设为0，每次访问邻居节点时将计数器加1。将visited重命名为distance，用于存储计数器的值。代码示例如下：
# 此处应补充代码
若要同时计算路径和距离，可使用两个变量分别存储相关信息。
算法优势及应用案例
广度优先搜索算法在塔防风格游戏中具有显著优势。我们可以用它搜寻所有位置到指定位置的路径，避免为每个敌人重复使用A*算法。此外，还可利用该算法寻找移动怪物在指定行动距离内的所有位置，以及进行地图的程序化生成。例如，Minecraft使用该算法进行可见性剔除。
后续拓展
代码实现
已实现Python和C++代码版本。
路径方向调整
若要找到从一个点出发而非到达一个点的路径，只需在检索路径时翻转came_from指针。
多目标路径处理
若需要多个点的路径，可在图的边缘为每个目标点添加一个额外的点。该额外点不会显示在网格中，但可表示图中的目标位置。
提前退出策略
若在寻找到达某一点或从某一点出发的路径，可采用提前退出策略，具体情况在A*算法的文章中已有描述。
加权边处理
若需要考虑不同的移动成本，可将广度优先搜索算法替换为Dijkstra算法，相关情况在A*算法的文章中有所说明。
启发式搜索
若要添加指导搜索目标的方法，可将广度优先算法替换为最佳优先算法，具体内容同样在A*算法的文章中描述。
若在广度优先算法的基础上，结合提前退出、加权边缘和启发式搜索，便得到了A算法，相关情况在A算法的文章中已有详细阐述。