A Path-finding Algorithm Based on Minimal-Rectangle-Closure Partition

被引：0

作者：

Li, Yan ^{[1
]}

Li, Tiesong ^{[1
]}

Chen, Cai ^{[1
]}

机构：

[1] Hebei Univ, Fac Math & Comp Sci, Machine Learning Ctr, Baoding City, Hebei Province, Peoples R China

来源：

2011 AASRI CONFERENCE ON APPLIED INFORMATION TECHNOLOGY (AASRI-AIT 2011), VOL 1 | 2011年

关键词：

path-finding; A*; HPA*; minimal rectangle; computer game;

D O I：

暂无

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Path-finding is an important part of Game AI and we give a general introduction of two popular path-finding algorithms: A* and HPA* in this paper. HPA* which is based on hierarchical searching has obviously reduced the store and time cost of A*. However, HPA* does not consider the terrain information when partitioning maps, lowering the path-finding optimal degree in open areas. We present a method based on finding a minimal rectangle which can cover the obstacles. By doing this, large open area changes into a few rectangle clusters of which number is smaller than that of HPA*. In such clusters, path-finding can be done like the beeline path-finding. At last, we point out the very kind of maps IPA* or our method suits.

引用

页码：114 / 117

页数：4