基于Swift实现拼图游戏

写了个拼图游戏，探究一下相关的 AI 算法。拼图游戏的复原问题也叫做 N 数码问题。

• 拼图游戏
  
• N 数码问题
  
• 广度优先搜刮
  
• 双向广度优先搜刮
  
• A*搜刮
  

游戏设定

实现一个拼图游戏，使它具备以下功能：

• 自由选取喜欢的图片来游戏
  
• 自由选定空格位置
  
• 空格相近的方块可移动，别的方块不允许移动
  
• 能识别图片是否复原完成，游戏胜利时给出反馈
  
• 一键洗牌，打乱图片方块
  
• 支持重新开始游戏
  
• 难度分级：高、中、低
  
• 具备人工智能，自动完成拼图复原
  
• 实现几种人工智能算法：广度优先搜刮、双向广度优先搜刮、A*搜刮
  
• 保存游戏进度
  
• 读取游戏进度
  

自动完成拼图复原

先看看完成后的结果。点自动按钮后，游戏将会把当前的拼图一步一步移动直到复原图片。

图片与方块

图片的选取可通过拍照、从相册选，或者使用内置默认图片。
由于游戏是在正方形区域内举行的，以是若想有最好的游戏结果，我们需要一张裁剪成正方形的图片。

选好图片后，需要把图片切割成 n x n 块。这里每一个方块 PuzzlePiece 都是一个 UIButton。
由于图片是会被打散打乱的，以是每个方块应该记住它自己在原图上的初始位置，这里给方块添加一个属性 ID，用于保存。

1. @interface PuzzlePiece : UIButton
3. /// 本方块在原图上的位置，从0开始编号
4. @property (nonatomic, assign) NSInteger ID;
6. /// 创建实例
7. + (instancetype)pieceWithID:(NSInteger)ID image:(UIImage *)image;
9. @end

复制代码

难度选择

切割后的图片块组成了一个 n x n 矩阵，亦即 n 阶方阵。而想要改变游戏难度，我们只需要改变方阵的阶数即可。
计划三档难度，从低到高分别对应 3 x 3、4 x 4、5 x 5 的方阵。

假如我们把游戏中某个时刻的方块排列次序称为一个状态，那么当阶数为 n 时，游戏的总状态数就是 n 的阶乘。
在差别难度下举行游戏将会有非常大的差别，无论是手动游戏还是 AI 举行游戏。

• 在低难度下，拼图共有 (3*3)! = 362880 个状态，并不多，即便是最慢的广搜算法也可以在短时间内搜出复原路径。
  

• 在中难度下，拼图变成了 4 阶方阵，拼图状态数飙升到 (4*4)! = 20922789888000，二十万亿。广搜算法已基本不能搜出结果，直到爆内存。
  

• 在高难度下，拼图变成了 5 阶方阵，状态数是个天文数字 (5*5)! = 1.551121004333098e25，10 的 25 次方。此时无论是广搜亦或是双向广搜都已无能为力，而 A*尚可一战。
  

方块移动

在选取完图片后，拼图是完整无缺的，此时让第一个被触击的方块成为空格。
从第二次触击开始，将会对所触击的方块举行移动，但只允许空格附近的方块发生移动。
每一次移动方块，实质上是让方块的位置与空格的位置举行互换。在这里头脑需要转个小弯，空格并不空，它也是一个对象，只不过表示出来是一块空白而已。那么我们移动了方块，是否可以反过来想，实在是移动了空格？答案是肯定的，并且头脑如许转过来后，更方便代码实现。

打乱方块次序

这里为了让打乱次序后的拼图有解，采用随机移动一定步数的方法来实现洗牌。
对于 n 阶方阵，可计划随机的步数为：n * n * 10。在实际测试当中，这个随机移动的步数已富足让拼图完全乱序，即使让随机的步数再加大 10 倍，其复原所需的移动步数也变化不大。复原步数与方阵的阶数有关，无论打乱多少次，复原步数都是趋于一个稳固的范围。

