《基于决策树划分的分层路径搜索》由会员分享，可在线阅读，更多相关《基于决策树划分的分层路径搜索（47页珍藏版）》请在金锄头文库上搜索。
1、河北大学 硕士学位论文 基于决策树划分的分层路径搜索 姓名：李文亮 申请学位级别：硕士 专业：计算机应用技术 指导教师：王熙照 2011-05 摘 要 I 摘 要 路径搜索是计算机游戏中的一个基本问题， 它的效率主要取决于需要探测的节点数 目。A*算法探测的节点数目随着搜索空间的增大而增大，难以在游戏的实时性、计算机 资源有限等诸多限制下快速寻路。HPA*算法采用分层的方法显著地提高了路径搜索的 效率可以快速地找到近似最优的路径。HPA*将一个复杂的路径搜索问题分解为多个简 单的小问题。 地形信息是路径搜索需要考虑的重要因素。本文发现 A*算法的效率对地形比较敏 感，尤其是目标点附近的地形。在
2、一定程度上，HPA*对地图进行均等划分可以降低地 形因素对算法效率的影响。在充分考虑地形因素的影响下，本文提出了基于决策树划分 的分层路径搜索算法，该算法视地图上的每个点为一个样例，依据决策树的割点对地图 进行划分。决策树划分的结果是将地图划分成若干矩形区域，每个矩形区域内的地形都 比较单一。实验结果表明该方法可以高效的寻找到较好的路径，同 HPA*相比使用该算 法寻找到的路径更优，而且探测的节点数更少。 关键词 信息熵 决策树 路径搜索 Abstract II Abstract Path-finding is a fundamental problem in computer games,
3、and its efficiency is mainly determined by the number of nodes it will expand. A* algorithm isnt suit for path-finding on large map under restrictions of limited computer sources and Real-time demand, because the number of nodes it will expand grows fast with the size of the search space. HPA* can p
4、romote the efficient of path finding using a hierarchical approach and find near optimal paths. HPA* divides a complex path-finding problem into many very simple problems. Terrain is one of the most important factors should be considered. In this paper we find that the efficient of A* is sensitive t
5、o the terrains, especially the terrain around the target point in grid-based environment. To a certain degree, the equal division of HPA* reduces the influence form terrain factor. We present DT-HPA* (Hierarchical Path-Finding A* based on Decision Tree), a hierarchical path-finding approach on the m
6、ap which has been divided by decision tree. This approach views each point on the map as an instance, divides the map according to cut points of continuous valued decision tree. The result of division is that the map is cut into some rectangular regions, and retains the regions contain a kind of ter
7、rain. The experimental results show that this technique can find better paths effectively. Compared to HPA*, DT-HPA* can find more optimal paths with fewer nodes to be detected. Keywords Information entropy Decision tree Path finding 第 1 章 绪 论 1 第 1 章 绪 论 1.1 研究背景和意义 随着计算机技术的发展，计算机游戏已经成为一项重要的产业， 200
8、9 年中国游戏 产业报告显示中国互联网用户达到了 3.53 亿，其中网络游戏用户多达 6587 万，网络 游戏市场的销售收入达 256.2 亿，游戏产业已倍受关注。玩家除了对游戏的图像和声音 质量有较高要求之外，对游戏智能水平的要求也越来越高，缺少智能的游戏已很难吸引 玩家，游戏的智能水平已经成为评价一个游戏好坏的重要标准之一。计算机游戏也是研 究人工智能技术的一个重要平台，得到了许多学者以及高校的关注。 路径搜索是计算机游戏的一个核心组成部分，是其它游戏部分的基础，无论是简单 的单机游戏还是大型的网络游戏，路径搜索都是必不可少的。路径搜索是提高游戏智能 和游戏质量的一个重要方面，主要负责帮助
9、 NPC 和玩家寻找从给定起始点到目标点的 最优路径。寻找到的路径的好坏将直接影响到游戏的真实性和玩家对游戏的兴趣，如果 路径搜索处理不好，即使声音图像再逼真也会给人不真实的感觉。游戏对路径搜索效率 的要求也很高，游戏的实时性要求 NPC 在短时间内完成路径的搜索，如果每走一步都 停下来搜索的话会给人不真实的感觉。 随着计算机的发展， 计算机游戏的场景不断增大， 相应的路径搜索的复杂度也不断增大， A*算法的效率随着场景的增大而降低。 游戏路径 搜索对时间要求很高，而分配给路径搜索的计算机资源往往是十分有限的，因为图像和 声音等部分都要占据大量的计算机资源。因此，在有限的时间和空间资源下寻找到
10、一条 最优或者近似最优的路径有重要的意义。 1.2 路径搜索现状 路径搜索算法是人工智能的一块基石， 对路径搜索算法的研究得到了许多学者的关 注，出现了大量的路径搜索算法以及它们的优化算法，如Dijkstra算法、A*算法12以及 迭代深化A*（IDA*）等，其中以A*算法作为著名。在简单场景下，这些路径搜索算法 的研究已经十分成熟，A*算法的研究可以说达到了极限。在时间充足的条件下A*算法 总能找到起始点到终止点的一条最短路径。但是随着游戏场景的增大，这些算法的时间 空间复杂度都已经难以满足计算机游戏的要求。以A*算法为例，随着搜索过程的增大， *算法的open表中需要存储大量的节点，算法每
11、探测一个新的节点都需要对open表中 河北大学工学硕士学位论文 2 的节点进行排序，无论是节点的排序还是存储都会消耗大量的计算机资源。 路径搜索算法的分类方法很多， 按照是否需要启发式信息可分为盲目搜索和启发式 搜索，盲目搜索通常是按照一定的搜索顺序搜索，适用于简单问题的求解；启发式搜索 中加入启发式信息，对搜索方向起到引导作用。启发式好比搜索的眼睛，总是朝着目标 点方向搜索，这也是启发式搜索优于盲目搜索的原因。目前，大部分搜索算法都是基于 启发式的，对启发式搜索的研究3也比较多。根据地图是不是可变的分为动态的和静态 的，静态搜索过程中地图的地形不会发生改变，而动态搜索过程中的地图是可变的，比
12、 如随着游戏的进行某个桥梁可能被炸断，这时地形的可走性就发生了变化，原来可走的 路径现在变得不可走了。动态路径搜索通常适合于起始点和目标点相对固定，那么他们 之间路径发生变化时，就需要重新寻路。根据地图表示方法可分为基于网格的和非网格 的，基于网格的地图最为常见，地图的表示方法决定了算法的可走性，基于网格的地图 的搜索方向是相对固定的。 根据agent的大小和多少又可分为单agent和多agent4的路径搜 索， 以往的路径搜索都是基于单个agent的寻路， 随着游戏的发展， 特别是在网络游戏中， NPC的数量比较多， 这就涉及到了多个agent之间配合， 如何利用多个agent的寻路结果来
13、寻路是多agent寻路研究的重点。 路径搜索算法的研究和优化主要集中在两个方面：一是搜索空间，二是搜索算法， 搜索算法是在搜索空间中进行路径搜索。搜索空间决定了问题的复杂程度，涉及到地图 的表示方式，如何描述地图；搜索算法是指具体的路径搜索策略，是盲目的搜索还是按 照某种规则进行搜索。 2004 年，Adi Botea等人提出了分层路径搜索算法HPA*5，该方法对地图进行均等 划分，将一个大地图分割成若干的相互连接的小地图，对分割后的子图进行抽象，选取 连接不同子图的部分可走节点作为关键点，他们将这些关键点定义为entrance。寻找路 径时首先在由关键点构成的抽象图中寻找路径，这条路径连接了
14、不同的小地图。之后再 在根据寻找到的抽象路径寻找各个子图内的真实路径。HPA*算法成功的地方在于它将 一个复杂问题分解为若干小问题，将地图分解也就是将搜索问题分解。由于不同块内的 路径搜索互不影响， A*算法需要存储的节点数目就会减少， 对节点的排序等操作也就变 得简单，需要探测的节点数少，搜索速度就快，HPA*的搜索速度大约相当于A*算法搜 索速度的 10 倍。HPA*可以实现快速寻路，同时也可以保证找到的路径是近似最优的。 2005 年，M.R.Jansen等人在HPA*的基础上提出了一些改进方法6，包括对寻找到的 第 1 章 绪 论 3 路径进行优化，计算子图内部节点之间距离的时候使用D
15、ijkstra算法要比使用A*算法要 好，以及在动态环境下如何使用HPA*。 1988 年，H. Samet提出了四叉树方法7，1998 年四叉树方法被应用到路径搜索领域 中8，使用四叉树方法对网格表示的地图进行分割。四叉树划分的地图要去地图的长和 宽都是 2 的倍数，该方法首先将地图等分为四块，如果某个块内不包含障碍物或者全部 是障碍物， 则不对该块进行处理； 如果既有障碍物又有可走区域则继续对该块进行划分， 直至所有子块内的地形单一时为止。四叉树方法的成功在于它简化了的搜索空间，降低 了网格划分的规模。四叉树方法可以看作是一种特殊的网格划分方法，对于没有障碍物 或者全是障碍物的区域不进行划
16、分。 2004 年，H.Choset等人采用随机撒点的方法9对地图进行抽象，在搜索空间的可走 区域内随机撒点， 之后选择一部分有代表性的点。 将这些点与它们相邻的点用直线连接， 这样便可以用这些点来表示抽象图，该方法的优点是抽象图容易构建，适合高维空间的 路径搜索。这种方法的难点在于关键点的选择，如何选择尽量少的节点来尽可能的覆盖 整个地图。 2006 年，Douglas Demyen和Michael Buro提出了一种基于三角形划分的路径搜索算 法10，该方法将障碍物的顶点进行连接，把地图划分为若干大小不等的三角形区域，选 择每个三角形的中心作为关键点， 该方法适用于障碍物数量比较少而且障碍物形状比较 规则的地图。 2004 年，S. Koening、M. Likhachev等提出LPA*11，该方法是一种A*算法的增量方 法，适用于地图上的地形经常变化而且起点和终点又相对固定的情况。当地图中仅有部 分
