论文部分内容阅读
在商业计算机游戏中，路径搜索的性能直接影响玩家的感受及其对游戏的满意程度。并且游戏中的路径规划常常受到计算机内存和CPU资源的限制。在动态性环境中，角色必须对随时可能变化的地形做出即时反应，需要搜索方法具有较强重规划能力。标准A*算法的时间复杂度高，内存耗费大；HPA*算法在空旷区域的路径曲折，并仍需要较大存储；LPA*算法最差情况下搜索节点数很多。本文在传统的路径搜索算法A*，HPA*，LPA*等基础上，针对游戏地图路径搜索中存在的以上问题进行了研究，改善了几个算法的性能。具体来说，本研究工作主要分为以下两部分：1.提出了不均匀分区的分层路径搜索KM-A*方法。KM-A*参照聚类结果对地图进行不均匀分区，能够体现不同地图障碍物分布特点，使用A*在抽象图上找到路径后，再使用A*或Bresenham直线算法细化，适用于静态环境路径搜索。2.提出了分层动态路径搜索HPLPA*方法。HPLPA*首先在抽象图上使用LPA*初次搜索，当地形发生变化后，使用A*更新抽象图，然后在更新后的抽象图上进行LPA*路径快速重规划，找到的抽象路径再使用A*细化为本地路径，适用于动态环境路径搜索。我们分别在地图发生器上随机生成和博德之门II的共60多幅游戏地图上进行了实验，对几种算法的平均在线搜索时间，平均路径长度，平均搜索节点数等进行了对比。实验证明了本文提出的方法的有效性。