A算法演示系統(tǒng)畢業(yè)設(shè)計

摘要本次課程設(shè)計的題目是“A星算法的演示系統(tǒng)”，A*算法在人工智能中是一種典型的啟發(fā)式搜索算法,這是一種在圖形平面上，有多個節(jié)點(diǎn)的路徑，求出最低通過成本的算法。常用于游戲中的NPC的移動計算，或在線游戲的BOT的移動計算上。本次課程設(shè)計要求能夠演示出整個算法的執(zhí)行過程，能夠進(jìn)行單步演示，動態(tài)演示，把算法的執(zhí)行過程的精髓演示出來。在對算法充分了解的基礎(chǔ)上，演示算法的執(zhí)行過程，就要涉及到圖像的繪制，而對于圖像的編程，顯然高級語言有其開發(fā)效率高的特點(diǎn)，java強(qiáng)大的運(yùn)算和圖形展示功能，使圖像編程變得更加的簡單和直觀。本課題基于eclipse的java集成開發(fā)環(huán)境，設(shè)計并實現(xiàn)了A星算法的演示系統(tǒng)，展示A星算法如何進(jìn)行啟發(fā)式搜索和尋路的過程。實現(xiàn)了設(shè)置起點(diǎn)、設(shè)置終點(diǎn)、設(shè)置障礙、清除障礙、直接尋路、單步尋路、動態(tài)尋路、重新尋路、添加默認(rèn)障礙這些功能的操作。使用者能夠通過自己的要求進(jìn)行A星算法的演示和使用，本軟件充分展示A星算法的執(zhí)行過程。關(guān)鍵字：A*算法，啟發(fā)式搜索，javaAbstractThetopicofthecoursedesignis"Astaralgorithmdemosoftware",A*algorithminartificialintelligenceisAkindoftypicalheuristicsearchalgorithm,thisisAgraphicsintheplane,havemorethanonenodepath,thealgorithmofminimumthroughcost.itoftenbeusedinthegameofmobilecomputingofNPC,oronlinegamesonmobilecomputingofBOT.Thecoursedesignrequirstodemonstratetheimplementationprocessofthewholealgorithm,canbesinglestepdemo,dynamicdemonstration,theessenceoftheexecutionprocessofalgorithmdemo.onthebasisoffullunderstandingofthealgorithm,DemonstrateingthealgorithmimplementationprocesswillinvolvetheGraphdrawing,andtheprogrammingonimage,obviouslyahigh-levellanguagehasthecharacteristicsofitsdevelopmentofhighefficiency,Javapowerfulcomputingandgraphicsdisplayfunction,maketheimageprogrammingmoresimpleandintuitive.Thisprojectisbasedoneclipse'sJavaintegrateddevelopmentenvironment,Astaralgorithmdemosoftwarewasdesignedandimplemented,showinghowAstaralgorithmofheuristicsearchandpathfinding.Implementssetthestartingpointandendpoint,barriers,clearobstacles,directlypathfinding,singlesteppathfinding,dynamicpathfinding,pathfindingagain,adddefaultbarrierfunctionoftheseoperations.theusercanusethesoftwareaccordingtotheirrequirments,thesoftwarefullyshowstheexecutionofAstaralgorithm.Keywords：AStararithmetic，heuristicsearch，java目錄0Abstract...........................................................................................................................................121需求分析.....................................................................................................................................31.1編寫目的...........................................................................................................................31.2背景...................................................................................................................................31.2.1A*搜索算法介紹.....................................................................................................31.2.2Dijkstra算法............................................................................................................41.2.3java語言介紹..........................................................................................................51.2.4java圖形化編程的知識..........................................................................................71.3任務(wù)概述...........................................................................................................................71.4運(yùn)行環(huán)境規(guī)定...................................................................................................................81.5其他A星軟件的優(yōu)劣......................................................................................................8(1)軟件一..........................................................................................................................8(2)軟件二..........................................................................................................................92概要設(shè)計...................................................................................................................................102.1界面設(shè)計.........................................................................................................................102.1.1軟件的進(jìn)入界面設(shè)計...........................................................................................102.1.2軟件的進(jìn)入界面的分析.......................................................................................102.1.3軟件主題界面的設(shè)計...........................................................................................112.1.4軟件主體界面的分析...........................................................................................112.2程序需要實現(xiàn)的功能.....................................................................................................123詳細(xì)設(shè)計...................................................................................................................................133.1類圖的設(shè)計.....................................................................................................................133.2類之間的關(guān)系說明.........................................................................................................133.3類圖的分析.....................................................................................................................143.4程序的實現(xiàn).....................................................................................................................153.4.1程序邏輯的設(shè)計...................................................................................................153.3.2找到link中結(jié)點(diǎn)的F值最小的結(jié)點(diǎn)..................................................................193.4.3響應(yīng)繪制方塊paint的參數(shù)與getGraphics().....................................................223.4.4程序主體界面MyPanel中paint函數(shù)做的工作................................................233.4.5主體界面類做的工作...........................................................................................233.3.6鼠標(biāo)監(jiān)聽mouseClickedORmousePressed.........................................................243.3.7動態(tài)尋路的演示...................................................................................................243.3.8設(shè)置起點(diǎn)的工作...................................................................................................243.3.9設(shè)置終點(diǎn)的工作...................................................................................................243.3.10找不到路徑的提示.............................................................................................2526276參考資料...................................................................................................................................28需求分析1.1編寫目的A*算法作為為基本尋路算法常出現(xiàn)在游戲設(shè)計中，剛剛接觸 A*算法，難免初學(xué)者會產(chǎn)生迷惑，為了使算法的執(zhí)行步驟更加的清晰，是算法的思路完整的展現(xiàn)出來，此次課題的要求就是用圖形化的方式，一步一步的展現(xiàn)A*算法的執(zhí)行步驟，使想了解A*算法的人能夠更清晰的理解此算法，等真正理解了，就會發(fā)現(xiàn)，原來游戲的尋路是這樣的，從而也會是學(xué)習(xí)者有更大的興趣深入其他算法的學(xué)習(xí)。1.2背景1.2.1A*搜索算法介紹A*在游戲設(shè)計中有它很典型的用法， 是人工智能在游戲中的代表。 A*算法在人工智能中是一種典型的啟發(fā)式搜索算法在說啟發(fā)式搜索之前先提狀態(tài)空間搜索。狀態(tài)空間搜索，如果按專業(yè)點(diǎn)的說法就是將問題求解過程表現(xiàn)為從初始狀態(tài)到目標(biāo)狀態(tài)尋找這個路徑的過程。通俗點(diǎn)說，兩點(diǎn)之間求一線路，這兩點(diǎn)是求解的開始和問題的結(jié)果，而這一線路不一定是直線，可以是曲折的。由于求解問題的過程中分枝有很多，主要是求解過程中求解條件的不確定性，不完備性造成的，使得求解的路徑很多這就構(gòu)成了一個圖，我們說這個圖就是狀態(tài)空間。問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結(jié)果。這個尋找的過程就是狀態(tài)空間搜索。常用的狀態(tài)空間搜索有深度優(yōu)先和廣度優(yōu)先。 廣度優(yōu)先是從初始狀態(tài)一層一層向下找，直到找到目標(biāo)為止。深度優(yōu)先是按照一定的順序先查找完一個分支，再查找另一個分支，以至找到目標(biāo)為止。這兩種算法在數(shù)據(jù)結(jié)構(gòu)書中都有描述，可以參看這些書得到更詳細(xì)的解釋。前面說的廣度和深度優(yōu)先搜索有一個很大的缺陷就是他們都是在一個給定的狀態(tài)空間中窮舉。這在狀態(tài)空間不大的情況下是很合適的算法，可是當(dāng)狀態(tài)空間十分大，且不預(yù)測的情況下就不可取了。他的效率實在太低，甚至不可完成。在這里就要用到啟發(fā)式搜索了。啟發(fā)式搜索就是在狀態(tài)空間中的搜索對每一個搜索的位置進(jìn)行評估， 得到最好的位置，再從這個位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無謂的搜索路徑，提高了效率。在啟發(fā)式搜索中，對位置的估價是十分重要的。采用了不同的估價可以有不同的效果。啟發(fā)中的估價是用估價函數(shù)表示的，如： f(n)=g(n)+h(n)其中f(n)是節(jié)點(diǎn)n的估價函數(shù)，g(n)是在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實際代價，h(n)是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計代價。在這里主要是h(n)體現(xiàn)了搜索的啟發(fā)信息，因為g(n)是已知的。如果說詳細(xì)點(diǎn)，g(n)代表了搜索的廣度的優(yōu)先趨勢。但是當(dāng)h(n)>>g(n)時，可以省略g(n)，而提高效率。啟發(fā)式搜索其實有很多的算法，比如：局部擇優(yōu)搜索法、最好優(yōu)先搜索法等等。當(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)都舍棄了，因為求解的最佳節(jié)點(diǎn)只是在該階段的最佳并不一定是全局的最佳。最好優(yōu)先就聰明多了，他在搜索時，并沒有舍棄節(jié)點(diǎn)（除非該節(jié)點(diǎn)是死節(jié)點(diǎn)），在每一步的估價中都把當(dāng)前的節(jié)點(diǎn)和以前的節(jié)點(diǎn)的估價值比較得到一個“最佳的節(jié)點(diǎn)”。這樣可以有效的防止“最佳節(jié)點(diǎn)”的丟失。那么A*算法又是一種什么樣的算法呢？其實A*算法也是一種最好優(yōu)先的算法，只不過要加上一些約束條件罷了。由于在一些問題求解時，我們希望能夠求解出狀態(tài)空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！我們先下個定義，如果一個估價函數(shù)可以找出最短的路徑，我們稱之為可采納性。A*算法是一個可采納的最好優(yōu)先算法。A*算法的估價函數(shù)可表示為：f'(n)=g'(n)+h'(n)這里，f'(n) 是估價函數(shù)，g'(n) 是起點(diǎn)到節(jié)點(diǎn)n的最短路徑值，h'(n)是n到目標(biāo)的最短路經(jīng)的啟發(fā)值。舉一個例子，其實廣度優(yōu)先算法就是 A*算法的特例。其中 g(n)是節(jié)點(diǎn)所在的層數(shù)，h(n)=0，這種h(n)肯定小于h'(n)，所以由前述可知廣度優(yōu)先算法是一種可采納的。實際也是。當(dāng)然它是一種最臭的 A*算法。再說一個問題，就是有關(guān) h(n)啟發(fā)函數(shù)的信息性。h(n)的信息性通俗點(diǎn)說其實就是在估計一個節(jié)點(diǎn)的值時的約束條件，如果信息越多或約束條件越多則排除的節(jié)點(diǎn)就越多，估價函數(shù)越好或說這個算法越好。這就是為什么廣度優(yōu)先算法的那么臭的原因了，誰叫它的h(n)=0，一點(diǎn)啟發(fā)信息都沒有。但在游戲開發(fā)中由于實時性的問題， h(n)的信息越多，它的計算量就越大，耗費(fèi)的時間就越多。就應(yīng)該適當(dāng)?shù)臏p小 h(n)的信息，即減小約束條件。但算法的準(zhǔn)確性就差了，這里就有一個平衡的問題。游戲中速度和精確度之間的選擇并不是全局的。在地圖上的某些區(qū)域，精確度是重要的，你可以基于此進(jìn)行動態(tài)選擇。例如，假設(shè)我們可能在某點(diǎn)停止重新計算路徑或者改變方向，則在接近當(dāng)前位置的地方，選擇一條好的路徑則是更重要的，因此為何要對后續(xù)路徑的精確度感到厭煩？或者，對于在地圖上的一個安全區(qū)域， 最短路徑也許并不十分重要，但是當(dāng)從一個敵人的村莊逃跑時，安全和速度是最重要的。所以A星算法應(yīng)用在游戲中時可以根據(jù)具體的情況為各種不同的障礙設(shè)置不同的加權(quán)值是盡可能的出最有效的方案。1.2.2Dijkstra算法圖1.1Dijkstra 算法的執(zhí)行圖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)重。1.2.3java語言介紹（1）起源Java是由SunMicrosystems公司于1995年5月推出的Java面向?qū)ο蟪绦蛟O(shè)計語言（以下簡稱Java語言）和Java平臺的總稱。由JamesGosling和同事們共同研發(fā)，并在1995年正式推出。Java最初被稱為Oak，是1991年為消費(fèi)類電子產(chǎn)品的嵌入式芯片而設(shè)計的。1995年更名為Java，并重新設(shè)計用于開發(fā)Internet應(yīng)用程序。用Java實現(xiàn)的HotJava瀏覽器（支持Javaapplet）顯示了Java的魅力：跨平臺、動態(tài)的Web、Internet計算。從此，Java被廣泛接受并推動了Web的迅速發(fā)展，常用的瀏覽器均支持Javaapplet。另一方面，Java技術(shù)也不斷更新。（2）組成Java由四方面組成：●Java編程語言●Java文件格式●Java虛擬機(jī)(JVM)●Java應(yīng)用程序接口(JavaAPI)（3）體系Java分為三個體系JavaSE（J2SE）（Java2PlatformStandardEdition標(biāo)準(zhǔn)版），JavaEE(J2EE)(Java2Platform,EnterpriseEdition ，java

，java平臺企業(yè)版

平臺)，JavaME(J2ME)(Java2PlatformMicroEdition

，java

平臺微型版

)。（4）優(yōu)勢與傳統(tǒng)程序不同，Sun公司在推出Java 之際就將其作為一種開放的技術(shù)。全球數(shù)以萬計的Java 開發(fā)公司被要求所設(shè)計的 Java軟件必須相互兼容。“Java語言靠群體的力量而非公司的力量”是Sun公司的口號之一，并獲得了廣大軟件開發(fā)商的認(rèn)同。這與微軟公司所倡導(dǎo)的注重精英和封閉式的模式完全不同。Sun公司對Java編程語言的解釋是：Java編程語言是個簡單、面向?qū)ο?、分布式、解釋性、健壯、安全與系統(tǒng)無關(guān)、可移植、高性能、多線程和動態(tài)的語言。Java平臺是基于Java語言的平臺。這樣的平臺非常流行。因此微軟公司推出了與之競爭的.NET平臺以及模仿Java的C#語言。Java是功能完善的通用程序設(shè)計語言，可以用來開發(fā)可靠的、要求嚴(yán)格的應(yīng)用程序。（5）語言特征Java編程語言的風(fēng)格十分接近 C語言、C++語言。Java是一個純粹的面向?qū)ο蟮某绦蛟O(shè)計語言，它繼承了C++語言面向?qū)ο蠹夹g(shù)的核心。 Java舍棄了C語言中容易引起錯誤的指針（以引用取代）、運(yùn)算符重載（ operatoroverloading ）、多重繼承（以接口取代）等特性，增加了垃圾回收器功能用于回收不再被引用的對象所占據(jù)的內(nèi)存空間，使得程序員不用再為內(nèi)存管理而擔(dān)憂。在Java1.5版本中，Java又引入了泛型編程（GenericProgramming）、類型安全的枚舉、不定長參數(shù)和自動裝/拆箱等語言特性。Java不同于一般的編譯執(zhí)行計算機(jī)語言和解釋執(zhí)行計算機(jī)語言。它首先將源代碼編譯成二進(jìn)制字節(jié)碼（bytecode），然后依賴各種不同平臺上的虛擬機(jī)來解釋執(zhí)行字節(jié)碼。從而實現(xiàn)了“一次編譯、到處執(zhí)行”的跨平臺特性。不過，每次的執(zhí)行編譯后的字節(jié)碼需要消耗一定的時間，這同時也在一定程度上降低了Java程序的性能。（6）主要特性Java語言是易學(xué)的。Java語言的語法與C語言和C++語言很接近，使得大多數(shù)程序員很容易學(xué)習(xí)和使用 Java。另一方面，Java丟棄了C++中很少使用的、很難理解的、令人迷惑的那些特性，如操作符重載、多繼承、自動的強(qiáng)制類型轉(zhuǎn)換。特別地，Java語言不使用指針，而是引用。并提供了自動的廢料收集，使得程序員不必為內(nèi)存管理而擔(dān)憂。Java語言是強(qiáng)制面向?qū)ο蟮?。Java語言提供類、接口和繼承等原語，為了簡單起見，只支持類之間的單繼承，但支持接口之間的多繼承，并支持類與接口之間的實現(xiàn)機(jī)制（關(guān)鍵字為implements）。Java語言全面支持動態(tài)綁定，而C++語言只對虛函數(shù)使用動態(tài)綁定。總之，Java語言是一個純的面向?qū)ο蟪绦蛟O(shè)計語言。Java語言是分布式的。Java語言支持Internet應(yīng)用的開發(fā)，在基本的Java應(yīng)用編程接口中有一個網(wǎng)絡(luò)應(yīng)用編程接口（javanet），它提供了用于網(wǎng)絡(luò)應(yīng)用編程的類庫，包括URL、URLConnection、Socket、ServerSocket等。Java的RMI（遠(yuǎn)程方法激活）機(jī)制也是開發(fā)分布式應(yīng)用的重要手段。Java語言是健壯的。Java的強(qiáng)類型機(jī)制、異常處理、垃圾的自動收集等是 Java程序健壯性的重要保證。對指針的丟棄是Java的明智選擇。Java的安全檢查機(jī)制使得Java更具健壯性。Java語言是安全的。Java通常被用在網(wǎng)絡(luò)環(huán)境中，為此，Java提供了一個安全機(jī)制以防惡意代碼的攻擊。除了Java語言具有的許多安全特性以外，Java對通過網(wǎng)絡(luò)下載的類具有一個安全防范機(jī)制（類ClassLoader），如分配不同的名字空間以防替代本地的同名類、字節(jié)代碼檢查，并提供安全管理機(jī)制（類SecurityManager）讓Java應(yīng)用設(shè)置安全哨兵。Java語言是體系結(jié)構(gòu)中立的。Java程序（后綴為java的文件）在Java平臺上被編譯為體系結(jié)構(gòu)中立的字節(jié)碼格式（后綴為 class的文件），然后可以在實現(xiàn)這個 Java平臺的任何系統(tǒng)中運(yùn)行。這種途徑適合于異構(gòu)的網(wǎng)絡(luò)環(huán)境和軟件的分發(fā)。Java語言是解釋型的。如前所述，Java程序在Java平臺上被編譯為字節(jié)碼格式，然后可以在實現(xiàn)這個Java平臺的任何系統(tǒng)中運(yùn)行。在運(yùn)行時，Java平臺中的Java解釋器對這些字節(jié)碼進(jìn)行解釋執(zhí)行，執(zhí)行過程中需要的類在聯(lián)接階段被載入到運(yùn)行環(huán)境中。Java是性能略高的。與那些解釋型的高級腳本語言相比， Java的性能還是較優(yōu)的。Java語言是原生支持多線程的。在 Java語言中，線程是一種特殊的對象，它必須由Thread類或其子（孫）類來創(chuàng)建。通常有兩種方法來創(chuàng)建線程：其一，使用型構(gòu)為Thread(Runnable)的構(gòu)造子將一個實現(xiàn)了 Runnable接口的對象包裝成一個線程，其二，從Thread類派生出子類并重寫 run方法，使用該子類創(chuàng)建的對象即為線程。值得注意的是Thread類已經(jīng)實現(xiàn)了Runnable接口，因此，任何一個線程均有它的 run方法，而run方法中包含了線程所要運(yùn)行的代碼。 線程的活動由一組方法來控制。 Java語言支持多個線程的同時執(zhí)行，并提供多線程之間的同步機(jī)制（關(guān)鍵字為 synchronized）。Java語言是動態(tài)的。Java語言的設(shè)計目標(biāo)之一是適應(yīng)于動態(tài)變化的環(huán)境。 Java程序需要的類能夠動態(tài)地被載入到運(yùn)行環(huán)境，也可以通過網(wǎng)絡(luò)來載入所需要的類。這也有利于軟件的升級。另外，Java中的類有一個運(yùn)行時刻的表示，能進(jìn)行運(yùn)行時刻的類型檢查。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)和在多平臺之間傳遞信息的低成本方式。特別是 Java企業(yè)應(yīng)用編程接口（JavaEnterpriseAPIs ）為企業(yè)計算及電子商務(wù)應(yīng)用系統(tǒng)提供了有關(guān)技術(shù)和豐富的類庫。1.2.4java圖形化編程的知識java的GUI編程（GraphicUserInterface ，圖形用戶接口），是在它的抽象窗口工具箱（Abstract WindowToolkit ，AWT）上實現(xiàn)的，java.awt 是AWT的工具類庫，其中包括了豐富的圖形、用戶界面元件和布局管理器的支持。GUI主要用在兩個地方：Application ；Applet。1）GUI界面：用戶與程序之間交互的一個控制面板，其內(nèi)包含有菜單，控件（或組件），容器并能響應(yīng)用戶的事件?，F(xiàn)在有各種各樣的窗口系統(tǒng)，不同的窗口系統(tǒng)提供給程序設(shè)計的程序庫是大不一樣的，例如，基于Windows的SDK，和基于Unix平臺的XWindows的Xlib。為了使程序能在不同的窗口系統(tǒng)下運(yùn)行，Java提出了“抽象窗口系統(tǒng)”的概念，提供了AWT（抽象窗口工具箱），使得java能夠在不同的窗口系統(tǒng)下運(yùn)行。2）Java中的GUI實現(xiàn)方式：采用AWT（抽象窗口工具集）從而可使 GUI適用于不同OS的環(huán)境。特點(diǎn)如下：①其具體實現(xiàn)由目標(biāo)平臺下的OS來解釋，從而導(dǎo)致JavaGUI在不同平臺下會出現(xiàn)不同的運(yùn)行效果（窗口外觀、字體等的顯示效果會發(fā)生變化）。②組件在設(shè)計時不應(yīng)采用絕對定位，而應(yīng)采用布局管理器來實現(xiàn)相對定位，以達(dá)到與平臺及設(shè)備無關(guān)。3）新增的SwingGUI組件AWT組件以及事件響應(yīng)不及微軟的SDK豐富（因為有些OS平臺無微軟的Windows組件），Sun在Java2中新增了SwingGUI組件。但是，AWT比較簡單，功能也能滿足大多數(shù)界面需求，特別在JavaApplet的設(shè)計中受到了普遍的應(yīng)用。1.3任務(wù)概述本次課程設(shè)計的題目是“A星算法的演示系統(tǒng)”，A*算法在人工智能中是一種典型的啟發(fā)式搜索算法,這是一種在圖形平面上，有多個節(jié)點(diǎn)的路徑，求出最低通過成本的算法。常用于游戲中的NPC的移動計算，或在線游戲的BOT的移動計算上。本次課程設(shè)計要求能夠演示出整個算法的執(zhí)行過程，能夠進(jìn)行單步演示，動態(tài)演示，把算法的執(zhí)行過程的精髓演示出來。實現(xiàn)了設(shè)置起點(diǎn)、設(shè)置終點(diǎn)、設(shè)置障礙、清除障礙、直接尋路、單步尋路、動態(tài)尋路、重新尋路、添加默認(rèn)障礙這些功能的操作。1.4運(yùn)行環(huán)境規(guī)定任何安裝java運(yùn)行環(huán)境的系統(tǒng)1：在eclipse2：安裝java3：安裝java

