从画一个迷宫说开去

2018 4月 10日

前段时间为了优化项目中的一个动画效果，在查看开发文档的过程中发现了GameplayKit这一个框架，这个框架为映射游戏中的一些角色、路径等提供了一组工具。使用游戏引擎内部的渲染可以很好的解决项目中原有的高内存动画效果，在深入的了解了这个框架之后发现里面涉及到了很多的经典算法，也有Apple自己在算法上做的优化，于是在优化项目之后整理出来相关内容，加深对算法的理解。

1. 基于GameplayKit的实现

根据文档中的描述，在许多游戏导航是一个重要的概念，GameplayKit为抽象游戏提供了一组工具，除了游戏，还可以根据实际需求应用于非游戏场景中。在为游戏设计Pathfinding章节可以知道，通过GKGraph类相关的api来实现一个图表以实现寻路操作，这里有三种方法可以实现不同需求中的场景：

如果一个连续的空间被障碍物打断，一个组合是使用 GKPolygomPbstacle 来表示障碍物、使用 GKGraphNode2D 来表示连续控件上的点，然后使用 GKObstacleGraph 将两者包含起来。
在一个二维坐标的分散网格中，自由一些点是有效的。使用 GKGridGraph 和 GKGridGraphNode 来创建网格图表。这就是本次迷宫游戏中需要用到的组合模式。
在一些离散的点中找出来他们之间的连线，使用 GKGraphNode 来表示每一个节点， GKGraph 来表示图表。

当通过以上三种方式创建好了图表之后，就可以使用GKGraph对象根据其现有的节点之间的关系图添加新节点、从关系图中删除节点、查找特殊节点等操作。最重要的是，找到图中从一个节点到另一个地方的最佳路径，放到迷宫游戏中就是寻找正确的路径走出迷宫。

GKGraph类中的finsPathFromNode:toNode:就是用来找到图中的路径的方法，这个方法返回的是一个数组，数组中装的是 GKGraphNode 的子类，然后可以通过该类的position来获取每一个node的坐标，开发者可以根据这个数组进行UI处理展示出来路径。

1.1 demo分析

demo是在深度优先算法的基础上生成迷宫地图，但是会有一些限制，比如只支持尺寸为奇数的迷宫地图。具体算法流程为：

在给定尺寸（记为dimensions）的图上根据每一个节点(x,y)筛选出来x或y为奇数的点（具体效果如下图所示），将这些点作为墙节点-wallNode

从给定的起始点作为topNode，随机挑选topNode的四个方向(上下左右)上相邻的非墙节点进行访问：
- 如果该相邻节点已经被访问，再随机挑选，直到找到未被访问的相邻节点，这个相邻节点记为neigNode，将topNode和neigNode之间的wallNode移除，并且将topNode、neigNode标记为已经访问，将改topNode加入到一个数组中，记为visitedNodes
- 如果topNode的所有相邻节点都已经被访问过，则向上回溯，根据visitedNodes中的元素，从后向前遍历，直到遍历到的节点还有未访问的邻居节点，如果回溯的过程中所有的节点的邻居节点都被访问，则算法结束

根据上面的算法描述，使用一个5*5的迷宫来展示这一过程，如下图所示：
title

这里提供的算法是在深度优先算法的基础上进行改进的，主要的一点是加入了墙节点的概念。这样的做法可以让需要遍历的节点减少一半之多，具体需要遍历的节点个数为：(dimensions - dimensions / 2)^2^，这大大的减少了需要遍历的时间。另一方面，算法最后生成迷宫的可能情况也会有所减少，比如，以一个3*3的迷宫为例，使用该算法只能生成两种样式，并且只能生成尺寸为奇数大小的迷宫，但是单纯的使用深度优先算法却可以有6种情况：
title

对于迷宫这种游戏来说，基本上尺寸都不会很小，尺寸越大可能的结果就越多，相对于这个数字来说，损失的那些情况可以忽略不计，Apple的这个算法在牺牲了可能性数量的基础上提高了访问速度，整体上来说还是很合适的一个算法。但由于GameplayKit内部针对于GKGraph提供了pathfinding相关的api，所以不知道它内部是使用的何种算法来查找路径的，估计也是在A-star算法的基础上优化过的算法，这一点有待考证。

