軟件工程畢業(yè)論文-a算法演示系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

1、<p><b>　　本科畢業(yè)論文</b></p><p><b>　?。?0 屆）</b></p><p>　　A*算法演示系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)</p><p><b>　　摘要</b></p><p>　　本次課程設(shè)計(jì)的題目是“A星算法的演示系統(tǒng)”，A*算法在人工智能

2、中是一種典型的啟發(fā)式搜索算法,這是一種在圖形平面上，有多個(gè)節(jié)點(diǎn)的路徑，求出最低通過(guò)成本的算法。常用于游戲中的NPC的移動(dòng)計(jì)算，或在線游戲的BOT的移動(dòng)計(jì)算上。本次課程設(shè)計(jì)要求能夠演示出整個(gè)算法的執(zhí)行過(guò)程，能夠進(jìn)行單步演示，動(dòng)態(tài)演示，把算法的執(zhí)行過(guò)程的精髓演示出來(lái)。</p><p>　　在對(duì)算法充分了解的基礎(chǔ)上，演示算法的執(zhí)行過(guò)程，就要涉及到圖像的繪制，而對(duì)于圖像的編程，顯然高級(jí)語(yǔ)言有其開發(fā)效率高的特點(diǎn)，java強(qiáng)

3、大的運(yùn)算和圖形展示功能，使圖像編程變得更加的簡(jiǎn)單和直觀。本課題基于eclipse的java集成開發(fā)環(huán)境，設(shè)計(jì)并實(shí)現(xiàn)了A星算法的演示系統(tǒng)，展示A星算法如何進(jìn)行啟發(fā)式搜索和尋路的過(guò)程。實(shí)現(xiàn)了設(shè)置起點(diǎn)、設(shè)置終點(diǎn)、設(shè)置障礙、清除障礙、直接尋路、單步尋路、動(dòng)態(tài)尋路、重新尋路、添加默認(rèn)障礙這些功能的操作。使用者能夠通過(guò)自己的要求進(jìn)行A星算法的演示和使用，本軟件充分展示A星算法的執(zhí)行過(guò)程。</p><p>　　關(guān)鍵字：A*算法

4、，啟發(fā)式搜索，java</p><p><b>　　Abstract</b></p><p>　　The topic of the course design is"A star algorithm demo software", A * algorithm in artificial intelligence is A kind of typic

5、al 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 compu

6、ting of BOT.The course design requirs to demonstrate the implementation process of the whole algorithm, can be single step demo, dynamic demonstration, th</p><p>　　on the basis of full understanding of the a

7、lgorithm, 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, J

8、ava powerful computing and graphics display function, make the image programming more simple and intuitive.This project is based on eclipse's Java integrated development environment, A star algorithm demo software wa

9、s designed and implem</p><p>　　Keywords：AStar arithmetic ，heuristic search，java</p><p><b>　　目錄</b></p><p><b>　　摘要1</b></p><p>　　Abstract2</

10、p><p><b>　　目錄3</b></p><p><b>　　1 需求分析4</b></p><p>　　1.1 編寫目的4</p><p><b>　　1.2 背景4</b></p><p>　　1.2.1 A*搜索算法介紹4</p&

11、gt;<p>　　1.2.2 Dijkstra算法5</p><p>　　1.2.3 java語(yǔ)言介紹6</p><p>　　1.2.4 java圖形化編程的知識(shí)8</p><p>　　1.3 任務(wù)概述8</p><p>　　1.4 運(yùn)行環(huán)境規(guī)定9</p><p>　　1.5 其他A星軟件的優(yōu)劣

12、9</p><p><b>　　(1)軟件一9</b></p><p><b>　　(2)軟件二10</b></p><p><b>　　2 概要設(shè)計(jì)11</b></p><p>　　2.1 界面設(shè)計(jì)11</p><p>　　2.1.1 軟件的

13、進(jìn)入界面設(shè)計(jì)11</p><p>　　2.1.2 軟件的進(jìn)入界面的分析11</p><p>　　2.1.3 軟件主題界面的設(shè)計(jì)12</p><p>　　2.1.4 軟件主體界面的分析12</p><p>　　2.2 程序需要實(shí)現(xiàn)的功能13</p><p><b>　　3 詳細(xì)設(shè)計(jì)14</b&

14、gt;</p><p>　　3.1 類圖的設(shè)計(jì)14</p><p>　　3.2 類之間的關(guān)系說(shuō)明14</p><p>　　3.3 類圖的分析15</p><p>　　3.4 程序的實(shí)現(xiàn)16</p><p>　　3.4.1 程序邏輯的設(shè)計(jì)16</p><p>　　3.3.2 找到link

15、中結(jié)點(diǎn)的F值最小的結(jié)點(diǎn)20</p><p>　　3.4.3 響應(yīng)繪制方塊paint的參數(shù)與getGraphics( )23</p><p>　　3.4.4 程序主體界面MyPanel中paint函數(shù)做的工作24</p><p>　　3.4.5 主體界面類做的工作24</p><p>　　3.3.6 鼠標(biāo)監(jiān)聽mouseClicked O

16、R mousePressed25</p><p>　　3.3.7 動(dòng)態(tài)尋路的演示25</p><p>　　3.3.8 設(shè)置起點(diǎn)的工作25</p><p>　　3.3.9 設(shè)置終點(diǎn)的工作25</p><p>　　3.3.10 找不到路徑的提示26</p><p><b>　　4 總結(jié)27</b

17、></p><p><b>　　5 致謝28</b></p><p><b>　　6 參考資料29</b></p><p><b>　　1 需求分析</b></p><p><b>　　1.1 編寫目的</b></p><p&

18、gt;　　A*算法作為為基本尋路算法常出現(xiàn)在游戲設(shè)計(jì)中，剛剛接觸A*算法，難免初學(xué)者會(huì)產(chǎn)生迷惑，為了使算法的執(zhí)行步驟更加的清晰，是算法的思路完整的展現(xiàn)出來(lái)，此次課題的要求就是用圖形化的方式，一步一步的展現(xiàn)A*算法的執(zhí)行步驟，使想了解A*算法的人能夠更清晰的理解此算法，等真正理解了，就會(huì)發(fā)現(xiàn)，原來(lái)游戲的尋路是這樣的，從而也會(huì)是學(xué)習(xí)者有更大的興趣深入其他算法的學(xué)習(xí)。</p><p><b>　　1.2 背景

19、</b></p><p>　　1.2.1 A*搜索算法介紹</p><p>　　A*在游戲設(shè)計(jì)中有它很典型的用法，是人工智能在游戲中的代表。 A*算法在人工智能中是一種典型的啟發(fā)式搜索算法</p><p>　　在說(shuō)啟發(fā)式搜索之前先提狀態(tài)空間搜索。狀態(tài)空間搜索，如果按專業(yè)點(diǎn)的說(shuō)法就是將問(wèn)題求解過(guò)程表現(xiàn)為從初始狀態(tài)到目標(biāo)狀態(tài)尋找這個(gè)路徑的過(guò)程。通俗點(diǎn)說(shuō)，兩點(diǎn)

