让你的拼图聪明起来——自动还原拼图(iOS 游戏)

澳门新葡亰娱乐在线 4

初学lufylegend.js之日,我用lufylegend.js开发了第一个HTML5小游戏——拼图游戏,还写了篇博文来炫耀一下:HTML5小游戏《智力大拼图》发布,挑战你的思维风暴。不过当时初学游戏开发,经验浅薄,所以没有好好专研游戏里的算法和代码的缺陷,导致游戏出现了很多bug,甚至拼图打乱后很可能无法复原。最近经常有朋友问起这个游戏,希望我能把代码里的bug改一下方便初学者学习,顺便我也打算测试一下自己写这种小游戏的速度,所以就抽出了一些时间将这个游戏从头到尾重新写了一遍,计算了一下用时,从准备、修改素材到最后完成游戏,一共用了大约2h的时间。

写在前面

上一篇文章我写了一个简单的iOS
拼图游戏(童年的记忆——拼图游戏),现在我要让这个游戏聪明起来,帮助你来完成拼图。写这篇文章的时候正好在看《最强大脑》,节目里的第一个PK就是复原这种拼图(非图而是数字,数字华容道),节目营造了非常紧张的气氛,其实这种拼图复原算是比较简单的。
澳门新葡亰娱乐在线,不再前戏,直接进入正题:游戏源码点这里(拼图游戏),您可以从这份源码中get到的技术点:

> 设置代理类为控制器瘦身
> A*算法(含借助完全二叉树实现优先队列)
> GCD信号量控制数组遍历流量
> 定时器+GCD信号量实现数组遍历的暂停、继续

游戏效果:

澳门新葡亰娱乐在线 1

游戏效果.gif

以下是游戏地址:

基本思路

那么怎样让原本屌丝气质的游戏具备人工智能(AI),自动还原拼图,从此华丽变身高大上呢?

  • 方案一:
    我们很容易想到的方法,按打乱的顺序逆序还原。此方案的打乱顺序即将原本有序的图片按照游戏规则移动数次,从而实现打乱效果。但是我想你们已经发现了一个问题,我所设计的游戏打乱后空位设置在右下角,我们还需要想办法将空位移动到右下角的目标位置。
  • 方案二:
    不关心打乱的过程,依次将编号0、1、2…
    回归到正确位置,逐渐缩小乱序图区域。不过往往最后两行的几块需要稍微调整下策略。
  • 方案三:
    不关心打乱的过程,从打乱后的状态开始,根据一定约束条件,对下一步的多种可能性进行搜索判断,逐步演进,从而找出复原步骤。我选用的是A*搜索算法。

方案解读

这是我的游戏记录,欢迎各位挑战:

* 方案一

方案一实现起来较为简单,假定我们现在已经将有序的(处于复原态)拼图移动了数次,也就是拼图打乱了(如下图左)。接下来将空位移动到右下角。

澳门新葡亰娱乐在线 2

图1.png

显然,移动的策略有很多种,我们只需要一种,比如这样:空位先逐步横向移动到最右侧,再逐步纵向移动到最下侧。你看,可以啦。(上图右边)

算法分解:

1。求出当前空位所在行、列。
2。当前空位与其右侧格子换位。
3。重复1、2,直到空位位于最右侧(最大列)。
4。当前空位与其下侧格子换位。
5。重复1、4,直到空位位于最下侧(最大行)。

如此,我们已经完成了打乱步骤。当然,我们移动的每一步都需要记录在案,以便按照记录逆步骤进行还原。注:我提供的游戏源码中并没有包含该方案(方案一)的代码实现,感兴趣的读者可以自行实现。

澳门新葡亰娱乐在线 3

* 方案二

对于方案二,写这篇文章的时候才临时考虑加入这个方案。基本思路上文中其实已经阐明,暂不展开讨论。

接下来就来讲讲如何开发完成这款游戏的。(按“编年体”)

* 方案三

对于方案三,容易联想到尝试每种步骤可能性,最终选出可以复原的步骤链。

澳门新葡亰娱乐在线 4

图2.png

上图即表示每一个状态衍生出的可能路径,排除了重复的状态。对于这种暴力搜索算法,性能是较低的(关于搜索算法,我此前的文章有介绍过最短路径的两个经典算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

网站地图xml地图