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

摘要：

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 HPA* or our method suits.

关键词： path-finding A* HPA* minimal rectangle computer game

作者: Yan Li Tiesong Li Cai Chen

作者单位: Machine Learning Center, Faculty of Mathematics and Computer Science, Hebei University Baoding City, Hebei Province, China

会议类型: 国际会议

会议名称: 2010 International Conference on Circuit and Signal Processing(2010年电路与信号处理国际会议 ICCSP 2010)

会议地点: 上海

会议语种:英文

页码: 111-114

在线出版日期: 2010-12-25（万方平台首次上网日期，不代表论文的发表时间）