路径搜索是智能游戏的重要组成部分，游戏地图是路径搜索的平台，设计游戏地图及寻路算法时考虑障碍物在地图中的分布至关重要。目前，人工智能领域存在的大多数路径搜索算法都没有充分考虑到地图中障碍物的分布信息，造成了不必要的时间和存储耗费。如传统的A*、Dijkstra算法时间空间复杂度高，难以满足大规模游戏地图的寻路要求；HPA*、M-A*等分层寻路算法在分区时未考虑地图中障碍物的分布信息，降低了路径的最优程度；Quadtree算法分区终止条件严格，抽象节点非常多，耗费大量内存。针对以上问题，研究工作主要分为以下两部分：1．提出了考虑地图分布信息的分层路径搜索算法CDHPA*。CDHPA*算法首先依据地图场景的分布情况将地图划分为不均等的子区域并构成完整的抽象图。根据障碍物分布情况不同，抽象节点之间的最短路径采用曼哈顿距离或自底向上融合算法来计算。然后使用A*算法找到抽象路径并依据所涉及分区的状态选择Bresenham直线算法或A*算法进行细化，得到最终实际路径。CDHPA*算法在同一幅地图上进行多次寻路时仅需一次预处理，在线寻路速度相比同类方法M-A*、HPA*更快，并且得出的路径为最优路径。2．定义了一种基于异或累加的地图复杂性度量标准ACX。ACX通过逐行逐列的统计相邻单元格的异或值来度量地图的复杂性，为设计游戏地图提供参考。ACX所得结果只与地图中相邻单元格的状态有关，与地图的大小及障碍物的个数无关。