路径搜索是计算机游戏中的一个基本问题,它的效率主要取决于需要探测的节点数目。A*算法探测的节点数目随着搜索空间的增大而增大,难以在游戏的实时性、计算机资源有限等诸多限制下快速寻路。HPA*算法采用分层的方法显著地提高了路径搜索的效率可以快速地找到近似最优的路径。HPA*将一个复杂的路径搜索问题分解为多个简单的小问题。地形信息是路径搜索需要考虑的重要因素。本文发现A*算法的效率对地形比较敏感,尤其是目标点附近的地形。在一定程度上,HPA*对地图进行均等划分可以降低地形因素对算法效率的影响。在充分考虑地形因素的影响下,本文提出了基于决策树划分的分层路径搜索算法,该算法视地图上的每个点为一个样例,依据决策树的割点对地图进行划分。决策树划分的结果是将地图划分成若干矩形区域,每个矩形区域内的地形都比较单一。实验结果表明该方法可以高效的寻找到较好的路径,同HPA*相比使用该算法寻找到的路径更优,而且探测的节点数更少。