实验3：基于 A*算法的迷宫游戏开发_a*算法实验

1、 项目概述

1.1 项目目标和主要内容

1. 迷宫游戏是非常经典的游戏，要求随机生成一个迷宫，并求解迷宫。
2. 要求游戏支持玩家走迷宫，和系统走迷宫路径两种模式。玩家走迷宫，通过键盘方向键控制，并在行走路径上留下痕迹；系统走迷宫路径要求基于A*算法实现，输出走迷宫的最优路径并显示。
3. 设计交互友好的游戏图形界面。
4. 要求交互界面友好，程序健壮。

1.2 项目的主要功能

1. 方向键的上下左右键实现四个方向的移动。
2. 迷宫随机生成。
3. 玩家走迷宫，留下足迹。
4. 系统用A*算法寻路，输出走迷宫的最优路径并显示。

2、 项目设计
2.1 项目总体框架
设计思想：
迷宫生成策略：利用深度遍历的思想。访问到一个节点时，搜索这个节点没有被访问过的相邻节点，选择一个继续做同样的操作，直到没有邻节点为止再回溯到上一个访问的节点，并选择另外的邻节点。
选择一个靠近边缘的1作为起点，在它的周围随机找另一个黄色的1（这里的“周围”指的是上下左右4个方向）。找到就把他们联通，并且把两个1之间的0（灰色墙）也变成通路，这里用红色来表示。
直到，找不到周围有黄色的1，就回溯，回到之前的位置，看看周围是否有黄色的1，如果有，就按照2步骤，不断将黄色1变联通，接下来就是不停地重复上面的步骤，找到就联通，找不到就往回走。 在遍历过程中将遍历路径通路节点之间的墙“抹掉”—换成空白的格子，即打通为通路，这样就可形成一个完整的迷宫，如上图。这样遍历一次后任意两点之间都可以找到一条路， 所以迷宫的出口和入口只需要从外围的通路节点任选两个即可。通路以外的格子设为墙。
使用Java进行图形化开发设计。Swing 是 Java 为图形界面应用开发提供的一组工具包，是 Java 基础类的一部分。它包含了构建图形界面（GUI）的各种组件，如: 窗口、标签、按钮、文本框等。

迷宫特点：

1. 通路和障碍物是同宽度的
2. 迷宫的起点到终点肯定是存在一条通路的。
3. 我们把这个迷宫的所有路拉直，就变成为一个无向图。那我们可以转换为无向图的两个顶点之间的通路问题， 图的遍历。
   层次逻辑图：
   

包括系统框架图或层次逻辑图，设计思想等。
2.2 系统详细设计
【1】 模块划分图及描述
在计算机科学中，A*算法作为Dijkstra（迪杰斯特拉）算法的扩展，是一种静态路网中求解最短路径有效的直接搜索方法，因其高效性被广泛应用于寻路及图的遍历中。

【2】 类关系图及描述
Class Position里面封装了A*算法求解求解过程中所需要的参数。
Class Lattice封装了节点的位置信息，还有节点的种类。

【3】 程序流程图及描述
在遍历过程中将遍历路径通路节点之间的墙“抹掉”—换成空白的格子，即打通为通路，这样就可形成一个完整的迷宫，如上图。这样遍历一次后任意两点之间都可以找到一条路， 所以迷宫的出口和入口只需要从外围的通路节点任选两个即可。通路以外的格子设为墙。

【4】 存储结构、内存分配
使用节点类Lattice中一个整形成员变量Flag来记录节点是墙还是通路。
上述内容也可以按照函数或模块划分分别设计。
2.3 关键算法分析
算法 1：private boolean createMaze()
【1】 算法功能
使用A*算法求解出路。
【2】 算法基本思想
重复以下步骤，直到遍历到终点 End：
1、选取当前 open 列表中评价值 F 最小的节点，将这个节点称为 S； 将 S 从 open 列表移除，然后添加 S 到 closed 列表中； 对于与 S 相邻的每一块可移动的相邻节点 T：如果 T 在 closed 列表中，忽略；如果 T 不在 open 列表中，添加它然后计算出它的评价值 F；如果 T 已经在 open 列表中，当我们从 S 到达 T 时，检查是否能得到 更小的 F 值，如果是，更新它的 F 值和它的前继(parent = S)。
【3】 算法空间、时间复杂度分析
时间复杂度O（n），空间复杂度O（n）。

