深度优先遍历算法、随机布点法及回溯法在迷宫游戏中的应用  

Application of Depth-first Traversal,Randomly Distributed Point Algorithm and Backtracking Method to Maze Game

作　　者：田翠华[1,2] 许卫平[1] 陈玉明[1] 

机构地区：[1]厦门理工学院,福建厦门361024 [2]沈阳工业大学,辽宁沈阳110023

出　　处：《河北北方学院学报（自然科学版）》2013年第3期19-24,共6页Journal of Hebei North University:Natural Science Edition

基　　金：国家自然科学基金项目(61103246);厦门理工学院科学技术项目(YKJ11012R;YKT10037R);厦门理工学院学院创新创业教育改革与建设项目(JGCX201117)

摘　　要：在Eclipse平台下采用Java语言实现迷宫游戏的设计与开发。采用随机布点算法生成不规则迷宫地图,采用图的深度优先遍历算法随机生成规则地图。地图格的大小、不同在相同的窗口生成较低、中等、较高三种不同难度的规则或不规则地图。把走迷宫的对象设置成角色方块,使用键盘方向键控制当前移动点进行游戏。遍历规则地图的起点不同,把游戏分为简单、中等、高难3种难易程度。运用回溯法从入口一步步进行探索,最后找到迷宫出口,并在界面上显示出该路径。编写画布类函数Canvas(),实现游戏设置。游戏的成功开发表明,算法研究至关重要,应用这些算法开发游戏是有效的。The paper designed and developed a Maze game under the Eclipse platform by using Java development tool.The randomly distributed point algorithm was used to generate an irregular map,and the algorithm of depth-first traveling to generate a regular map.Setting different size of the map’ s grid in the map on the same game window formed regular or irregular maps with low,medium and high degree of difficulty.The game walker was set as a role object and the keyboard’ s arrow keys were used to control the current point move.And we can play the game from different points to travel form three level games on regular map with levels of simple,medium,and difficulty.Backtracking method was taken to search the path from entrance to the exit step by step to find it at last,showing the path on the interface.The function Canvas()was programmed to set the game configurations.The result of successfully developing the Maze game shows that algorithms are critical and effective to develop the game.

关 键 词：迷宫游戏 深度优先遍历 算法设计 回溯法 

分 类 号：S[农业科学]