写在前面
上一篇文章我写了一个简单的 iOS 拼图游戏( 童年的记忆--拼图游戏 ),现在我要让这个游戏聪明起来,帮助你来完成拼图.写这篇文章的时候正好在看《最强大脑》,节目里的第一个 PK 就是复原这种拼图(非图而是数字,数字华容道),节目营造了非常紧张的气氛,其实这种拼图复原算是比较简单的.
不再前戏,直接进入正题:游戏源码点这里( 拼图游戏 ),您可以从这份源码中 get 到的技术点:
> 设置代理类为控制器瘦身
> A * 算法(含借助完全二叉树实现优先队列)
> GCD 信号量控制数组遍历流量
> 定时器 + GCD 信号量实现数组遍历的暂停,继续
游戏效果:
基本思路
那么怎样让原本屌丝气质的游戏具备人工智能(AI),自动还原拼图,从此华丽变身高大上呢?
方案一:
我们很容易想到的方法,按打乱的顺序逆序还原.此方案的打乱顺序即将原本有序的图片按照游戏规则移动数次,从而实现打乱效果.但是我想你们已经发现了一个问题,我所设计的游戏打乱后空位设置在右下角,我们还需要想办法将空位移动到右下角的目标位置.
方案二:
不关心打乱的过程,依次将编号 0,1,2... 回归到正确位置,逐渐缩小乱序图区域.不过往往最后两行的几块需要稍微调整下策略.
方案三:
不关心打乱的过程,从打乱后的状态开始,根据一定约束条件,对下一步的多种可能性进行搜索判断,逐步演进,从而找出复原步骤.我选用的是 A * 搜索算法.
方案解读
* 方案一
方案一实现起来较为简单,假定我们现在已经将有序的(处于复原态)拼图移动了数次,也就是拼图打乱了(如下图左).接下来将空位移动到右下角.
显然,移动的策略有很多种,我们只需要一种,比如这样:空位先逐步横向移动到最右侧,再逐步纵向移动到最下侧.你看,可以啦.(上图右边)
算法分解:
.求出当前空位所在行,列.
.当前空位与其右侧格子换位.
.重复1,2,直到空位位于最右侧(最大列).
.当前空位与其下侧格子换位.
.重复1,4,直到空位位于最下侧(最大行).
如此,我们已经完成了打乱步骤.当然,我们移动的每一步都需要记录在案,以便按照记录逆步骤进行还原.注:我提供的游戏源码中并没有包含该方案(方案一)的代码实现,感兴趣的读者可以自行实现.
* 方案二
对于方案二,写这篇文章的时候才临时考虑加入这个方案.基本思路上文中其实已经阐明,暂不展开讨论.
* 方案三
对于方案三,容易联想到尝试每种步骤可能性,最终选出可以复原的步骤链.
上图即表示每一个状态衍生出的可能路径,排除了重复的状态.对于这种暴力搜索算法,性能是较低的(关于搜索算法,我此前的文章有介绍过最短路径的两个经典算法 点我 ).拼图为 4 阶方阵时,拼图状态数 (4*4)! = 20922789888000,广搜算法已基本不能搜出结果,直到爆内存.拼图为 5 阶方阵时,状态数 (5*5)! = 1.551121004333098e25,10 的 25 次方.先别着急,我们可以选择性能较高的 A * 算法为拼图游戏助力.
A * 算法简介:
A*(A-Star) 算法是一种静态路网中求解 最短路径 最有效的直接搜索方法,也是解决许多搜索问题的有效算法.它并不是搜索每一种可能的状态,而是有选择地启发式搜索,每一次在多个状态中选择可能最接近目标状态的一个.依此层层搜索,显然相比暴力搜索,少走了很多的弯路.
本文并不打算深入描述该算法技术细节.推荐阅读 A * 算法详解 .
对于该游戏,对每一个状态到目标状态的 "距离" 进行估算,将每一个方块偏离它正确位置的距离进行累加,取偏离值最小者择优录取.图示说明:
当前状态估价(本例中也就是曼哈顿距离)计算方式:
4距离它正确的位置也就是上图中7的位置:横向1+纵向1=2;
1距离它正确的位置0;
3距离它正确的位置也就是上图中2的位置:横向2+纵向1=3;
2距离它正确的位置也就是上图中3的位置:横向2+纵向1=3;
7距离它正确的位置也就是上图中5的位置:横向0+纵向1=1;
0距离它正确的位置也就是上图中4的位置:横向2+纵向1=3;
6距离它正确的位置0;
我们给予空格位特权,不对它考核.
5距离它正确的位置也就是上图中0的位置:横向0+纵向1=1;
然后将上述距离值累加.
当然实际还可以在这个基础上对估价进行调整,比如乘以一定系数.
性能优化(TODO)
暂时想到了以下优化方向:
当前源码每次 UICollectionView 数据源刷新时,为全局刷新方式,实际除了重置游戏,每次都只是 2 个格子在变化.可以修改为局部刷新.
当前源码为搜索完成后再进行拼图复原.需要耗费一定的时间.尝试边搜索边拼图的方式(边 "生产" 边 "消费").
根据方格数的多少(难易程度)灵活调整 A * 算法的估价,意在优化游戏还原步数.
鸣谢
本文配套源码中直接套用了《 拼图游戏和它的 AI 算法 》该文作者封装的 A * 算法,在此对原作者表示感谢.
来源: https://www.cnblogs.com/imsz/p/8309484.html