雷文杰

摘要：游戲?qū)揭恢笔怯螒虻貓D編輯器研究領域的熱門的話題，如何提高尋徑速度，提高尋徑智能表現(xiàn)是其主要的研究目的?，F(xiàn)有的諸多算法已經(jīng)成熟的應用于游戲地圖編輯器，然而智能搜索算法在游戲地圖尋徑中的應用卻是很少。該文闡述了遺傳算法（GA）在地圖尋徑問題中的實現(xiàn)，對于算法的處理過程進行了較詳細的描述。

關鍵詞：地圖尋徑；遺傳算法；人工智能；游戲地圖編輯器

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2012)16-3938-02

Map Routing Problem of Game Based on Genetic Algorithm

LEI Wen-jie

(Network Center, Changchun House Exchange Co., Ltd.,Changchun 130041,China)

Abstract: Routing game map editor has been a hot research topic. How to improve the routing speed,Intelligent routing to improve per? formance is the main purpose of the study. Many existing algorithms have been applied to a mature game map editor. However, artificial in? telligence search algorithms used in the game of the map is very small. In this paper, genetic algorithm is used to search route in game map editor, the algorithm is described.

Key words: map routing; GA; AI; game map editor

電子游戲的迅猛發(fā)展，游戲制作對游戲地圖編輯器的要求也在不斷的變化，更新，提高，將來只有具備更快，更穩(wěn)定，更智能的地圖編輯器才能使游戲制作變得更加的適合，做出來的游戲才能更加智能化，更加的完美。當前大多數(shù)游戲的需求都能被現(xiàn)在得游戲地圖編輯器所滿足，然而伴隨著技術的成熟發(fā)展，游戲玩家對游戲的追求變得很高，簡單的地圖編輯器將不在能滿足未來的游戲模式，如果地圖編輯器的發(fā)展不好將不會利于游戲的發(fā)展。

該文研究了地圖中的尋徑問題，將遺傳算法應用在游戲地圖尋徑，希望找到一種快速高效穩(wěn)定的算法使得尋徑更優(yōu)。

并重復上述過程，一直到所有的結(jié)點都被發(fā)現(xiàn)，否則將反復進行上述過程。2.4蠻力法

蠻力法也叫窮舉法，暴力法，蠻力法要求設計者找出所有可能的方法，然后選擇其中的一種方法，若該方法不可行則試探下一種可行的方法。蠻力法也是一種直接解決問題的方法，常常直接基于問題的描述和所涉及的概念定義。

蠻力法的優(yōu)點是邏輯清晰，編寫程序簡潔。相對于高效的，巧妙的算法，蠻力法編寫的程序簡單，可能更快解決問題。同時蠻力法也是很多算法的基礎，可以在蠻力法的基礎上加以優(yōu)化，得到更高效的算法。2.5啟發(fā)式搜索

我們在靜態(tài)路網(wǎng)中求解最短路徑時會用到啟發(fā)式搜索算法。通過正確的使用，此算法一定可以發(fā)現(xiàn)兩點間的最優(yōu)路徑而且效率也是會非常高的。2.6遺傳算法

遺傳算法（GA）是模擬了達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，它模擬了自然進化的過程來搜索最優(yōu)解的一種方法。GA是一類隨機化搜索方法，它的主要特點是直接操作結(jié)構(gòu)對象，不存在限定求導和函數(shù)連續(xù)性這些條件；具有很好的并行性和更好的全局尋優(yōu)能力；采用了概率化的尋優(yōu)方法，它能夠自動的獲取和指導優(yōu)化的搜索空間，自適應地去調(diào)整搜索方向，而不需要確定一些規(guī)則。正因為遺傳算法的這些優(yōu)點，已經(jīng)被廣泛地應用于許多領域，如組合優(yōu)化、機器學習、信號處理、自適應控制和人工生命等領域。它同樣也是現(xiàn)代有關智能計算中的重要技術。

遺傳操作包括以下三個基本遺傳算子：選擇、交叉(crossover)、變異。

1）選擇：從群體中選擇優(yōu)勝的個體，淘汰劣質(zhì)個體的操作叫選擇。選擇的目的是把優(yōu)化的個體(或解)直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。

2）交叉：所謂交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。交叉算子根據(jù)交叉率將種群中的兩個個體隨機地交換某些基因，能夠產(chǎn)生新的基因組合，期望將有益基因組合在一起。

3）變異：變異算子的基本內(nèi)容是對群體中的個體串的某些基因座上的基因值作變動。遺傳算法導引入變異的目的有兩個，一是使遺傳算法具有局部的隨機搜索能力，二是使遺傳算法可維持群體多樣性，以防止出現(xiàn)未成熟收斂現(xiàn)象。

[2] Akgun V,Erkut E,Batta R.On finding dissimilar paths[J].European Journal of Operational Research,2000,121(2):232-246.

[3]胡小兵,葉吉祥.定點距離最優(yōu)化的遺傳算法研究[J].計算機工程與科學, 2003,25(2):5-6.

[4]徐瓊,陳榮清,官云蘭,等.基于遺傳算法最短路徑問題的探討[J].華東地質(zhì)學院學報,2003,26(2):168-172.

[5]王小平,曹立明.遺傳算法——理論、應用與軟件實現(xiàn)[M].西安:西安交通大學出版社,2002.

[6]陳曦,蔡輝,柳林.基于遺傳算法的路徑安排[J].長沙交通學院學報,2005,21(4):76-80.

[7]周明,孫樹棟.遺傳算法原理及應用[M].北京:國防工業(yè)出版社,1999.

[8]李擎,張偉,尹怡欣,等.一種用于最優(yōu)路徑規(guī)劃的改進遺傳算法[J].信息與控制, 2006,35(4):444-447.

[9]王敬東.游戲地圖尋徑及地圖編輯器的研究[D].長春:東北電力大學,2008.

[10]唐立新.旅行商問題(TSP)的改進遺傳算法[J].東北大學學報,1998 (1).

[11]王正志,薄濤.進化計算[M].北京：國防科技大學出版社,2000.

[12]熊盛武,方志祥.遺傳算法在地理信息系統(tǒng)領域中的作用[J].測繪通報,2002 (1):47-49.

[13]徐瓊,陳榮清,官云蘭,等.基于遺傳算法最短路徑問題的探討[J].華東地質(zhì)學院學報,2003(2):168-172.