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

3、大的運(yùn)算和圖形展示功能，使圖像編程變得更加的簡單和直觀。本課題基于eclipse的java集成開發(fā)環(huán)境，設(shè)計(jì)并實(shí)現(xiàn)了A星算法的演示系統(tǒng)，展示A星算法如何進(jìn)行啟發(fā)式搜索和尋路的過程。實(shí)現(xiàn)了設(shè)置起點(diǎn)、設(shè)置終點(diǎn)、設(shè)置障礙、清除障礙、直接尋路、單步尋路、動態(tài)尋路、重新尋路、添加默認(rèn)障礙這些功能的操作。使用者能夠通過自己的要求進(jìn)行A星算法的演示和使用，本軟件充分展示A星算法的執(zhí)行過程。</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語言介紹6</p><p>　　1.2.4 java圖形化編程的知識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)系說明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 動態(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é)者會產(chǎn)生迷惑，為了使算法的執(zhí)行步驟更加的清晰，是算法的思路完整的展現(xiàn)出來，此次課題的要求就是用圖形化的方式，一步一步的展現(xiàn)A*算法的執(zhí)行步驟，使想了解A*算法的人能夠更清晰的理解此算法，等真正理解了，就會發(fā)現(xiàn)，原來游戲的尋路是這樣的，從而也會是學(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>　　在說啟發(fā)式搜索之前先提狀態(tài)空間搜索。狀態(tài)空間搜索，如果按專業(yè)點(diǎn)的說法就是將問題求解過程表現(xiàn)為從初始狀態(tài)到目標(biāo)狀態(tài)尋找這個路徑的過程。通俗點(diǎn)說，兩點(diǎn)

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

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

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

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

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

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

26、納性。A*算法是一個可采納的最好優(yōu)先算法。A*算法的估價函數(shù)可表示為：</p><p>　　f'(n) = g'(n) + h'(n)</p><p>　　這里，f'(n)是估價函數(shù)，g'(n)是起點(diǎn)到節(jié)點(diǎn)n的最短路徑值，h'(n)是n到目標(biāo)的最短路經(jīng)的啟發(fā)值。舉一個例子，其實(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>　　再說一個問題，就是有關(guān)h(n)啟發(fā)函數(shù)的信息性。h(n)的信息性通俗點(diǎn)說其實(shí)就是在估計(jì)一個節(jié)點(diǎn)的值時的約束條件，如果信息越多或約束條件越多則排除的節(jié)點(diǎn)就越多，估價函數(shù)越好或說這個算法越好。這就是為什么廣度優(yōu)先算法的那么臭的原因了，誰叫它的h(n)=0，一點(diǎn)啟發(fā)信息

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

29、重要的，因此為何要對后續(xù)路徑的精確度感到厭煩？或者，對于在地圖上的一個安全區(qū)域，最短路徑也許并不十分重要，但是當(dāng)從一個敵人的村莊逃跑時，安全和速度是最重要的。所以A星算法應(yīng)用在游戲中時可以根據(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)有向圖的單源最短路徑問題，算法最終得到一個最短路徑樹。并沒有啟發(fā)尋路，屬于A*算法的特例。這個算法的工作過程就是從起始點(diǎn)開始，不斷的向未知點(diǎn)擴(kuò)展，使從已知點(diǎn)集合到達(dá)任意未知點(diǎn)的距離權(quán)重都是最小的，這樣當(dāng)擴(kuò)展到終止點(diǎn)的時候，也就找到了最短的權(quán)重。</p><p>　　1.2.3 java語言介紹</p><p

31、><b>　　（1）起源</b></p><p>　　Java是由Sun Microsystems公司于 1995年5月推出的Java面向?qū)ο蟪绦蛟O(shè)計(jì)語言（以下簡稱Java語言）和Java平臺的總稱。由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)的Web、Internet計(jì)算。從此，Java被廣泛接受并推動了Web的迅速發(fā)展，常用的瀏覽器均支持Javaapplet。另一方面，Java技術(shù)也不斷更新。</p><p><b>　　（2）組成</b></p><p>　　Java由四方面

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

50、包含有菜單，控件（或組件），容器并能響應(yīng)用戶的事件。</p><p>　　現(xiàn)在有各種各樣的窗口系統(tǒng)，不同的窗口系統(tǒng)提供給程序設(shè)計(jì)的程序庫是大不一樣的，例如，基于Windows的SDK，和基于Unix平臺的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)平臺下的OS來解釋，從而導(dǎo)致Java GUI在不同平臺下會出現(xiàn)不同的運(yùn)行效果（窗口

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

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

