老鼠走迷宫数据结构课程设计报告

1、信息科学与技术学院数据结构课程设计报告题目名称：专业班级：学生姓名：学生学号：指导教师：走迷宫游戏计科20132班何意2013508063 高攀完成日期： 2016年1 月 5 日1、 需求分析程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。要求：1、老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2、迷宫的墙足够结实，老鼠不能穿墙而过；3、正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；4、添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；5、找出走出迷宫的所有路径，以及最

2、短路径。利用序列化功能实现迷宫地图文件的存盘和读出等功能。本程序使用OpenGL图形库来实现上述程序功能，采用面向对象的程序设计方法编写了一个3D小游戏，定义两个类：老鼠类和迷宫类。OpenGL简介：OpenGL 作为当前主流的图形 API具有以下特点： 1、与 C 语言紧密结合。 OpenGL 命令最初就是用 C 语言函数来进行描述的，对于学习过 C 语言的人来讲，OpenGL 是容易理解和学习。2、 强大的可移植性。 微软的 Direct3D 虽然也是十分优秀的图形 API，但它只用于 Windows 系统（现在还要加上一个 XBOX 游 戏机）。而 OpenGL 不仅用于 Windows

3、，还可以用于 Unix/Linux 等其它系统，它甚至在大型计算机、各种 专业计算机（如：医疗用显示设备）上都有应用。并且，OpenGL 的基本命令都做到了硬件无关，甚至是 平台无关。 3、高性能的图形渲染。OpenGL 是一个工业标准，它的技术紧跟时代，现今各个显卡厂家无一不对 OpenGL 提供强力支持，激烈 的竞争中使得 OpenGL 性能一直领先。 总之，OpenGL 是一个很强大的图形软件接口。DOOM3 和 QUAKE4 等专业大型游戏出色的视觉表现力就是OpenGL强大性能的体现。2、 概要设计1、 设计思路整体设计思路：采用面向对象的程序设计方法，将迷宫和老鼠作为两个单独的类来

4、实现。游戏逻辑设计思路：首先使用DFS算法思想根据用户输入迷宫的规模随机生成一个用二维矩阵形式表示的逻辑上的迷宫，再计算出迷宫在实际空间中的坐标，调用OpenGL提供的绘图API绘制迷宫，再绘制一只老鼠，当玩家按下游戏控制键后，先检测碰撞，再根据按的键计算出老鼠的新位置的坐标，然后重新绘制老鼠，期间还要一直进行所用时间的判断，若超时则提前结束游戏，若玩家成功完成游戏则输出玩家得分并结束游戏。2、程序所使用的重要抽象数据类型（部分）1、栈stacksk定义：<stack>库文件中的标准定义。功能：DFS-遍历栈，记录表示迷宫矩阵中已经处理过的方格，将还需要打通的方格压入栈中，将已经不

5、能打通的方格弹出栈，算法将遍历每一个方格，保证每个方格都会被打洞。操作：压栈操作Push()，弹出操作Pop()，取栈顶元素Top()。2、二维向量Int2定义：template<typename Type>struct Vector2 Vector2(Type _x = Type(0), Type _y = Type(0) :x(_x), y(_y) Type x, y;typedef Vector2<int>Int2;功能：用来记录创建迷宫时当前操作的位置行号与列号，检测碰撞中记录当前检测点所在的迷宫行号与列号。操作：对x和y的赋值。3、三维向量GLfloat3定义

6、：template<typename Type>struct Vector3f Vector3f(Type _x = Type(0), Type _y = Type(0), Type _dir = Type(0) :x(_x), y(_y), dir(_dir)Type x, y, dir;typedef Vector3f<GLfloat> GLfloat3;功能：用来记录绘制迷宫墙体的立方体的坐标和朝向。操作：对x,y和dir的赋值。4、二维矩阵globalNorth，globalEast和globalRecord定义：bool globalNorth100100;b

7、ool globalEast100100;bool globalRecord100100;功能：在创建迷宫时所用的数据结构，globalNorth表示迷宫格子北面(上)的墙的状态（0可通行，1墙），globalEast表示迷宫东面的墙状态，record表示迷宫格子本身是否被处理过（1-没有处理,0-处理过）。3、程序的六个主要功能模块：1) 主程序模块，功能：负责初始化游戏窗口和控制程序中各个模块的协调工作；2) 绘制老鼠模块，功能：实现老鼠形象的创建；3) 绘制迷宫的模块，功能：实现迷宫的绘制；4）键盘控制捕捉模块；5）老鼠的移动和碰撞检测模块，功能：实现老鼠对键盘的响应和检测是否与墙壁产生