拼图状态

我们需要界说一个类来表示拼图在某个时刻的状态。
一个状态应持有以下几个属性：

• 矩阵阶数
  
• 方块数组，以数组的次序来表示本状态下方块的排列次序
  
• 空格所在的位置，其值指向方块数组中表现成空白的那一个方块
  

同时它应能提供操纵方块的方法，以演进游戏状态。

• 判定空格是否能移动到某个位置
  
• 把空格移动到某个位置
  
• 移除所有方块
  
• 打乱所有方块，变成一个随机状态
  
• 与另一个状态对象举行比力，判定是否状态等同
  

1. /// 表示游戏过程中，某一个时刻，所有方块的排列状态
2. @interface PuzzleStatus : NSObject <JXPathSearcherStatus, JXAStarSearcherStatus>
4. /// 矩阵阶数
5. @property (nonatomic, assign) NSInteger matrixOrder;
7. /// 方块数组，按从上到下，从左到右，顺序排列
8. @property (nonatomic, strong) NSMutableArray<PuzzlePiece *> *pieceArray;
10. /// 空格位置，无空格时为-1
11. @property (nonatomic, assign) NSInteger emptyIndex;
13. /// 创建实例，matrixOrder至少为3，image非空
14. + (instancetype)statusWithMatrixOrder:(NSInteger)matrixOrder image:(UIImage *)image;
16. /// 复制本实例
17. - (instancetype)copyStatus;
19. /// 判断是否与另一个状态相同
20. - (BOOL)equalWithStatus:(PuzzleStatus *)status;
22. /// 打乱，传入随机移动的步数
23. - (void)shuffleCount:(NSInteger)count;
25. /// 移除所有方块
26. - (void)removeAllPieces;
28. /// 空格是否能移动到某个位置
29. - (BOOL)canMoveToIndex:(NSInteger)index;
31. /// 把空格移动到某个位置
32. - (void)moveToIndex:(NSInteger)index;
34. @end

复制代码

使游戏具备人工智能(Artificial Intelligence, AI)

我们把拼图在某个时刻的方块排列称为一个状态，那么一旦发生方块移动，就会生成一个新的状态。
对于每个状态来说，它都可以或许通过改变空格的位置而衍生出另一个状态，而衍生出的状态又可以或许衍生出另一些状态。这种行为非常像一棵树的生成，当然这里的树指的是数据结构上的树结构。

推演移动路径的过程，就是根据当前状态不绝衍生状态，然后判定新状态是否为我们的目标状态(拼图完全复原时的状态)。假如找到了目标，就可以原路返回，依次找出目标所颠末的所有状态。
由此，状态树中的每一个结点都需要提供以下属性和方法：

• 父结点引用。要实现从目标状态逆向找回所有颠末的状态，需要让每一个状态都持有它上一状态的引用，即持有它的父结点引用。
  
• 结点的唯一标识。用于算法过程中识别状态等同，以及哈希策略去重。
  
• 子结点的生成方法。用于衍生出新的结点，演进搜刮。
  

1. /// 状态协议
2. @protocol JXPathSearcherStatus <NSObject>
4. /// 父状态
5. @property (nonatomic, strong) id<JXPathSearcherStatus> parentStatus;
7. /// 此状态的唯一标识
8. - (NSString *)statusIdentifier;
10. /// 取所有邻近状态(子状态)，排除父状态。每一个状态都需要给parentStatus赋值。
11. - (NSMutableArray<id<JXPathSearcherStatus>> *)childStatus;
13. @end

复制代码

对于一个路径搜刮算法来说，它应该知道开始于哪里，和竣事于哪里。
再有，作为一个通用的算法，不仅限于拼图游戏的话，它还需要算法使用者传入一个比力器，用于判定两个搜刮状态是否等同，由于算法并不清晰它所搜刮的是什么东西，也就不知道怎样确定任意两个状态是否一样的。
给路径搜刮算法作如下属性和方法界说：