中加載該項目，直接打開并運(yùn)行該項目。運(yùn)行環(huán)境的機(jī)器中，控制臺下，進(jìn)入bin目錄，輸入java.java1運(yùn)行環(huán)境的機(jī)器中，直接運(yùn)行已經(jīng)打包好的 axing.jar1.5其他A星軟件的優(yōu)劣(1)軟件一圖1.2C#完成的A*算法的演示程序這個程序的好處就是實現(xiàn)的功能很全。優(yōu)點(diǎn)：1）對于障礙的不同級別，進(jìn)行了設(shè)置，表現(xiàn)在程序上我覺得就是障礙的加權(quán)值的不同，而且在實際的執(zhí)行過程中也可以越過一些障礙。2）時間的延遲進(jìn)行了設(shè)置，對于程序的演示效果能有更好的展現(xiàn)。3）方格的大小也進(jìn)行了設(shè)置，可以進(jìn)行隨便的調(diào)節(jié)，也是為了方便展示。缺點(diǎn)：（1）功能過于復(fù)雜，初次拿到軟件的人會先進(jìn)行一段時間的熟悉，不適合激發(fā)初學(xué)A星算法的人的興趣。2）文字說明多，也是其復(fù)雜原因的一種，如果用圖形化的方式進(jìn)行更多的說明會事半功倍。(2)軟件二圖1.3VC++完成的A*算法的演示程序這個軟件演示的很清晰，說明很到位，沒有實現(xiàn)動態(tài)執(zhí)行的功能。優(yōu)點(diǎn)：該有的功能一般都有了，操作起來并不復(fù)雜，演示效果很好，圖形化的執(zhí)行很不錯。缺點(diǎn)：每次執(zhí)行都要全屏展示，在我的電腦上如果一旦按WINDOWS鍵進(jìn)行其他操作，在打開此程序，發(fā)現(xiàn)看不到之前的執(zhí)行路徑了。基于上面的研究成果，我本次使用JAVA語言寫的A星算法演示程序，爭取盡可能的簡單易操作。概要設(shè)計2.1界面設(shè)計2.1.1軟件的進(jìn)入界面設(shè)計圖2.1 軟件的進(jìn)入界面2.1.2軟件的進(jìn)入界面的分析1）一般軟件都有自己的進(jìn)入界面，軟件的進(jìn)入界面能夠使軟件更富有意義，界面設(shè)計是為了滿足軟件專業(yè)化標(biāo)準(zhǔn)化的需求而產(chǎn)生的對軟件的使用界面進(jìn)行美化優(yōu)化規(guī)范化的設(shè)計分支。2）此界面大小長950像素，寬710像素，能夠滿足大部分計算機(jī)的整個屏幕的顯示，跟程序的主體界面大小一致。圖形的顯示位置在x=30，y=10的位置?！癆Star算法演示軟件”幾個字采用70號字，總體加粗。作者和姓名及“進(jìn)入演示程序”字體采用40號，F(xiàn)ont_LAYOUT_NO_LIMIT_CONTEXT號字。3）整個框架是外面的MyFace包含F(xiàn)acePanel，左右圖形的繪制通過FacePanel中的paint函數(shù)實現(xiàn)。4）背景是宇宙，有很多的星星，周圍放出萬丈光芒，宇宙能夠給人以無限的想象，此處希望本程序的演示也能給使用者以無限的想象。藍(lán)色的光線是從兩邊的中心位置依次向上面和下面畫線，下面的間距為30個像素，這樣的設(shè)計能夠突出中間文字的顯示效果。5）此處星星的設(shè)計和程序的名稱有相對應(yīng)的地方，星星的繪制是通過在界面的區(qū)域內(nèi)隨機(jī)產(chǎn)生450個三種顏色的點(diǎn)來顯示的。6）當(dāng)點(diǎn)擊“進(jìn)入程序演示”就會啟動一個線程執(zhí)行顯示程序主體界面的程序，同時本界面會隱藏。2.1.3軟件主題界面的設(shè)計圖2.2 軟件主體界面2.1.4軟件主體界面的分析（1）整個FRAME的大小，長950像素，寬710像素，內(nèi)包含兩個Panel，頂層的Panel包含4個JRadioButton，分別是“設(shè)置起點(diǎn)”、“設(shè)置終點(diǎn)”、“設(shè)置障礙”，“清除障礙”。下面的Panel是自定義的，包含左邊的方塊區(qū)域和右邊的說明區(qū)域，方塊區(qū)域的長700像素，寬600像素。2）小方塊的邊長為50，整個區(qū)域長14個方塊，高12個方塊。之所以這幾這么大小，是因為，這樣的大小基本適合13寸以上的電腦能夠在整個屏幕內(nèi)演示，能夠滿足大部分使用此軟件的人員的要求。3）JRadioButton剛開始默認(rèn)選定是設(shè)置障礙，可以通過點(diǎn)擊其他的單選按鈕，進(jìn)行相應(yīng)的操作。當(dāng)點(diǎn)擊其他的單選按鈕后，鼠標(biāo)對下面方框區(qū)域的操作與其對應(yīng)。4）右邊說明的主題意思是通過方塊顏色的不同來區(qū)分起始結(jié)點(diǎn)，終止結(jié)點(diǎn)，CLOSE中的節(jié)點(diǎn)，OPEN中的節(jié)點(diǎn)等。另外箭頭指向啟發(fā)式尋路過程中的每個節(jié)點(diǎn)的前驅(qū)。2.2程序需要實現(xiàn)的功能1：設(shè)置起點(diǎn)2：設(shè)置終點(diǎn)3：設(shè)置障礙4：清除障礙5：直接尋路（點(diǎn)擊按鈕就顯示出最后的尋路結(jié)果）6：單步尋路（通過不斷的點(diǎn)擊按鈕，一步一步顯示出程序的尋路過程）7：動態(tài)尋路8：重新尋路9：添加默認(rèn)障礙詳細(xì)設(shè)計3.1類圖的設(shè)計圖3.1A 星算法演示軟件的類圖3.2類之間的關(guān)系說明（1）繼承關(guān)系：繼承指的是一個類（稱為子類、子接口）繼承另外的一個類（稱為父類、父接口）的功能，并可以增加它自己的新功能的能力。在 Java中繼承關(guān)系通過關(guān)鍵字extends明確標(biāo)識，在設(shè)計時一般沒有爭議性。在UML類圖設(shè)計中，繼承用一條帶空心三角箭頭的實線表示，從子類指向父類，或者子接口指向父接口。2）實現(xiàn)關(guān)系：實現(xiàn)指的是一個class類實現(xiàn)interface接口（可以是多個）的功能，實現(xiàn)是類與接口之間最常見的關(guān)系。在Java中此類關(guān)系通過關(guān)鍵字implements明確標(biāo)識，在設(shè)計時一般沒有爭議性。在UML類圖設(shè)計中，實現(xiàn)用一條帶空心三角箭頭的虛線表示，從類指向?qū)崿F(xiàn)的接口。3）依賴關(guān)系：簡單的理解，依賴就是一個類A使用到了另一個類B，而這種使用關(guān)系是具有偶然性的、臨時性的、非常弱的，但是類B的變化會影響到類A。比如某人要過河，需要借用一條船，此時人與船之間的關(guān)系就是依賴。表現(xiàn)在代碼層面，為類B作為參數(shù)被類A在某個method方法中使用。在UML類圖設(shè)計中，依賴關(guān)系用由類A指向類B的帶箭頭虛線表示。4）關(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)可以是單向、雙向的。表現(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è)計中，關(guān)聯(lián)關(guān)系用由關(guān)聯(lián)類A指向被關(guān)聯(lián)類B的帶箭頭實線表示，在關(guān)聯(lián)的兩端可以標(biāo)注關(guān)聯(lián)雙方的角色和多重性標(biāo)記。5）聚合關(guān)系：聚合是關(guān)聯(lián)關(guān)系的一種特例，它體現(xiàn)的是整體與部分的關(guān)系，即has-a的關(guān)系。此時整體與部分之間是可分離的，它們可以具有各自的生命周期，部分可以屬于多個整體對象，也可以為多個整體對象共享。比如計算機(jī)與CPU、公司與員工的關(guān)系等，比如一個航母編隊包括海空母艦、驅(qū)護(hù)艦艇、艦載飛機(jī)及核動力攻擊潛艇等。表現(xiàn)在代碼層面，和關(guān)聯(lián)關(guān)系是一致的，只能從語義級別來區(qū)分。在UML類圖設(shè)計中，聚合關(guān)系以空心菱形加實線箭頭表示。（6）組合關(guān)系：組合也是關(guān)聯(lián)關(guān)系的一種特例，它體現(xiàn)的是一種contains-a的關(guān)系，這種關(guān)系比聚合更強(qiáng)，也稱為強(qiáng)聚合。它同樣體現(xiàn)整體與部分間的關(guān)系，但此時整體與部分是不可分的，整體的生命周期結(jié)束也就意味著部分的生命周期結(jié)束， 比如人和人的大腦。表現(xiàn)在代碼層面，和關(guān)聯(lián)關(guān)系是一致的，只能從語義級別來區(qū)分。在UML類圖設(shè)計中，組合關(guān)系以實心菱形加實線箭頭表示。3.3類圖的分析1）類圖(Classdiagram)是顯示了模型的靜態(tài)結(jié)構(gòu)，特別是模型中存在的類、類的內(nèi)部結(jié)構(gòu)以及它們與其他類的關(guān)系等，一般在詳細(xì)設(shè)計過程中出現(xiàn)，主要用來描述系統(tǒng)中各個模塊中類之間的關(guān)系，包括類或者類與接口的繼承關(guān)系，類之間的依賴、聚合等關(guān)系。2）此次的A*算法演示程序共用到了7個類，此7個類的關(guān)系相對比較簡單，有依賴關(guān)系和聚合關(guān)系組成。（3）java1類是程序的入口點(diǎn)，包含程序需的main函數(shù)，main函數(shù)產(chǎn)生了界面類的對象。進(jìn)而界面類會調(diào)用界面類包含的Panel類的paint函數(shù)，繪制出軟件的進(jìn)入界面。4）軟件的進(jìn)入界面類對應(yīng)MyFace類，MyFace類包含F(xiàn)acePanel類的對象，此界面的繪圖操作是通過FacePanel類的paint函數(shù)來繪制的，（見上面的圖2.1軟件的進(jìn)入界面）5）當(dāng)點(diǎn)擊“進(jìn)入演示程序”按鈕之后，會啟動一個線程，此線程會產(chǎn)生MyFrame類的對象。6）MyFrame類是程序的主題界面顯示的類，如圖2.2軟件主體界面，此類包含兩個Panel，頂層的Panel包含單選按鈕和按鈕，底層的Panel包含圖形的繪制主體方塊和說明信息。7）MyPanel是自己定義的JPanel，它繼承自JPanel，這個類主要是畫出主體方塊區(qū)域和現(xiàn)實說明信息。8）Axing類用來設(shè)計整個A星算法，其中包含圖形的起始坐標(biāo)，終止坐標(biāo)，每走一步的帶權(quán)值，以及最重要的A星算法的實現(xiàn)代碼等。9）AxingNode類是程序的結(jié)點(diǎn)類，它設(shè)計了程序的結(jié)點(diǎn)，因為A星算法要用到兩個鏈表，鏈表的結(jié)點(diǎn)類型就是AxingNode類型，每個節(jié)點(diǎn)都包含自己在方塊區(qū)域的坐標(biāo)，G、H、F值，指向前驅(qū)的字符串，direct用來指示cameFrom的方向，flag用來標(biāo)記每個結(jié)點(diǎn)的類型，0:起始點(diǎn)1:障礙2:目標(biāo)點(diǎn)3:其他，還有顏色值。3.4程序的實現(xiàn)3.4.1程序邏輯的設(shè)計我此處用了兩個鏈表：OpenList 初始化時存放起始結(jié)點(diǎn)，用來存放還為探測的結(jié)點(diǎn)。CloseList 初始化為空，用來存放已經(jīng)探測過得結(jié)點(diǎn)。整個圖的結(jié)點(diǎn)用一個 AxingNode型數(shù)組來存放因為A星算法需要進(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作為總權(quán)值。每次比較就是按照F值進(jìn)行的比較。F=G+HG=從起點(diǎn)沿著產(chǎn)生的路徑，移動到網(wǎng)格上指定方格的移動耗費(fèi)。H=從網(wǎng)格上那個方格移動到終點(diǎn) B的預(yù)估移動耗費(fèi)。正如上面所說，G表示沿路徑從起點(diǎn)到當(dāng)前點(diǎn)的移動耗費(fèi)。在這個例子里，我們令水平或者垂直移動的耗費(fèi)為10。既然我們在計算沿特定路徑通往某個方格的G值，求值的方法就是取它的前驅(qū)結(jié)點(diǎn)的G值，然后依照它相對前驅(qū)結(jié)點(diǎn)直角方向(非對角線)，增加和10。例子中這個方法的需求會變得更多，因為我們從起點(diǎn)方格以外獲取了不止一個方格。值可以用不同的方法估算。我們這里使用的方法被稱為曼哈頓方法，它計算從當(dāng)前格到目的格之間水平和垂直的方格的數(shù)量總和，忽略對角線方向。然后把結(jié)果乘以10。這被成為曼哈頓方法是因為它看起來像計算城市中從一個地方到另外一個地方的街區(qū)數(shù)，在那里你不能沿對角線方向穿過街區(qū)。很重要的一點(diǎn)，我們忽略了一切障礙物。這是對剩余距離的一個估算，而非實際值，這也是這一方法被稱為啟發(fā)式的原因。F的值是G和H的和。第一步搜索的結(jié)果可以在下面的圖表中看到。F,G和H的評分被寫在每個方格里。正如在緊挨起始格右側(cè)的方格所表示的，F(xiàn)被打印在左上角，G在左下角，H則在右下角。具體算法的尋路思路如下：1）將從起始點(diǎn)開始，方塊添加到open列表中，該列表有最小的和值。且將這個方塊稱為S吧。2）將S從open列表移除，然后添加S到closed列表中。3）對于與S相鄰的每一塊可通行的方塊T：（這里我問題只要有上下左右可以通行）1）如果T為終止結(jié)點(diǎn)，則結(jié)束。2）如果T在closed列表中：不管它。3）如果T不在open列表中：添加它然后計算出它的和值，并標(biāo)記 S為他的前驅(qū)。4）如果T已經(jīng)在open列表中：當(dāng)我們使用當(dāng)前生成的路徑到達(dá)那里時計算新F值，檢查新F值與原有F值相比是否更小。如果是，更新它的F值和它的前驅(qū)。繼續(xù)掃描open列表中擁有最小的F值的結(jié)點(diǎn)，記為S，重復(fù)（3）//A星算法的具體代碼如下publicbooleanAfun(){while(!openList.isEmpty()){AxingNodetempNode=openList.get(findMinF(openList));if(tempNode.flag==2)//如果是最后一個結(jié)點(diǎn){path[startx][starty].F=path[endx][endy].F;path[startx][starty].H=path[endx][endy].G;returntrue;// 能夠到達(dá)最后的結(jié)點(diǎn)}openList.remove(tempNode);closeList.add(tempNode);另外添加，對于openList,closeList中的結(jié)點(diǎn)的顏色進(jìn)行設(shè)置if(tempNode.flag!=0)// 如果不是開始結(jié)點(diǎn){tempNode.color=Color.cyan;// 藍(lán)綠色標(biāo)志為進(jìn)入 closeList 中的結(jié)點(diǎn)。}//對于剛加入closeList 即剛從openList 中刪除的結(jié)點(diǎn)，看其周圍的結(jié)點(diǎn)LinkedList<AxingNode>neighborNodes=newLinkedList<AxingNode>();if(tempNode.x>0&&path[tempNode.x-1][tempNode.y].flag!=1&&!closeList.contains(path[tempNode.x-1][tempNode.y]))// 左{如果openList不包含周圍的結(jié)點(diǎn)，即周圍的結(jié)點(diǎn)并沒有提前在openList 中，那么可以更改 directif(!openList.contains(path[tempNode.x-1][tempNode.y])){path[tempNode.x-1][tempNode.y].direct=1;}//neighborNodes加入的順序是“左右上下”，這個順序隨意neighborNodes.add(path[tempNode.x-1][tempNode.y]);}if(tempNode.x<13&&path[tempNode.x+1][tempNode.y].flag!=1&&!closeList.contains(path[tempNode.x+1][tempNode.y]))//{

