分层路径搜索算法研究

吕龙辉+靳红霞

摘要：自动寻路算法是智能游戏中的重要组成部分，通过对现有自动寻路算法的分析，了解目前已有自动寻路算法所存在的不足。基于地图划分的思想设计分层路径搜索算法，通过将地图细分，计算细分区域中抽象节点的最短路径，在地图加载过程中，实现地图的预处理，从而在确定了路径起始点和结束点之后，快速实现自动寻路。

关键词：自动寻路算法；地图细分；抽象图

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）30-0066-02

1 概述

随着信息技术的发展，游戏的画面质量不断提高，角色技能越来越丰富，当游戏的画面质量和角色技能发展到一定阶段之后，单纯的提高游戏画面效果和角色已经难以满足玩家的需求，而游戏的难易程度、趣味性和操作游戏就成为了智能游戏的研究热点。

自动寻路是智能游戏中非常重要的组成部分，传统的A*自动寻路算法通过剪枝优化自动寻路搜索进程，最终找到一条路径起点和终点之间的最短路径。但A*的空间复杂度较高，在大地图上的自动寻路效果较差。而M-A*、HPA*算法通过对地图的多尺度划分来缩小搜素空间，提高了自动寻路算法效率，但是降低了所寻路径的最优程度。

2 自动寻路算法优化思路

目前，大多数的自动寻路算法都未考虑地图中障碍物的分布问题，而且相同自动寻路算法的性能在不同障碍物分布地图上的差别较大。Dijkstra和A*算法的难以满足大地图自动寻路算法的性能要求；HPA*算法未考虑地形信息，降低最终路径的最有程度；M-A*仅的分区仅考虑起点和终点的区域信息，导致每一次自动寻路都需要重新分区，造成性能降低；Quadtree算法的抽象节点较多，终止条件过于严格，内存耗费严重。

针对目前主流自动寻路算法所存在的不足，提出一种考虑地图分布信息的分层路径搜索算法，通过对地图的分区，根据区域中障碍物的分布情况来选择合适的自动寻路算法来设计寻找路径，进而提高整个自动寻路算法的性能。

3 分层路径搜索算法设计

分层路径搜索算法根据大地图中障碍物的分布情况，将大地图分为不均等的若干区域，并根据每个区域的障碍物信息来设置区域状态，并将区域边界的空白节点看做抽象节点来构建地图的抽象图；并依据区域的状态，选择曼哈顿距离或者向上融合算法来获得抽象节点间的最短路径；使用A*算法在抽象图上实现抽象寻路，依据相关节点在所在区域的状态来选择对应的自动寻路算法进行细化；最终得到实际的最短路径。

3.1 相关系数设计

在分层路径搜索算法中，引入了区域障碍物比例[α]，区域状态标记[λ]和阈值[β]三个系数。

1）区域障碍物比例

区域障碍物比例[α]用于计算区域的障碍物多少，为是否需要继续细分提供依据，其计算公式如式（1）所示。

[α=当前分区障碍物总数当前分区的节点总数] （1）

2）区域状态标记

区域状态标记[λ]取值0或1，对分区过程中所构建四叉树上不再细分的叶子及节点状态进行标记。如果区域内的障碍物较多，那么[λ]取值0，在该区域中使用A*算法实现自动寻路；如果[λ]取值1表示当前区域的障碍物较少，可以使用Bresenham直线方法寻找最优路径。

3）阈值

阈值[β]为是否需要对区域继续进行划分的边界值，[β]值越大，那么区有的划分就越细，地图中的抽象节点额越多，扩展节点越少，耗费时间越少，但耗费的内存越多；[β]值越小，区域划分越粗糙，抽象节点越小，耗费的内存越小。

3.2 地图区域划分

将大地图根据障碍物信息细分成多个区域是分层路径搜索算法的核心思想。其区域划分思想与同样进行地图划分的Quadtree算法不同，在算法中首选将地图划等分为四份，然后根据每个分区的区域障碍物比例[α]和阈值[β]的关系来设置区域状态标记[λ]。根据三个参数的定义，地图区域划分分为如下三种情况。

1）[α=0]，表明当前区域没有障碍物，设置[λ=1]，设置为叶子节点，表明该分区没有障碍物，不再进行细分，该区域使用Bresenhhan直线方法来寻找最短路径。

2）[0?α?β]，区域内障碍物较多，继续细分。

3）[α?β?1]，区域内障碍物较少，设置[λ=0]，设置为叶子节点，表明该分区有障碍物，在该区域内使用A*算法进行自动寻路。

分层路径搜索算法的分区算法流程图设计如图1所示。

在按照如上的思路进行地图区域划分，最终得到一个包含地图区域信息的一个四叉树。

3.3 抽象图构造

在完成地图区域划分之后，需要将所得到的四叉树叶子节点上边界上的非障碍物节点作为抽下点，来构造地图的抽象图。根据区域的状态分别采用曼哈顿距离或者自底向上融合算法来计算子区域抽象节点的最短距离。

如果子区域的[λ=1]，则表明该区域内没有障碍物，直接使曼哈顿算法计算两个抽象节点之间的距离；否则，改区域中含有障碍物，使用自底向上融合的方法计算区域内抽象节点之间的最短距离。其中曼哈顿距离计算公式如式（2）所示。

[DisP1，P2=X1-X2+Y1-Y2] （2）

在得到区域内抽象节点的最短路径之后，最终完成地图的抽象图。

3.4 自动寻路设计

在获得地图完整的抽象图之后，根据玩家所设定的路径起始点和目标点，找到其所在的区域进行插入操作。首先，判断路径的起始点或目标点是否为抽象点，如果是抽象点，那么可以在抽象图上进行自动寻路；其次，判断起始点和目标点是否在同一个分区内，如果是，则根据所在分区的[λ]值，选择Bresenhhan直线或A*算法实现自动寻路；最后，如果起始点和目标点不再同一个分区，则分别连接起始点和目标点与其所在区域的抽象节点的连接，完成起始点和目标点的插入操作。

在完成了相关系数的设计、地图区域的划分和获得抽象图之后，最终的自动寻路设计如图2所示。

4 结束语

分层路径搜索算法是一种考虑了地图内部障碍物分布情况的地图分层路径搜索算法，在算法中根据障碍物分布信息将地图划分为一系列不均等的子区域，并将子区域边界上的所有非障碍物节点看成是抽象节点构造地图的抽象图，并根据区域内的障碍物分布情况，选择Bresenhhan直线或A*算法实现自动寻路计算区域中抽象节点之间的最路径；最终根据玩家所设定的路径起始节点和结束节点实现路径细化，得到实际的最优路径。分层路径搜索算法在地图加载过程中，完成的预处理，可以提高玩家在使用时的最优路径选择，完成自动寻路。

参考文献：

[1] 李艳，周振华，赵文举，等.一种考虑地图分布信息的分层路径搜索算法[J].小型微型计算机系统，2013，11：2607-2611.

[2] 李艳，李铁松.一种基于相对海明距离的地图复杂性度量[J].计算机工程，2012，38（7）：10-12.

[3] 冯林，紫红霞.基于动态阈值启发式图搜索的SLAM算法[J].计算机工程，2011，37（17）：185-187.

[4] 李艳，陈彩，李文亮，等.KM-A*：一种基于A*和K-means聚类的计算机游戏寻路算法[C].2010年第三届计算智能与工业应用国际学术研讨会，2010，7：291-294.