1. /// 比较器定义
2. typedef BOOL(^JXPathSearcherEqualComparator)(id<JXPathSearcherStatus> status1, id<JXPathSearcherStatus> status2);
4. /// 路径搜索
5. @interface JXPathSearcher : NSObject
7. /// 开始状态
8. @property (nonatomic, strong) id<JXPathSearcherStatus> startStatus;
10. /// 目标状态
11. @property (nonatomic, strong) id<JXPathSearcherStatus> targetStatus;
13. /// 比较器
14. @property (nonatomic, strong) JXPathSearcherEqualComparator equalComparator;
16. /// 开始搜索，返回搜索结果。无法搜索时返回nil
17. - (NSMutableArray *)search;
19. /// 构建路径。isLast表示传入的status是否路径的最后一个元素
20. - (NSMutableArray *)constructPathWithStatus:(id<JXPathSearcherStatus>)status isLast:(BOOL)isLast;
22. @end

复制代码

关于“搜刮”两字，在代码上可以理解为拿着某个状态与目标状态举行比力，假如这两个状态一致，则搜刮乐成；假如不一致，则继承取另一个状态与目标状态比力，云云循环下去直到找出与目标一致的状态。
各算法的区别，主要在于它们对搜刮空间内的状态结点有差别的搜刮次序。
广度优先搜刮(Breadth First Search, BFS)

广度优先搜刮是一种盲目搜刮算法，它以为所有状态(或者说结点)都是等价的，不存在优劣之分。

假如我们把所有需要搜刮的状态组成一棵树来看，广搜就是一层搜完再搜下一层，直到找出目标结点，或搜完整棵树为止。

• 我们可以使用一个先辈先出(First Input First Output, FIFO)的队列来存放待搜刮的状态，这个队列可以给它一个名称叫开放队列，也有人把它叫做开放列表(Open List)。
  
• 然后还需要把所有已搜刮过的状态记录下来，以确保不会对已搜刮过的状态作重复扩展，注意这里的扩展即为衍生出子状态，对应于拼图游戏来说就是空格移动了一格。
  由于每搜到一个状态，都需要拿着这个状态去已搜记录中查询是否有这个状态存在，那么已搜记录要使用怎样的存储方式才能顺应这种高频率查找需求呢？
  假如我们使用数组来存储所有已搜记录，那么每一次查找都需要遍历整个数组。当已搜记录表的数据有 10 万条时，再去搜一个新状态，就需要做 10 万次循环来确定新状态是从来没有被搜刮过的。显然如许做的效率好坏常低的。
  一种高效的方法是哈希策略，哈希表(Hash Table)能通过键值映射直接查找到目标对象，免去遍历整个存储空间。在 Cocoa 框架中，已经有能满足这种键值映射的数据结构--字典。这里我没有再去实现一个哈希表，而是使用 NSMutableDictionary 来存放已搜记录。我们可以给这个存储空间起个名字叫关闭堆，也有人把它叫做关闭列表(Close List)。
  
• 搜刮开始时，开放队列是空的，然后我们把起始状态入队，此时开放队列有了一个待搜刮的状态，搜刮循环开始。
  
• 每一次循环的目标，就是搜刮一个状态。所谓搜刮，前面已经讲过，可以通俗理解为就是比力。我们需要从开放队列中取出一个状态来，假如取出的状态是已经比力过了的，则放弃此次循环，直到取出一个从来没有比力过的状态。
  
• 拿着取出的新状态，与目标状态比力，假如一致，则分析路径已找到。为何说路径已找到了呢？由于每一个状态都持有一个父状态的引用，意思是它记录着自己是来源于哪一个状态衍生出来的，以是每一个状态都一定知道自己上一个状态是谁，除了开始状态。
  