20、之間求一線路，這兩點(diǎn)是求解的開始和問(wèn)題的結(jié)果，而這一線路不一定是直線，可以是曲折的。由于求解問(wèn)題的過(guò)程中分枝有很多，主要是求解過(guò)程中求解條件的不確定性，不完備性造成的，使得求解的路徑很多這就構(gòu)成了一個(gè)圖，我們說(shuō)這個(gè)圖就是狀態(tài)空間。問(wèn)題的求解實(shí)際上就是在這個(gè)圖中找到一條路徑可以從開始到結(jié)果。這個(gè)尋找的過(guò)程就是狀態(tài)空間搜索。</p><p>　　常用的狀態(tài)空間搜索有深度優(yōu)先和廣度優(yōu)先。廣度優(yōu)先是從初始狀態(tài)一層一層向下

21、找，直到找到目標(biāo)為止。深度優(yōu)先是按照一定的順序先查找完一個(gè)分支，再查找另一個(gè)分支，以至找到目標(biāo)為止。這兩種算法在數(shù)據(jù)結(jié)構(gòu)書中都有描述，可以參看這些書得到更詳細(xì)的解釋。</p><p>　　前面說(shuō)的廣度和深度優(yōu)先搜索有一個(gè)很大的缺陷就是他們都是在一個(gè)給定的狀態(tài)空間中窮舉。這在狀態(tài)空間不大的情況下是很合適的算法，可是當(dāng)狀態(tài)空間十分大，且不預(yù)測(cè)的情況下就不可取了。他的效率實(shí)在太低，甚至不可完成。在這里就要用到啟發(fā)式搜索

22、了。 </p><p>　　啟發(fā)式搜索就是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無(wú)謂的搜索路徑，提高了效率。在啟發(fā)式搜索中，對(duì)位置的估價(jià)是十分重要的。采用了不同的估價(jià)可以有不同的效果。</p><p>　　啟發(fā)中的估價(jià)是用估價(jià)函數(shù)表示的，如：f(n) = g(n) + h(n)</p><p

23、>　　其中f(n) 是節(jié)點(diǎn)n的估價(jià)函數(shù)，g(n)是在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，h(n)是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。在這里主要是h(n)體現(xiàn)了搜索的啟發(fā)信息，因?yàn)間(n)是已知的。如果說(shuō)詳細(xì)點(diǎn)，g(n)代表了搜索的廣度的優(yōu)先趨勢(shì)。但是當(dāng)h(n) >> g(n)時(shí)，可以省略g(n)，而提高效率。</p><p>　　啟發(fā)式搜索其實(shí)有很多的算法，比如：局部擇優(yōu)搜索法、最好優(yōu)先搜索

24、法等等。當(dāng)然A*也是。這些算法都使用了啟發(fā)函數(shù)，但在具體的選取最佳搜索節(jié)點(diǎn)時(shí)的策略不同。像局部擇優(yōu)搜索法，就是在搜索的過(guò)程中選取“最佳節(jié)點(diǎn)”后舍棄其他的兄弟節(jié)點(diǎn)，父親節(jié)點(diǎn)，而一直得搜索下去。這種搜索的結(jié)果很明顯，由于舍棄了其他的節(jié)點(diǎn)，可能也把最好的節(jié)點(diǎn)都舍棄了，因?yàn)榍蠼獾淖罴压?jié)點(diǎn)只是在該階段的最佳并不一定是全局的最佳。最好優(yōu)先就聰明多了，他在搜索時(shí)，并沒(méi)有舍棄節(jié)點(diǎn)（除非該節(jié)點(diǎn)是死節(jié)點(diǎn)），在每一步的估價(jià)中都把當(dāng)前的節(jié)點(diǎn)和以前的節(jié)點(diǎn)的估價(jià)值

25、比較得到一個(gè)“最佳的節(jié)點(diǎn)”。這樣可以有效的防止“最佳節(jié)點(diǎn)”的丟失。那么A*算法又是一種什么樣的算法呢？</p><p>　　其實(shí)A*算法也是一種最好優(yōu)先的算法，只不過(guò)要加上一些約束條件罷了。由于在一些問(wèn)題求解時(shí)，我們希望能夠求解出狀態(tài)空間搜索的最短路徑，也就是用最快的方法求解問(wèn)題，A*就是干這種事情的！</p><p>　　我們先下個(gè)定義，如果一個(gè)估價(jià)函數(shù)可以找出最短的路徑，我們稱之為可采

26、納性。A*算法是一個(gè)可采納的最好優(yōu)先算法。A*算法的估價(jià)函數(shù)可表示為：</p><p>　　f'(n) = g'(n) + h'(n)</p><p>　　這里，f'(n)是估價(jià)函數(shù)，g'(n)是起點(diǎn)到節(jié)點(diǎn)n的最短路徑值，h'(n)是n到目標(biāo)的最短路經(jīng)的啟發(fā)值。舉一個(gè)例子，其實(shí)廣度優(yōu)先算法就是A*算法的特例。其中g(shù)(n)是節(jié)點(diǎn)所在的層數(shù)，h(

27、n)=0，這種h(n)肯定小于h'(n)，所以由前述可知廣度優(yōu)先算法是一種可采納的。實(shí)際也是。當(dāng)然它是一種最臭的A*算法。</p><p>　　再說(shuō)一個(gè)問(wèn)題，就是有關(guān)h(n)啟發(fā)函數(shù)的信息性。h(n)的信息性通俗點(diǎn)說(shuō)其實(shí)就是在估計(jì)一個(gè)節(jié)點(diǎn)的值時(shí)的約束條件，如果信息越多或約束條件越多則排除的節(jié)點(diǎn)就越多，估價(jià)函數(shù)越好或說(shuō)這個(gè)算法越好。這就是為什么廣度優(yōu)先算法的那么臭的原因了，誰(shuí)叫它的h(n)=0，一點(diǎn)啟發(fā)信息

28、都沒(méi)有。但在游戲開發(fā)中由于實(shí)時(shí)性的問(wèn)題，h(n)的信息越多，它的計(jì)算量就越大，耗費(fèi)的時(shí)間就越多。就應(yīng)該適當(dāng)?shù)臏p小h(n)的信息，即減小約束條件。但算法的準(zhǔn)確性就差了，這里就有一個(gè)平衡的問(wèn)題。</p><p>　　游戲中速度和精確度之間的選擇并不是全局的。在地圖上的某些區(qū)域，精確度是重要的，你可以基于此進(jìn)行動(dòng)態(tài)選擇。例如，假設(shè)我們可能在某點(diǎn)停止重新計(jì)算路徑或者改變方向，則在接近當(dāng)前位置的地方，選擇一條好的路徑則是更

29、重要的，因此為何要對(duì)后續(xù)路徑的精確度感到厭煩？或者，對(duì)于在地圖上的一個(gè)安全區(qū)域，最短路徑也許并不十分重要，但是當(dāng)從一個(gè)敵人的村莊逃跑時(shí)，安全和速度是最重要的。所以A星算法應(yīng)用在游戲中時(shí)可以根據(jù)具體的情況為各種不同的障礙設(shè)置不同的加權(quán)值是盡可能的出最有效的方案。</p><p>　　1.2.2 Dijkstra算法</p><p>　　圖1.1 Dijkstra算法的執(zhí)行圖</p>

30、;<p>　　Dijkstra算法迪科斯徹算法使用了廣度優(yōu)先搜索解決非負(fù)權(quán)有向圖的單源最短路徑問(wèn)題，算法最終得到一個(gè)最短路徑樹。并沒(méi)有啟發(fā)尋路，屬于A*算法的特例。這個(gè)算法的工作過(guò)程就是從起始點(diǎn)開始，不斷的向未知點(diǎn)擴(kuò)展，使從已知點(diǎn)集合到達(dá)任意未知點(diǎn)的距離權(quán)重都是最小的，這樣當(dāng)擴(kuò)展到終止點(diǎn)的時(shí)候，也就找到了最短的權(quán)重。</p><p>　　1.2.3 java語(yǔ)言介紹</p><p

