基于遗传算法的游戏地图寻径问题

摘要：游戏寻径一直是游戏地图编辑器研究领域的热门的话题，如何提高寻径速度，提高寻径智能表现是其主要的研究目的。现有的诸多算法已经成熟的应用于游戏地图编辑器，然而智能搜索算法在游戏地图寻径中的应用却是很少。该文阐述了遗传算法（GA）在地图寻径问题中的实现，对于算法的处理过程进行了较详细的描述。

关键词：地图寻径；遗传算法；人工智能；游戏地图编辑器

中图分类号：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

电子游戏的迅猛发展，游戏制作对游戏地图编辑器的要求也在不断的变化，更新，提高，将来只有具备更快，更稳定，更智能的地图编辑器才能使游戏制作变得更加的适合，做出来的游戏才能更加智能化，更加的完美。当前大多数游戏的需求都能被现在得游戏地图编辑器所满足，然而伴随着技术的成熟发展，游戏玩家对游戏的追求变得很高，简单的地图编辑器将不在能满足未来的游戏模式，如果地图编辑器的发展不好将不会利于游戏的发展。

该文研究了地图中的寻径问题，将遗传算法应用在游戏地图寻径，希望找到一种快速高效稳定的算法使得寻径更优。

并重复上述过程，一直到所有的结点都被发现，否则将反复进行上述过程。2.4蛮力法

蛮力法也叫穷举法，暴力法，蛮力法要求设计者找出所有可能的方法，然后选择其中的一种方法，若该方法不可行则试探下一种可行的方法。蛮力法也是一种直接解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。

蛮力法的优点是逻辑清晰，编写程序简洁。相对于高效的，巧妙的算法，蛮力法编写的程序简单，可能更快解决问题。同时蛮力法也是很多算法的基础，可以在蛮力法的基础上加以优化，得到更高效的算法。2.5启发式搜索

我们在静态路网中求解最短路径时会用到启发式搜索算法。通过正确的使用，此算法一定可以发现两点间的最优路径而且效率也是会非常高的。2.6遗传算法

遗传算法（GA）是模拟了达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，它模拟了自然进化的过程来搜索最优解的一种方法。GA是一类随机化搜索方法，它的主要特点是直接操作结构对象，不存在限定求导和函数连续性这些条件；具有很好的并行性和更好的全局寻优能力；采用了概率化的寻优方法，它能够自动的获取和指导优化的搜索空间，自适应地去调整搜索方向，而不需要确定一些规则。正因为遗传算法的这些优点，已经被广泛地应用于许多领域，如组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它同样也是现代有关智能计算中的重要技术。

遗传操作包括以下三个基本遗传算子：选择、交叉(crossover)、变异。

1）选择：从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。

2）交叉：所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。

3）变异：变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。遗传算法导引入变异的目的有两个，一是使遗传算法具有局部的随机搜索能力，二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。

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

[3]胡小兵,叶吉祥.定点距离最优化的遗传算法研究[J].计算机工程与科学, 2003,25(2):5-6.

[4]徐琼,陈荣清,官云兰,等.基于遗传算法最短路径问题的探讨[J].华东地质学院学报,2003,26(2):168-172.

[5]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002.

[6]陈曦,蔡辉,柳林.基于遗传算法的路径安排[J].长沙交通学院学报,2005,21(4):76-80.

[7]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.

[8]李擎,张伟,尹怡欣,等.一种用于最优路径规划的改进遗传算法[J].信息与控制, 2006,35(4):444-447.

[9]王敬东.游戏地图寻径及地图编辑器的研究[D].长春:东北电力大学,2008.

[10]唐立新.旅行商问题(TSP)的改进遗传算法[J].东北大学学报,1998 (1).

[11]王正志,薄涛.进化计算[M].北京：国防科技大学出版社,2000.

[12]熊盛武,方志祥.遗传算法在地理信息系统领域中的作用[J].测绘通报,2002 (1):47-49.

[13]徐琼,陈荣清,官云兰,等.基于遗传算法最短路径问题的探讨[J].华东地质学院学报,2003(2):168-172.