• 找到目标状态后，就可以构建路径。所谓路径，就是从开始状态到目标状态的搜刮过程中，颠末的所有状态连起来组成的数组。我们可以从搜刮竣事的状态开始，把它放入数组中，然后把这个状态的父状态放入数组中，再把其先人状态放入数组中，直到放入开始状态。怎样识别出开始状态呢？当发现某个状态是没有父状态的，就分析确它是开始状态。末了算法把构建完成的路径作为结果返回。
  
• 在第 5 步中，假如发现取出的新状态并非目标状态，这时就需要衍生新的状态来推进搜刮。调用生成子状态的方法，把产生的子状态入队，依次追加到队列尾，这些入队的子状态将会在以后的循环中被搜刮。由于队列的 FIFO 特性，在循环举行过程中，将会优先把某个状态的子状态全部出列完后，再出列其子状态的子状态。入列和出列的两步操纵决定了算法的搜刮次序，这里的操纵实现了广度优先搜刮。
  

广度优先搜刮：

1. - (NSMutableArray *)search {
2.     if (!self.startStatus || !self.targetStatus || !self.equalComparator) {
3.         return nil;
4.     }
5.     NSMutableArray *path = [NSMutableArray array];
6.    
7.     // 关闭堆，存放已搜索过的状态
8.     NSMutableDictionary *close = [NSMutableDictionary dictionary];
9.     // 开放队列，存放由已搜索过的状态所扩展出来的未搜索状态
10.     NSMutableArray *open = [NSMutableArray array];
11.    
12.     [open addObject:self.startStatus];
13.    
14.     while (open.count > 0) {
15.         // 出列
16.         id status = [open firstObject];
17.         [open removeObjectAtIndex:0];
18.         
19.         // 排除已经搜索过的状态
20.         NSString *statusIdentifier = [status statusIdentifier];
21.         if (close[statusIdentifier]) {
22.             continue;
23.         }
24.         close[statusIdentifier] = status;
25.         
26.         // 如果找到目标状态
27.         if (self.equalComparator(self.targetStatus, status)) {
28.             path = [self constructPathWithStatus:status isLast:YES];
29.             break;
30.         }
31.         
32.         // 否则，扩展出子状态
33.         [open addObjectsFromArray:[status childStatus]];
34.     }
35.     NSLog(@"总共搜索了: %@个状态", @(close.count));
36.     return path;
37. }

复制代码

构建路径：

1. /// 构建路径。isLast表示传入的status是否路径的最后一个元素
2. - (NSMutableArray *)constructPathWithStatus:(id<JXPathSearcherStatus>)status isLast:(BOOL)isLast {
3.     NSMutableArray *path = [NSMutableArray array];
4.     if (!status) {
5.         return path;
6.     }
7.    
8.     do {
9.         if (isLast) {
10.             [path insertObject:status atIndex:0];
11.         }
12.         else {
13.             [path addObject:status];
14.         }
15.         status = [status parentStatus];
16.     } while (status);
17.     return path;
18. }

复制代码

双向广度优先搜刮(Bi-Directional Breadth First Search)

双向广度优先搜刮是对广度优先搜刮的优化，但是有一个使用条件：搜刮路径可逆。
搜刮原理
双向广搜是同时从开始状态和目标状态展开搜刮的，如许就会产生两棵搜刮状态树。我们想象一下，让起始于开始状态的树从上往下生长，再让起始于目标状态的树从下往上生长，同时在它们的生长空间中遍布着一个一个的状态结点，等待着这两棵树延伸去触及。
由于任一个状态都是唯一存在的，当两棵搜刮树都触及到了某个状态时，这两棵树就出现了交织，搜刮即告竣事。
让两棵树从发生交织的状态结点各自原路返回构建路径，然后算法把两条路径拼接起来，即为结果路径。
可用条件
对于拼图游戏来说，已经知道了开始状态(某个乱序的状态)和目标状态(图片复原时的状态)，而这两个状态实在是可以互换的，完全可以从目标复原状态开始搜刮，反向推进，直到找出拼图开始时的乱序状态。以是，我们的拼图游戏是路径可逆的，得当双向广搜。
单线程下的双向广搜
要实现双向广搜，并不需要真的用两条线程分别从开始状态和目标状态对向展开搜刮，在单线程下也完全可以实现，实现的关键是于让两个开放队列交替出列元素。
在每一次循环中，比力两个开放队列的长度，每一次都选择最短的队列举行搜刮，优先让较小的树生长出子结点。如许做可以或许使两个开放队列维持大致相同的长度，同步增长，达到平衡两棵搜刮树的结果。

