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

雷文杰

摘要：游戏寻径一直是游戏地图编辑器研究领域的热门的话题，如何提高寻径速度，提高寻径智能表现是其主要的研究目的。现有的诸多算法已经成熟的应用于游戏地图编辑器，然而智能搜索算法在游戏地图寻径中的应用却是很少。该文阐述了遗传算法（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蛮力法

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