电子游戏是当今一种非常风靡的娱乐方式。电子游戏技术的发展往往伴随着计算机技术水平的不断更新。在以往的几年内，游戏中震撼的音效、精致的画面是吸引游戏玩家的重要因素，玩家倾向于更接近于真实环境的游戏。伴随着计算机软硬件技术的提高，电子游戏在画面、声音上已做到了极致。游戏的比拼从声音与画面转移到了游戏情节和游戏人物的智能水平上，因此人工智能技术被越来越多的被应用到了电子游戏领域。游戏中的路径搜索技术是游戏人工智能的一个重要应用。高效的路径搜索算法可以大大降低搜索的时间，减少搜索的主机资源占用。其中A*算法是早期出现的一种经典的搜索算法，在存在路径的前提下总是能够找到最优路径，应用十分广泛。但A*存在的缺点是地图较大时存储空间，时间耗费大，不能满足游戏实时性需求。于是在近期出现了基于分层搜索的算法，其中HPA*算法是一种典型的分层路径搜索算法，大大提高了A*搜索的效率。HPA*的缺点是在对地图划分时没有考虑地形的信息，降低了空旷区域上的路径搜索的最优程度。本文基于这个缺点提出了用最小矩形包围障碍物的方法，是对HPA*地图划分的一种改进。把较大空白区域划分成尽量少的矩形区域，使空白区的路径寻找变成近似直线寻路，同时减少了区域之间关键点的数量，增强了寻路的最优性，实验验证了方法的有效性。另一方面，游戏地图是路径搜索的平台，而游戏地图设计的会影响游戏的复杂性和路径搜索的效率，从而影响到了游戏的趣味性。于是需要能够衡量地图复杂度的方法来衡量地图的设计。本文首先介绍一种基于海明距离的地图复杂性度量，然后针对不同规模地图复杂性度量的问题提出一种相对海明距离的计算方法，通过计算地图的实际复杂度与可达到的最大复杂度的比值作为相对复杂度，并引入了地图区域间方差的概念。结果证明新的地图复杂性度量方法能够更好的反映不同规模与障碍分布地图的复杂度，并与分层路径搜索算法HPA*的搜索效率有着较强的关联性。