隐藏图形信息迷宫自动生成研究

摘要

迷宫游戏属于益智游戏，对儿童的心智发展有促进作用，并且利用迷宫游戏可以训练儿童的观察、推理与思维等多方面能力。国外已经有不少教育者、研究者开始将迷宫研究的重心转向促进儿童心理与智力等方面的发展上，从如何生成更符合儿童兴趣爱好的迷宫，到迷宫作为益智游戏是如何促进儿童多方面发展等方面，并取得了一定的研究成果。而国内更多的研究是将重点放在利用迷宫模拟危险复杂环境的路径搜索，如电脑鼠走迷宫问题、蚁群算法求解迷宫最优路径等，这说明对于迷宫问题，大多数研究者的研究兴趣都集中在求解上，而对迷宫的生成关注不多。迷宫游戏作为一种优秀的儿童教育资源，在国外家庭教育、甚至学校课堂教学都非常普遍，而在国内却寥寥无几，为了弥补这一空白，或者说希望引发更多的教育者、研究者将迷宫作为儿童益智游戏看待、并研究开发出更多被儿童所喜爱的迷宫益智游戏，本研究进行了隐藏一定图形信息迷宫游戏创建的探索，主要工作包括以下几方面: 1.常用迷宫算法的分析与比较。迷宫算法种类繁多，主要分为生成迷宫算法和求解迷宫路径算法，本研究主要探究迷宫的创建，因此所涉及的算法都是迷宫生成算法，当然不排除某些普适性的算法，如递归回溯算法等。从时间效率、空间效率、生成迷宫外观以及迷宫复杂度四方面对十二种迷宫生成算法进行分析比较，选出了递归回溯与非回溯算法作为创建隐藏图形信息迷宫的基本算法。 2.分析迷宫在计算机中的存储、表现，根据计算机迷宫的本质与特征，总结出两种创建迷宫的方法，即“拆除墙体法”与“布设墙体法”。计算机迷宫本质上是一个生成树，是在使用一定的算法遍历迷宫网格后得到的，“拆除墙体法”是在遍历迷宫网格（无向图）的过程中进行的，其本质是去除无向图的边，最终得到生成树。另外，在十二种算法中，“拆除墙体法”适用于多种迷宫生成算法，而“布设墙体法”只适用于一种。 3.采用逆向思维方式进行隐藏一定图形信息迷宫的创建。通常迷宫的生成都是一步完成的，即通过一次运行算法就可以得到包含一条从起点到终点的唯一路径的perfect迷宫，事实上一步到位的方法虽然简单，却不能实现隐藏一定图形信息迷宫的创建。逆向思维方法是先考虑创建一条唯一的迷宫路径，该路径可以组成某一个图形，在此基础上再创建剩下的部分。在创建唯一路径时，需要先构造哈密尔顿图，通过规定的遍历顺序与策略找出其哈密尔顿路径，得到的哈密尔顿路径正是所要创建的迷宫的解决方案。

目录

声明

摘要

第1章 绪论

1．1 研究背景与研究意义

1．2 迷宫问题与研究现状

1．2．1 国内研究现状

1．2．2 国外研究现状

1．3 本文结构与内容安排

第2章 迷宫相关概念与技术概述

2．1 迷宫的分类

2．1．1 按维度分类

2．1．2 按拓扑结构分类

2．1．3 按镶嵌结构分类

2．1．4 按迷宫路径分类

2．1．5 按纹理结构分类

2．1．6 按聚焦点分类

2．1．7 其他类型

2．2 常见迷宫生成算法

2．2．1 算法简介

2．2．2 算法分析与比较

2．3 迷宫游戏与儿童能力训练

2．3．1 儿童游戏本质心理

2．3．2 游戏对儿童的心理发展之作用

2．3．3 迷宫游戏训练儿童多方面能力

2．4 本章小结

第3章 迷宫的存储、表现与创建

3．1 迷宫的存储与表现

3．2 计算机迷宫的创建

3．2．1 拆除墙体法形成迷宫

3．2．2 布设墙体法形成迷宫

3．2．3 两种创建迷宫方法比较

3．3 求解迷宫揭露隐藏图形

3．3．1 迷宫解决方案

3．3．2 揭露隐藏图形

3．4 本章小结

第4章 隐藏图形信息迷宫的创建

4．1 迷宫中可以隐藏的图形分类

4．1．1 简单的数学几何图

4．1．2 汉字与阿拉伯数字

4．1．3 简单的实物投影图

4．2 逆向法创建迷宫的初步探索

4．2．1 设计包含一定图形信息的迷宫解决方案

4．2．2 递归回溯法与非回溯法遍历背景单元格

4．3 逆向法创建迷宫的进一步探索

4．3．1 放大迷宫网格构造哈密尔顿图

4．3．2 寻找哈密尔顿路径

4．3．3 遍历背景单元格形成完整迷宫

4．4 手绘风格迷宫的一种替代方案

4．5 本章小结

第5章 隐藏图形信息迷宫游戏的实现

5．1 打印类迷宫小游戏

5．2 基于Android的迷宫游戏设计与实现

5．2．1 迷宫游戏的交互性

5．2．2 动态生成迷宫与“人—机—人”互动

5．2．3 提供用户提示

5．2．4 寻路与回退

5．2．5 游戏快照

5．3 隐藏图形信息迷宫游戏的效果测试

5．3．1 测试设备的选择

5．3．2 模拟器上的测试效果

5．3．3 物理机上的测试效果

5．3．4 测试效果总结

5．4 本章小结

第6章 总结与展望

6．1 全文总结

6．2 研究不足与展望

参考文献

致谢