分支限界法在游戏地图寻径中的应用  

Application of branch-and-bound algorithm in path-finding for the map of game

作　　者：徐洪智[1] 李仁发[1] 颜一鸣[1] 

机构地区：[1]湖南大学计算机与通信学院

出　　处：《计算机工程与应用》2007年第1期104-106,共3页Computer Engineering and Applications

基　　金：国家863高技术研究发展计划资助项目(2003AA-8-TS-01);湖南省自然科学基金资助项目(05JJ40007)。

摘　　要：分析了游戏地图寻径中的宽度优先,深度优先和启发式搜索算法,提出了一种基于宽度优先直接标记路径的分支限界搜索算法,最多使用O(N+L)的时间完成最短路径搜索,能很好地适用游戏地图中复杂地形的寻径要求。This paper analyzes the algorithm of breadth-first,depth-first and heuristic-search in path-finding for the map of game,puts forward the Branch-and-Bound algorithm marking path directly based on breadth-first,the algorithm can find the shortest path by using O（N＋L） at most,and can meet the path-finding requiremeras for game map with complicated landform.

关 键 词：游戏地图 路径 分支限界 搜索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]