Pathfinding improved algorithm in game

doi:10.3778/j.issn.1002-8331.2009.23.011

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (23): 38-39.DOI: 10.3778/j.issn.1002-8331.2009.23.011

• 研究、探讨 • Previous Articles Next Articles

Pathfinding improved algorithm in game

DONG Gai-fang¹，XU Dao-yun²

1.College of Computer and Information Engineering，Inner Mongolia Agricultural University，Hohhot 010018，China
2.College of Computer Science & Technology，Guizhou University，Guiyang 550025，China

Received:2008-10-10 Revised:2008-11-21 Online:2009-08-11 Published:2009-08-11
Contact: DONG Gai-fang

游戏中寻找路径的改进算法

董改芳¹，许道云²

1.内蒙古农业大学计算机与信息工程学院，呼和浩特 010018
2.贵州大学计算机科学与技术学院，贵阳 550025

通讯作者: 董改芳

Abstract

Abstract: By analyzing A*algorithm，desigh and implement improved A*algorithm which represented by indexed array and binary heap.Comparing with the algorithm represented by indexed array the algorithm can save 11% searching time.

Key words: pathfinding algorithm, A* algorithm, artificial inteligence, indexed arrays, binary heaps

摘要： 通过分析A*算法，设计并实现用索引数组和二叉堆表示开放列表的A*改进算法。该算法与用索引数组表示的开放列表相比，可以节省约11%的运行时间。

关键词: 寻径算法, A*算法, 人工智能, 索引数组, 二叉堆

CLC Number:

TP301

DONG Gai-fang¹，XU Dao-yun². Pathfinding improved algorithm in game[J]. Computer Engineering and Applications, 2009, 45(23): 38-39.

董改芳¹，许道云². 游戏中寻找路径的改进算法[J]. 计算机工程与应用, 2009, 45(23): 38-39.

[1]	KONG Jili, ZHANG Pengkun, LIU Xiaoping. Research on Improved A* Algorithm of Bidirectional Search Mechanism [J]. Computer Engineering and Applications, 2021, 57(8): 231-237.
[2]	HUAI Chuangfeng, GUO Long, JIA Xueyan, ZHANG Zihao. Improved A* Algorithm and Dynamic Window Method for Robot Dynamic Path Planning [J]. Computer Engineering and Applications, 2021, 57(8): 244-248.
[3]	HAN Xiaowei, HAN Zhen, YUE Gaofeng, CUI Jianjiang. Path Planning Algorithm of Disaster Relief UAV Based on Optimized A [J]. Computer Engineering and Applications, 2021, 57(6): 232-238.
[4]	ZHAO Wei, WU Ziying. Dynamic Path Planning Based on Bilevel Optimization A* Algorithm and Dynamic Window Method [J]. Computer Engineering and Applications, 2021, 57(22): 295-303.
[5]	LIU Zihao, ZHAO Jin, LIU Chang, LAI Kuncheng, WANG Xiqiao. Path Planning of Indoor Mobile Robot Based on Improved A* Algorithm [J]. Computer Engineering and Applications, 2021, 57(2): 186-190.
[6]	WANG Xiaojun, WANG Bo, YANG Chunxia, JIN Minjie, CHEN Haibo. AGV Path Planning and Collision Avoidance Strategy for Compact and Dense Auto Store System [J]. Computer Engineering and Applications, 2021, 57(15): 259-270.
[7]	LIU Jianjuan, XUE Liqi, ZHANG Huijuan, LIU Zhongpu. Robot Dynamic Path Planning Based on Improved A* and DWA Algorithm [J]. Computer Engineering and Applications, 2021, 57(15): 73-81.
[8]	WANG Baojian, HU Dasha, JIANG Yuming. Application of Improved A* Algorithm in Path Planning [J]. Computer Engineering and Applications, 2021, 57(12): 243-247.
[9]	HUA Hong, ZHANG Zhi’an, SHI Zhenwen, CHEN Guanxing. Robot Path Planning Method of Multiple A* Algorithm in Dynamic Environment [J]. Computer Engineering and Applications, 2021, 57(10): 173-180.
[10]	YUAN Yang, YE Feng, LAI Yizong, ZHAO Yuting. Multi-AGV Path Planning Combined with Load Balancing and A* Algorithm [J]. Computer Engineering and Applications, 2020, 56(5): 251-256.
[11]	WANG Fan, LI Tiejun, LIU Jinyue, ZHAO Haiwen. Research on Autonomous Path Planning and Obstacle Avoidance of Building Robot Based on BIM [J]. Computer Engineering and Applications, 2020, 56(17): 224-230.
[12]	HU Weimin, JIN Wenzhou. Multi-AGV Path Planning Based on Improved Smooth A* Algorithm [J]. Computer Engineering and Applications, 2020, 56(16): 204-210.
[13]	ZHONG Zhifeng, YI Mingxing, CHEN Zhijun, TAN Pu, ZENG Zhangfan. Method of Shopping Guide Path Planning Based on Modified A* Algorithm [J]. Computer Engineering and Applications, 2019, 55(5): 129-134.
[14]	WU Peng, SANG Chengjun, LU Zhonghua, YU Shuang, FANG Linyang, ZHANG Yi. Research on Mobile Robot Path Planning Based on Improved A* Algorithm [J]. Computer Engineering and Applications, 2019, 55(21): 227-233.
[15]	HAO Qinzhi, ZHOU Zhongliang, ZHANG Yu. Comprehensive path planning in penetration phase under standoff jamming [J]. Computer Engineering and Applications, 2017, 53(20): 95-99.

Pathfinding improved algorithm in game

游戏中寻找路径的改进算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics