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