云南大学软件学院数据结构实验四实验报告——迷宫游戏

（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度：A□B□C□序号学号姓名成绩123指导教师（签名）学期：任课教师:实验题目:实验四数组的表示及其应用小组长:联系电话:电子邮件:完成提交时间：年月日云南大学软件学院数据结构实验报告云南大学软件学院2010学年秋季学期《数据结构实验》成绩考核表学号：姓名：本人承担角色：课题分析，算法设计，程序编写，后期调试，完成实验报告评分项目评分指标分值得分实验构思（10%）1.实验目的明确52.实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1.有对基本数据结构的抽象数据类型定义52.实验方案设计完整，数据结构、算法选择合理53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1.代码编写规范、风格统一、注释清楚易读52.程序运行正常，测试结果正确153.界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1.内容详实无缺漏，文字流畅、图表清楚52.实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1.个人完成工作量152.个人技术水平103.团队合作精神5实验运作（10%）1.有一定用户群52.应用前景分析5综合得分：（满分100分）指导教师：年月日（注：此表在难度为C时使用，每个成员一份。）云南大学软件学院2010学年秋季学期《数据结构实验》成绩考核表学号：姓名：本人承担角色：课题分析，算法设计，后期调试评分项目评分指标分值得分实验构思（10%）1.实验目的明确52.实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1.有对基本数据结构的抽象数据类型定义52.实验方案设计完整，数据结构、算法选择合理53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1.代码编写规范、风格统一、注释清楚易读52.程序运行正常，测试结果正确153.界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1.内容详实无缺漏，文字流畅、图表清楚52.实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1.个人完成工作量152.个人技术水平103.团队合作精神5实验运作（10%）1.有一定用户群52.应用前景分析5综合得分：（满分100分）指导教师：年月日（注：此表在难度为C时使用，每个成员一份。）（下面的内容由学生填写，格式统一为，字体:楷体,行距:固定行距18，字号:小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）本次实验，我们小组制作了一个具有一定可玩度的迷宫游戏，利用了随机数生成代码的方式生成了一个每次运行程序都不一样的迷宫。主要算法：构造一个树，在地图中的一个指定位置（由游戏难度决定）设定一个起始点，将这个地图的序号为奇数的点看为一个个节点，将起始点看作树的根，然后取系统的时钟信号，生成一个伪随机数，用来随机地生成地图，当这一个树构造完毕，即遍历完所有的目标点位后，一个比较规则的迷宫也就建成了，从起点到终点有且只有一条路。主要子程序：键盘监听程序：利用一个文本框来监听键盘，响应一系列键盘的事件，此子程序一直在后台运行，随时保持监听状态。二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）namespace实验四迷宫第三次尝试//调用本程序的命名空间{publicpartialclassForm1:Form//定义一个窗口类{publicForm1()//窗口1的构造函数，用于初始化某些控件privatevoidbutton1_Click(objectsender,EventArgse)//当用户点下“开始游戏”按钮的响应事件publicvoidCreatMaze()//创造并显示一个合法的迷宫publicvoidToNorth()//控制小人向上方走一步publicvoidToSouth()//控制小人向下方走一步publicvoidToEast()//控制小人向右边走一步publicvoidToWest()//控制小人向左边走一步publicvoidIfArrive()//判断小人是否到达终点publicvoiddista()//计算小人与终点之间的距离publicvoidkeyup()//当用户按下向上箭头的时间publicvoidkeydown()//当用户按下向下箭头的时间publicvoidkeyright()//当用户按下向右箭头的时间publicvoidkeyleft()//当用户按下向左箭头的时间privatevoidbutton2_Click(objectsender,EventArgse)//当用户点击帮助按钮时的响应事件privatevoidbutton3_Click(objectsender,EventArgse)//当用户点击关于按钮时的响应事件privatevoidtextBox1_KeyDown(objectsender,KeyEventArgse)//监听键盘输入子程序}publicpartialclassForm2:Form//定义一个窗口类{publicForm2()//窗口2的构造函数，用于初始化相关的函数和控件privatevoidbutton1_Click(objectsender,EventArgse)//当用户点击确认按钮时的响应事件privatevoidradioButton1_CheckedChanged(objectsender,EventArgse)//用户选择大师级难度的响应事件privatevoidradioButton2_CheckedChanged(objectsender,EventArgse)//用户选择高手级难度的响应事件privatevoidradioButton3_CheckedChanged(objectsender,EventArgse)//用户选择标准级难度的响应事件privatevoidradioButton4_CheckedChanged(objectsender,EventArgse)//用户选择低手级难度的响应事件privatevoidradioButton5_CheckedChanged(objectsender,EventArgse)//用户选择菜鸟级难度的响应事件}}三、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）深度优先遍历算法：深度优先遍历从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的下一个新的顶点进行访问，重复此步骤，直到所有结点都被访问完为止。将这个算法运用到迷宫中即：将所有的点位全部设置为“墙”，只保留一个其实点位为“路”，然后利用深度优先算法，遍历全部节点并且做下记录（利用栈），完成遍历后将栈中的遍历表复原，即得到一个迷宫，迷宫的难度由遍历的起始点决定。倘若起始点在用户的出发点位即为最简单的迷宫，因为用户使处于逻辑树的根部，终点在一个节点。倘若起始点在终点的位置，那么即为中间难度的迷宫，因为用户处于逻辑树的叶子节点，终点在逻辑树的根。倘若起始点在地图的中间点位的话，即为最高难度的迷宫，因为用户出发点位于逻辑树的叶子节点，终点也是在逻辑树的叶子节点，变数非常大实现上述深度优先遍历算法之后，我们将得到一颗二叉树，每一个分支对应着图上的每一个分岔口，形成一座有且只有一个出口的迷宫（因为二叉树没有回路）。而且我们为不同的难度的玩家配备了数目不同的破墙钻头，方便玩家过关。当用户感到过关无望时，可以使用破墙钻头（虽然数目有限）来帮玩家额外地在开辟出一条过关之路。四、【测试结果（Testing）】(10%)（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）在测试之初选择游戏难度时选择“菜鸟级”，经过测试，成功实现以起点为根的树的构造。在测试之初选择游戏难度为“大师级”，经过测试，成功实现以地图中间为树的根部的树的构造。综上：深度优先遍历算法成功。在游戏进行时使用键盘的上下左右按键实施操控，游戏中的主人公成功地按照我们所指定的方向前行。综上：游戏操控单元：键盘监听程序成功。四、【实验总结】(10%)（本部分应包括：自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得）这次和我们小组完成这个迷宫游戏——洞穴探险我在这个小组中参与了课题分析，算法设计，后期测试。独立完成了程序代码的编写，实验报告的编写。我们经历了五个版本：v1.0Beta1Beta2Beta3v1.1我们一点点的通过我们的努力使这个程序从命令行到桌面游戏从简单的随机实现的散乱的迷宫算法到规则的深度优先遍历迷宫算法从功能简单到功能丰富从界面呆板到生动活泼我们大家分工协作，配合默契。这次实验让我们体会到了什么才是真正的团队合作，看似是一个时间紧，任务重的，不可能完成的任务，我们依靠团队的力量成功的实现了之前的目标。解决了很多以前靠单打独斗解决不了的问题，学到了技术之外对我们更重要的团队精神。今后，我们会将这种合作精神运用到软件设计的各个环节，使整个团队工作在更高的效率之下。五、【项目运作描述（Operate）】(10%)（本部分应包括：项目的成本效益分析，应用效果等的分析。）1.本程序运行的环境为32位或64位WindowsNT环境。2.要求有.NETFramework3.5环境及以上。若系统不满足上述要求，本程序的setup.exe会自动检测以决定是否安装.NETFramework3.5。安装界面：3.安装完成后，会在桌面以及开始菜单（可选择）里面看到洞穴探险v1.1的图标，双击进入后我们会看到如下对话框：4.然后单击确定，进入游戏主界面，同时会弹出游戏参数设置的窗口：根据自己的实力选择游戏的等级，大师级最难，菜鸟级最容易本说明将选择“菜鸟级”作为范例：单击开始游戏按钮，迷宫将呈现在你的面前：使用上下左右按键操控主人公移动，直至走到终点，过关，之后会弹出如下对话框至此，此关游戏结束。你可以选择是否进入下一关。不再赘述。-------------------------------------------------------------------------当用户有什么对游戏的困难时，可以点击左边的问号，或者点击帮助菜单里面的游戏帮助，会弹出一个内容非常丰富的帮助文档：有关制作人的信息会放在关于菜单内，以便用户引用时查看：本程序使用了专业的程序管理方案，当用户不想使用本程序或因为种种原因不再想使用本程序时，我们将会完全地，不留任何残留文件地卸载本软件。点击“确定”本程序将被完全卸载。我们欢迎各路高手提出宝贵意见和建议，请联系：