31、><b>　?。?）起源</b></p><p>　　Java是由Sun Microsystems公司于 1995年5月推出的Java面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言（以下簡(jiǎn)稱Java語(yǔ)言）和Java平臺(tái)的總稱。由James Gosling和同事們共同研發(fā)，并在1995年正式推出。Java最初被稱為Oak，是1991年為消費(fèi)類電子產(chǎn)品的嵌入式芯片而設(shè)計(jì)的。1995年更名為Java，并重新設(shè)計(jì)用于開

32、發(fā)Internet應(yīng)用程序。用Java實(shí)現(xiàn)的HotJava瀏覽器（支持Java applet）顯示了Java的魅力：跨平臺(tái)、動(dòng)態(tài)的Web、Internet計(jì)算。從此，Java被廣泛接受并推動(dòng)了Web的迅速發(fā)展，常用的瀏覽器均支持Javaapplet。另一方面，Java技術(shù)也不斷更新。</p><p><b>　?。?）組成</b></p><p>　　Java由四方面

33、組成：</p><p><b>　　●Java編程語(yǔ)言</b></p><p><b>　　●Java文件格式</b></p><p>　　●Java虛擬機(jī)(JVM)</p><p>　　●Java應(yīng)用程序接口(Java API)</p><p><b>　?。?）

34、體系</b></p><p>　　Java分為三個(gè)體系JavaSE（J2SE）（Java2 Platform Standard Edition，java平臺(tái)標(biāo)準(zhǔn)版），JavaEE(J2EE)(Java 2 Platform,Enterprise Edition，java平臺(tái)企業(yè)版)，JavaME(J2ME)(Java 2 Platform Micro Edition，java平臺(tái)微型版)。</p

35、><p><b>　?。?）優(yōu)勢(shì)</b></p><p>　　與傳統(tǒng)程序不同，Sun 公司在推出 Java 之際就將其作為一種開放的技術(shù)。全球數(shù)以萬(wàn)計(jì)的 Java 開發(fā)公司被要求所設(shè)計(jì)的 Java軟件必須相互兼容?！癑ava 語(yǔ)言靠群體的力量而非公司的力量”是Sun公司的口號(hào)之一，并獲得了廣大軟件開發(fā)商的認(rèn)同。這與微軟公司所倡導(dǎo)的注重精英和封閉式的模式完全不同。</

36、p><p>　　Sun 公司對(duì) Java 編程語(yǔ)言的解釋是：Java 編程語(yǔ)言是個(gè)簡(jiǎn)單、面向?qū)ο蟆⒎植际?、解釋性、健壯、安全與系統(tǒng)無(wú)關(guān)、可移植、高性能、多線程和動(dòng)態(tài)的語(yǔ)言。</p><p>　　Java 平臺(tái)是基于 Java 語(yǔ)言的平臺(tái)。這樣的平臺(tái)非常流行。因此微軟公司推出了與之競(jìng)爭(zhēng)的.NET平臺(tái)以及模仿Java的C#語(yǔ)言。</p><p>　　Java是功能完善的通用

37、程序設(shè)計(jì)語(yǔ)言，可以用來(lái)開發(fā)可靠的、要求嚴(yán)格的應(yīng)用程序。</p><p><b>　　（5）語(yǔ)言特征</b></p><p>　　Java編程語(yǔ)言的風(fēng)格十分接近C語(yǔ)言、C++語(yǔ)言。Java是一個(gè)純粹的面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言，它繼承了 C++語(yǔ)言面向?qū)ο蠹夹g(shù)的核心。Java舍棄了C語(yǔ)言中容易引起錯(cuò)誤的指針（以引用取代）、運(yùn)算符重載（operator overloading

38、）、多重繼承（以接口取代）等特性，增加了垃圾回收器功能用于回收不再被引用的對(duì)象所占據(jù)的內(nèi)存空間，使得程序員不用再為內(nèi)存管理而擔(dān)憂。在 Java 1.5 版本中，Java 又引入了泛型編程（Generic Programming）、類型安全的枚舉、不定長(zhǎng)參數(shù)和自動(dòng)裝/拆箱等語(yǔ)言特性。</p><p>　　Java不同于一般的編譯執(zhí)行計(jì)算機(jī)語(yǔ)言和解釋執(zhí)行計(jì)算機(jī)語(yǔ)言。它首先將源代碼編譯成二進(jìn)制字節(jié)碼（bytecode）

39、，然后依賴各種不同平臺(tái)上的虛擬機(jī)來(lái)解釋執(zhí)行字節(jié)碼。從而實(shí)現(xiàn)了“一次編譯、到處執(zhí)行”的跨平臺(tái)特性。不過(guò)，每次的執(zhí)行編譯后的字節(jié)碼需要消耗一定的時(shí)間，這同時(shí)也在一定程度上降低了 Java 程序的性能。</p><p><b>　?。?）主要特性</b></p><p>　　Java語(yǔ)言是易學(xué)的。Java語(yǔ)言的語(yǔ)法與C語(yǔ)言和C++語(yǔ)言很接近，使得大多數(shù)程序員很容易學(xué)習(xí)和使用

40、Java。另一方面，Java丟棄了C++中很少使用的、很難理解的、令人迷惑的那些特性，如操作符重載、多繼承、自動(dòng)的強(qiáng)制類型轉(zhuǎn)換。特別地，Java語(yǔ)言不使用指針，而是引用。并提供了自動(dòng)的廢料收集，使得程序員不必為內(nèi)存管理而擔(dān)憂。</p><p>　　Java語(yǔ)言是強(qiáng)制面向?qū)ο蟮摹ava語(yǔ)言提供類、接口和繼承等原語(yǔ)，為了簡(jiǎn)單起見，只支持類之間的單繼承，但支持接口之間的多繼承，并支持類與接口之間的實(shí)現(xiàn)機(jī)制（關(guān)鍵字為i

41、mplements）。Java語(yǔ)言全面支持動(dòng)態(tài)綁定，而C++語(yǔ)言只對(duì)虛函數(shù)使用動(dòng)態(tài)綁定?？傊?，Java語(yǔ)言是一個(gè)純的面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言。</p><p>　　Java語(yǔ)言是分布式的。Java語(yǔ)言支持Internet應(yīng)用的開發(fā)，在基本的Java應(yīng)用編程接口中有一個(gè)網(wǎng)絡(luò)應(yīng)用編程接口（java net），它提供了用于網(wǎng)絡(luò)應(yīng)用編程的類庫(kù)，包括URL、URLConnection、Socket、ServerSocket等。

42、Java的RMI（遠(yuǎn)程方法激活）機(jī)制也是開發(fā)分布式應(yīng)用的重要手段。</p><p>　　Java語(yǔ)言是健壯的。Java的強(qiáng)類型機(jī)制、異常處理、垃圾的自動(dòng)收集等是Java程序健壯性的重要保證。對(duì)指針的丟棄是Java的明智選擇。Java的安全檢查機(jī)制使得Java更具健壯性。</p><p>　　Java語(yǔ)言是安全的。Java通常被用在網(wǎng)絡(luò)環(huán)境中，為此，Java提供了一個(gè)安全機(jī)制以防惡意代碼的攻

43、擊。除了Java語(yǔ)言具有的許多安全特性以外，Java對(duì)通過(guò)網(wǎng)絡(luò)下載的類具有一個(gè)安全防范機(jī)制（類ClassLoader），如分配不同的名字空間以防替代本地的同名類、字節(jié)代碼檢查，并提供安全管理機(jī)制（類SecurityManager）讓Java應(yīng)用設(shè)置安全哨兵。</p><p>　　Java語(yǔ)言是體系結(jié)構(gòu)中立的。Java程序（后綴為java的文件）在Java平臺(tái)上被編譯為體系結(jié)構(gòu)中立的字節(jié)碼格式（后綴為class的文

44、件），然后可以在實(shí)現(xiàn)這個(gè)Java平臺(tái)的任何系統(tǒng)中運(yùn)行。這種途徑適合于異構(gòu)的網(wǎng)絡(luò)環(huán)境和軟件的分發(fā)。</p><p>　　Java語(yǔ)言是解釋型的。如前所述，Java程序在Java平臺(tái)上被編譯為字節(jié)碼格式，然后可以在實(shí)現(xiàn)這個(gè)Java平臺(tái)的任何系統(tǒng)中運(yùn)行。在運(yùn)行時(shí)，Java平臺(tái)中的Java解釋器對(duì)這些字節(jié)碼進(jìn)行解釋執(zhí)行，執(zhí)行過(guò)程中需要的類在聯(lián)接階段被載入到運(yùn)行環(huán)境中。</p><p>　　Java

45、是性能略高的。與那些解釋型的高級(jí)腳本語(yǔ)言相比，Java的性能還是較優(yōu)的。</p><p>　　Java語(yǔ)言是原生支持多線程的。在Java語(yǔ)言中，線程是一種特殊的對(duì)象，它必須由Thread類或其子（孫）類來(lái)創(chuàng)建。通常有兩種方法來(lái)創(chuàng)建線程：其一，使用型構(gòu)為Thread(Runnable)的構(gòu)造子將一個(gè)實(shí)現(xiàn)了Runnable接口的對(duì)象包裝成一個(gè)線程，其二，從Thread類派生出子類并重寫run方法，使用該子類創(chuàng)建的對(duì)象

46、即為線程。值得注意的是Thread類已經(jīng)實(shí)現(xiàn)了Runnable接口，因此，任何一個(gè)線程均有它的run方法，而run方法中包含了線程所要運(yùn)行的代碼。線程的活動(dòng)由一組方法來(lái)控制。Java語(yǔ)言支持多個(gè)線程的同時(shí)執(zhí)行，并提供多線程之間的同步機(jī)制（關(guān)鍵字為synchronized）。</p><p>　　Java語(yǔ)言是動(dòng)態(tài)的。Java語(yǔ)言的設(shè)計(jì)目標(biāo)之一是適應(yīng)于動(dòng)態(tài)變化的環(huán)境。Java程序需要的類能夠動(dòng)態(tài)地被載入到運(yùn)行環(huán)境，

47、也可以通過(guò)網(wǎng)絡(luò)來(lái)載入所需要的類。這也有利于軟件的升級(jí)。另外，Java中的類有一個(gè)運(yùn)行時(shí)刻的表示，能進(jìn)行運(yùn)行時(shí)刻的類型檢查。</p><p>　　Java語(yǔ)言的優(yōu)良特性使得Java應(yīng)用具有無(wú)比的健壯性和可靠性，這也減少了應(yīng)用系統(tǒng)的維護(hù)費(fèi)用。Java對(duì)對(duì)象技術(shù)的全面支持和Java平臺(tái)內(nèi)嵌的API能縮短應(yīng)用系統(tǒng)的開發(fā)時(shí)間并降低成本。Java的編譯一次，到處可運(yùn)行的特性使得它能夠提供一個(gè)隨處可用的開放結(jié)構(gòu)和在多平臺(tái)之間傳

48、遞信息的低成本方式。特別是Java企業(yè)應(yīng)用編程接口（Java Enterprise APIs）為企業(yè)計(jì)算及電子商務(wù)應(yīng)用系統(tǒng)提供了有關(guān)技術(shù)和豐富的類庫(kù)。</p><p>　　1.2.4 java圖形化編程的知識(shí)</p><p>　　java的GUI編程（Graphic User Interface，圖形用戶接口），是在它的抽象窗口工具箱（Abstract Window Toolkit，AWT

49、）上實(shí)現(xiàn)的，java.awt是AWT的工具類庫(kù)，其中包括了豐富的圖形、用戶界面元件和布局管理器的支持。</p><p>　　GUI主要用在兩個(gè)地方：</p><p>　　Application；Applet。</p><p><b>　　1）GUI界面：</b></p><p>　　用戶與程序之間交互的一個(gè)控制面板，其內(nèi)

50、包含有菜單，控件（或組件），容器并能響應(yīng)用戶的事件。</p><p>　　現(xiàn)在有各種各樣的窗口系統(tǒng)，不同的窗口系統(tǒng)提供給程序設(shè)計(jì)的程序庫(kù)是大不一樣的，例如，基于Windows的SDK，和基于Unix平臺(tái)的X Windows的Xlib。</p><p>　　為了使程序能在不同的窗口系統(tǒng)下運(yùn)行，Java提出了“抽象窗口系統(tǒng)”的概念，提供了AWT（抽象窗口工具箱），使得java能夠在不同的窗口系

51、統(tǒng)下運(yùn)行。</p><p>　　2）Java中的GUI實(shí)現(xiàn)方式：</p><p>　　采用AWT（抽象窗口工具集）從而可使GUI適用于不同OS的環(huán)境。</p><p><b>　　特點(diǎn)如下：</b></p><p>　?、?其具體實(shí)現(xiàn)由目標(biāo)平臺(tái)下的OS來(lái)解釋，從而導(dǎo)致Java GUI在不同平臺(tái)下會(huì)出現(xiàn)不同的運(yùn)行效果（窗口

52、外觀、字體等的顯示效果會(huì)發(fā)生變化）。</p><p>　?、?組件在設(shè)計(jì)時(shí)不應(yīng)采用絕對(duì)定位，而應(yīng)采用布局管理器來(lái)實(shí)現(xiàn)相對(duì)定位，以達(dá)到與平臺(tái)及設(shè)備無(wú)關(guān)。</p><p>　　3）新增的Swing GUI組件</p><p>　　AWT組件以及事件響應(yīng)不及微軟的SDK豐富（因?yàn)橛行㎡S平臺(tái)無(wú)微軟的Windows組件），Sun在Java2中新增了Swing GUI組件。但

53、是，AWT比較簡(jiǎn)單，功能也能滿足大多數(shù)界面需求，特別在Java Applet的設(shè)計(jì)中受到了普遍的應(yīng)用。</p><p><b>　　1.3 任務(wù)概述</b></p><p>　　本次課程設(shè)計(jì)的題目是“A星算法的演示系統(tǒng)”，A*算法在人工智能中是一種典型的啟發(fā)式搜索算法,這是一種在圖形平面上，有多個(gè)節(jié)點(diǎn)的路徑，求出最低通過(guò)成本的算法。常用于游戲中的NPC的移動(dòng)計(jì)算，或在

54、線游戲的BOT的移動(dòng)計(jì)算上。本次課程設(shè)計(jì)要求能夠演示出整個(gè)算法的執(zhí)行過(guò)程，能夠進(jìn)行單步演示，動(dòng)態(tài)演示，把算法的執(zhí)行過(guò)程的精髓演示出來(lái)。</p><p>　　實(shí)現(xiàn)了設(shè)置起點(diǎn)、設(shè)置終點(diǎn)、設(shè)置障礙、清除障礙、直接尋路、單步尋路、動(dòng)態(tài)尋路、重新尋路、添加默認(rèn)障礙這些功能的操作。</p><p>　　1.4 運(yùn)行環(huán)境規(guī)定</p><p>　　任何安裝java運(yùn)行環(huán)境的系統(tǒng)&l

55、t;/p><p>　　1：在eclipse中加載該項(xiàng)目，直接打開并運(yùn)行該項(xiàng)目。</p><p>　　2：安裝java運(yùn)行環(huán)境的機(jī)器中，控制臺(tái)下，進(jìn)入bin目錄，輸入java com.net.java1 3：安裝java運(yùn)行環(huán)境的機(jī)器中，直接運(yùn)行已經(jīng)打包好的axing.jar</p><p>　　1.5 其他A星軟件的優(yōu)劣</p><p><

56、b>　　(1)軟件一 </b></p><p>　　圖1.2 C#完成的A*算法的演示程序</p><p>　　這個(gè)程序的好處就是實(shí)現(xiàn)的功能很全。</p><p><b>　　優(yōu)點(diǎn)：</b></p><p>　?。?）對(duì)于障礙的不同級(jí)別，進(jìn)行了設(shè)置，表現(xiàn)在程序上我覺(jué)得就是障礙的加權(quán)值的不同，而且在實(shí)際的

57、執(zhí)行過(guò)程中也可以越過(guò)一些障礙。</p><p>　　（2）時(shí)間的延遲進(jìn)行了設(shè)置，對(duì)于程序的演示效果能有更好的展現(xiàn)。</p><p>　?。?）方格的大小也進(jìn)行了設(shè)置，可以進(jìn)行隨便的調(diào)節(jié)，也是為了方便展示。</p><p><b>　　缺點(diǎn)：</b></p><p>　　（1）功能過(guò)于復(fù)雜，初次拿到軟件的人會(huì)先進(jìn)行一段時(shí)間

58、的熟悉，不適合激發(fā)初學(xué)A星算法的人的興趣。</p><p>　?。?）文字說(shuō)明多，也是其復(fù)雜原因的一種，如果用圖形化的方式進(jìn)行更多的說(shuō)明會(huì)事半功倍。</p><p><b>　　(2)軟件二</b></p><p>　　圖1.3 VC++完成的A*算法的演示程序</p><p>　　這個(gè)軟件演示的很清晰，說(shuō)明很到位，沒(méi)有

59、實(shí)現(xiàn)動(dòng)態(tài)執(zhí)行的功能。</p><p><b>　　優(yōu)點(diǎn)：</b></p><p>　　該有的功能一般都有了，操作起來(lái)并不復(fù)雜，演示效果很好，圖形化的執(zhí)行很不錯(cuò)。</p><p><b>　　缺點(diǎn)：</b></p><p>　　每次執(zhí)行都要全屏展示，在我的電腦上如果一旦按WINDOWS鍵進(jìn)行其他操作，

60、在打開此程序，發(fā)現(xiàn)看不到之前的執(zhí)行路徑了。</p><p>　　基于上面的研究成果，我本次使用JAVA語(yǔ)言寫的A星算法演示程序，爭(zhēng)取盡可能的簡(jiǎn)單易操作。</p><p><b>　　2 概要設(shè)計(jì)</b></p><p><b>　　2.1 界面設(shè)計(jì)</b></p><p>　　2.1.1 軟件的進(jìn)入

61、界面設(shè)計(jì)</p><p>　　圖2.1 軟件的進(jìn)入界面</p><p>　　2.1.2 軟件的進(jìn)入界面的分析</p><p>　?。?）一般軟件都有自己的進(jìn)入界面，軟件的進(jìn)入界面能夠使軟件更富有意義，界面設(shè)計(jì)是為了滿足軟件專業(yè)化標(biāo)準(zhǔn)化的需求而產(chǎn)生的對(duì)軟件的使用界面進(jìn)行美化優(yōu)化規(guī)范化的設(shè)計(jì)分支。</p><p>　?。?）此界面大小長(zhǎng)950像素

62、，寬710像素，能夠滿足大部分計(jì)算機(jī)的整個(gè)屏幕的顯示，跟程序的主體界面大小一致。圖形的顯示位置在x=30，y=10的位置?！癆Star算法演示軟件”幾個(gè)字采用70號(hào)字，總體加粗。作者和姓名及“進(jìn)入演示程序”字體采用40號(hào)，F(xiàn)ont _LAYOUT _NO _LIMIT_CONTEXT號(hào)字。</p><p>　　（3）整個(gè)框架是外面的MyFace 包含F(xiàn)acePanel ，左右圖形的繪制通過(guò)FacePanel中的p

63、aint函數(shù)實(shí)現(xiàn)。</p><p>　?。?）背景是宇宙，有很多的星星，周圍放出萬(wàn)丈光芒，宇宙能夠給人以無(wú)限的想象，此處希望本程序的演示也能給使用者以無(wú)限的想象。藍(lán)色的光線是從兩邊的中心位置依次向上面和下面畫線，下面的間距為30個(gè)像素，這樣的設(shè)計(jì)能夠突出中間文字的顯示效果。</p><p>　?。?）此處星星的設(shè)計(jì)和程序的名稱有相對(duì)應(yīng)的地方，星星的繪制是通過(guò)在界面的區(qū)域內(nèi)隨機(jī)產(chǎn)生450個(gè)三

64、種顏色的點(diǎn)來(lái)顯示的。</p><p>　?。?）當(dāng)點(diǎn)擊“進(jìn)入程序演示”就會(huì)啟動(dòng)一個(gè)線程執(zhí)行顯示程序主體界面的程序，同時(shí)本界面會(huì)隱藏。</p><p>　　2.1.3 軟件主題界面的設(shè)計(jì)</p><p>　　圖2.2 軟件主體界面</p><p>　　2.1.4 軟件主體界面的分析</p><p>　?。?）整個(gè)FRAM

65、E的大小，長(zhǎng)950像素，寬710像素，內(nèi)包含兩個(gè)Panel，頂層的Panel包含4個(gè)JRadioButton，分別是“設(shè)置起點(diǎn)”、“設(shè)置終點(diǎn)”、“設(shè)置障礙”，“清除障礙”。下面的Panel是自定義的，包含左邊的方塊區(qū)域和右邊的說(shuō)明區(qū)域，方塊區(qū)域的長(zhǎng)700像素，寬600像素。</p><p>　?。?）小方塊的邊長(zhǎng)為50，整個(gè)區(qū)域長(zhǎng)14個(gè)方塊，高12個(gè)方塊。之所以這幾這么大小，是因?yàn)?，這樣的大小基本適合13寸以上的

66、電腦能夠在整個(gè)屏幕內(nèi)演示，能夠滿足大部分使用此軟件的人員的要求。</p><p>　?。?）JRadioButton剛開始默認(rèn)選定是設(shè)置障礙，可以通過(guò)點(diǎn)擊其他的單選按鈕，進(jìn)行相應(yīng)的操作。當(dāng)點(diǎn)擊其他的單選按鈕后，鼠標(biāo)對(duì)下面方框區(qū)域的操作與其對(duì)應(yīng)。</p><p>　　（4）右邊說(shuō)明的主題意思是通過(guò)方塊顏色的不同來(lái)區(qū)分起始結(jié)點(diǎn)，終止結(jié)點(diǎn)，CLOSE中的節(jié)點(diǎn)，OPEN中的節(jié)點(diǎn)等。另外箭頭指向啟發(fā)