算法 2：drawPath(Graphics g)
【1】 算法功能
在地图上显示出通过A*算法求解出来的路径。
【2】 算法基本思想
从终点开始，通过while循环，依次遍历父节点，对其进行上色。
【3】 算法空间、时间复杂度分析
时间复杂度O（n），空间复杂度O（1）。

算法 3：paintComponent(Graphics g)
【1】 算法功能
建立游戏区，在程序面板上画出一个大的正方形表格。
【2】 算法基本思想
通过对二维成员数组theNextItem的遍历，在游戏区对指定的方块进行上色，从而形成相对应的图形。
【3】 算法空间、时间复杂度分析
时间复杂度O（n*n），空间复杂度O（n）。

2.4 其他
该游戏主要用到了一些OOP的思想。比如定义一个基类base，方块集类继承自base类,其中还有对象的封装，属性。
包括使用了哪些面向对象的知识，以及继承、多态、模板类、STL 等有助于提高代码简洁度和效率的方法说明。
3、 程序运行结果分析

程序运行后，生成一个游戏区域类对象，然后不停地接收用户输入的命令，并进行处理。命令格式自定。游戏开始命令。此命令被转发给游戏区域处理。退出命令。用户可随时退出游戏，不需要转发给游戏区域处理，直接退出程序。方块左移、右移、旋转、下移命令:转发给游戏区域处理。
注意，由于此时游戏区域对象的函数可能会抛出异常表示游戏结束，所以需要捕获这些异常。捕获到异常时说明游戏结東，此时提问用户是退出还是继续游戏，用户要求退出则退出程序，如果要求继续游戏则执行一次“游戏开始命令”即可。
包括、输出显示方式、操作流程、运行时间、运行效果等。
4、 总结
4.1 项目的难点和关键点
迷宫游戏的难点和关键点主要还是A*寻路算法的计算。对于与 S 相邻的每一块可移动的相邻节点 T：如果 T 在 closed 列表中，忽略；如果 T 不在 open 列表中，添加它然后计算出它的评价值 F；如果 T 已经在 open 列表中，当我们从 S 到达 T 时，检查是否能得到 更小的 F 值，如果是，更新它的 F 值和它的前继(parent = S)。
例如，调试方法，程序优化和改进，消息机制，屏幕刷新等方面，以及用什么方法解决了什么问题
4.2 项目的评价
老师提出的需求基本上实现了，但是我的程序界面不够美观。因为第一次做项目，时间上还是很紧的，实现完基本功能后就马不停蹄地去进行下一个项目了。
包括课题本身的评价，还有对自己完成情况的评价，哪些地方不足，为什么，如何改进等。
4.3 心得体会
编码是软件开发过程中最基本、最底层的技艺，然而也是最重要的技艺。任何一个领域的专家都需要花费大量的时间来进行基本技艺的锻炼，木匠需要花费大量的时间来锻炼他们对各种工具的掌握，厨师则需要练习刀工和火候。程序员也是一样的，对我们来说，语言的各种特性必须要了然于胸。而对软件的管理也需要从代码做起。
软件的开发过程就象是一部精密的机器，任何一个环节的变化，都会对其它的环节产生影响。把软件过程按照瀑布的形式进行划分是一种分解的处理思路，但同时我们还应该看到不同活动之间的相互影响。软件开发中的生命周期模型也是一个层次模型，从业务建模一直到软件实现，需要跨越数个层次，同样会出现执行不力的情况，例如，代码设计偏离需求、偏离设计的情况比比皆是。
5、 参考文献
《Java编程从入门到实践》作者：李兴华
《Java编程思想》作者：埃克尔
《Head First Java》作者：Kathy Sierra