2. 生成迷宫的算法

如果一个迷宫中没有任何回路、没有多条解决路径，那么就可以称得上这个迷宫是一个完美迷宫。迷宫的生成以及寻找路径都是基于图论的，一般来说，生成迷宫最常用的有两种方法：递归回溯算法（深度优先算法)、Prim(普利姆)随机算法。而寻找最优路径的算法有广度优先算法、A*算法。

2.1 Tremaux搜索

在迷宫游戏中探索出一条通路，最早的方法是使用一种叫做Tremaux的算法，而他和深度优先算法很类似，在《算法》中是这么描述它的：

选择一条没有标记过的通道，在你走过的路上铺一条绳子
标记所有你第一次路过的路口和通道
当来到一个标记过的路口时（用绳子）回退到上个路口
当回退到的路口已没有可走的通道时继续回退
最后整个绳子的路径就是最终的一种解法

这个算法并没有完全探索了整个迷宫中的所有节点以及边，比如上面添加的橙色路径和节点，基于目前的选择，已经到达了终点，也就不用再去探索其余的情况了，所以他们（橙色路径和节点）在这个探索过程中是没有被探索到的未知地。要知道是否完全探索了整个迷宫需要的证明更复杂，只有用图搜索才能够更好地处理问题。Tremaux 搜索很直接，但它与完全搜索一张图仍然稍有不同，而搜索连通图的经典递归算法（遍历所有的节点和边）和 Tremaux 搜索类似，那就是深度优先算法。

2.2 递归回溯算法

深度优先搜索（Depth First Search）是图论中对图的节点一种遍历方式，核心思想就是在图中尽量的深入。假如设定一个起始节点，访问这个节点，然后在该节点的邻接节点中选取没有访问过的节点进行访问，如果邻接节点都被访问过，就回溯到上一个有未被访问邻接节点的节点，依次下去，直到整个图中的节点都被访问完。

在《算法导论》中对DFS的举例是使用的一个有向循环图，实际应用中，比较多的还是有向无循环图，下面分别是算法导论中的例子和一个简化版本的有向无循环图的深度优先搜索：

根据DFS的这一特性，可以很好的去遍历一个n*n的图来构建一个迷宫，根据维基百科中对使用DFS算法生成迷宫的核心解释为：

1.将起点作为当前迷宫单元并标记为已访问  
2.当还存在未标记的迷宫单元，进行循环  
    1.如果当前迷宫单元有未被访问过的的相邻的迷宫单元  
    	1.随机选择一个未访问的相邻迷宫单元  
		2.将当前迷宫单元入栈  
		3.移除当前迷宫单元与相邻迷宫单元的墙  
		4.标记相邻迷宫单元并用它作为当前迷宫单元  
    2.如果当前迷宫单元不存在未访问的相邻迷宫单元，并且栈不空  
		1.栈顶的迷宫单元出栈  
    	2.令其成为当前迷宫单元

由于深度优先搜索可以设定起点，但是不可以决定一个点为终点，在使用这个算法去生成迷宫的时候

从算法描述中可以看出来，深度优先算法根据最新选择过的单元作为优先判断条件，寻找相邻的未被访问的单元格

2.3 普利姆随机算法

只是和最小生成树的Prim算法同名字而已，普里姆随机算法在维基百科中解释的描述为：

1.让迷宫全是墙.  
2.选一个单元格作为迷宫的通路，然后把它的邻墙放入列表  
3.当列表里还有墙时  
    1.从列表里随机选一个墙，如果这面墙分隔的两个单元格只有一个单元格被访问过  
        1.那就从列表里移除这面墙，即把墙打通，让未访问的单元格成为迷宫的通路  
        2.把这个格子的墙加入列表  
    2.如果墙两面的单元格都已经被访问过，那就从列表里移除这面墙