ISG 迷宫游戏

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就出来了。
第一次标示的路径：

化简之后的路径：

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

最后得到了flag
ISG{RRRRPG_MMMMMMAKER}

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

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

一: 用photoshop打开一张迷宫图:

二: 在工具栏上选择魔棒工具, 然后在图上点右键, 选择色彩范围, 颜色容差200.

(如果你的图对比度很高, 又很清晰, 可以直接跳到第5步)
三:点击确定, 然后新建一图层

四:编辑–>填充(黑色[其他色也行]), 然后把背景图取消可见, 效果如下图:

五:选择魔棒工具, 在迷宫图的线条上点一下, 效果如下:

六:依次:选择–>修改–>扩展 扩展量16像素.(这个值不一定, 根据你图的大小)

确定后达到如下效果即可, 你可以试几次

七: 新建一图层, 编辑–>填充(本例填充的是红色),效果如图:

九:按dele键删除选取, 然后取消选择, OK 迷宫路线已经出来了, 效果如图

八:依次点: 选择–>修改–>收缩 ; 收缩量8像素

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

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

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

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

FROM :appleu0.sinaapp.com | Author:appleu0