HPA*的部分翻译

3 Hierarchical Path-finding(分级路径搜索)

在我们的分级结构(framework)中,路径搜索可以分为三步,我们称为:on-Line 搜索。
首先,遍历包含开始位置节点的邻接边界(border of the neighborhood).
第二,从开始区域的边界到目标区域的边界搜索一条路径。我们使用抽象级别去实现它,这个搜索是简单快速的。因为一个行走动作会穿越一个相对较大的区域(area),而且并不需要去处理这个区域的细节。
第三,从目标区域边界到目标点的位置生成路径,完成路径搜索。

on-line搜索的图形是根据从原始迷宫中提取的数据进行生成的。我们对以下两个方面进行详细描述:怎样建立分级搜索结构(pre-Processing);怎样使用它进行路径搜索(on-line搜索)。开始我们只建立一个二级的搜索:一个底层级(原图),一个抽象级。在后面的章节我们再讨论多级搜索。我们使用一个如图Figure1(a)的40X40的地图进行演示:
figure1a

3.1 Pre-processing a Grid(预处理网格)

建立分级搜索框架的第一步是定义一个迷宫的拓扑提取层。我们使用这个迷宫提取层去建立分级搜索的二级图形。

这个拓扑提取层是由一系列覆盖迷宫的分离的长方形组成的,这些长方形我们称它为:Cluster。在图Firgure1(b)中用粗线框起的就是Cluster。在本例中,这个40×40的网格被重新组合为16个10X10的Cluster。Notethat no domain knowledge is used to do this abstraction (otherthan, perhaps, tuning the size of the clusters).

对于两个相邻Cluster的边界线,我们标识一系列的入口(可能没有)进行对他们连接。一个入口是在沿着相邻的两个Clusterc1,c2的公共边中一个最大尺寸的无障碍段,它的定义会在下面给出。考虑点的两条相邻边l1,l2(由节点组成的线),他们在各自的Cluster中,这决定了这条边界边在c1和c2之间。一个节点t属于l1Ul2,我们定义symm(t)为在c1和c2的边界间的对称节点。注意t和symm(t)是相邻的并且不属于相同的Cluster。如图:有蓝色描绘的一系列节点为l1,l2,有绿色填充的节点演示了节点t及symm(t)figure2
一个入口e需要满足以下条件:
1. 边界限制条件:e属于l1 U l2。这个条件规定了一个入口必须是沿着但不能超过两个相邻Cluster的边界边。
2. 对称条件:对于所有满足节点t属于l1 U l2:如果t属于e,则symm(t)属于e。
3. 无障碍条件:一个入口不能包含有障碍的节点。
4. 最大尺寸条件:在符合以上条件的基础上,入口应该尽量往两边延伸,达到最大。

Firgure2显示了地图左上角的被放大了的四分图:f21
通过这幅图我们可以找到入口的详细信息,并使用它去建立二级图。在这个例子中,左边的两个Cluster的连接分别被两个宽度为3与宽度为6的入口所连接。对于每一个入口,我们定义一个或两个过渡点(transitions),这需要根据入口的宽度进行选择。如果入口宽度小于我们预先定义的一个常量(这里我们规定为6),那么我们就只定义入口的中间节点为过渡点;否则,我们定义两个过渡点,分别规定在入口的两边。

我们使用过渡点去建立二级图。对于每一个过渡点(应该称为过渡结构更合适),我们规定它包括两个节点和连接这两个节点的一条边。对于一条这样的边,他是连接两个Cluster的,我们叫他inter-边。inter-边常常规定长度为1.对于cluster内部中的每一对这样的过渡点节点,我们也定义一条边连接他们,这条边叫intra-边。要计算Cluster内部的最优路径我们可以使用intra-边来完成。

Figure2显示了所有的过渡点节点(灰色节点),还有所有的inter-边(灰色边),还有部分intra-边(只显示了右上角的Cluster).Figure3显示了Firgure2中右上角的Cluster的抽象内部拓扑信息。它的数据结构包含了一系列过渡点节点和他们之间的距离。我们定义直线距离为1,斜线距离为1.42.Weonly cache distances between nodes and discard the actual optimalpaths corresponding to thesedistances。如果你想,也可以将路径保存,这样也会需要额外的存储空间。这我们在3.2.2节讨论。
f3

Firgure4(a)显示了我们运行的二级图。这个图包含了插入开始节点S与目标节点G之后的结果图(虚线表示),这个我们将在下一节讨论。这个图有68个过渡点节点,包括S,G,他们可以在任何一个搜索中改变。在这个级别的图中,有16个Cluster并且有43条inter-边连接和88条intra-边连接。还有两条额外的边连接S和G到总图中。作为对比,底层图包含1,463个节点,每一个无障碍的节点都算其中一个,并且有2,714条边。

一旦二级图被建立,并且Intra-边距离被计算出来,这个网格就已经准备好进行分级搜索了。这个信息可以被预先计算出来保存到磁盘,当游戏运行时再将它装载到内存。对于静态网格(没有动态变化)来说这样已经足够了。但对于可以动态改变的网格来说,这些预先计算的数据不得不在运行时进行优化修改。当网格拓扑图改变(比如一座桥被毁掉),受到影响的cluster的intra-边和inter-边就需要被重新计算。
f4

3.2 On-line Search(on-line搜索)

on-line搜索的第一个阶段是连接开始位置S到包含S的cluster的边界。要完成这个步骤可以通过将S临时插入到二级图中。类似的,连接目标位置G到它的cluster边界也通过插入G到二级图中。

S和G被加入之后,我们可以使用A*算法在这个二级图中在S和G之间搜索一条路径。这是on-line搜索中最重要的部分。它提供了一个二

发表评论

邮箱地址不会被公开。 必填项已用*标注

* Copy This Password *

* Type Or Paste Password Here *