1. - (NSMutableArray *)search {
2.     if (!self.startStatus || !self.targetStatus || !self.equalComparator) {
3.         return nil;
4.     }
5.     NSMutableArray *path = [NSMutableArray array];
6.    
7.     // 关闭堆，存放已搜索过的状态
8.     NSMutableDictionary *positiveClose = [NSMutableDictionary dictionary];
9.     NSMutableDictionary *negativeClose = [NSMutableDictionary dictionary];
10.    
11.     // 开放队列，存放由已搜索过的状态所扩展出来的未搜索状态
12.     NSMutableArray *positiveOpen = [NSMutableArray array];
13.     NSMutableArray *negativeOpen = [NSMutableArray array];
14.    
15.     [positiveOpen addObject:self.startStatus];
16.     [negativeOpen addObject:self.targetStatus];
17.    
18.     while (positiveOpen.count > 0 || negativeOpen.count > 0) {
19.         // 较短的那个扩展队列
20.         NSMutableArray *open;
21.         // 短队列对应的关闭堆
22.         NSMutableDictionary *close;
23.         // 另一个关闭堆
24.         NSMutableDictionary *otherClose;
25.         // 找出短队列
26.         if (positiveOpen.count && (positiveOpen.count < negativeOpen.count)) {
27.             open = positiveOpen;
28.             close = positiveClose;
29.             otherClose = negativeClose;
30.         }
31.         else {
32.             open = negativeOpen;
33.             close = negativeClose;
34.             otherClose = positiveClose;
35.         }
36.         
37.         // 出列
38.         id status = [open firstObject];
39.         [open removeObjectAtIndex:0];
40.         
41.         // 排除已经搜索过的状态
42.         NSString *statusIdentifier = [status statusIdentifier];
43.         if (close[statusIdentifier]) {
44.             continue;
45.         }
46.         close[statusIdentifier] = status;
47.         
48.         // 如果本状态同时存在于另一个已检查堆，则说明正反两棵搜索树出现交叉，搜索结束
49.         if (otherClose[statusIdentifier]) {
50.             NSMutableArray *positivePath = [self constructPathWithStatus:positiveClose[statusIdentifier] isLast:YES];
51.             NSMutableArray *negativePath = [self constructPathWithStatus:negativeClose[statusIdentifier] isLast:NO];
52.             // 拼接正反两条路径
53.             [positivePath addObjectsFromArray:negativePath];
54.             path = positivePath;
55.             break;
56.         }
57.         
58.         // 否则，扩展出子状态
59.         [open addObjectsFromArray:[status childStatus]];
60.     }
61.     NSLog(@"总搜索数量: %@", @(positiveClose.count + negativeClose.count - 1));
62.     return path;
63. }

复制代码

A*搜刮(A Star)

差别于盲目搜刮，A*算法是一种启发式算法(Heuristic Algorithm)。
上文提到，盲目搜刮对于所有要搜刮的状态结点都是一视同仁的，因此在每次搜刮一个状态时，盲目搜刮并不会考虑这个状态到底是有利于趋向目标的，还是偏离目标的。
而启发式搜刮的启发二字，看起来是不是感觉这个算法就变得智慧一点了呢？正是如许，启发式搜刮对于待搜刮的状态会举行差别的优劣判定，这个判定的结果将会对算法搜刮次序起到一种启发作用，越精良的状态将会得到越高的搜刮优先级。
我们把对于状态优劣判定的方法称为启发函数，通过给它评定一个搜刮代价来量化启发值。
启发函数应针对差别的使用场景来计划，那么在拼图的游戏中，怎样评定某个状态的优劣性呢？粗略的评估方法有两种：

