计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (1): 104-104.

• 产品、研发、测试 • 上一篇    下一篇

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

徐洪智,李仁发,颜一鸣   

  1. 吉首大学信息管理与工程学院
  • 收稿日期:2006-04-26 修回日期:1900-01-01 出版日期:2007-01-01 发布日期:2007-01-01
  • 通讯作者: 徐洪智 xuhongzhi

Application of Branch-and-Bound Algorithm in Path-Finding for the Map of Game

HongZhi XU,,   

  1. 吉首大学信息管理与工程学院
  • Received:2006-04-26 Revised:1900-01-01 Online:2007-01-01 Published:2007-01-01
  • Contact: HongZhi XU

摘要: 分析了游戏地图寻径中的宽度优先,深度优先和启发式搜索算法,提出了一种基于宽度优先直接标记路径的分支限界搜索算法,最多使用O(N+L)的时间完成最短路径搜索,能很好的适用游戏地图中复杂地形的寻径要求。

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

Abstract: Analyzed the algorithm of breadth-first, depth-first and heuristic-Search in path-finding for the map of game, put 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 requirements for game map with complicated landform.

Key words: game map, path, Branch-and-Bound, search