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

Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (1): 104-104.

• 产品、研发、测试 • Previous Articles Next Articles

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

HongZhi XU,,

吉首大学信息管理与工程学院

Received:2006-04-26 Revised:1900-01-01 Online:2007-01-01 Published:2007-01-01
Contact: HongZhi XU

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

徐洪智,李仁发,颜一鸣

吉首大学信息管理与工程学院

通讯作者: 徐洪智 xuhongzhi

Abstract

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

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

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

HongZhi XU,,. Application of Branch-and-Bound Algorithm in Path-Finding for the Map of Game[J]. Computer Engineering and Applications, 2007, 43(1): 104-104.

徐洪智,李仁发,颜一鸣. 分支限界法在游戏地图寻径中的应用[J]. 计算机工程与应用, 2007, 43(1): 104-104.

[1]	SI Yanna, PU Jiexin, SUN Lifan. Review of Research on Approximate Reinforcement Learning Algorithms [J]. Computer Engineering and Applications, 2022, 58(8): 33-44.
[2]	CHEN Bowen, ZOU Hai. Self-Conclusion and Self-Adaptive Variation Particle Swarm Optimization [J]. Computer Engineering and Applications, 2022, 58(8): 67-75.
[3]	ZHAO Jiang, MENG Chenyang, WANG Xiaobo, HAO Chongqing, LI Ran, LIU Huixian, WANG Zhaolei. Modeling and Analysis of AGV Grid Method Based on Feature Points Extraction [J]. Computer Engineering and Applications, 2022, 58(8): 156-167.
[4]	GUO Xiaojing, YANG Zhuocheng. Improved A* Algorithm Based on Neighbor Extension in Static Environment [J]. Computer Engineering and Applications, 2022, 58(8): 168-174.
[5]	WANG Wei, PU Yiwen. Classification Method of Hypertensive Retinopathy Based on Regional Feature Fusion [J]. Computer Engineering and Applications, 2022, 58(8): 230-236.
[6]	DAI Wanyu, ZHANG Lijuan, WU Jiafeng, MA Xianghua. Research on Local Path Planning Algorithm Based on Improved TEB Algorithm [J]. Computer Engineering and Applications, 2022, 58(8): 283-288.
[7]	HU Xiaobing, MENG Xiangzhi. Many-to-Many Path Planning Method for Material Distribution Under Dynamic Disaster Environment [J]. Computer Engineering and Applications, 2022, 58(8): 297-306.
[8]	LIU Aobo, YUAN Jie. Robot Path Planning Based on Goal Biased Bidirectional RRT* Algorithm [J]. Computer Engineering and Applications, 2022, 58(6): 234-240.
[9]	LIU Shuangshuang, HUANG Yiqing. Application of Multi-strategy Ant Colony Algorithm in Robot Path Planning [J]. Computer Engineering and Applications, 2022, 58(6): 278-286.
[10]	YANG Zhou, LIU Haibin. AGV Dynamic Path Planning Based on Improved Ant Colony Algorithm and Dynamic Window Approach [J]. Computer Engineering and Applications, 2022, 58(6): 287-295.
[11]	TANG Xuhui, XIN Shaojie. Improved Ant Colony Algorithm for Mobile Robot Path Planning [J]. Computer Engineering and Applications, 2022, 58(5): 287-295.
[12]	OUYANG Chengtian, ZHOU Kai. Teaching-Learning Based Optimization Algorithm with Improved Beetle Antennae Search [J]. Computer Engineering and Applications, 2022, 58(4): 91-99.
[13]	ZHOU Xiaohan, WANG Xiuhui. Novel Gait Recognition Method Based on Asymmetric Two-Path Network [J]. Computer Engineering and Applications, 2022, 58(4): 150-156.
[14]	CAO Jianqiu, ZHANG Guangyan, XU Peng. A* Initialized Mutable Gray Wolf Optimizer for UAV Path Planning [J]. Computer Engineering and Applications, 2022, 58(4): 275-282.
[15]	YAN Jun, CHANG Le, FENG Lihua. Online Order Batching and Picking Path Planning Model and Algorithm [J]. Computer Engineering and Applications, 2022, 58(4): 283-289.

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

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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics