基于遺傳算法的游戲地圖尋徑問題

雷文杰

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

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

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：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)定，更智能的地圖編輯器才能使游戲制作變得更加的適合，做出來的游戲才能更加智能化，更加的完美。當(dāng)前大多數(shù)游戲的需求都能被現(xiàn)在得游戲地圖編輯器所滿足，然而伴隨著技術(shù)的成熟發(fā)展，游戲玩家對游戲的追求變得很高，簡單的地圖編輯器將不在能滿足未來的游戲模式，如果地圖編輯器的發(fā)展不好將不會利于游戲的發(fā)展。

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

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

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

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

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

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

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

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

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

3）變異：變異算子的基本內(nèi)容是對群體中的個體串的某些基因座上的基因值作變動。遺傳算法導(dǎo)引入變異的目的有兩個，一是使遺傳算法具有局部的隨機(jī)搜索能力，二是使遺傳算法可維持群體多樣性，以防止出現(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]胡小兵,葉吉祥.定點(diǎn)距離最優(yōu)化的遺傳算法研究[J].計(jì)算機(jī)工程與科學(xué), 2003,25(2):5-6.

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

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

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

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

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

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

[10]唐立新.旅行商問題(TSP)的改進(jìn)遺傳算法[J].東北大學(xué)學(xué)報(bào),1998 (1).

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

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

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