0×00 前言
前两天做isg的题 看到有一道题是涉及的迷宫的问题。
0×01 手工来解
这个题目是一个游戏,是一个RPG maker生成的游戏。我玩了一下,使用了左手贴墙一直前进的法则去遍历这个迷宫。玩了半小时之后,发现不是太靠谱。不过在玩的过程中也发现,可以先想办法把地图弄出来,在地图上用肉眼通关,不会受制于游戏中的速度,也可以找到更快的捷径。

我们使用RPG Maker XP新建一个工程,把Game.rxproj工程文件拷贝到游戏文件夹下,就可以打开游戏了,文件内容是 RPGXP 1.03

在RPG Maker里可以设置1/4的大小,然后把地图慢慢截图出来。500*500大小的迷宫,真是丧心病狂。7*4 一共28张图才把地图拼了出来。还支持ruby的脚本,可以使用ruby脚本去跑出来,方便保存,也是可以的。

然后就是在迷宫先用左手法则,贴着墙走,因为不是复合多层的迷宫,所以可以使用这个方法去通过。思想其实就是深度优先搜索,把迷宫的每一个角落都遍历一次,肯定可以找到解。然后我们可以多做一些标记,使用箭头配合数字的方法去把方向顺序标示清楚。分别从迷宫的两端出发,一步步逼近这个解。

最后用了3个小时找到了遍历的路径,再用了2个小时,把路径化简清晰,把重复冗余的舍去,最后得到了一份地图,按着地图走在游戏里大概只要20分钟只有就可以找到宝箱,对着宝箱回车一下flag就出来了。
第一次标示的路径:

ISG 迷宫游戏-安全盒子

化简之后的路径:
ISG 迷宫游戏-安全盒子

因为游戏是使用了网络通信,可以flag并没有存在本地,逆向突破之类的话,也比较麻烦。还想到可以用编程的方法去实现,做一个脚本去游戏中自动深度遍历迷宫,但是需要设置好停止的方法,因为迷宫只有一个入口,不要超过宝箱了。

ISG 迷宫游戏-安全盒子

ISG 迷宫游戏-安全盒子
最后得到了flag
ISG{RRRRPG_MMMMMMAKER}

0×02 ps解法
我在自己走迷宫的时候,其实也是想过使用ps也能来辅助一下的,最后因为本机没装ps只好作罢,结束之后看到有一种是使用ps的解法。
参考一下这个 我转载一下
phoshop另类用法:用photoshop快速走迷宫

其实很多人还不知道解迷宫其实有一个非常简单的方法, 就是用photoshop, 非常简单, 几步就搞定, 会photosop的一看就明白, 没用过photoshop的也可以照着我下面说的步骤试一下:
(本例是用的photoshop8.0, 不管哪个版本的都可以)

一: 用photoshop打开一张迷宫图:
ISG 迷宫游戏-安全盒子
二: 在工具栏上选择魔棒工具, 然后在图上点右键, 选择色彩范围, 颜色容差200.
ISG 迷宫游戏-安全盒子
(如果你的图对比度很高, 又很清晰, 可以直接跳到第5步)
三:点击确定, 然后新建一图层
ISG 迷宫游戏-安全盒子
四:编辑–>填充(黑色[其他色也行]), 然后把背景图取消可见, 效果如下图:
ISG 迷宫游戏-安全盒子
五:选择魔棒工具, 在迷宫图的线条上点一下, 效果如下:
ISG 迷宫游戏-安全盒子
六:依次:选择–>修改–>扩展 扩展量16像素.(这个值不一定, 根据你图的大小)
ISG 迷宫游戏-安全盒子
确定后达到如下效果即可, 你可以试几次
ISG 迷宫游戏-安全盒子
七: 新建一图层, 编辑–>填充(本例填充的是红色),效果如图:
ISG 迷宫游戏-安全盒子
九:按dele键删除选取, 然后取消选择, OK 迷宫路线已经出来了, 效果如图
ISG 迷宫游戏-安全盒子
八:依次点: 选择–>修改–>收缩 ; 收缩量8像素

ISG 迷宫游戏-安全盒子

0×03 编程解法
还有一种方法就是想办法把迷宫的地图作为一个数据结构存起来,然后使用算法来解

就是利用一些搜索算法,比如说dfs深度优先搜索,bfs广度优先搜索,A*启发式搜索算法。
之前 琪琪师傅 带我看了dfs算法,我之后去写写看 能不能搞一个解迷宫的dfs算法出来,之后再更新出来。

这里有一个A*的算法可以参考一下
ISG2015 FlappyPig Writeup

0×04 MC迷宫
之前的比赛 SCTF 还尝试过在MC的游戏里搭建迷宫
先搭建好第一层,然后使用WE插件复制一层,提高迷宫的高度,让人能通过,最后可以使用南瓜灯或者是用应试封顶来照亮地图。或者是更丧心病狂的玻璃迷宫,应该会很变态的,以后去试试。
这种迷宫应该会更加难走的,因为封顶之后,是没法用地图插件看到整个地图的,而且那个迷宫走起来因为到处都长得一样,所以走久了会特别恶心,让你一直对着一个画面,然后机械的用左手法则深度搜索这个迷宫,我试过一次,100*100的MC迷宫,我走了半小时,才走出来了,太恶心了。
附一下之前SCTF的一张图

ISG 迷宫游戏-安全盒子