寻路算法在人工智能领域里处于基础性的地位，很多相关应用都需要优良的寻路算法的支持。在地图类游戏中，无论是玩家控制角色还是电脑控制角色都需要从地图上一个位置转移到另一个位置，即在地图上进行寻路。尤其是一些实时战略游戏对寻路的需求更加频繁。自从A*算法被提出以后，诸多的改进算法应运而生。有进行均匀分区的HPA*算法，有基于聚类的KM-A*算法，还有对地图进行多尺度分区的M-A*算法等等。他们都对待搜索地图进行抽象，但HPA*搜得的路径并非最优，KM-A*和M-A*则存在抽象过程过长的缺点。另一方面，寻路算法的性能很大程度上受到地图中障碍物分布的影响。因此，对于某种特定的寻路算法而言，如常用的A*类算法，创建一个适合该寻路算法的地图也显得尤为重要。于是，对于地图复杂性度量的研究也在一直进行。本文的工作主要有以下两点：1．针对M-A*在分区过程中不考虑地形分布并且形成的抽象图结点较多等问题，本文提出了一种考虑地形分布的多尺度分解路径规划加速方法（MTD-A*），用以快速寻找地图上两个指定点之间的最短路径。该算法在形成抽象图过程中，对于大面积的无障碍分区不再进行细分，简化了抽象过程；在空白分区细化实际路径时，利用Bresenham直线算法代替A*寻路，加速了寻路过程。实验结果表明，与M-A*相比，该算法形成抽象图时间更短、抽象图结点数更少、搜索速度更快。2．本文首先提出了全连通地图的概念，而后给出了接触面的定义，提出了基于接触面的地图复杂性度量方法。在对地图进行分析的过程中，我们发现地图是由一些非常简单的元素（接触面）所组成，而这些接触面的不同状态也在一定程度上决定了一张地图的复杂程度。由于在统计过程中排除了对寻路过程无影响的接触面，我们所提出的地图复杂性度量方法与基于海明距离的和基于相对海明距离的地图复杂性度量方法相比能够更准确的反映寻路困难度。