67、式尋路過(guò)程中的每個(gè)節(jié)點(diǎn)的前驅(qū)。</p><p>　　2.2 程序需要實(shí)現(xiàn)的功能</p><p><b>　　1：設(shè)置起點(diǎn)</b></p><p><b>　　2：設(shè)置終點(diǎn)</b></p><p><b>　　3：設(shè)置障礙</b></p><p><

68、b>　　4：清除障礙</b></p><p>　　5：直接尋路（點(diǎn)擊按鈕就顯示出最后的尋路結(jié)果）</p><p>　　6：?jiǎn)尾綄ぢ罚ㄍㄟ^(guò)不斷的點(diǎn)擊按鈕，一步一步顯示出程序的尋路過(guò)程）</p><p><b>　　7：動(dòng)態(tài)尋路</b></p><p><b>　　8：重新尋路</b>

69、</p><p><b>　　9：添加默認(rèn)障礙</b></p><p><b>　　3 詳細(xì)設(shè)計(jì)</b></p><p><b>　　3.1 類圖的設(shè)計(jì)</b></p><p>　　圖3.1 A星算法演示軟件的類圖</p><p>　　3.2 類之間的

70、關(guān)系說(shuō)明</p><p>　?。?）繼承關(guān)系：繼承指的是一個(gè)類（稱為子類、子接口）繼承另外的一個(gè)類（稱為父類、父接口）的功能，并可以增加它自己的新功能的能力。在Java中繼承關(guān)系通過(guò)關(guān)鍵字extends明確標(biāo)識(shí)，在設(shè)計(jì)時(shí)一般沒(méi)有爭(zhēng)議性。在UML類圖設(shè)計(jì)中，繼承用一條帶空心三角箭頭的實(shí)線表示，從子類指向父類，或者子接口指向父接口。 </p><p>　　（2）實(shí)現(xiàn)關(guān)系：實(shí)現(xiàn)指的是一個(gè)clas

71、s類實(shí)現(xiàn)interface接口（可以是多個(gè)）的功能，實(shí)現(xiàn)是類與接口之間最常見的關(guān)系。在Java中此類關(guān)系通過(guò)關(guān)鍵字implements明確標(biāo)識(shí)，在設(shè)計(jì)時(shí)一般沒(méi)有爭(zhēng)議性。在UML類圖設(shè)計(jì)中，實(shí)現(xiàn)用一條帶空心三角箭頭的虛線表示，從類指向?qū)崿F(xiàn)的接口。 </p><p>　?。?）依賴關(guān)系：簡(jiǎn)單的理解，依賴就是一個(gè)類A使用到了另一個(gè)類B，而這種使用關(guān)系是具有偶然性的、臨時(shí)性的、非常弱的，但是類B的變化會(huì)影響到類A。比如某

72、人要過(guò)河，需要借用一條船，此時(shí)人與船之間的關(guān)系就是依賴。表現(xiàn)在代碼層面，為類B作為參數(shù)被類A在某個(gè)method方法中使用。在UML類圖設(shè)計(jì)中，依賴關(guān)系用由類A指向類B的帶箭頭虛線表示。 </p><p>　?。?）關(guān)聯(lián)關(guān)系：關(guān)聯(lián)體現(xiàn)的是兩個(gè)類之間語(yǔ)義級(jí)別的一種強(qiáng)依賴關(guān)系，比如我和我的朋友，這種關(guān)系比依賴更強(qiáng)、不存在依賴關(guān)系的偶然性、關(guān)系也不是臨時(shí)性的，一般是長(zhǎng)期性的，而且雙方的關(guān)系一般是平等的。關(guān)聯(lián)可以是單向、雙

73、向的。表現(xiàn)在代碼層面，為被關(guān)聯(lián)類B以類的屬性形式出現(xiàn)在關(guān)聯(lián)類A中，也可能是關(guān)聯(lián)類A引用了一個(gè)類型為被關(guān)聯(lián)類B的全局變量。在UML類圖設(shè)計(jì)中，關(guān)聯(lián)關(guān)系用由關(guān)聯(lián)類A指向被關(guān)聯(lián)類B的帶箭頭實(shí)線表示，在關(guān)聯(lián)的兩端可以標(biāo)注關(guān)聯(lián)雙方的角色和多重性標(biāo)記。 </p><p>　?。?）聚合關(guān)系：聚合是關(guān)聯(lián)關(guān)系的一種特例，它體現(xiàn)的是整體與部分的關(guān)系，即has-a的關(guān)系。此時(shí)整體與部分之間是可分離的，它們可以具有各自的生命周期，部分

74、可以屬于多個(gè)整體對(duì)象，也可以為多個(gè)整體對(duì)象共享。比如計(jì)算機(jī)與CPU、公司與員工的關(guān)系等，比如一個(gè)航母編隊(duì)包括?？漳概灐Ⅱ?qū)護(hù)艦艇、艦載飛機(jī)及核動(dòng)力攻擊潛艇等。表現(xiàn)在代碼層面，和關(guān)聯(lián)關(guān)系是一致的，只能從語(yǔ)義級(jí)別來(lái)區(qū)分。在UML類圖設(shè)計(jì)中，聚合關(guān)系以空心菱形加實(shí)線箭頭表示。 </p><p>　?。?）組合關(guān)系：組合也是關(guān)聯(lián)關(guān)系的一種特例，它體現(xiàn)的是一種contains-a的關(guān)系，這種關(guān)系比聚合更強(qiáng)，也稱為強(qiáng)聚合。它同

75、樣體現(xiàn)整體與部分間的關(guān)系，但此時(shí)整體與部分是不可分的，整體的生命周期結(jié)束也就意味著部分的生命周期結(jié)束，比如人和人的大腦。表現(xiàn)在代碼層面，和關(guān)聯(lián)關(guān)系是一致的，只能從語(yǔ)義級(jí)別來(lái)區(qū)分。在UML類圖設(shè)計(jì)中，組合關(guān)系以實(shí)心菱形加實(shí)線箭頭表示。</p><p><b>　　3.3 類圖的分析</b></p><p>　?。?）類圖(Class diagram)是顯示了模型的靜態(tài)結(jié)

76、構(gòu)，特別是模型中存在的類、類的內(nèi)部結(jié)構(gòu)以及它們與其他類的關(guān)系等，一般在詳細(xì)設(shè)計(jì)過(guò)程中出現(xiàn)，主要用來(lái)描述系統(tǒng)中各個(gè)模塊中類之間的關(guān)系，包括類或者類與接口的繼承關(guān)系，類之間的依賴、聚合等關(guān)系。</p><p>　?。?）此次的A*算法演示程序共用到了7個(gè)類，此7個(gè)類的關(guān)系相對(duì)比較簡(jiǎn)單，有依賴關(guān)系和聚合關(guān)系組成。</p><p>　?。?）java1類是程序的入口點(diǎn)，包含程序需的main函數(shù)，m