8、碰撞；6）游戏中的时间控制模块，功能：实现对玩家所用时间和剩余时间的计算，以及判断是否超时。模块之间的调用关系图如图1-0所示：主程序模块键盘控制捕捉模块绘制迷宫模块绘制老鼠模块移动和碰撞检测模块时间控制模块图1-04、 程序运行流程图如图1-1所示：图1-13、 详细设计1、 老鼠类的定义UML类图如图1-2所示： 图1-22、 函数实现说明：1、 主函数void main(int argc,char *rgc)功能：实现对游戏整体的运行控制，依次调用各个功能模块。伪代码：void main(int argc, char *argv) 读入玩家输入的迷宫规模；调用迷宫类对象的createma

9、ze()函数创建迷宫；调用老鼠类对象的getmaze()函数获取老鼠所在的迷宫指针；初始化OpenGL图形窗口；while(游戏未结束)调用CPU闲时绘图函数重复绘图；检测键盘控制；return；2、绘制老鼠函数void Mouse:drawmouse()功能：负责在OpenGL构图空间中绘制老鼠形象。用法：在需要绘制老鼠的时候调用mymouse.drawmouse()函数即可，本程序是在myDispaly()函数中调用的。伪代码：void Mouse:drawmouse()设置对原点的偏移量，实现老鼠的移动；设置旋转角度，实现老鼠的转向，实际先旋转再平移；拉伸躯干和面部绘制老鼠躯干；绘制老鼠

10、头部；绘制右眼睛；绘制左眼睛；绘制一面白色胡须；另一面的胡须；碰撞检测参考点；绘制鼻子；绘制效果如图1-3：图1-33、创建迷宫函数void Maze:createMaze()功能：使用DFS深度优先搜索算法在一个二维矩阵中生成一个逻辑上的迷宫，并且将逻辑形式上的迷宫的墙体在OpenGL构图空间的实际坐标值和方向计算出来并保存在一个栈vecCube中，共绘图函数直接使用。代码：void Maze:createMaze()for (int i = 0; i <= S; i+)/给迷宫设置一个外围for (int j = 0; j <= S; j+) globalNorthij = t

11、rue;globalEastij = true;globalRecordij = true;for (int i = 0; i <= S + 1; i+) globalRecordi0 = globalRecordiS + 1 = false;for (int i = 0; i <= S + 1; i+) globalRecord0i = globalRecordS + 1i = false;Int2 dir4 = Int2(0, -1),Int2(1, 0),Int2(0, 1),Int2(-1, 0);vector<int> vg;/记录格子(左上右下)可以打洞的方