• 可以想到，某个状态它的方块位置放对的越多，分析它能复原目标的渴望就越大，这个状态就越精良，优先选择它就能减少无效的搜刮，颠末它而推演到目标的代价就会小。以是可求出某个状态所有方块的错位数量来作为评估值，错位越少，状态越精良。
  
• 假如让拼图上的每个方块都可以穿过相近方块，无阻碍地移动到目标位置，那么每个不在正确位置上的方块它间隔正确位置都会存在一个移动间隔，这个非直线的间隔即为曼哈顿间隔(Manhattan Distance)，我们把每个方块间隔其正确位置的曼哈顿间隔相加起来，所求的和可以作为搜刮代价的值，值越小则可以为状态越精良。
  

实在上述两种评定方法都只是对当前状态间隔目标状态的代价评估，我们还忽略了一点，就是这个状态间隔搜刮开始的状态是否已经非常远了，亦即状态结点的深度值。
在拼图游戏中，我们举行的是路径搜刮，假如搜刮出来的一条移动路径其需要的步数非常多，即使终极可以或许把拼图复原，那也不是我们渴望的路径。以是，路径搜刮存在一个最优解的问题，搜刮出来的路径所需要移动的步数越少，就越优。
A*算法对某个状态结点的评估，应综合考虑这个结点间隔开始结点的代价与间隔目标结点的代价。总估价公式可以表示为：

1. f(n) = g(n) + h(n)

复制代码

n 表示某个结点，f(n) 表示对某个结点举行评价，值即是这个结点间隔开始结点的已知价 g(n) 加上间隔目标结点的估算价 h(n)。
为什么说 g(n) 的值是确定已知的呢？在每次生成子状态结点时，子状态的 g 值应在它父状态的底子上 +1，以此表示间隔开始状态增长了一步，即深度加深了。以是每一个状态的 g 值并不需要估算，是实实在在确定的值。
影响算法效率的关键点在于 h(n) 的计算，采用差别的方法来计算 h 值将会让算法产生巨大的差别。

• 当增大 h 值的权重，即让 h 值远超 g 值时，算法方向于快速探求到目标状态，而忽略路径长度，如许搜刮出来的结果就很难保证是最优解了，意味着可能会多绕一些弯路，通往目标状态的步数会比力多。
  
• 当减小 h 值的权重，降低启发信息量，算法将方向于注意已搜深度，当 h(n) 恒为 0 时，A*算法实在已退化为广度优先搜刮了。(这是为照应上文的方便说法。严谨的说法应是退化为 Dijkstra 算法，在本游戏中，广搜可等同为 Dijkstra 算法，关于 Dijkstra 这里不作深入展开。)
  

以下是拼图状态结点 PuzzleStatus 的估价方法，在实际测试中，使用方块错位数量来作估价的结果不太显着，以是这里只使用曼哈顿间隔来作为 h(n) 估价，已能达到不错的算法效率。

1. /// 估算从当前状态到目标状态的代价
2. - (NSInteger)estimateToTargetStatus:(id<JXPathSearcherStatus>)targetStatus {
3.     PuzzleStatus *target = (PuzzleStatus *)targetStatus;
4.    
5.     // 计算每一个方块距离它正确位置的距离
6.     // 曼哈顿距离
7.     NSInteger manhattanDistance = 0;
8.     for (NSInteger index = 0; index < self.pieceArray.count; ++ index) {
9.         // 略过空格
10.         if (index == self.emptyIndex) {
11.             continue;
12.         }
13.         
14.         PuzzlePiece *currentPiece = self.pieceArray[index];
15.         PuzzlePiece *targetPiece = target.pieceArray[index];
16.         
17.         manhattanDistance +=
18.         ABS([self rowOfIndex:currentPiece.ID] - [target rowOfIndex:targetPiece.ID]) +
19.         ABS([self colOfIndex:currentPiece.ID] - [target colOfIndex:targetPiece.ID]);
20.     }
21.    
22.     // 增大权重
23.     return 5 * manhattanDistance;
24. }

