2015-03-迷宫寻径-Maze-Project

相关背景

去年 C 程序设计专题的第一个 Project (模块化程序设计与递归函数专题),当时出于一种拿高分+逼格的目的,写了两个版本—— Console 版和 GUI 版。

Project 的要求就是用递归求解平面迷宫问题(或者用递归求解 N 皇后问题),然后再无其他限制。

当时在老师提及八皇后问题后,已经尝试写过若干个版本的 N 皇后了,所以 Project 就选择了迷宫问题。

效果图

Console 版

console-1

console-2 console-3

GUI 版(EGE实现)

maze-1 maze-2 maze-3

感想

怎么说呢,在当时,对我而言,这也算是有一定的难度的。当时最为繁琐的就是图形库的选择与图形化的实现,尤其是图形库的选择过程。当时尝试了GTK+, SDL, easyX, EGE,最后只有 easyX 和 EGE 能在我的电脑上正常的使用。然后又听说 EGE 的效率比 easyX 高,于是便选择了 EGE ,看了大约两个小时文档(然后发现几乎都没用到),最后写出了 GUI 版的 Project。

然后为了演示的效果,又用深度优先搜索实现了迷宫的自动生成。最终与基于递归实现的迷宫寻径整合到一起,实现了这个 Project。

具体实现及思路

采用一个全局的动态二维数组用于储存迷宫信息(如下表所示),同时记录墙体与空间位置。然后用若干个结构体记录坐标。

迷宫生成的方式,则是参考了 Wikipedia 的描述,首先将原始迷宫初始化为一张完全方格图,然后设定起点和终点,从起点开始进行深度优先搜索,每次遍历的方向与步数都随机取值,途中遇能拆的墙(墙对面有未遍历过的空间)则“拆墙”(将该位置改为空余的空间),直至遍历全图。

至于路经的寻找则是用相对简单的递归实现的(实际也是一个深度优先搜索,其实用广度优先搜索效率会高一些?,但是题目要求使用递归实现),一个简简单单的回溯过程。将终点位置作为递归出口,递推关系为相邻两空余点间的水平或垂直移动——若可以从当前坐标移动到某一相邻坐标(墙壁或路径点或标记不可通点为无法移动到的点),则将该点标记为路径点,从可移动位置进行下一轮的移动;若从当前点无法移动到其所有相邻的坐标,则将改点标记为不可通点,从当前函数返回,继续进行上一路径点所对应的移动过程。以此类推,在迷宫可通、迷宫大小合适的情况下,必然可得出至少一个可行解。(这一段是当时在报告上写的,直接了粘贴过来)这种思路很简单,可惜递归的实现一点都不优雅,当问题规模增大时,必然会堆栈溢出。尽管当时我的能力足以实现一个模拟堆栈的版本,但精力有限(总不能将时间都耗在这门课上),未去实现。

(差不多都忘了……早知当时就该顺手更新上来的)

源码

有点惨不忍睹……算是自己的黑历史吧。。。

当时交的版本随机遍历以生成迷宫,未采用 DFS

(当时写的修改版中函数竟然用的是 ‘dps’ 什么鬼(⊙﹏⊙))

Console 版(上交时的格式)

GUI 版(还有一个 Res 目录存放了实现动画的图片)

采用 DFS 的 GUI 版

 

发表评论

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