【文章內(nèi)容簡(jiǎn)介】 前，游戲業(yè)界的標(biāo)準(zhǔn)是使用 A*算法或 IDA*算法， A*算法一般要快一些，而 IDA*算法則比 A*算法要使用更少的內(nèi)存。 總的來(lái)說(shuō)，游戲場(chǎng)景中的路徑搜索是一個(gè)非常復(fù)雜的問(wèn)題，通常情況下需要混合多種解決方 法并在實(shí)踐中不斷探索才能得到一個(gè)比較好的解決方案， 因此，在以后的計(jì)算機(jī)編程應(yīng)用中，搜索算法也 有 著深遠(yuǎn)的影響 [1]。 論文的主要工作和章節(jié)安排 在已有的搜索技術(shù)基礎(chǔ)上，通過(guò)自己 的探索和研究， 開(kāi)發(fā)一個(gè)游戲?qū)降脑拖到y(tǒng)，并 以直觀的方式展現(xiàn)搜索結(jié)果。 本論文共分為五章。 詳細(xì)討論了論文中所用到的相關(guān)理論以及作者所做的研究和開(kāi)發(fā)工作， 并結(jié)合一個(gè)具體的實(shí)例 ，實(shí)現(xiàn) A*算法。最后對(duì) A*算法給出評(píng)測(cè)， 并對(duì)其發(fā)展方向做出展望，提出參考性建議。 第一章，緒論。 主要介紹了研究的背景和意義，概括性的介紹了游戲人工智能的現(xiàn)狀 ，以及游戲路徑搜索算法的研究現(xiàn)狀，并闡述了本論文的研究?jī)?nèi)容和主要工作。 第二章，搜索 技術(shù)概述 。 本章首先 以 尋路問(wèn)題 引入 ，對(duì)尋路問(wèn)題中所 用到的 搜索策略做 簡(jiǎn)單介紹 ；然后 介紹幾種 搜索算法 。 第三章， A算法和 A*算法 。 詳細(xì)介紹 A算法和 A*算法 。 第四章， 游戲 尋徑系統(tǒng) 設(shè)計(jì)與實(shí)現(xiàn) 。本章主要結(jié)合 A*算法 開(kāi)發(fā) 游戲地圖系統(tǒng) ，并結(jié)合實(shí)例詳細(xì)講解 A*算法 。 第五章， 結(jié)論 。對(duì)論文所做的工作進(jìn)行總結(jié) 、存在問(wèn)題及解決方案 ， 給出 最后論文 結(jié)論 。 東南大學(xué)成賢學(xué)院畢業(yè)論文 3 第二章 搜索 技術(shù)概述 各種人工智能應(yīng)用領(lǐng)域 , 如知識(shí)庫(kù)專家系統(tǒng)、智能機(jī)器人、模式識(shí)別與物景 分析、自然語(yǔ)言理解與生成、機(jī)器博弈、定理證明、自動(dòng)程序設(shè)計(jì)等 , 都是利用知識(shí)進(jìn)行廣義的問(wèn)題求解的知識(shí)工程系統(tǒng)。它們都需要以知識(shí)表達(dá)、知識(shí)推理、知識(shí)獲取為基礎(chǔ)。其中知識(shí)表達(dá)和知識(shí)獲取是必要的前提條件 , 而知識(shí)推理是問(wèn)題求解的主要手段。在知識(shí)推理中主要包括推理方向及搜索技術(shù)等內(nèi)容。 搜索是人工智能中一個(gè)基本問(wèn)題 , 它直接關(guān)系到智能系統(tǒng)的性能與運(yùn)行效率 , 因而美國(guó)人工智能專家尼爾遜 ( N .J .Nils son ) ( 1974 年 ) 把它列為人工智能研究的四個(gè)核心問(wèn)題 (知識(shí)的模型化和表示 。 常識(shí)性推理、演繹和 問(wèn)題求解 。 啟發(fā)式搜索 。 人工智能系統(tǒng)和語(yǔ)言 )之一 [3]。 問(wèn)題的引入 在圖論中，尋徑問(wèn)題通常是人們研究的熱點(diǎn)問(wèn)題之一，其所要解決的問(wèn)題是如何設(shè)法從圖中尋找到一條從起點(diǎn)到目標(biāo)點(diǎn)的通路；而在網(wǎng)絡(luò)游戲中，地圖尋徑問(wèn)題并非如此簡(jiǎn)單，必須考慮多方面的因素，比如游戲地圖的文件結(jié)構(gòu)、中途是否可通等。 在游戲軟件中，地圖一般是由一塊塊小的方格圖片拼接而成的，組成地圖的圖片元素被稱為“瓷磚”。地圖編輯器將瓷磚按一定的規(guī)則“鋪”成一張完整的地圖，并將地圖組成規(guī)則保存在一個(gè)文件中，此文件被稱為地圖文件。游戲軟件運(yùn)行過(guò) 程中，當(dāng)切換到某個(gè)場(chǎng)景時(shí)，首先需要讀取地圖文件，其次按文件所提供的數(shù)據(jù)，在地圖方格內(nèi)放入相應(yīng)的瓷磚，最后把鋪好瓷磚的游戲地圖顯示在屏幕上。精靈在地圖上行走時(shí)，應(yīng)隨時(shí)判斷周邊的瓷磚是否可通，以便計(jì)算出下一步行走路線。 鑒于此，在遇到這類(lèi)問(wèn)題時(shí)，只能依靠經(jīng)驗(yàn)，利用已有知識(shí)逐步摸索求解，于是搜索策略在我們的日常生活運(yùn)用越來(lái)越廣 [4]。 搜索 技術(shù) 智能系統(tǒng)所要解決的問(wèn)題是各種各樣的 , 其中 , 大部分是結(jié)構(gòu)不良或非結(jié)構(gòu)化的問(wèn)題 , 對(duì)這樣的問(wèn)題一般沒(méi)有算法可以求解 , 而只能是利用已有的知識(shí)一步步地摸索前進(jìn)。在 此過(guò)程中 , 存在著如何尋找可用知識(shí)的問(wèn)題 , 即如何確定推理路線 , 使其付出的代價(jià)盡可能的少 , 而問(wèn)題又能得到較好的解決。例如在推理中 , 可能存在多條路線都可實(shí)現(xiàn)對(duì)問(wèn)題的求解 , 這就又存在按哪一條路線進(jìn)行求解以獲得較高的運(yùn)行效率的問(wèn)題。像這樣根據(jù)問(wèn)題的實(shí)際情況不斷尋找可利用的知識(shí) , 從而構(gòu)造一條代價(jià)較少的推理路線 ,使問(wèn)題得到圓滿解決的過(guò)程稱為搜索。在智能系統(tǒng)中 , 即使對(duì)于結(jié)構(gòu)性能較好、理論上有算法可依的問(wèn)題 , 由于問(wèn)題本身的復(fù)雜性以及計(jì)算機(jī)在時(shí)間、空間上的局限性 , 有時(shí)也需要通過(guò)搜索來(lái)求解。 對(duì)于搜索的類(lèi)型，可 根據(jù)搜索過(guò)程是否使用啟發(fā)式信息分為盲目搜索和啟發(fā)式搜索，也可根據(jù)問(wèn)題的表示方式分為狀態(tài)空間搜索和與 /或樹(shù)搜索。 盲目搜索是按預(yù)定 的控制策略進(jìn)行搜索，在搜索過(guò)程中獲得的中間信息并不改變控制策略，但 由于搜索總是按預(yù)先規(guī)定的路線進(jìn)行，沒(méi)有考慮到問(wèn)題本身的特性，因此這種搜索具有盲目性，效率不高，不便于復(fù)雜問(wèn)題的求解。啟發(fā)式搜索是在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。狀態(tài)空間搜索是指用狀態(tài)空間法來(lái)求解問(wèn)題所進(jìn)行的搜索。與 /或樹(shù)搜索是指用問(wèn)題歸約法來(lái)求解 問(wèn)題所進(jìn)行的搜索。狀態(tài)空間法和問(wèn)題歸約法是人工智能中最基本的兩種問(wèn)題求解方法，狀態(tài)空間表示法和與/或樹(shù)表示法則是人工智能中最基本的兩種問(wèn)題表示方法 [3][5]。 非啟發(fā)式搜索（ 盲目搜索 ） 盲目搜索 是指在問(wèn)題的求解過(guò)程中 , 不運(yùn)用啟發(fā)性知識(shí) , 只按照一般的邏輯法則或控制性知識(shí) , 在預(yù)定的控制策略下進(jìn)行搜索 , 在搜索過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略。由于搜索總是按預(yù)東南大學(xué)成賢學(xué)院畢業(yè)論文 4 先規(guī)定的路線進(jìn)行 , 沒(méi)有考慮到問(wèn)題本身的特性 , 這種方法缺乏對(duì)求解問(wèn)題的針對(duì)性 , 需要進(jìn)行全方位的搜索 , 而沒(méi)有選擇最優(yōu)的搜索途徑 , 因此 , 這種搜索具有盲目性 , 效率較低 , 容易出現(xiàn)“組合爆炸”問(wèn)題。 例如 , 寬度優(yōu)先搜索法 , 雖然是完備的算法 , 但是對(duì)于復(fù)雜問(wèn)題的求解 , 將出現(xiàn)“組合爆炸”問(wèn)題 , 其搜索效率低 , 需要對(duì)全部狀態(tài)空間進(jìn)行盲目搜索 [3]。 啟發(fā)式搜索 盲目搜索沒(méi)有利用問(wèn)題本身的特性信息，在決定要被擴(kuò)展的節(jié)點(diǎn)時(shí)，都沒(méi)有考慮該節(jié)點(diǎn)在解的路徑上的可能性有多大，它是否有利于問(wèn)題求解以及求出的解是否為最優(yōu)解等。 因此，我們引入啟發(fā)式搜索。 啟發(fā)式搜索是指在問(wèn)題的求解過(guò)程中 , 為了提高搜索效率 , 運(yùn)用與問(wèn)題有關(guān)的啟發(fā)性知識(shí) , 即解決問(wèn)題 的策略、技巧、竅門(mén)等實(shí)踐經(jīng)驗(yàn)和知識(shí) , 來(lái)指導(dǎo)搜索朝著最有希望的方向前進(jìn) ,加速問(wèn)題求解過(guò)程并找到最優(yōu)解 [3]。 例如 , 在圖搜索的方法中 , 利用啟發(fā)性知識(shí)改進(jìn)的深度優(yōu)先搜索法 , 如局部擇優(yōu)搜索法、全局擇優(yōu)搜索法等 , 只需要對(duì)局部狀態(tài)空間進(jìn)行搜索 , 可提高搜索效率。在本文中主要運(yùn)用 A*算法實(shí)現(xiàn)路徑搜索算法。 狀態(tài)空間法 對(duì)某個(gè)具體問(wèn)題 , 可經(jīng)過(guò)抽象變?yōu)槟硞€(gè)有向圖中尋找目標(biāo)或路徑的問(wèn)題。人工智能科學(xué)中 , 把這種描述問(wèn)題的有向圖稱為狀態(tài)空間圖 , 簡(jiǎn)稱狀態(tài)圖。其中狀態(tài)圖中的節(jié)點(diǎn)代表問(wèn)題的一種格局 , 一般稱為問(wèn)題的一個(gè)狀態(tài) 。 邊表示兩節(jié)點(diǎn)之間的某種聯(lián)系 , 如它可以是某種操作、規(guī)則、變換、算法 或關(guān)系等等。在狀態(tài)圖中 , 從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條路徑 , 或者所找的目標(biāo)節(jié)點(diǎn) , 就是相應(yīng)問(wèn)題的一個(gè)解。 在現(xiàn)實(shí)生活中 , 不論是智力問(wèn)題 ( 如梵塔問(wèn)題、旅行商問(wèn)題、八皇后問(wèn)題、農(nóng)夫過(guò)河問(wèn)題等 )還是實(shí)際問(wèn)題 (如定理證明、演繹推理、機(jī)器人行動(dòng)規(guī)劃等 )都可以歸結(jié)為在某一狀態(tài)圖中尋找目標(biāo)或路徑的問(wèn)題。所以 , 狀態(tài)圖是一類(lèi)問(wèn)題的抽象表示。 狀態(tài)空間法是人工智能中最基本的問(wèn)題求解方法，它所采用的問(wèn)題表示方法稱為狀態(tài)空間表示法。狀態(tài)空間法 的基本思想是用“狀態(tài)”和“操作”來(lái)表示并求解問(wèn)題 [12]。 1. 狀態(tài)空間表示法 在狀態(tài)空間表示法中，問(wèn)題是用“狀態(tài)”和“操作”來(lái)表示的，問(wèn)題求解過(guò)程是用“狀態(tài)空間”來(lái)表示的。 (1) 狀態(tài) 狀態(tài) (State)是表示問(wèn)題求解過(guò)程中每一步問(wèn)題狀況的數(shù)據(jù)結(jié)構(gòu)，它可形式地表示為： Sk={Sk0, Sk1, ?} 在這種表示方式中，當(dāng)對(duì)每一個(gè)分量都給以確定的值時(shí)，就得到了一個(gè)具體的狀態(tài)。實(shí)際上，任何一種類(lèi)型的數(shù)據(jù)結(jié)構(gòu)都可以用來(lái)描述狀態(tài)，只要它有利于問(wèn)題求 解，就可以選用。 (2) 操作 操作 (Operator)也稱為算符，它是把問(wèn)題從一種狀態(tài)變換為另一種狀態(tài)的手段。當(dāng)對(duì)一個(gè)問(wèn)題狀態(tài)使用某個(gè)可用操作時(shí)，它將引起該狀態(tài)中某些分量值的變化，從而使問(wèn)題從一個(gè)具體狀態(tài)變?yōu)榱硪粋€(gè)具體狀態(tài)。操作可以是一個(gè)機(jī)械步驟，一個(gè)運(yùn)算，一條規(guī)則或一個(gè)過(guò)程。操作可理解為狀態(tài)集合上的一個(gè)函數(shù)，它描述了狀態(tài)之間的關(guān)系。 (3) 狀態(tài)空間 狀態(tài)空間 (State Space)用來(lái)描述一個(gè)問(wèn)題的全部狀態(tài)以及這些狀態(tài)之間的相互關(guān)系。狀態(tài)空間常用一個(gè)三元組 東南大學(xué)成賢學(xué)院畢業(yè)論文 5 (S, F, G) 來(lái)表示。其中， S為問(wèn)題的所有初始狀態(tài)的集合； F為操作的集合； G為目標(biāo)狀態(tài)的集合。 狀態(tài)空間也可用一個(gè)賦值的有向圖來(lái)表示，該有向圖稱為狀態(tài)空間圖。在狀態(tài)空間圖中，節(jié)點(diǎn)表示問(wèn)題的狀態(tài)，有向邊表示操作。 2. 狀態(tài)空間問(wèn)題求解 任何以狀態(tài)和操作為基礎(chǔ)的問(wèn)題求解方法都可稱為狀態(tài)空間問(wèn)題求解方法，簡(jiǎn)稱狀態(tài)空間法。用狀態(tài)空間法求解問(wèn)題的基本過(guò)程是：首先為問(wèn)題選擇適當(dāng)?shù)摹盃顟B(tài)”及“操作”的形式化描述方法；然后從某個(gè)初始狀態(tài)出發(fā)，每次使用一個(gè)“操作”，遞增地建立起操作序列，直 到達(dá)到目標(biāo)狀態(tài)為止；最后，由初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是該問(wèn)題的一個(gè)解。 當(dāng)用狀態(tài)空間法解決問(wèn)題時(shí)，有以下兩個(gè)方面的因素需要考慮：一方面，對(duì)大問(wèn)題計(jì)算機(jī)無(wú)法保存其全部狀態(tài)空間；另一方面，對(duì)具體問(wèn)題與解有關(guān)的狀態(tài)空間一般僅是全部狀態(tài)空間的一部分。因此，在問(wèn)題求解過(guò)程中，沒(méi)有必要生成和保存該問(wèn)題的全部狀態(tài)空間，只要能夠生成和保存與解有關(guān)的那部分狀態(tài)空間即可。解決這一問(wèn)題的方法是采用狀態(tài)空間搜索技術(shù) [12]。 狀態(tài)空間的盲目搜索 狀態(tài)圖搜索 對(duì)狀態(tài)空間的搜索，由于問(wèn)題的狀態(tài)空間可用一個(gè)有向 圖來(lái)表示，因此狀態(tài)空間搜索實(shí)際上就是一個(gè)對(duì)有向圖的搜索。 圖搜索的基本思想 圖搜索就是一種在圖中尋找路徑的方法。這種尋找過(guò)程從圖中的初始節(jié)點(diǎn)開(kāi)始 , 至目標(biāo)節(jié)點(diǎn)為止。其中 , 初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別代表產(chǎn)生式系統(tǒng)的初始數(shù)據(jù)庫(kù)和滿足終止條件的數(shù)據(jù)庫(kù)。方法是先把問(wèn)題的初始狀態(tài)作為當(dāng)前狀態(tài) , 選擇適用的算符對(duì)其進(jìn)行操作 , 生成一組子狀態(tài) , 檢查目標(biāo)狀態(tài)是否在其中出現(xiàn)。若出現(xiàn) , 則搜索成功 , 找到了問(wèn)題的解 。 若不出現(xiàn) , 則按某種搜索策略從已生成的狀態(tài)中再選一個(gè)狀態(tài)作為當(dāng)前狀態(tài)。重復(fù)上述過(guò)程 , 直到目標(biāo)狀態(tài)出現(xiàn)或者不再 有可供操作的狀態(tài)及算符時(shí)為止 [3]。 圖搜索的一般過(guò)程 下面給出圖搜索的一般搜索過(guò)程。它是由尼爾遜 ( N .J .Nils son ) 提出的一個(gè)著名的圖搜索過(guò)程 GRAPHSEARCH , 它是表達(dá)能力很強(qiáng)的一個(gè)搜索策略框架。在此過(guò)程中要用到 OPEN 表和 CLOSED 表。其中 , OPEN 表用于存放剛生成的節(jié)點(diǎn) , 這些節(jié)點(diǎn)將作為以后待考察的對(duì)象。 OPEN 表是一個(gè)“ 有進(jìn)有出”的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。節(jié)點(diǎn)進(jìn)入 OPEN 表的排列順序 ( 也是出表的順序 )是由搜索策略決定 。 CLOSED 表用于存放將要擴(kuò)展或者已經(jīng)擴(kuò)展 的節(jié)點(diǎn) , 這些節(jié)點(diǎn)記錄著求解中的信息。 CLOSED 表是一個(gè)“有進(jìn)無(wú)出”的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) , 當(dāng)前節(jié)點(diǎn)進(jìn)入 CLOSED 表的最后。 OPEN 表和 CLOSED 表的結(jié)構(gòu)如圖 所示 [3]。 圖 OPEN 表和 CLOSED 表的結(jié)構(gòu) 圖搜索 ( GRAPHSEARCH )的一般過(guò)程如下 ： (1) 建立一個(gè)只含有初始節(jié)點(diǎn) S0 的搜索圖 G, 把 S0 放到 OPEN 表中。 (2) 建立 CLOSED 表 , 其初始為空表。 東南大學(xué)成賢學(xué)院畢業(yè)論文 6 (3) LOOP: 若 OPEN 表是空表 , 則問(wèn)題無(wú)解 , 失敗并退出。 (4) 把 OPEN 表上的第一個(gè)節(jié)點(diǎn)移出并放進(jìn) CLOSED 表的后面 , 標(biāo)記此節(jié)點(diǎn)為節(jié)點(diǎn) n(在CLOSED 表的編號(hào)欄標(biāo)記 )。 (5) 若 n 為一目標(biāo)節(jié)點(diǎn) , 則有解并成功退出 , 此解是追蹤圖 G 中沿著指針從 n 到 S0 這條路徑而得到的 (指針將在 (7)中設(shè)置 )。 (6) 擴(kuò)展節(jié)點(diǎn) n , 同時(shí)生成不是 n 的祖先的那些后繼節(jié)點(diǎn)的集合 M。把 M 的這些成員作為 n 的后繼節(jié)點(diǎn)添入圖 G 中。 (7) 對(duì)那些未曾在 G 中出現(xiàn)過(guò)的 (即未曾在 OPEN 表上或 CLOSED 表上出現(xiàn)過(guò)的 ) M 成員設(shè)置一個(gè)通向 n 的指針。把 M 的這些成員加進(jìn) OPEN 表。對(duì)已經(jīng)在 OPEN 表或 CLOSED 表上的每一個(gè) M 成員 , 確定是否需要更改通到 n 的指針?lè)较?。?duì)已在 CLOSED 表上的每一個(gè) M 成員 , 確定是否需要更改圖 G 中通向它的每一個(gè)后繼節(jié)點(diǎn)的指針?lè)较颉? (8) 按某種搜索策略或按某個(gè)探試值 , 重排 OPEN 表。 (9) 轉(zhuǎn) LOOP 。 上述過(guò)程生成一個(gè)顯式圖 G(稱為搜索圖 ) , 由返回指針確定 G 的子圖 T ( 稱為搜索樹(shù) ) ,OPEN 表中的節(jié)點(diǎn)是 T 的葉節(jié)點(diǎn)。 在第 (7 )步中改變返回指針的原則是 : 節(jié)點(diǎn)有多個(gè)父節(jié)點(diǎn)時(shí) , 返回指針指向代價(jià)最小的父節(jié)點(diǎn)。 對(duì)上述搜索過(guò)程需作如下幾點(diǎn)說(shuō)明： (1) 上述過(guò)程是狀態(tài)空間的一般圖搜索算法，它具有通用性，后面所要討論的 A算法和 A*算法狀態(tài)空間搜索策略都是上述過(guò)程的一個(gè)特例。各種搜索策