复制代码

状态估价由状态类自己负责，A*算法只扣问状态的估价结果，并举行 f(n) = g(n) + h(b) 操纵，确保每一次搜刮，都是待搜空间里代价最小的状态，即 f 值最小的状态。
那么问题来了，在给每个状态都计算并赋予上 f 值后，怎样做到每一次只取 f 值最小的谁人？
前文已讲到，所有扩展出来的新状态都会放入开放队列中的，假如 A*算法也像广搜那样只放在队列尾，然后每次只取队首元素来搜刮的话，那么 f 值完全没有起到作用。
究竟上，由于每个状态都有 f 值的存在，它们已经有了优劣高下之分，队列在存取它们的时候，应当按其 f 值而有选择地举行入列出列，这时候需要用到优先队列(Priority Queue)，它可以或许每次出列优先级最高的元素。
以下是 A*搜刮算法的代码实现：

1. - (NSMutableArray *)search {
2.     if (!self.startStatus || !self.targetStatus || !self.equalComparator) {
3.         return nil;
4.     }
5.     NSMutableArray *path = [NSMutableArray array];
6.     [(id<JXAStarSearcherStatus>)[self startStatus] setGValue:0];
7.    
8.     // 关闭堆，存放已搜索过的状态
9.     NSMutableDictionary *close = [NSMutableDictionary dictionary];
10.     // 开放队列，存放由已搜索过的状态所扩展出来的未搜索状态
11.     // 使用优先队列
12.     JXPriorityQueue *open = [JXPriorityQueue queueWithComparator:^NSComparisonResult(id<JXAStarSearcherStatus> obj1, id<JXAStarSearcherStatus> obj2) {
13.         if ([obj1 fValue] == [obj2 fValue]) {
14.             return NSOrderedSame;
15.         }
16.         // f值越小，优先级越高
17.         return [obj1 fValue] < [obj2 fValue] ? NSOrderedDescending : NSOrderedAscending;
18.     }];
19.    
20.     [open enQueue:self.startStatus];
21.    
22.     while (open.count > 0) {
23.         // 出列
24.         id status = [open deQueue];
25.         
26.         // 排除已经搜索过的状态
27.         NSString *statusIdentifier = [status statusIdentifier];
28.         if (close[statusIdentifier]) {
29.             continue;
30.         }
31.         close[statusIdentifier] = status;
32.         
33.         // 如果找到目标状态
34.         if (self.equalComparator(self.targetStatus, status)) {
35.             path = [self constructPathWithStatus:status isLast:YES];
36.             break;
37.         }
38.         
39.         // 否则，扩展出子状态
40.         NSMutableArray *childStatus = [status childStatus];
41.         // 对各个子状进行代价估算
42.         [childStatus enumerateObjectsUsingBlock:^(id<JXAStarSearcherStatus>  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
43.             // 子状态的实际代价比本状态大1
44.             [obj setGValue:[status gValue] + 1];
45.             // 估算到目标状态的代价
46.             [obj setHValue:[obj estimateToTargetStatus:self.targetStatus]];
47.             // 总价=已知代价+未知估算代价
48.             [obj setFValue:[obj gValue] + [obj hValue]];
49.             
50.             // 入列
51.             [open enQueue:obj];
52.         }];
53.     }
54.     NSLog(@"总共搜索: %@", @(close.count));
55.     return path;
56. }

复制代码

可以看到，代码基本是以广搜为模块，加入了 f(n) = g(n) + h(b) 的操纵，并且使用了优先队列作为开放表，如许改进后，算法的效率是不可同日而语。

末了，贴上高难度下依然战斗力爆表的 A*算法结果图：

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。