1、本科毕业论文（20 届）A*算法演示系统的设计与实现所在学院专业班级 计算机科学与技术学生姓名指导教师完成日期1摘要本次课程设计的题目是“A 星算法的演示系统”，A*算法在人工智能中是一种典型的启发式搜索算法,这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的 NPC 的移动计算，或在线游戏的 BOT 的移动计算上。本次课程设计要求能够演示出整个算法的执行过程，能够进行单步演示，动态演示，把算法的执行过程的精髓演示出来。在对算法充分了解的基础上，演示算法的执行过程，就要涉及到图像的绘制，而对于图像的编程，显然高级语言有其开发效率高的特点，java 强大的运算和图形展
2、示功能，使图像编程变得更加的简单和直观。本课题基于 eclipse 的 java 集成开发环境，设计并实现了 A 星算法的演示系统，展示 A 星算法如何进行启发式搜索和寻路的过程。实现了设置起点、设置终点、设置障碍、清除障碍、直接寻路、单步寻路、动态寻路、重新寻路、添加默认障碍这些功能的操作。使用者能够通过自己的要求进行 A 星算法的演示和使用，本软件充分展示 A 星算法的执行过程。关键字：A*算法，启发式搜索，java2AbstractThe topic of the course design is“A star algorithm demo software“, A * algorith
3、m in artificial intelligence is A kind of typical heuristic search algorithm, this is A graphics in the plane ,have more than one node path, the algorithm of minimum through cost.it often be used in the game of mobile computing of NPC, or online games on mobile computing of BOT.The course design req
4、uirs to demonstrate the implementation process of the whole algorithm, can be single step demo, dynamic demonstration, the essence of the execution process of algorithm demo.on the basis of full understanding of the algorithm, Demonstrateing the algorithm implementation process will involve the Grap
5、h drawing, and the programming on image, obviously a high-level language has the characteristics of its development of high efficiency, Java powerful computing and graphics display function, make the image programming more simple and intuitive.This project is based on eclipses Java integrated develo
6、pment environment, A star algorithm demo software was designed and implemented, showing how A star algorithm of heuristic search and pathfinding.Implements set the starting point and end point, barriers, clear obstacles, directly pathfinding, single step pathfinding, dynamic pathfinding, pathfinding
7、 again, add default barrier function of these operations.the user can use the software according to their requirments, the software fully shows the execution of A star algorithm.Keywords：AStar arithmetic ，heuristic search，java3目录摘要 .1Abstract.2目录 .31 需求分析 .41.1 编写目的 .41.2 背景 .41.2.1 A*搜索算法介绍 .41.2.2
8、 Dijkstra 算法 .51.2.3 java 语言介绍 .61.2.4 java 图形化编程的知识 .81.3 任务概述 .81.4 运行环境规定 .91.5 其他 A 星软件的优劣 .9(1)软件一 .9(2)软件二 .102 概要设计 .112.1 界面设计 .112.1.1 软件的进入界面设计 .112.1.2 软件的进入界面的分析 .112.1.3 软件主题界面的设计 .122.1.4 软件主体界面的分析 .122.2 程序需要实现的功能 .133 详细设计 .143.1 类图的设计 .143.2 类之间的关系说明 .143.3 类图的分析 .153.4 程序的实现 .163.4
9、.1 程序逻辑的设计 .163.3.2 找到 link 中结点的 F 值最小的结点 .203.4.3 响应绘制方块 paint 的参数与 getGraphics( ) .233.4.4 程序主体界面 MyPanel 中 paint 函数做的工作 .243.4.5 主体界面类做的工作 .243.3.6 鼠标监听 mouseClicked OR mousePressed .253.3.7 动态寻路的演示 .253.3.8 设置起点的工作 .253.3.9 设置终点的工作 .253.3.10 找不到路径的提示 .264 总结 .275 致谢 .286 参考资料 .2941 需求分析1.1 编写目的A
10、*算法作为为基本寻路算法常出现在游戏设计中，刚刚接触 A*算法，难免初学者会产生迷惑，为了使算法的执行步骤更加的清晰，是算法的思路完整的展现出来，此次课题的要求就是用图形化的方式，一步一步的展现 A*算法的执行步骤，使想了解 A*算法的人能够更清晰的理解此算法，等真正理解了，就会发现，原来游戏的寻路是这样的，从而也会是学习者有更大的兴趣深入其他算法的学习。1.2 背景1.2.1 A*搜索算法介绍A*在游戏设计中有它很典型的用法，是人工智能在游戏中的代表。 A*算法在人工智能中是一种典型的启发式搜索算法在说启发式搜索之前先提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从
11、初始状态到目标状态寻找这个路径的过程。通俗点说，两点之间求一线路，这两点是求解的开始和问题的结果，而这一线路不一定是直线，可以是曲折的。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序先查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更
12、详细的解释。前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n)其中 f(n) 是节点 n 的估价函数，g(n)是在状态
13、空间中从初始节点到 n 节点的实际代价，h(n)是从 n 到目标节点最佳路径的估计代价。在这里主要是 h(n)体现了搜索的启发信息，因为 g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) g(n)时，可以省略 g(n)，而提高效率。启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。像5局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解
14、的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，并没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么 A*算法又是一种什么样的算法呢？其实 A*算法也是一种最好优先的算法，只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：f(n)
15、 = g(n) + h(n)这里，f(n)是估价函数，g(n)是起点到节点 n 的最短路径值，h(n)是 n 到目标的最短路经的启发值。举一个例子，其实广度优先算法就是 A*算法的特例。其中 g(n)是节点所在的层数，h(n)=0，这种 h(n)肯定小于 h(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的 A*算法。再说一个问题，就是有关 h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的 h(n)=
16、0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小 h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。游戏中速度和精确度之间的选择并不是全局的。在地图上的某些区域，精确度是重要的，你可以基于此进行动态选择。例如，假设我们可能在某点停止重新计算路径或者改变方向，则在接近当前位置的地方，选择一条好的路径则是更重要的，因此为何要对后续路径的精确度感到厌烦？或者，对于在地图上的一个安全区域，最短路径也许并不十分重要，但是当从一个敌人的村庄逃跑时，安全和速度是最重要的。所以 A 星算法应用在游戏中时
17、可以根据具体的情况为各种不同的障碍设置不同的加权值是尽可能的出最有效的方案。1.2.2 Dijkstra 算法图 1.1 Dijkstra 算法的执行图6Dijkstra 算法迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。并没有启发寻路，属于 A*算法的特例。这个算法的工作过程就是从起始点开始，不断的向未知点扩展，使从已知点集合到达任意未知点的距离权重都是最小的，这样当扩展到终止点的时候，也就找到了最短的权重。1.2.3 java 语言介绍（1）起源Java 是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 面
18、向对象程序设计语言（以下简称 Java 语言）和 Java 平台的总称。由 James Gosling 和同事们共同研发，并在 1995 年正式推出。Java 最初被称为 Oak，是 1991 年为消费类电子产品的嵌入式芯片而设计的。1995 年更名为 Java，并重新设计用于开发 Internet 应用程序。用 Java 实现的 HotJava 浏览器（支持 Java applet）显示了 Java 的魅力：跨平台、动态的Web、Internet 计算。从此，Java 被广泛接受并推动了 Web 的迅速发展，常用的浏览器均支持 Javaapplet。另一方面，Java 技术也不断更新。（2）
19、组成Java 由四方面组成：Java 编程语言Java 文件格式Java 虚拟机(JVM)Java 应用程序接口( Java API)（3）体系Java 分为三个体系 JavaSE（J2SE）（Java2 Platform Standard Edition，java 平台标准版），JavaEE(J2EE)(Java 2 Platform,Enterprise Edition，java 平台企业版)，JavaME(J2ME)(Java 2 Platform Micro Edition，java 平台微型版)。（4）优势与传统程序不同，Sun 公司在推出 Java 之际就将其作为一种开放的技术。全
20、球数以万计的 Java 开发公司被要求所设计的 Java 软件必须相互兼容。“Java 语言靠群体的力量而非公司的力量”是 Sun 公司的口号之一，并获得了广大软件开发商的认同。这与微软公司所倡导的注重精英和封闭式的模式完全不同。Sun 公司对 Java 编程语言的解释是：Java 编程语言是个简单、面向对象、分布式、解释性、健壮、安全与系统无关、可移植、高性能、多线程和动态的语言。Java 平台是基于 Java 语言的平台。这样的平台非常流行。因此微软公司推出了与之竞争的.NET 平台以及模仿 Java 的 C#语言。Java 是功能完善的通用程序设计语言，可以用来开发可靠的、要求严格的应用
21、程序。（5）语言特征Java 编程语言的风格十分接近 C 语言、C+语言。Java 是一个纯粹的面向对象的程序设计语言，它继承了 C+语言面向对象技术的核心。Java 舍弃了 C 语言中容易引起错误的指针（以引用取代）、运算符重载（operator overloading）、多重继承（以接口取7代）等特性，增加了垃圾回收器功能用于回收不再被引用的对象所占据的内存空间，使得程序员不用再为内存管理而担忧。在 Java 1.5 版本中，Java 又引入了泛型编程（Generic Programming）、类型安全的枚举、不定长参数和自动装/拆箱等语言特性。Java 不同于一般的编译执行计算机语言和解
22、释执行计算机语言。它首先将源代码编译成二进制字节码（bytecode），然后依赖各种不同平台上的虚拟机来解释执行字节码。从而实现了“一次编译、到处执行”的跨平台特性。不过，每次的执行编译后的字节码需要消耗一定的时间，这同时也在一定程度上降低了 Java 程序的性能。（6）主要特性Java 语言是易学的。Java 语言的语法与 C 语言和 C+语言很接近，使得大多数程序员很容易学习和使用 Java。另一方面，Java 丢弃了 C+中很少使用的、很难理解的、令人迷惑的那些特性，如操作符重载、多继承、自动的强制类型转换。特别地，Java 语言不使用指针，而是引用。并提供了自动的废料收集，使得程序员不
23、必为内存管理而担忧。Java 语言是强制面向对象的。Java 语言提供类、接口和继承等原语，为了简单起见，只支持类之间的单继承，但支持接口之间的多继承，并支持类与接口之间的实现机制（关键字为 implements）。Java 语言全面支持动态绑定，而 C+语言只对虚函数使用动态绑定。总之，Java 语言是一个纯的面向对象程序设计语言。Java 语言是分布式的。Java 语言支持 Internet 应用的开发，在基本的 Java 应用编程接口中有一个网络应用编程接口（java net），它提供了用于网络应用编程的类库，包括 URL、URLConnection、Socket、ServerSocke
24、t 等。Java 的 RMI（远程方法激活）机制也是开发分布式应用的重要手段。Java 语言是健壮的。Java 的强类型机制、异常处理、垃圾的自动收集等是 Java 程序健壮性的重要保证。对指针的丢弃是 Java 的明智选择。Java 的安全检查机制使得 Java更具健壮性。Java 语言是安全的。Java 通常被用在网络环境中，为此，Java 提供了一个安全机制以防恶意代码的攻击。除了 Java 语言具有的许多安全特性以外，Java 对通过网络下载的类具有一个安全防范机制（类 ClassLoader），如分配不同的名字空间以防替代本地的同名类、字节代码检查，并提供安全管理机制（类 Secur
25、ityManager）让 Java 应用设置安全哨兵。Java 语言是体系结构中立的。Java 程序（后缀为 java 的文件）在 Java 平台上被编译为体系结构中立的字节码格式（后缀为 class 的文件），然后可以在实现这个 Java 平台的任何系统中运行。这种途径适合于异构的网络环境和软件的分发。Java 语言是解释型的。如前所述，Java 程序在 Java 平台上被编译为字节码格式，然后可以在实现这个 Java 平台的任何系统中运行。在运行时，Java 平台中的 Java 解释器对这些字节码进行解释执行，执行过程中需要的类在联接阶段被载入到运行环境中。Java 是性能略高的。与那些解
26、释型的高级脚本语言相比，Java 的性能还是较优的。Java 语言是原生支持多线程的。在 Java 语言中，线程是一种特殊的对象，它必须由Thread 类或其子（孙）类来创建。通常有两种方法来创建线程：其一，使用型构为Thread(Runnable)的构造子将一个实现了 Runnable 接口的对象包装成一个线程，其二，从 Thread 类派生出子类并重写 run 方法，使用该子类创建的对象即为线程。值得注意的8是 Thread 类已经实现了 Runnable 接口，因此，任何一个线程均有它的 run 方法，而 run方法中包含了线程所要运行的代码。线程的活动由一组方法来控制。Java 语言支
27、持多个线程的同时执行，并提供多线程之间的同步机制（关键字为 synchronized）。Java 语言是动态的。Java 语言的设计目标之一是适应于动态变化的环境。Java 程序需要的类能够动态地被载入到运行环境，也可以通过网络来载入所需要的类。这也有利于软件的升级。另外，Java 中的类有一个运行时刻的表示，能进行运行时刻的类型检查。Java 语言的优良特性使得 Java 应用具有无比的健壮性和可靠性，这也减少了应用系统的维护费用。Java 对对象技术的全面支持和 Java 平台内嵌的 API 能缩短应用系统的开发时间并降低成本。Java 的编译一次，到处可运行的特性使得它能够提供一个随处可
28、用的开放结构和在多平台之间传递信息的低成本方式。特别是 Java 企业应用编程接口（Java Enterprise APIs）为企业计算及电子商务应用系统提供了有关技术和丰富的类库。1.2.4 java 图形化编程的知识java 的 GUI 编程（Graphic User Interface，图形用户接口），是在它的抽象窗口工具箱（Abstract Window Toolkit，AWT）上实现的，java.awt 是 AWT 的工具类库，其中包括了丰富的图形、用户界面元件和布局管理器的支持。GUI 主要用在两个地方：Application；Applet。1）GUI 界面：用户与程序之间交互的一
29、个控制面板，其内包含有菜单，控件（或组件），容器并能响应用户的事件。现在有各种各样的窗口系统，不同的窗口系统提供给程序设计的程序库是大不一样的，例如，基于 Windows 的 SDK，和基于 Unix 平台的 X Windows 的 Xlib。为了使程序能在不同的窗口系统下运行，Java 提出了“抽象窗口系统”的概念，提供了 AWT（抽象窗口工具箱），使得 java 能够在不同的窗口系统下运行。2）Java 中的 GUI 实现方式：采用 AWT（抽象窗口工具集）从而可使 GUI 适用于不同 OS 的环境。特点如下： 其具体实现由目标平台下的 OS 来解释，从而导致 Java GUI 在不同平台
30、下会出现不同的运行效果（窗口外观、字体等的显示效果会发生变化）。 组件在设计时不应采用绝对定位，而应采用布局管理器来实现相对定位，以达到与平台及设备无关。3）新增的 Swing GUI 组件AWT 组件以及事件响应不及微软的 SDK 丰富（因为有些 OS 平台无微软的 Windows 组件），Sun 在 Java2 中新增了 Swing GUI 组件。但是，AWT 比较简单，功能也能满足大多数界面需求，特别在 Java Applet 的设计中受到了普遍的应用。91.3 任务概述本次课程设计的题目是“A 星算法的演示系统”，A*算法在人工智能中是一种典型的启发式搜索算法,这是一种在图形平面上，有
31、多个节点的路径，求出最低通过成本的算法。常用于游戏中的 NPC 的移动计算，或在线游戏的 BOT 的移动计算上。本次课程设计要求能够演示出整个算法的执行过程，能够进行单步演示，动态演示，把算法的执行过程的精髓演示出来。实现了设置起点、设置终点、设置障碍、清除障碍、直接寻路、单步寻路、动态寻路、重新寻路、添加默认障碍这些功能的操作。1.4 运行环境规定任何安装 java 运行环境的系统1：在 eclipse 中加载该项目，直接打开并运行该项目。2：安装 java 运行环境的机器中，控制台下，进入 bin 目录，输入 java .java1 3：安装 java 运行环境的机器中，直接运行已经打包好的 axing.jar1.5 其他 A 星软件的优劣(1)软件一 图 1.2 C#完成的 A*算法的演示程序这个程序的好处就是实现的功能很全。优点：
