a算法演示系统Word文档格式.docx
- 文档编号:1502489
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:36
- 大小:625.51KB
a算法演示系统Word文档格式.docx
《a算法演示系统Word文档格式.docx》由会员分享,可在线阅读,更多相关《a算法演示系统Word文档格式.docx(36页珍藏版)》请在冰点文库上搜索。
1需求分析
1.1编写目的
A*算法作为为基本寻路算法常出现在游戏设计中,刚刚接触A*算法,难免初学者会产生迷惑,为了使算法的执行步骤更加的清晰,是算法的思路完整的展现出来,此次课题的要求就是用图形化的方式,一步一步的展现A*算法的执行步骤,使想了解A*算法的人能够更清晰的理解此算法,等真正理解了,就会发现,原来游戏的寻路是这样的,从而也会是学习者有更大的兴趣深入其他算法的学习。
1.2背景
1.2.1A*搜索算法介绍
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.2Dijkstra算法
图1.1Dijkstra算法的执行图
Dijkstra算法迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法最终得到一个最短路径树。
并没有启发寻路,属于A*算法的特例。
这个算法的工作过程就是从起始点开始,不断的向未知点扩展,使从已知点集合到达任意未知点的距离权重都是最小的,这样当扩展到终止点的时候,也就找到了最短的权重。
1.2.3java语言介绍
(1)起源
Java是由SunMicrosystems公司于1995年5月推出的Java面向对象程序设计语言(以下简称Java语言)和Java平台的总称。
由JamesGosling和同事们共同研发,并在1995年正式推出。
Java最初被称为Oak,是1991年为消费类电子产品的嵌入式芯片而设计的。
1995年更名为Java,并重新设计用于开发Internet应用程序。
用Java实现的HotJava浏览器(支持Javaapplet)显示了Java的魅力:
跨平台、动态的Web、Internet计算。
从此,Java被广泛接受并推动了Web的迅速发展,常用的浏览器均支持Javaapplet。
另一方面,Java技术也不断更新。
(2)组成
Java由四方面组成:
●Java编程语言
●Java文件格式
●Java虚拟机(JVM)
●Java应用程序接口(JavaAPI)
(3)体系
Java分为三个体系JavaSE(J2SE)(Java2PlatformStandardEdition,java平台标准版),JavaEE(J2EE)(Java2Platform,EnterpriseEdition,java平台企业版),JavaME(J2ME)(Java2PlatformMicroEdition,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语言中容易引起错误的指针(以引用取代)、运算符重载(operatoroverloading)、多重继承(以接口取代)等特性,增加了垃圾回收器功能用于回收不再被引用的对象所占据的内存空间,使得程序员不用再为内存管理而担忧。
在Java1.5版本中,Java又引入了泛型编程(GenericProgramming)、类型安全的枚举、不定长参数和自动装/拆箱等语言特性。
Java不同于一般的编译执行计算机语言和解释执行计算机语言。
它首先将源代码编译成二进制字节码(bytecode),然后依赖各种不同平台上的虚拟机来解释执行字节码。
从而实现了“一次编译、到处执行”的跨平台特性。
不过,每次的执行编译后的字节码需要消耗一定的时间,这同时也在一定程度上降低了Java程序的性能。
(6)主要特性
Java语言是易学的。
Java语言的语法与C语言和C++语言很接近,使得大多数程序员很容易学习和使用Java。
另一方面,Java丢弃了C++中很少使用的、很难理解的、令人迷惑的那些特性,如操作符重载、多继承、自动的强制类型转换。
特别地,Java语言不使用指针,而是引用。
并提供了自动的废料收集,使得程序员不必为内存管理而担忧。
Java语言是强制面向对象的。
Java语言提供类、接口和继承等原语,为了简单起见,只支持类之间的单继承,但支持接口之间的多继承,并支持类与接口之间的实现机制(关键字为implements)。
Java语言全面支持动态绑定,而C++语言只对虚函数使用动态绑定。
总之,Java语言是一个纯的面向对象程序设计语言。
Java语言是分布式的。
Java语言支持Internet应用的开发,在基本的Java应用编程接口中有一个网络应用编程接口(javanet),它提供了用于网络应用编程的类库,包括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企业应用编程接口(JavaEnterpriseAPIs)为企业计算及电子商务应用系统提供了有关技术和丰富的类库。
1.2.4java图形化编程的知识
java的GUI编程(GraphicUserInterface,图形用户接口),是在它的抽象窗口工具箱(AbstractWindowToolkit,AWT)上实现的,java.awt是AWT的工具类库,其中包括了丰富的图形、用户界面元件和布局管理器的支持。
GUI主要用在两个地方:
Application;
Applet。
1)GUI界面:
用户与程序之间交互的一个控制面板,其内包含有菜单,控件(或组件),容器并能响应用户的事件。
现在有各种各样的窗口系统,不同的窗口系统提供给程序设计的程序库是大不一样的,例如,基于Windows的SDK,和基于Unix平台的XWindows的Xlib。
为了使程序能在不同的窗口系统下运行,Java提出了“抽象窗口系统”的概念,提供了AWT(抽象窗口工具箱),使得java能够在不同的窗口系统下运行。
2)Java中的GUI实现方式:
采用AWT(抽象窗口工具集)从而可使GUI适用于不同OS的环境。
特点如下:
①其具体实现由目标平台下的OS来解释,从而导致JavaGUI在不同平台下会出现不同的运行效果(窗口外观、字体等的显示效果会发生变化)。
②组件在设计时不应采用绝对定位,而应采用布局管理器来实现相对定位,以达到与平台及设备无关。
3)新增的SwingGUI组件
AWT组件以及事件响应不及微软的SDK丰富(因为有些OS平台无微软的Windows组件),Sun在Java2中新增了SwingGUI组件。
但是,AWT比较简单,功能也能满足大多数界面需求,特别在JavaApplet的设计中受到了普遍的应用。
1.3任务概述
1.4运行环境规定
任何安装java运行环境的系统
1:
在eclipse中加载该项目,直接打开并运行该项目。
2:
安装java运行环境的机器中,控制台下,进入bin目录,输入java.java13:
安装java运行环境的机器中,直接运行已经打包好的axing.jar
1.5其他A星软件的优劣
(1)软件一
图1.2C#完成的A*算法的演示程序
这个程序的好处就是实现的功能很全。
优点:
(1)对于障碍的不同级别,进行了设置,表现在程序上我觉得就是障碍的加权值的不同,而且在实际的执行过程中也可以越过一些障碍。
(2)时间的延迟进行了设置,对于程序的演示效果能有更好的展现。
(3)方格的大小也进行了设置,可以进行随便的调节,也是为了方便展示。
缺点:
(1)功能过于复杂,初次拿到软件的人会先进行一段时间的熟悉,不适合激发初学A星算法的人的兴趣。
(2)文字说明多,也是其复杂原因的一种,如果用图形化的方式进行更多的说明会事半功倍。
(2)软件二
图1.3VC++完成的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寸以上的电脑能够在整个屏幕内演示,能够满足大部分使用此软件的人员的要求。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 演示 系统