在A*寻路中使用二叉堆

　2006-07-23 11:33:11　来源：WEB开发网　　　

核心提示： 顶端的元素有两个子节点，数值是2和6，在A*寻路中使用二叉堆(7)，他们的F值是30和20，分别存储在opneList()中2和3的位置，然后给numberOfOpenListItems加1，然后把它添加到开启列表的底部，等等，基本上

顶端的元素有两个子节点，数值是2和6，他们的F值是30和20，分别存储在opneList()中2和3的位置，等等。基本上，我们的堆和以前相同，只是多了一些关于元素在地图上的位置，F值是多少，等等的信息。

在堆中添加新元素(第二部分）

好，我们实际的把这种技术用在A*寻路的开启列表排序中。我们使用的技术和先前描述的大体相同。

我们添加到开启列表中的第一个元素，一般是起始节点，被分配了一个数值是1的唯一ID，然后放入开启列表的#1位置。也就是 openList(1) = 1.我们还跟踪开启列表中元素的数量，现在也是1。我们把它保存在名为numberOfOpenListItems的变量里。

当我们往开启列表中添加新元素的时候，首先我们计算G，H和F值，就如在主文章中所述。然后按照前面讲的方法把他们添加进开启列表。

首先我们给新元素分配一格唯一 ID号，也就是squaresChecked变量的用途。每次我们添加一个新节点，就给这个变量加1，然后把它的数值分配给新节点。然后给numberOfOpenListItems加1。然后把它添加到开启列表的底部，所有这些可以翻译成：

squaresChecked = squaresChecked +1
numberOfOpenListItems = numberOfOpenListItems+1
openList(numberOfOpenListItems) = squaresChecked

然后我们依次把它和父节点比较直到它到达正确的位置。这是这些操作的代码：

m = numberOfOpenListItems
While m <> 1 ;While item hasn''t bubbled to the top (m=1)
　　;Check if child is <= parent. If so, swap them.
　　If Fcost(openList(m)) <= Fcost(openList(m/2)) Then
　　　　temp = openList(m/2)
　　　　openList(m/2) = openList(m)
　　　　openList(m) = temp
　　　　m = m/2
　　Else
　　　　Exit ;exit the while/wend loop
　　End If
Wend

从堆中删除元素(第二部分)

上一页 2 3 4 5 6 7 8 9 下一页