77、ain函數(shù)產(chǎn)生了界面類的對(duì)象。進(jìn)而界面類會(huì)調(diào)用界面類包含的Panel類的paint函數(shù)，繪制出軟件的進(jìn)入界面。</p><p>　?。?）軟件的進(jìn)入界面類對(duì)應(yīng)MyFace類，MyFace類包含F(xiàn)acePanel類的對(duì)象，此界面的繪圖操作是通過(guò)FacePanel類的paint函數(shù)來(lái)繪制的，（見上面的圖2.1 軟件的進(jìn)入界面）</p><p>　?。?）當(dāng)點(diǎn)擊“進(jìn)入演示程序”按鈕之后，會(huì)啟動(dòng)一

78、個(gè)線程，此線程會(huì)產(chǎn)生MyFrame類的對(duì)象。</p><p>　?。?）MyFrame類是程序的主題界面顯示的類，如圖2.2 軟件主體界面，此類包含兩個(gè)Panel，頂層的Panel包含單選按鈕和按鈕，底層的Panel包含圖形的繪制主體方塊和說(shuō)明信息。</p><p>　?。?）MyPanel是自己定義的JPanel，它繼承自JPanel，這個(gè)類主要是畫出主體方塊區(qū)域和現(xiàn)實(shí)說(shuō)明信息。<

79、/p><p>　?。?）Axing類用來(lái)設(shè)計(jì)整個(gè)A星算法，其中包含圖形的起始坐標(biāo)，終止坐標(biāo)，每走一步的帶權(quán)值，以及最重要的A星算法的實(shí)現(xiàn)代碼等。</p><p>　?。?）AxingNode類是程序的結(jié)點(diǎn)類，它設(shè)計(jì)了程序的結(jié)點(diǎn)，因?yàn)锳星算法要用到兩個(gè)鏈表，鏈表的結(jié)點(diǎn)類型就是AxingNode類型，每個(gè)節(jié)點(diǎn)都包含自己在方塊區(qū)域的坐標(biāo)，G、H、F值，指向前驅(qū)的字符串，direct用來(lái)指示cameF

80、rom的方向，flag用來(lái)標(biāo)記每個(gè)結(jié)點(diǎn)的類型，0:起始點(diǎn) 1:障礙 2:目標(biāo)點(diǎn) 3:其他，還有顏色值。</p><p><b>　　3.4 程序的實(shí)現(xiàn)</b></p><p>　　3.4.1 程序邏輯的設(shè)計(jì)</p><p>　　我此處用了兩個(gè)鏈表：</p><p>　　OpenList 初始化時(shí)存放起始結(jié)點(diǎn)，用來(lái)存放還為

81、探測(cè)的結(jié)點(diǎn)。</p><p>　　CloseList 初始化為空，用來(lái)存放已經(jīng)探測(cè)過(guò)得結(jié)點(diǎn)。</p><p>　　整個(gè)圖的結(jié)點(diǎn)用一個(gè)AxingNode型數(shù)組來(lái)存放</p><p>　　因?yàn)锳星算法需要進(jìn)行啟發(fā)式尋路，我采用的啟發(fā)式尋路的方式為當(dāng)前結(jié)點(diǎn)與目標(biāo)結(jié)點(diǎn)的橫縱坐標(biāo)的和作為啟發(fā)尋路的啟發(fā)H值，G值為前驅(qū)結(jié)點(diǎn)到起始結(jié)點(diǎn)的權(quán)值加上前驅(qū)結(jié)點(diǎn)到本結(jié)點(diǎn)的權(quán)值。F=G+H作

82、為總權(quán)值。每次比較就是按照F值進(jìn)行的比較。</p><p><b>　　F = G + H</b></p><p>　　G = 從起點(diǎn)沿著產(chǎn)生的路徑，移動(dòng)到網(wǎng)格上指定方格的移動(dòng)耗費(fèi)。</p><p>　　H = 從網(wǎng)格上那個(gè)方格移動(dòng)到終點(diǎn)B的預(yù)估移動(dòng)耗費(fèi)。</p><p>　　正如上面所說(shuō)，G表示沿路徑從起點(diǎn)到當(dāng)前點(diǎn)的移

83、動(dòng)耗費(fèi)。在這個(gè)例子里，我們令水平或者垂直移動(dòng)的耗費(fèi)為10。</p><p>　　既然我們?cè)谟?jì)算沿特定路徑通往某個(gè)方格的G值，求值的方法就是取它的前驅(qū)結(jié)點(diǎn)的G值，然后依照它相對(duì)前驅(qū)結(jié)點(diǎn)直角方向(非對(duì)角線)，增加和10。例子中這個(gè)方法的需求會(huì)變得更多，因?yàn)槲覀儚钠瘘c(diǎn)方格以外獲取了不止一個(gè)方格。</p><p>　　H值可以用不同的方法估算。我們這里使用的方法被稱為曼哈頓方法，它計(jì)算從當(dāng)前格到目

84、的格之間水平和垂直的方格的數(shù)量總和，忽略對(duì)角線方向。然后把結(jié)果乘以10。這被成為曼哈頓方法是因?yàn)樗雌饋?lái)像計(jì)算城市中從一個(gè)地方到另外一個(gè)地方的街區(qū)數(shù)，在那里你不能沿對(duì)角線方向穿過(guò)街區(qū)。很重要的一點(diǎn)，我們忽略了一切障礙物。這是對(duì)剩余距離的一個(gè)估算，而非實(shí)際值，這也是這一方法被稱為啟發(fā)式的原因。</p><p>　　F的值是G和H的和。第一步搜索的結(jié)果可以在下面的圖表中看到。F,G和H的評(píng)分被寫在每個(gè)方格里。正如在緊

85、挨起始格右側(cè)的方格所表示的，F(xiàn)被打印在左上角，G在左下角，H則在右下角。</p><p>　　具體算法的尋路思路如下：</p><p>　?。?）將從起始點(diǎn)開始，方塊添加到open列表中，該列表有最小的和值。且將這個(gè)方塊稱為S吧。</p><p>　?。?）將S從open列表移除，然后添加S到closed列表中。</p><p>　?。?）對(duì)

86、于與S相鄰的每一塊可通行的方塊T：（這里我問(wèn)題只要有上下左右可以通行）</p><p>　　1）如果T為終止結(jié)點(diǎn)，則結(jié)束。</p><p>　　2）如果T在closed列表中：不管它。</p><p>　　3）如果T不在open列表中：添加它然后計(jì)算出它的和值，并標(biāo)記S為他的前驅(qū)。</p><p>　　4）如果T已經(jīng)在open列表中：當(dāng)我們使

87、用當(dāng)前生成的路徑到達(dá)那里時(shí)計(jì)算新F值，檢查新F 值與原有F值相比是否更小。如果是，更新它的F值和它的前驅(qū)。</p><p>　　5)繼續(xù)掃描open列表中擁有最小的F值的結(jié)點(diǎn)，記為S，重復(fù)（3）</p><p>　　//A星算法的具體代碼如下</p><p>　　public boolean Afun()</p><p><b>　