54、線游戲的BOT的移動計(jì)算上。本次課程設(shè)計(jì)要求能夠演示出整個算法的執(zhí)行過程，能夠進(jìn)行單步演示，動態(tài)演示，把算法的執(zhí)行過程的精髓演示出來。</p><p>　　實(shí)現(xiàn)了設(shè)置起點(diǎn)、設(shè)置終點(diǎn)、設(shè)置障礙、清除障礙、直接尋路、單步尋路、動態(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ī)器中，控制臺下，進(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>　　這個程序的好處就是實(shí)現(xiàn)的功能很全。</p><p><b>　　優(yōu)點(diǎn)：</b></p><p>　?。?）對于障礙的不同級別，進(jìn)行了設(shè)置，表現(xiàn)在程序上我覺得就是障礙的加權(quán)值的不同，而且在實(shí)際的

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

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

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

60、在打開此程序，發(fā)現(xiàn)看不到之前的執(zhí)行路徑了。</p><p>　　基于上面的研究成果，我本次使用JAVA語言寫的A星算法演示程序，爭取盡可能的簡單易操作。</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)生的對軟件的使用界面進(jìn)行美化優(yōu)化規(guī)范化的設(shè)計(jì)分支。</p><p>　?。?）此界面大小長950像素

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

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

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

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

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

67、式尋路過程中的每個節(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：單步尋路（通過不斷的點(diǎn)擊按鈕，一步一步顯示出程序的尋路過程）</p><p><b>　　7：動態(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)系說明</p><p>　?。?）繼承關(guān)系：繼承指的是一個類（稱為子類、子接口）繼承另外的一個類（稱為父類、父接口）的功能，并可以增加它自己的新功能的能力。在Java中繼承關(guān)系通過關(guān)鍵字extends明確標(biāo)識，在設(shè)計(jì)時一般沒有爭議性。在UML類圖設(shè)計(jì)中，繼承用一條帶空心三角箭頭的實(shí)線表示，從子類指向父類，或者子接口指向父接口。 </p><p>　?。?）實(shí)現(xiàn)關(guān)系：實(shí)現(xiàn)指的是一個clas

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

72、人要過河，需要借用一條船，此時人與船之間的關(guān)系就是依賴。表現(xiàn)在代碼層面，為類B作為參數(shù)被類A在某個method方法中使用。在UML類圖設(shè)計(jì)中，依賴關(guān)系用由類A指向類B的帶箭頭虛線表示。 </p><p>　?。?）關(guān)聯(lián)關(guān)系：關(guān)聯(lián)體現(xiàn)的是兩個類之間語義級別的一種強(qiáng)依賴關(guān)系，比如我和我的朋友，這種關(guān)系比依賴更強(qiáng)、不存在依賴關(guān)系的偶然性、關(guān)系也不是臨時性的，一般是長期性的，而且雙方的關(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引用了一個類型為被關(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)系。此時整體與部分之間是可分離的，它們可以具有各自的生命周期，部分

74、可以屬于多個整體對象，也可以為多個整體對象共享。比如計(jì)算機(jī)與CPU、公司與員工的關(guān)系等，比如一個航母編隊(duì)包括?？漳概灐Ⅱ?qū)護(hù)艦艇、艦載飛機(jī)及核動力攻擊潛艇等。表現(xiàn)在代碼層面，和關(guān)聯(lián)關(guān)系是一致的，只能從語義級別來區(qū)分。在UML類圖設(shè)計(jì)中，聚合關(guān)系以空心菱形加實(shí)線箭頭表示。 </p><p>　　（6）組合關(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)系，但此時整體與部分是不可分的，整體的生命周期結(jié)束也就意味著部分的生命周期結(jié)束，比如人和人的大腦。表現(xiàn)在代碼層面，和關(guān)聯(lián)關(guān)系是一致的，只能從語義級別來區(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ì)過程中出現(xiàn)，主要用來描述系統(tǒng)中各個模塊中類之間的關(guān)系，包括類或者類與接口的繼承關(guān)系，類之間的依賴、聚合等關(guān)系。</p><p>　?。?）此次的A*算法演示程序共用到了7個類，此7個類的關(guān)系相對比較簡單，有依賴關(guān)系和聚合關(guān)系組成。</p><p>　?。?）java1類是程序的入口點(diǎn)，包含程序需的main函數(shù)，m

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

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

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

80、rom的方向，flag用來標(biāo)記每個結(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>　　我此處用了兩個鏈表：</p><p>　　OpenList 初始化時存放起始結(jié)點(diǎn)，用來存放還為

81、探測的結(jié)點(diǎn)。</p><p>　　CloseList 初始化為空，用來存放已經(jīng)探測過得結(jié)點(diǎn)。</p><p>　　整個圖的結(jié)點(diǎn)用一個AxingNode型數(shù)組來存放</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)生的路徑，移動到網(wǎng)格上指定方格的移動耗費(fèi)。</p><p>　　H = 從網(wǎng)格上那個方格移動到終點(diǎn)B的預(yù)估移動耗費(fèi)。</p><p>　　正如上面所說，G表示沿路徑從起點(diǎn)到當(dāng)前點(diǎn)的移

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

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

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

86、于與S相鄰的每一塊可通行的方塊T：（這里我問題只要有上下左右可以通行）</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á)那里時計(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)//如果是最后一個結(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>　　//另外添加，對于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>　　//對于剛加入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)并沒有提前在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加入的順序是“左右上下”，這個順序隨意</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指按照這個結(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會更小一些</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>　　代碼說明：</b></p>&l

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