12、向stack<Int2> sk;/DFS-遍历栈，将遍历每一个方格，保证每个方格都会被打洞/生成“老鼠”所在的格子int x = rand() % S + 1;int y = rand() % S + 1;sk.push(Int2(x, y);while (!sk.empty() Int2 pos = sk.top();vg.clear();for (int i = 0; i < 4; i+) int c = pos.x + diri.x;int r = pos.y + diri.y;/可以打洞if (globalRecordcr) vg.push_back(i);if (v

13、g.size() <= 0) /该格子四周都不需要打洞sk.pop();continue;else /随机一个方向打洞int i = vgrand() % vg.size();globalRecordpos.x + diri.xpos.y + diri.y = false;globalRecordpos.xpos.y = false;switch (i) case 0:globalEastpos.xpos.y - 1 = false; break;case 1:globalNorthpos.xpos.y = false; break;case 2:globalEastpos.xpos.y

14、 = false; break;case 3:globalNorthpos.x - 1pos.y = false; break;if (vg.size() = 1) sk.pop();sk.push(Int2(pos.x + diri.x, pos.y + diri.y);/最外层墙壁打洞，(生成出口)globalNorthSS = false;globalNorth01 = false;/横向线段for (int i = 0; i <= S; i+)for (int j = 1; j <= S; j+) if (globalNorthij) GLfloat3 a;a.x = (j

15、 - 1)*GSZ+j*GSZ)/2;a.y = i*GSZ;a.dir = NORTH;vecCube.push_back(a);/竖向线段for (int i = 1; i <= S; i+)for (int j = 0; j <= S; j+) if (globalEastij) GLfloat3 b;b.x = j*GSZ;b.y = (i*GSZ+(i - 1)*GSZ)/2;b.dir = EAST;vecCube.push_back(b);4、 绘制迷宫函数void Maze：drawmaze()功能：负责在OpenGL构图空间中绘制迷宫。用法：在需要绘制迷宫调用类对

16、象的绘图成员函数即可，本程序中是在myDisply()函数中调用的。伪代码：void Maze:drawMaze()设置围墙颜色；从保存围墙分部信息的栈vecCube中依次取出栈顶元素进行绘制墙体；绘制终点线；绘制的效果如图1-4：图1-45、 移动和碰撞检测函数void Mouse:move()功能：实现老鼠对键盘的响应和使用盒式包围法检测是否与墙壁产生碰撞。用法：在OpenGL提供提供的键盘控制捕捉函数glutKeyboardFunc()中调用，对玩家输入老鼠的移动进行响应并重新设置老鼠的新位置坐标和新方向，若产生碰撞则调用碰撞处理函数。伪代码：void Mouse:move( unsig

17、ned char key,int x,int y)/按键响应函数，设置老鼠的移动并检测碰撞,使用盒式包围法思想，共需要检测四个点的碰撞情况ABCD时间逻辑判断部分；首次按键开始计时；移动和碰撞检测部分；判断老鼠是否到达终点，是转到1，否到21：到达终点；显示得分画面并结束游戏2：switch (key)/对按键响应case 'w or a or s or d' :if(direction=方向）/给出朝向为Y轴正方向的的详细代码计算碰撞点A，B的逻辑坐标 ；计算A，B点在迷宫中的行号和列号；检测A点是否碰撞；检测B点是否碰撞；若未发生碰撞，则根据方向设置老鼠位置；若发生碰撞，则

18、调用碰撞处理函数；摄像机移动部分；当老鼠朝向为Y轴正方向时，按w键（前进）时计算碰撞点的逻辑坐标；检测A点是否碰撞；检测B点是否碰撞；4、 调试分析1. 刚开始的时候绘制迷宫时没搞清楚迷宫行号和列号与空间坐标的映射关系，导致迷宫的绘制一直不正确，后来仔细作图分析才最终确定出了正确的映射关系。2. 个人感觉最难的部分就是碰撞处理，因为碰撞多种情况，每种情况必须单独仔细的分析，计算出精确到空间像素点之间的位置关系，这个模块花费了大量的时间和脑力。3. 本程序的模块划分比较合理,而且采用面向对象的程序设计方法，很好的封装了类对象的数据和操作，增强的程序与实际的仿真性，而且使用各个模块只需调用相应对象的成员函数即可，方便直观。 4、在构图时需要运用大量空间几何的数学知识，因为绘图时需要计算关键像素点的空间位置以及和其他关键点的相对位置。5. 本课程设计作业采用面向对象的程序设计方法，设计