88、　{</b></p><p>　　while(!openList.isEmpty())</p><p><b>　　{</b></p><p>　　AxingNode tempNode=openList.get(findMinF(openList));</p><p>　　if(tempNode.flag==

89、2)//如果是最后一個(gè)結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　path[startx][starty].F=path[endx][endy].F;</p><p>　　path[startx][starty].H=path[endx][endy].G;</p><p>　　return true

90、;//能夠到達(dá)最后的結(jié)點(diǎn)</p><p><b>　　}</b></p><p>　　openList.remove(tempNode);</p><p>　　closeList.add(tempNode);</p><p>　　//另外添加，對(duì)于openList,closeList中的結(jié)點(diǎn)的顏色進(jìn)行設(shè)置</p&g

91、t;<p>　　if(tempNode.flag!=0)//如果不是開始結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　tempNode.color=Color.cyan;//藍(lán)綠色標(biāo)志為進(jìn)入closeList中的結(jié)點(diǎn)。</p><p><b>　　}</b></p><

92、p>　　//對(duì)于剛加入closeList即剛從openList中刪除的結(jié)點(diǎn)，看其周圍的結(jié)點(diǎn)</p><p>　　LinkedList<AxingNode> neighborNodes=new LinkedList<AxingNode>();</p><p>　　if(tempNode.x>0&&path[tempNode.x-1][tem

93、pNode.y].flag!=1&&!closeList.contains(path[tempNode.x-1][tempNode.y]))//左</p><p><b>　　{</b></p><p>　　//如果openList 不包含周圍的結(jié)點(diǎn)，即周圍的結(jié)點(diǎn)并沒(méi)有提前在openList中，那么可以更改direct</p><p

94、>　　if(!openList.contains(path[tempNode.x-1][tempNode.y]))</p><p><b>　　{</b></p><p>　　path[tempNode.x-1][tempNode.y].direct=1;</p><p><b>　　}</b></p>

95、<p>　　//neighborNodes加入的順序是“左右上下”，這個(gè)順序隨意</p><p>　　neighborNodes.add(path[tempNode.x-1][tempNode.y]);</p><p><b>　　}</b></p><p>　　if(tempNode.x<13&&path[t

96、empNode.x+1][tempNode.y].flag!=1&&!closeList.contains(path[tempNode.x+1][tempNode.y]))//右</p><p><b>　　{</b></p><p>　　if(!openList.contains(path[tempNode.x+1][tempNode.y]))<

97、;/p><p><b>　　{</b></p><p>　　path[tempNode.x+1][tempNode.y].direct=0;</p><p><b>　　}</b></p><p>　　neighborNodes.add(path[tempNode.x+1][tempNode.y]);&

98、lt;/p><p><b>　　}</b></p><p>　　if(tempNode.y>0&&path[tempNode.x][tempNode.y-1].flag!=1&&!closeList.contains(path[tempNode.x][tempNode.y-1]))//上</p><p><

99、;b>　　{</b></p><p>　　if(!openList.contains(path[tempNode.x][tempNode.y-1]))</p><p><b>　　{</b></p><p>　　path[tempNode.x][tempNode.y-1].direct=3;</p><p&

100、gt;<b>　　}</b></p><p>　　neighborNodes.add(path[tempNode.x][tempNode.y-1]);</p><p><b>　　}</b></p><p>　　if(tempNode.y<11&&path[tempNode.x][tempNode.y

101、+1].flag!=1&&!closeList.contains(path[tempNode.x][tempNode.y+1]))//下</p><p><b>　　{</b></p><p>　　if(!openList.contains(path[tempNode.x][tempNode.y+1]))</p><p><

102、;b>　　{</b></p><p>　　path[tempNode.x][tempNode.y+1].direct=2;</p><p><b>　　}</b></p><p>　　neighborNodes.add(path[tempNode.x][tempNode.y+1]);</p><p>&

103、lt;b>　　}</b></p><p>　　isBetter=false;//很重要，防止之前的</p><p>　　for(i=0;i<neighborNodes.size();i++)</p><p><b>　　{</b></p><p>　　//if(closeList.cont

104、ains(neighborNodes.get(i)))</p><p><b>　　//{</b></p><p>　　//continue;</p><p><b>　　//}</b></p><p>　　//tempNode 是從openList中取出的最小的，剛加入c

105、loseList中的結(jié)點(diǎn)</p><p>　　//tempG指按照這個(gè)結(jié)點(diǎn)計(jì)算出的 四周的結(jié)點(diǎn)的 G 值</p><p>　　tempG=path[tempNode.x][tempNode.y].G+price;//從起點(diǎn)到neighbor的G距離</p><p>　　if(!openList.contains(neighborNodes.get(i)))</

106、p><p><b>　　{</b></p><p>　　openList.add(neighborNodes.get(i));</p><p>　　isBetter=true;</p><p><b>　　}</b></p><p>　　else if(tempG<neig

107、hborNodes.get(i).G)</p><p><b>　　{</b></p><p>　　//openList之前已經(jīng)包含neighborNode結(jié)點(diǎn)，但是按照當(dāng)前的結(jié)點(diǎn)計(jì)算tempG會(huì)更小一些</p><p>　　if(neighborNodes.get(i).x<tempNode.x)//鄰居節(jié)點(diǎn)X小于當(dāng)前節(jié)點(diǎn)X,即在當(dāng)前節(jié)

108、點(diǎn)的左邊，應(yīng)指向右</p><p><b>　　{</b></p><p>　　neighborNodes.get(i).direct=1;</p><p><b>　　}</b></p><p>　　if(neighborNodes.get(i).x>tempNode.x)//指向左<

109、/p><p><b>　　{</b></p><p>　　neighborNodes.get(i).direct=0;</p><p><b>　　}</b></p><p>　　if(neighborNodes.get(i).y>tempNode.y)//指向上</p><p

110、><b>　　{</b></p><p>　　neighborNodes.get(i).direct=2;</p><p><b>　　}</b></p><p>　　if(neighborNodes.get(i).y<tempNode.y)//指向下</p><p><b>

111、　　{</b></p><p>　　neighborNodes.get(i).direct=3;</p><p><b>　　}</b></p><p>　　isBetter=true;</p><p><b>　　}</b></p><p><b>　

112、　else </b></p><p><b>　　{</b></p><p>　　isBetter=false;</p><p><b>　　}</b></p><p>　　if(isBetter)</p><p><b>　　{</b>&l

113、t;/p><p>　　neighborNodes.get(i).cameFrom=Character.toString(szDirect[neighborNodes.get(i).direct]);</p><p>　　neighborNodes.get(i).G=tempG;</p><p>　　neighborNodes.get(i).H=(Math.abs(end

114、x-neighborNodes.get(i).x)+Math.abs(endy-neighborNodes.get(i).y))*price;</p><p>　　neighborNodes.get(i).F=neighborNodes.get(i).G+neighborNodes.get(i).H;</p><p>　　if(neighborNodes.get(i).flag!=2)//

115、如果不是終止結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　neighborNodes.get(i).color=Color.blue;//藍(lán)色設(shè)置為加入openList中的結(jié)點(diǎn)的顏色</p><p><b>　　}</b></p><p><b>　　}</b&g

116、t;</p><p>　　}//end for(neighbor)</p><p>　　}//end while</p><p>　　return false;</p><p><b>　　}</b></p><p><b>　　代碼說(shuō)明：</b></p>&l

117、t;p>　　代碼中的path是相對(duì)于主體界面（圖2.2 軟件主體界面）桔黃色尋路區(qū)域的二維數(shù)組代碼表示，是AXingNode類型的結(jié)點(diǎn)。</p><p>　　neighboeNodes也是AXingNode類型的鏈表的表示。用來(lái)存飯每次要進(jìn)行拓展的當(dāng)前結(jié)點(diǎn)的可以進(jìn)行再探測(cè)的結(jié)點(diǎn)。</p><p>　　總體的執(zhí)行思路就是按照上面給出的執(zhí)行邏輯進(jìn)行的編碼。</p><