a算法演示系统.doc

河北农业大学 本科毕业论文(设计) 题 目： A*算法演示系统 摘要本次课程设计的题目是“A星算法的演示系统”，A*算法在人工智能中是一种典型的启发式搜索算法,这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或在线游戏的BOT的移动计算上。本次课程设计要求能够演示出整个算法的执行过程，能够进行单步演示，动态演示，把算法的执行过程的精髓演示出来。在对算法充分了解的基础上，演示算法的执行过程，就要涉及到图像的绘制，而对于图像的编程，显然高级语言有其开发效率高的特点，java强大的运算和图形展示功能，使图像编程变得更加的简单和直观。本课题基于eclipse的java集成开发环境，设计并实现了A星算法的演示系统，展示A星算法如何进行启发式搜索和寻路的过程。实现了设置起点、设置终点、设置障碍、清除障碍、直接寻路、单步寻路、动态寻路、重新寻路、添加默认障碍这些功能的操作。使用者能够通过自己的要求进行A星算法的演示和使用，本软件充分展示A星算法的执行过程。关键字：A*算法，启发式搜索，javaAbstractThe topic of the course design isA star algorithm demo software, A * algorithm 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 requirs 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 Graph 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 development 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 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，java目录摘要1Abstract2目录31 需求分析41.1 编写目的41.2 背景41.2.1 A*搜索算法介绍41.2.2 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.1 程序逻辑的设计163.3.2 找到link中结点的F值最小的结点203.4.3 响应绘制方块paint的参数与getGraphics( )233.4.4 程序主体界面MyPanel中paint函数做的工作243.4.5 主体界面类做的工作243.3.6 鼠标监听mouseClicked OR mousePressed253.3.7 动态寻路的演示253.3.8 设置起点的工作253.3.9 设置终点的工作253.3.10 找不到路径的提示264 总结275 致谢286 参考资料291 需求分析1.1 编写目的A*算法作为为基本寻路算法常出现在游戏设计中，刚刚接触A*算法，难免初学者会产生迷惑，为了使算法的执行步骤更加的清晰，是算法的思路完整的展现出来，此次课题的要求就是用图形化的方式，一步一步的展现A*算法的执行步骤，使想了解A*算法的人能够更清晰的理解此算法，等真正理解了，就会发现，原来游戏的寻路是这样的，从而也会是学习者有更大的兴趣深入其他算法的学习。1.2 背景1.2.1 A*搜索算法介绍A*在游戏设计中有它很典型的用法，是人工智能在游戏中的代表。 A*算法在人工智能中是一种典型的启发式搜索算法在说启发式搜索之前先提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，两点之间求一线路，这两点是求解的开始和问题的结果，而这一线路不一定是直线，可以是曲折的。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序先查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n)其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) g(n)时，可以省略g(n)，而提高效率。启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。像局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，并没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法，只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：f(n) = 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)=0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。游戏中速度和精确度之间的选择并不是全局的。在地图上的某些区域，精确度是重要的，你可以基于此进行动态选择。例如，假设我们可能在某点停止重新计算路径或者改变方向，则在接近当前位置的地方，选择一条好的路径则是更重要的，因此为何要对后续路径的精确度感到厌烦？或者，对于在地图上的一个安全区域，最短路径也许并不十分重要，但是当从一个敌人的村庄逃跑时，安全和速度是最重要的。所以A星算法应用在游戏中时可以根据具体的情况为各种不同的障碍设置不同的加权值是尽可能的出最有效的方案。1.2.2 Dijkstra算法 图1.1 Dijkstra算法的执行图 Dijkstra算法迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。并没有启发寻路，属于A*算法的特例。这个算法的工作过程就是从起始点开始，不断的向未知点扩展，使从已知点集合到达任意未知点的距离权重都是最小的，这样当扩展到终止点的时候，也就找到了最短的权重。1.2.3 java语言介绍（1）起源Java是由Sun Microsystems公司于 1995年5月推出的Java面向对象程序设计语言（以下简称Java语言）和Java平台的总称。由James Gosling和同事们共同研发，并在1995年正式推出。Java最初被称为Oak，是1991年为消费类电子产品的嵌入式芯片而设计的。1995年更名为Java，并重新设计用于开发Internet应用程序。用Java实现的HotJava浏览器（支持Java applet）显示了Java的魅力：跨平台、动态的Web、Internet计算。从此，Java被广泛接受并推动了Web的迅速发展，常用的浏览器均支持Javaapplet。另一方面，Java技术也不断更新。（2）组成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 之际就将其作为一种开放的技术。全球数以万计的 Java 开发公司被要求所设计的 Java软件必须相互兼容。“Java 语言靠群体的力量而非公司的力量”是Sun公司的口号之一，并获得了广大软件开发商的认同。这与微软公司所倡导的注重精英和封闭式的模式完全不同。Sun 公司对 Java 编程语言的解释是：Java 编程语言是个简单、面向对象、分布式、解释性、健壮、安全与系统无关、可移植、高性能、多线程和动态的语言。Java 平台是基于 Java 语言的平台。这样的平台非常流行。因此微软公司推出了与之竞争的.NET平台以及模仿Java的C#语言。Java是功能完善的通用程序设计语言，可以用来开发可靠的、要求严格的应用程序。（5）语言特征Java编程语言的风格十分接近C语言、C+语言。Java是一个纯粹的面向对象的程序设计语言，它继承了 C+语言面向对象技术的核心。Java舍弃了C语言中容易引起错误的指针（以引用取代）、运算符重载（operator overloading）、多重继承（以接口取代）等特性，增加了垃圾回收器功能用于回收不再被引用的对象所占据的内存空间，使得程序员不用再为内存管理而担忧。在 Java 1.5 版本中，Java 又引入了泛型编程（Generic Programming）、类型安全的枚举、不定长参数和自动装/拆箱等语言特性。Java不同于一般的编译执行计算机语言和解释执行计算机语言。它首先将源代码编译成二进制字节码（bytecode），然后依赖各种不同平台上的虚拟机来解释执行字节码。从而实现了“一次编译、到处执行”的跨平台特性。不过，每次的执行编译后的字节码需要消耗一定的时间，这同时也在一定程度上降低了 Java 程序的性能。（6）主要特性Java语言是易学的。Java语言的语法与C语言和C+语言很接近，使得大多数程序员很容易学习和使用Java。另一方面，Java丢弃了C+中很少使用的、很难理解的、令人迷惑的那些特性，如操作符重载、多继承、自动的强制类型转换。特别地，Java语言不使用指针，而是引用。并提供了自动的废料收集，使得程序员不必为内存管理而担忧。Java语言是强制面向对象的。Java语言提供类、接口和继承等原语，为了简单起见，只支持类之间的单继承，但支持接口之间的多继承，并支持类与接口之间的实现机制（关键字为implements）。Java语言全面支持动态绑定，而C+语言只对虚函数使用动态绑定。总之，Java语言是一个纯的面向对象程序设计语言。Java语言是分布式的。Java语言支持Internet应用的开发，在基本的Java应用编程接口中有一个网络应用编程接口（java net），它提供了用于网络应用编程的类库，包括URL、URLConnection、Socket、ServerSocket等。Java的RMI（远程方法激活）机制也是开发分布式应用的重要手段。Java语言是健壮的。Java的强类型机制、异常处理、垃圾的自动收集等是Java程序健壮性的重要保证。对指针的丢弃是Java的明智选择。Java的安全检查机制使得Java更具健壮性。Java语言是安全的。Java通常被用在网络环境中，为此，Java提供了一个安全机制以防恶意代码的攻击。除了Java语言具有的许多安全特性以外，Java对通过网络下载的类具有一个安全防范机制（类ClassLoader），如分配不同的名字空间以防替代本地的同名类、字节代码检查，并提供安全管理机制（类SecurityManager）让Java应用设置安全哨兵。Java语言是体系结构中立的。Java程序（后缀为java的文件）在Java平台上被编译为体系结构中立的字节码格式（后缀为class的文件），然后可以在实现这个Java平台的任何系统中运行。这种途径适合于异构的网络环境和软件的分发。Java语言是解释型的。如前所述，Java程序在Java平台上被编译为字节码格式，然后可以在实现这个Java平台的任何系统中运行。在运行时，Java平台中的Java解释器对这些字节码进行解释执行，执行过程中需要的类在联接阶段被载入到运行环境中。Java是性能略高的。与那些解释型的高级脚本语言相比，Java的性能还是较优的。Java语言是原生支持多线程的。在Java语言中，线程是一种特殊的对象，它必须由Thread类或其子（孙）类来创建。通常有两种方法来创建线程：其一，使用型构为Thread(Runnable)的构造子将一个实现了Runnable接口的对象包装成一个线程，其二，从Thread类派生出子类并重写run方法，使用该子类创建的对象即为线程。值得注意的是Thread类已经实现了Runnable接口，因此，任何一个线程均有它的run方法，而run方法中包含了线程所要运行的代码。线程的活动由一组方法来控制。Java语言支持多个线程的同时执行，并提供多线程之间的同步机制（关键字为synchronized）。Java语言是动态的。Java语言的设计目标之一是适应于动态变化的环境。Java程序需要的类能够动态地被载入到运行环境，也可以通过网络来载入所需要的类。这也有利于软件的升级。另外，Java中的类有一个运行时刻的表示，能进行运行时刻的类型检查。Java语言的优良特性使得Java应用具有无比的健壮性和可靠性，这也减少了应用系统的维护费用。Java对对象技术的全面支持和Java平台内嵌的API能缩短应用系统的开发时间并降低成本。Java的编译一次，到处可运行的特性使得它能够提供一个随处可用的开放结构和在多平台之间传递信息的低成本方式。特别是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界面：用户与程序之间交互的一个控制面板，其内包含有菜单，控件（或组件），容器并能响应用户的事件。现在有各种各样的窗口系统，不同的窗口系统提供给程序设计的程序库是大不一样的，例如，基于Windows的SDK，和基于Unix平台的X Windows的Xlib。为了使程序能在不同的窗口系统下运行，Java提出了“抽象窗口系统”的概念，提供了AWT（抽象窗口工具箱），使得java能够在不同的窗口系统下运行。2）Java中的GUI实现方式：采用AWT（抽象窗口工具集）从而可使GUI适用于不同OS的环境。特点如下： 其具体实现由目标平台下的OS来解释，从而导致Java GUI在不同平台下会出现不同的运行效果（窗口外观、字体等的显示效果会发生变化）。 组件在设计时不应采用绝对定位，而应采用布局管理器来实现相对定位，以达到与平台及设备无关。3）新增的Swing GUI组件AWT组件以及事件响应不及微软的SDK丰富（因为有些OS平台无微软的Windows组件），Sun在Java2中新增了Swing GUI组件。但是，AWT比较简单，功能也能满足大多数界面需求，特别在Java Applet的设计中受到了普遍的应用。1.3 任务概述本次课程设计的题目是“A星算法的演示系统”，A*算法在人工智能中是一种典型的启发式搜索算法,这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或在线游戏的BOT的移动计算上。本次课程设计要求能够演示出整个算法的执行过程，能够进行单步演示，动态演示，把算法的执行过程的精髓演示出来。实现了设置起点、设置终点、设置障碍、清除障碍、直接寻路、单步寻路、动态寻路、重新寻路、添加默认障碍这些功能的操作。1.4 运行环境规定任何安装java运行环境的系统1：在eclipse中加载该项目，直接打开并运行该项目。2：安装java运行环境的机器中，控制台下，进入bin目录，输入java .java1 3：安装java运行环境的机器中，直接运行已经打包好的axing.jar1.5 其他A星软件的优劣(1)软件一 图1.2 C#完成的A*算法的演示程序这个程序的好处就是实现的功能很全。优点：（1）对于障碍的不同级别，进行了设置，表现在程序上我觉得就是障碍的加权值的不同，而且在实际的执行过程中也可以越过一些障碍。（2）时间的延迟进行了设置，对于程序的演示效果能有更好的展现。（3）方格的大小也进行了设置，可以进行随便的调节，也是为了方便展示。缺点：（1）功能过于复杂，初次拿到软件的人会先进行一段时间的熟悉，不适合激发初学A星算法的人的兴趣。（2）文字说明多，也是其复杂原因的一种，如果用图形化的方式进行更多的说明会事半功倍。(2)软件二图1.3 VC+完成的A*算法的演示程序这个软件演示的很清晰，说明很到位，没有实现动态执行的功能。优点：该有的功能一般都有了，操作起来并不复杂，演示效果很好，图形化的执行很不错。缺点：每次执行都要全屏展示，在我的电脑上如果一旦按WINDOWS键进行其他操作，在打开此程序，发现看不到之前的执行路径了。基于上面的研究成果，我本次使用JAVA语言写的A星算法演示程序，争取尽可能的简单易操作。2 概要设计2.1 界面设计2.1.1 软件的进入界面设计 图2.1 软件的进入界面2.1.2 软件的进入界面的分析（1）一般软件都有自己的进入界面，软件的进入界面能够使软件更富有意义，界面设计是为了满足软件专业化标准化的需求而产生的对软件的使用界面进行美化优化规范化的设计分支。（2）此界面大小长950像素，宽710像素，能够满足大部分计算机的整个屏幕的显示，跟程序的主体界面大小一致。图形的显示位置在x=30，y=10的位置。“AStar算法演示软件”几个字采用70号字，总体加粗。作者和姓名及“进入演示程序”字体采用40号，Font _LAYOUT _NO _LIMIT_CONTEXT号字。（3）整个框架是外面的MyFace 包含FacePanel ，左右图形的绘制通过FacePanel中的paint函数实现。（4）背景是宇宙，有很多的星星，周围放出万丈光芒，宇宙能够给人以无限的想象，此处希望本程序的演示也能给使用者以无限的想象。蓝色的光线是从两边的中心位置依次向上面和下面画线，下面的间距为30个像素，这样的设计能够突出中间文字的显示效果。（5）此处星星的设计和程序的名称有相对应的地方，星星的绘制是通过在界面的区域内随机产生450个三种颜色的点来显示的。（6）当点击“进入程序演示”就会启动一个线程执行显示程序主体界面的程序，同时本界面会隐藏。2.1.3 软件主题界面的设计 图2.2 软件主体界面2.1.4 软件主体界面的分析（1）整个FRAME的大小，长950像素，宽710像素，内包含两个Panel，顶层的Panel包含4个JRadioButton，分别是“设置起点”、“设置终点”、“设置障碍”，“清除障碍”。下面的Panel是自定义的，包含左边的方块区域和右边的说明区域，方块区域的长700像素，宽600像素。（2）小方块的边长为50，整个区域长14个方块，高12个方块。之所以这几这么大小，是因为，这样的大小基本适合13寸以上的电脑能够在整个屏幕内演示，能够满足大部分使用此软件的人员的要求。（3）JRadioButton刚开始默认选定是设置障碍，可以通过点击其他的单选按钮，进行相应的操作。当点击其他的单选按钮后，鼠标对下面方框区域的操作与其对应。（4）右边说明的主题意思是通过方块颜色的不同来区分起始结点，终止结点，CLOSE中的节点，OPEN中的节点等。另外箭头指向启发式寻路过程中的每个节点的前驱。2.2 程序需要实现的功能1：设置起点2：设置终点3：设置障碍4：清除障碍5：直接寻路（点击按钮就显示出最后的寻路结果）6：单步寻路（通过不断的点击按钮，一步一步显示出程序的寻路过程）7：动态寻路8：重新寻路9：添加默认障碍3 详细设计3.1 类图的设计 图3.1 A星算法演示软件的类图3.2 类之间的关系说明（1）继承关系：继承指的是一个类（称为子类、子接口）继承另外的一个类（称为父类、父接口）的功能，并可以增加它自己的新功能的能力。在Java中继承关系通过关键字extends明确标识，在设计时一般没有争议性。在UML类图设计中，继承用一条带空心三角箭头的实线表示，从子类指向父类，或者子接口指向父接口。 （2）实现关系：实现指的是一个class类实现interface接口（可以是多个）的功能，实现是类与接口之间最常见的关系。在Java中此类关系通过关键字implements明确标识，在设计时一般没有争议性。在UML类图设计中，实现用一条带空心三角箭头的虚线表示，从类指向实现的接口。 （3）依赖关系：简单的理解，依赖就是一个类A使用到了另一个类B，而这种使用关系是具有偶然性的、临时性的、非常弱的，但是类B的变化会影响到类A。比如某人要过河，需要借用一条船，此时人与船之间的关系就是依赖。表现在代码层面，为类B作为参数被类A在某个method方法中使用。在UML类图设计中，依赖关系用由类A指向类B的带箭头虚线表示。 （4）关联关系：关联体现的是两个类之间语义级别的一种强依赖关系，比如我和我的朋友，这种关系比依赖更强、不存在依赖关系的偶然性、关系也不是临时性的，一般是长期性的，而且双方的关系一般是平等的。关联可以是单向、双向的。表现在代码层面，为被关联类B以类的属性形式出现在关联类A中，也可能是关联类A引用了一个类型为被关联类B的全局变量。在UML类图设计中，关联关系用由关联类A指向被关联类B的带箭头实线表示，在关联的两端可以标注关联双方的角色和多重性标记。 （5）聚合关系：聚合是关联关系的一种特例，它体现的是整体与部分的关系，即has-a的关系。此时整体与部分之间是可分离的，它们可以具有各自的生命周期，部分可以属于多个整体对象，也可以为多个整体对象共享。比如计算机与CPU、公司与员工的关系等，比如一个航母编队包括海空母舰、驱护舰艇、舰载飞机及核动力攻击潜艇等。表现在代码层面，和关联关系是一致的，只能从语义级别来区分。在UML类图设计中，聚合关系以空心菱形加实线箭头表示。 （6）组合关系：组合也是关联关系的一种特例，它体现的是一种contains-a的关系，这种关系比聚合更强，也称为强聚合。它同样体现整体与部分间的关系，但此时整体与部分是不可分的，整体的生命周期结束也就意味着部分的生命周期结束，比如人和人的大脑。表现在代码层面，和关联关系是一致的，只能从语义级别来区分。在UML类图设计中，组合关系以实心菱形加实线箭头表示。3.3 类图的分析（1）类图(Class diagram)是显示了模型的静态结构，特别是模型中存在的类、类的内部结构以及它们与其他类的关系等，一般在详细设计过程中出现，主要用来描述系统中各个模块中类之间的关系，包括类或者类与接口的继承关系，类之间的依赖、聚合等关系。（2）此次的A*算法演示程序共用到了7个类，此7个类的关系相对比较简单，有依赖关系和聚合关系组成。（3）java1类是程序的入口点，包含程序需的main函数，main函数产生了界面类的对象。进而界面类会调用界面类包含的Panel类的paint函数，绘制出软件的进入界面。（4）软件的进入界面类对应MyFace类，MyFace类包含FacePanel类的对象，此界面的绘图操作是通过FacePanel类的paint函数来绘制的，（见上面的图2.1 软件的进入界面）（5）当点击“进入演示程序”按钮之后，会启动一个线程，此线程会产生MyFrame类的对象。（6）MyFrame类是程序的主题界面显示的类，如图2.2 软件主体界面，此类包含两个Panel，顶层的Panel包含单选按钮和按钮，底层的Panel包含图形的绘制主体方块和说明信息。（7）MyPanel是自己定义的JPanel，它继承自JPanel，这个类主要是画出主体方块区域和现实说明信息。（8）Axing类用来设计整个A星算法，其中包含图形的起始坐标，终止坐标，每走一步的带权值，以及最重要的A星算法的实现代码等。（9）AxingNode类是程序的结点类，它设计了程序的结点，因为A星算法要用到两个链表，链表的结点类型就是AxingNode类型，每个节点都包含自己在方块区域的坐标，G、H、F值，指向前驱的字符串，direct用来指示cameFrom的方向，flag用来标记每个结点的类型，0:起始点 1:障碍 2:目标点 3:其他，还有颜色值。3.4 程序的实现3.4.1 程序逻辑的设计我此处用了两个链表：OpenList 初始化时存放起始结点，用来存放还为探测的结点。CloseList 初始化为空，用来存放已经探测过得结点。整个图的结点用一个AxingNode型数组来存放因为A星算法需要进行启发式寻路，我采用的启发式寻路的方式为当前结点与目标结点的横纵坐标的和作为启发寻路的启发H值，G值为前驱结点到起始结点的权值加上前驱结点到本结点的权值。F=G+H作为总权值。每次比较就是按照F值进行的比较。F = G + HG = 从起点沿着产生的路径，移动到网格上指定方格的移动耗费。H = 从网格上那个方格移动到终点B的预估移动耗费。正如上面所说，G表示沿路径从起点到当前点的移动耗费。在这个例子里，我们令水平或者垂直移动的耗费为10。既然我们在计算沿特定路径通往某个方格的G值，求值的方法就是取它的前驱结点的G值，然后依照它相对前驱结点直角方向(非对角线)，增加和10。例子中这个方法的需求会变得更多，因为我们从起点方格以外获取了不止一个方格。H值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法，它计算从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向。然后把结果乘以10。这被成为曼哈顿方法是因为它看起来像计算城市中从一个地方到另外一个地方的街区数，在那里你不能沿对角线方向穿过街区。很重要的一点，我们忽略了一切障碍物。这是对剩余距离的一个估算，而非实际值，这也是这一方法被称为启发式的原因。F的值是G和H的和。第一步搜索的结果可以在下面的图表中看到。F,G和H的评分被写在每个方格里。正如在紧挨起始格右侧的方格所表示的，F被打印在左上角，G在左下角，H则在右下角。具体算法的寻路思路如下：（1）将从起始点开始，方块添加到open列表中，该列表有最小的和值。且将这个方块称为S吧。（2）将S从open列表移除，然后添加S到closed列表中。（3）对于与S相邻的每一块可通行的方块T：（这里我问题只要有上下左右可以通行）1）如果T为终止结点，则结束。2）如果T在closed列表中：不管它。3）如果T不在open列表中：添加它然后计算出它的和值，并标记S为他的前驱。4）如果T已经在open列表中：当我们使用当前生成的路径到达那里时计算新F值，检查新F 值与原有F值相比是否更小。如果是，更新它的F值和它的前驱。5)继续扫描open列表中拥有最小的F值的结点，记为S，重复（3）/A星算法的具体代码如下public boolean Afun()while(!openList.isEmpty()AxingNode tempNode=openList.get(findMinF(openList);if(tempNode.flag=2)/如果是最后一个结点pathstartxstarty.F=pathendxendy.F;pathstartxstarty.H=pathendxendy.G;return true;/能够到达最后的结点openList.remove(tempNode);closeList.add(tempNode);/另外添加，对于openList,closeList中的结点的颜色进行设置if(tempNode.flag!=0)/如果不是开始结点tempNode.color=Color.cyan;/蓝绿色标志为进入closeList中的结点。/对于刚加入closeList即刚从openList中删除的结点，看其周围的结点LinkedList neighborNodes=new LinkedList();if(tempNode.x0&pathtempNode.x-1tempNode.y.flag!=1&!closeList.contains(pathtempNode.x-1tempNode.y)/左/如果openList 不包含周围的结点，即周围的结点并没有提前在openList中，那么可以更改directif(!openList.contains(pa