基于A*算法的游戏地图寻路实现及性能比较

被引：43

作者：

邱磊

机构：

[1] 武汉船舶职业技术学院电子系

来源：

陕西科技大学学报(自然科学版) | 2011年 / 29卷 / 06期

关键词：

游戏地图; 地图划分; 寻路; A*算法; 启发式函数;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

140502 [人工智能];

摘要：

在A*算法描述的基础上,给出了基于分层寻路思想的A*算法优化方法及划分游戏地图的6种方式.针对26×20=520个节点的游戏地图,利用栅格法按8方向连接对游戏地图进行了划分,分别采用Dijkstra算法、双向宽度优先搜索算法、A*(曼哈顿距离)算法、A*(欧氏距离)算法、A*(切比雪夫距离)算法和动态A*算法5种算法进行了寻路仿真实验,对比分析了各种寻路算法的性能.实验结果表明A*算法是各种寻路算法中扩展节点数量最少和计算耗时最短的一种算法;当采用不同的启发式函数,A*寻路时扩展的节点数量也不同,因此选择一个高效的启发式函数对A*算法是至关重要的.

引用

页码：89 / 93

页数：5

共 5 条

[1]

游戏领域中启发式寻径算法的运用和优化 [D].

靳旭栋 .

华东师范大学,

2007

[2]

双层A*算法在游戏寻路方面的研究 [J].

蔡方方 ;

杨士颖 ;

张小凤 ;

刘东平 .

微型电脑应用, 2010, 26 (01) :26-28+5

[3]

人工智能.[M].马少平;朱小燕编著;.清华大学出版社.2004,

[4]

游戏编程精粹.[M].(美)MarkA.Deloura编;袁国忠;陈蔚译;.人民邮电出版社.2003,

[5]

游戏的设计与开发.[M].叶展;叶丁编著;.航空工业出版社.2003,

← 1 →