右if(!openList.contains(path[tempNode.x+1][tempNode.y])){path[tempNode.x+1][tempNode.y].direct=0;}neighborNodes.add(path[tempNode.x+1][tempNode.y]);}if(tempNode.y>0&&path[tempNode.x][tempNode.y-1].flag!=1&&!closeList.contains(path[tempNode.x][tempNode.y-1]))//{

上if(!openList.contains(path[tempNode.x][tempNode.y-1])){path[tempNode.x][tempNode.y-1].direct=3;}neighborNodes.add(path[tempNode.x][tempNode.y-1]);}if(tempNode.y<11&&path[tempNode.x][tempNode.y+1].flag!=1&&!closeList.contains(path[tempNode.x][tempNode.y+1]))//{

下if(!openList.contains(path[tempNode.x][tempNode.y+1])){path[tempNode.x][tempNode.y+1].direct=2;}neighborNodes.add(path[tempNode.x][tempNode.y+1]);}isBetter=false;// 很重要，防止之前的for(i=0;i<neighborNodes.size();i++){////

if(closeList.contains(neighborNodes.get(i))){//

continue;//

}//tempNode

是從

openList

中取出的最小的，剛加入

closeList

中的結(jié)點(diǎn)//tempG指按照這個結(jié)點(diǎn)計算出的 四周的結(jié)點(diǎn)的G值tempG=path[tempNode.x][tempNode.y].G+price;// 從起點(diǎn)到neighbor的G距離if(!openList.contains(neighborNodes.get(i))){openList.add(neighborNodes.get(i));isBetter=true;}elseif(tempG<neighborNodes.get(i).G){//openList之前已經(jīng)包含neighborNode結(jié)點(diǎn)，但是按照當(dāng)前的結(jié)點(diǎn)計算tempG會更小一些if(neighborNodes.get(i).x<tempNode.x)// 鄰居節(jié)點(diǎn)X小于當(dāng)前節(jié)點(diǎn)X,即在當(dāng)前節(jié)點(diǎn)的左邊，應(yīng)指向右{neighborNodes.get(i).direct=1;}if(neighborNodes.get(i).x>tempNode.x)// 指向左{neighborNodes.get(i).direct=0;}if(neighborNodes.get(i).y>tempNode.y)// 指向上{neighborNodes.get(i).direct=2;}if(neighborNodes.get(i).y<tempNode.y)// 指向下{neighborNodes.get(i).direct=3;}isBetter=true;}else{isBetter=false;}if(isBetter){neighborNodes.get(i).cameFrom=Character.toString(szDirect[neighborNodes.get(i).direct]);neighborNodes.get(i).G=tempG;neighborNodes.get(i).H=(Math.abs(endx-neighborNodes.get(i).x)+Math.abs(endy-neighborNodes.get(i).y))*price;neighborNodes.get(i).F=neighborNodes.get(i).G+neighborNodes.get(i).H;if(neighborNodes.get(i).flag!=2)// 如果不是終止結(jié)點(diǎn){neighborNodes.get(i).color=Color.blue;// 藍(lán)色設(shè)置為加入openList中的結(jié)點(diǎn)的顏色}}}//endfor(neighbor)}//endwhilereturnfalse;}代碼說明：代碼中的path是相對于主體界面（圖2.2軟件主體界面）桔黃色尋路區(qū)域的二維數(shù)組代碼表示，是AXingNode類型的結(jié)點(diǎn)。neighboeNodes也是AXingNode類型的鏈表的表示。用來存飯每次要進(jìn)行拓展的當(dāng)前結(jié)點(diǎn)的可以進(jìn)行再探測的結(jié)點(diǎn)。總體的執(zhí)行思路就是按照上面給出的執(zhí)行邏輯進(jìn)行的編碼。3.3.2找到link中結(jié)點(diǎn)的F值最小的結(jié)點(diǎn)找到link中結(jié)點(diǎn)的F值最小的結(jié)點(diǎn)的下標(biāo)（最后探測到的）從后向前掃描，找到最前面的最小的F的結(jié)點(diǎn)的下標(biāo)，返回注意探測的鏈表因為下標(biāo)從0開始都是數(shù)據(jù)，所以使用前一定要判斷鏈表不為空才行?。。ublicintfindMinF(LinkedList<AxingNode>link){inti,minF,index=0;minF=link.get(0).F;從前向后掃描，找到最小的那個F的下標(biāo)，如果幾個相同的下標(biāo)，取最后面的最小的那個，這樣可以以最快的方式到達(dá)目標(biāo)結(jié)點(diǎn)for(i=1;i<link.size();i++){if(link.get(i).F<=minF)//*** 如果此處沒有‘=’，那么會去最前面的最小的結(jié)點(diǎn)，會探測一些無用的點(diǎn)。{index=i;minF=link.get(i).F;}}returnindex;// 返回下標(biāo)}探測結(jié)果如下：圖3.2FindMin 加上“=”的執(zhí)行效果圖如果//** 處的<=改成<，代碼如下：publicintfindMinF(LinkedList<AxingNode>link){inti,minF,index=0;minF=link.get(0).F;for(i=1;i<link.size();i++){if(link.get(i).F<minF)//*** 此處沒有‘=’{index=i;minF=link.get(i).F;}}returnindex;// 返回下標(biāo)}對于相同的障礙，結(jié)果如下：圖3.3FindMin不加上“=”的執(zhí)行效果圖很明顯，后面的情況會探測很多無用功的結(jié)點(diǎn)。通過此函數(shù)的演示效果，可以說明不同的最小值選取防止對于程序的執(zhí)行結(jié)果優(yōu)化程度是不同的，這里之所以選取從前向后最后探測到的那個最小的結(jié)點(diǎn)作為繼續(xù)探測的最小的結(jié)點(diǎn)，是因為1）每次探測結(jié)點(diǎn)都是在鏈表后面進(jìn)行插入。2）每次探測我們做的選擇都是目前最優(yōu)的選擇，及選擇最接近目標(biāo)結(jié)點(diǎn)的那個結(jié)點(diǎn)進(jìn)行探測。3）因為我的啟發(fā)式搜索的H的計算采用的是通過當(dāng)前結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)橫縱坐標(biāo)的絕對值之差相加。所有不算是最精確的啟發(fā)式尋路，尋路過程難免會有許多F值相同的情況，而這種情況一多，如果采用每次都找最之前的那個結(jié)點(diǎn)進(jìn)行探測就會探測很多無用的結(jié)點(diǎn)。情況如下：圖3.4 執(zhí)行效果差異分析圖本來已經(jīng)通過之前的探測，到了圖中的1處，因為1處的F和2處的F一樣，所以在接下來的尋路中有重新回到了2處繼續(xù)進(jìn)行探測，就會使1處的探測沒有進(jìn)行到底，最好的方式是按照已經(jīng)走過的路一路走到底，這樣也就是減少很多不必要的探測，也是之前的探測大部分都有意義，實踐證明，這樣效率更高。3.4.3響應(yīng)繪制方塊paint的參數(shù)與getGraphics()我們知道，對于 Panel，第一次顯示以及以后每次調(diào)用 repaint() 函數(shù)，程序都會調(diào)用類中的paint，但是paint函數(shù)要完成整個圖形的繪制工作，為了簡單，對于繪制單個的方塊，我希望能夠單獨(dú)的封裝成一個函數(shù)，這樣對于設(shè)置默認(rèn)障礙時也可以很方便的進(jìn)行調(diào)用。那么就同樣要用到 paint 函數(shù)的Graphicsg參數(shù)，這個參數(shù)怎么傳遞給 drawNode函數(shù)呢？我首先想到了 getGraphics() 方法，getGraphics() 方法得到一個Graphics類的對象，這個對象和 update() 方法和paint() 方法中所傳遞的對象一樣，但是在 drawNode()函數(shù)中調(diào)用此方法獲得 Graphics對象后，并不能畫出圖形。解決方案，因為在相同的類中， paint( )方法已經(jīng)獲得了Graphics對象，我只需定義一個全局的Graphics對象用來接收paint 的參數(shù)即可，使剛進(jìn)入 paint 函數(shù)就用參數(shù)給全局的g_g賦值，這樣，drawNode函數(shù)可以直接利用 g_g畫出方塊了。分析，因為Mypanel類的對象剛創(chuàng)建的時候已經(jīng)調(diào)用象繪制圖形，而一旦在相同的類中再調(diào)用 getGraphics()象并不是一樣的。通過程序也獲得了驗證：

paint 函數(shù)獲得了方法，兩個獲得的

Graphics的對Graphics對g_g2=getGraphics();if(g_g==g_g2)// 其中g(shù)_g是通過paint 函數(shù)最開始進(jìn)行的賦值。{System.out.println("equal");}else{System.out.println("notequal");}程序打印的結(jié)果是notequal3.4.4程序主體界面MyPanel中paint函數(shù)做的工作1）g_g=g;給全局的Graphics對象賦值。2）通過drawLine()畫出各個方塊的輪廓。畫出說明文字，以及調(diào)用drawNode函數(shù)畫出實際的方塊。3）把openList中最小結(jié)點(diǎn)的下標(biāo)的結(jié)點(diǎn)顯示成白色。這樣可以在尋路的過程中更好的觀察哪個是OPEN鏈表中最小的結(jié)點(diǎn)，從而使使用者有清晰的思路。3.4.5主體界面類做的工作（1）定義自己的MyPanel，設(shè)置方塊的大小為50，畫出方塊，并將提示的文字顯示在Panel的右側(cè)。2）定義普通的Pane，用來盛放，單選按鈕以及按鈕。3）定義MyFrame，將MyPanel和Panel加入MyFrame。4）在MyFrame中初始化各個控件，并且給各個控件添加相應(yīng)的監(jiān)聽，這些監(jiān)聽包括MouseListener用于對鼠標(biāo)行為進(jìn)行監(jiān)聽，這里主要響應(yīng)了mousePressed()函數(shù)。itemListener相應(yīng)單選按鈕的狀態(tài)變化，我相應(yīng)的創(chuàng)建了一個標(biāo)志位，如果單選按鈕狀態(tài)發(fā)生變化，那么相應(yīng)的標(biāo)志位就設(shè)置成不同的值，以后在對鼠標(biāo)點(diǎn)擊進(jìn)行響應(yīng)的時候，只需根據(jù)這個標(biāo)志位的值進(jìn)行操作即可，其中包括設(shè)置起點(diǎn)，設(shè)置終點(diǎn)，設(shè)置障礙，清楚障礙的操作。ActionListener 是對actionPerformed 函數(shù)聯(lián)系，用來處理按鈕的狀態(tài)響應(yīng)處理， 其中包括直接尋路、單步尋路、動態(tài)尋路、重新尋路、添加默認(rèn)障礙這些操作。Runnable是用來實現(xiàn)多線程的接口，主要對“動態(tài)尋路”進(jìn)行操作。3.3.6鼠標(biāo)監(jiān)聽mouseClickedORmousePressed在設(shè)置監(jiān)聽時：對于鼠標(biāo)單擊方塊，改變方塊的顏色，起初我是放mouseClicked(MouseEvente)中進(jìn)行處理，但是效果不好，有時總是單擊幾下才能改變顏色，于是我把這種處理放在了mousePressed(MouseEvente)中處理，顯現(xiàn)效果好了。為什么會出現(xiàn)這樣的效果呢？難道 mouseClicked不是對單擊進(jìn)行的監(jiān)聽嗎？讓我們來看看鼠標(biāo)監(jiān)聽接口中的方法 :1）mousePressed()當(dāng)用戶按下鼠標(biāo)按鈕時發(fā)生.2）mouseReleased()當(dāng)用戶松開鼠標(biāo)按鈕時發(fā)生.3）mouseClicked()當(dāng)用戶按下并松開鼠標(biāo)按鈕時發(fā)生.用戶在選擇或雙擊圖標(biāo)的時候通常會點(diǎn)擊鼠標(biāo)按鈕.用戶如果在松開鼠標(biāo)之前移動鼠標(biāo),點(diǎn)擊不會導(dǎo)致鼠標(biāo)相應(yīng)事件出現(xiàn).（4）因為點(diǎn)擊鼠標(biāo)是按下鼠標(biāo)和松開鼠標(biāo)的結(jié)合 , 在事件分配給 mouseClicked() 方法之前, mousePressed() 和 mouseReleased() 方法已同時被調(diào)用.5）mouseEntered()當(dāng)鼠標(biāo)離開當(dāng)前組件并進(jìn)入你所監(jiān)聽的組件時激活事件.6）mouseExited()當(dāng)鼠標(biāo)離開你所監(jiān)聽的組件時發(fā)生.7）mouseDragged()當(dāng)用戶按下鼠標(biāo)按鈕并在松開之前進(jìn)行移動時發(fā)生.在mouseDragged() 后松開鼠標(biāo)不會導(dǎo)致 mouseClicked().（8）mouseMoved() 當(dāng)鼠標(biāo)在組件上移動而 不時拖動時發(fā)生問題

.3.4.2:

主線程與子線程的好了，當(dāng)看到 mouseClicked()函數(shù)的說明時，我們也就明白了。3.3.7動態(tài)尋路的演示在動態(tài)顯示尋路過程時，我起初只是想把單擊顯示的過程連續(xù)調(diào)用，然后加上Thread.Sleep(1000)，即可，但是在主線程中，總是顯示不出效果，實際的情況是，等一段時間之后，才立馬顯示出最后的尋路結(jié)果，這不是想要的效果，于是我另外創(chuàng)建了一個線程來單獨(dú)處理“動態(tài)尋路”的過程，在這個單獨(dú)的線程中，Thread.Sleep() 就起作用了。3.3.8設(shè)置起點(diǎn)的工作1）修改以前的起始點(diǎn)屬性為默認(rèn)點(diǎn)的屬性2）更改起始點(diǎn)的坐標(biāo)3）設(shè)置新起始點(diǎn)的屬性4）如果之前起始點(diǎn)的坐標(biāo)把終止點(diǎn)的坐標(biāo)覆蓋了，就應(yīng)該重新更新一下終止點(diǎn)的坐標(biāo)3.3.9設(shè)置終點(diǎn)的工作1）修改以前的終止點(diǎn)屬性為默認(rèn)點(diǎn)的屬性2）更改終止點(diǎn)的坐標(biāo)3）設(shè)置新終止點(diǎn)的屬性4）如果之前終止點(diǎn)的坐標(biāo)把起始點(diǎn)的坐標(biāo)覆蓋了，就應(yīng)該重新更新一下起始點(diǎn)的坐標(biāo)3.3.10找不到路徑的提示如果找不到路徑會彈出提示對話框“找不到最短路徑！請重新尋路。 ”，如下圖：圖3.5 找不到路徑的提示圖點(diǎn)擊確定后，就可以繼續(xù)重新尋路了。總結(jié)通過此次的畢業(yè)設(shè)計，我對于尋路算法有了更清晰的了解，也明白了只有通過自己動手的實踐才能更透徹的理解知識，以前對于A*算法，聽說過，但是感覺很神秘，很深奧，一直沒有勇氣去實踐中了解，這次的課程設(shè)計，我主動跟老師說想做這個，也抱著挑戰(zhàn)一下自己的決心開始了畢業(yè)設(shè)計項目的開發(fā)，對于java的知識，已經(jīng)忘得差不多了，尤其對于畫圖這一塊，當(dāng)時學(xué)的時候也沒有講多少，所以幾乎一切從0開始，從畫線到界面的布局，期間不斷的找資料學(xué)習(xí)，不斷的實踐，最后終于完成了，其實對于A*算法本身，并沒有費(fèi)很多的功夫，倒是用圖形的方式顯示出來的過程中，不斷的遇到技術(shù)上的難題。不過，通過實踐也都得到了解決。這次圖形的設(shè)計也得益于畢業(yè)實習(xí)那段時間我旁聽了java的一節(jié)課，那節(jié)課對于做出這個課題有了很大的啟發(fā)。在做這個課題的時候，發(fā)現(xiàn)網(wǎng)上已經(jīng)有一些A星算法的信息，給了我很多靈感，自己也感到真正的要把一件事情做好是很難的，為此在以后的學(xué)習(xí)工作過程中我也會繼續(xù)不斷的努力，爭取取得長足的進(jìn)步。致謝在歷時三個多月的畢業(yè)設(shè)計中，感謝我的指導(dǎo)教師劉博老師。在項目開發(fā)過程中他雖然由于讀博時間比較緊，但是依然嚴(yán)格要求自己抽出時間回校檢查我們的程序，對于我們的幫助他也是不煩不燥、耐心教導(dǎo)，幽默的風(fēng)格使我們交流順暢。總之，感謝所有幫助過我的老師，指導(dǎo)我的老師，所有教過我的老師，這是有了你們的辛勤耕耘，我才能有目前的進(jìn)步。感謝劉博老師，他一直是我的榜樣，學(xué)習(xí)的榜樣，工作的榜樣，他是我的目標(biāo)。我從劉博老師的身上看到了敬業(yè)，看到了努力，看到了幽默，看到了年輕，看到了快樂，看到了平凡。參考資料1）A星算法VC實現(xiàn)/shanshanpt/article/details/89775122）A星算法flash演示/fla/9419.shtml（3）孫晨霞 《Java程序設(shè)計教程》 中國計劃出版社出版 2007-084）維基百科A*算法偽代碼/wiki/A*%E6%90%9C%E5%AF%BB%E7%AE%97%E6%B3%955）李興華《JAVA開始實戰(zhàn)經(jīng)典》清華大學(xué)出版社2009-08-01（6）[美]?？藸?《java編程思想》 機(jī)械工業(yè)出版社 2007-06-017）明日科技《java從入門到精通》清華大學(xué)出版社2012-09-018）李剛《瘋狂java講義》電子工業(yè)出版社2012-01-01（9）[美]霍斯特曼，[美]科內(nèi)爾 陳昊鵬譯java 核心技術(shù)卷 I 機(jī)械工業(yè)出版社 2014-02-0110）A星算法介紹/zh-hans/21503/a%E6%98%9F%E5%AF%BB%E8%B7%AF%E7%AE%97%E6%B3%95%E4%BB%8B%E7%BB%8D基于C8051F單