背景
最近在玩一个休闲益智小游戏，叫做《浅塘》(华容道的华丽升级版) (IOS|Android)
Tutorial.png
游戏的主要内容是通过移动木块指引困境中的小鱼逃出生天,而且木块只能向其长度方向移动
在和好友分享的过程中忍不住PK了一把，结果被虐的体无完肤
一怒之下，决定用计算机来辅助自己战胜敌人
WechatIMG74.jpeg
确定了可行性之后，抽各种零碎时间完成了浅塘游戏的攻略，在此发表这次经历，记录我热爱编码的一生
游戏介绍及攻略思想
游戏模式
- 休闲模式：用户可以移动任意步数，只要最终将小鱼成功解救即可
- 专家模式：有完美步数的要求，当你移动步数超过允许范围时，将强制停止闯关
攻略思想
无论在那种模式下，正常人在玩这款游戏时，本能的追求最小步数和最短时间，因此往往在移动一步时需要思索各个木块之间的关系，关卡的复杂度越高，越烧脑，也越好玩
虽然计算机是个笨蛋，但是通过快速移动木块进行大量试错，往往能比人更快找到解决方法
第一，先确定计算机要找的结果是什么样子的。
这个简单，只要小鱼的前面没有阻碍的木块就算可以脱离困境啦
第二，确定如何每个木块如何移动
由于木块只能水平或者上下移动，所以只要想移动的方向上没有阻碍，那么就每次移动一个木块算一个步骤(不论这个步骤移动了几个方格)，并把此时的场景当做一个新的状态，我们把每个状态称为一个map，简称m
以浅塘专家模式第一局举例说明：
firstblood.png
第三，由于每次只尝试移动一个木块，多次移动后难免有重复map，所以还要记录已经尝试过的map并去重
最后，一起复习一下简单的数据结构---队列（Queue）：“ 先进先出，后进后出”，复习完毕
最短时间优先算法
最短时间算法的核心思想就是，一条道走到黑，不断移动当前的map直到找到可以出去的状态
用个学术点的名字描述这个过程叫做(深度优先，DFS)，具体描述如下：
- 判断当前map(m0)是否满足逃出条件，如果满足则执行第4步
- 获取m0移动一步能够移动的所有状态M[m00,m01,m02,...m0n],并在每个状态中标记其母为m0
- 顺序获取M中的元素并将其从M中移除，将获取的元素做为m0，重复第1步
- 通过满足逃出条件map的母map依次找到这条路径上的所有maps
-
如果所有的元素都不满足逃出条件，说明这个关卡设计的有问题，根本无法逃出
图形表示：
DFS.jpeg
最少步数优先算法
最少步数算法的核心思想是，每次都要把当前map的所有可能状态allmaps遍历一遍，查看是否可通关，并依次对allmaps的中所有map重复这个过程，直到找到可通关的map
同样有个学术点的描述(广度优先，BFS)，具体描述如下：
- 将初始map添加到队列Queue(简称Q)中
- 出列Q中的map，如果此map满足逃出条件，跳转4
- 获取出列map的所有可移动状态M[m00,m01,m02,...m0n]，并将其添加到Q中,重复第二个步骤
- 通过满足逃出条件map的母map依次找到这条路径上的所有maps
-
如果Q已经空了,仍然没有找到满足逃出条件的map，逃出失败
图形表示：
BFS.jpeg
代码实现及验证(以休闲模式 121 、133 为例)
源码已经贴到GitHub上了，欢迎提交改进
使用步骤：
- 截图浅塘的某个关卡，并将游戏操作区域截取出来(源码中有截图示例)
- 上下滑动屏幕选择使用BFS还是DFS (默认BFS)
- 单击程序任何一处，选择第一步处理的照片，自动开始破解过程，可以打开log看操作日志
- 破解成功后，会有动画展示木块的移动过程
破解过程的效率问题：
- 写这份代码的时候只是为了娱乐，没有深究效率问题，现在想来如果把算法核心部分换成C来实现，应该会节省不少时间
- DFS的耗时很短，基本10s左右就出结果了，但是要走好几百步才能完成任务，一个关卡就能把手指磨没了，这个属于装X失败的典范，直接放弃
- BFS耗时较长，但操作效果良好，是玩专家模式的不二之选（用本地化记录已经破解过的关卡的解决步骤，节省同一关卡的破解时间，不过新的关卡会露馅，哈哈）
完成效果（BFS）演示：
qt121.gif
qt133.gif
本篇总结
- 给大家安利了一个休闲小游戏《浅塘》（如果游戏作者看到这篇文章，欢迎打赏广告费）
- 介绍了游戏攻略程序需要的算法原理并对算法部分进行了图文描述
- 对攻略程序进行了简单的实现并分析了存在的问题
后续规划
- 分析耗时关键节点，提高BFS效率
- 增强关卡输入的能力，做到扫描即可输入关卡
写这篇文章的时候《雷神3》即将中国首映，欢迎大家去支持我最爱的超级英雄---雷神
雷神(侵权删).jpg
网友评论