隨筆檔案

   對于開放列表的維護(hù)方案來說，前面我說的，都是一些小花樣了，在一些很小的地圖上用他們并沒有什么太大的問題，但是如果地圖很大，需要搜尋的格子很多，那么開放列表里的元素必然會很多，那么我們是否可以用另外一種思維來考慮一下開放列表的維護(hù)工作？
 
   其實(shí)我們每次從開放列表里面取值，每次只需要取里面所有元素的最小值就行了，而前面所說的兩種方案都有自己的優(yōu)點(diǎn)，第一種不需要對開放列表做排序，但每次找起最小值來實(shí)在消耗很大，第2種在找最小值的時候只需取第一個元素就行，而麻煩在于需要一直維持開放列表里面所有元素的有序排列，那么我們是不是可以把這兩種方法的優(yōu)點(diǎn)都結(jié)合起來呢

   當(dāng)然，這種方法是有的，那就是很多高級A*程序更苛求速度的一種做法，利用Binary Heap數(shù)據(jù)結(jié)構(gòu)，也就是二叉堆，來維護(hù)開放列表。

   其實(shí)有關(guān)二叉堆，相信了解他的高手很多，我就不再班門弄斧，，其實(shí)我也只是剛剛學(xué)習(xí)他而已，這里只簡單的介紹一下他的一些特點(diǎn)以及在A*中他所起到的作用。

   百度百科中對二叉堆的定義： 二叉堆是一種特殊的堆，二叉堆是完全二元樹或者是近似完全二元樹。二叉堆滿足堆特性：父結(jié)點(diǎn)的鍵值總是大于或等于任何一個子節(jié)點(diǎn)的鍵值。

   那么應(yīng)用于A*的開放列表里，我們只要反過來，父結(jié)點(diǎn)的鍵值總是小于或等于任何一個子節(jié)點(diǎn)的鍵值，這樣就沒問題了。

   利用這種特性進(jìn)行過排列的開放列表，那么我們可以保證，具有F值特性最小的那個元素，肯定是在這個二插樹的根節(jié)點(diǎn)，于是取值的時候，只要把根節(jié)點(diǎn)上的值取出來用就行了。（當(dāng)然，取完以后還得維護(hù)開放列表的二叉堆特性，這點(diǎn)我下面會談），一般來說，二叉堆是利用數(shù)組來表示，那么正好，我所使用的vector結(jié)構(gòu)便可以派上用場，二插堆的結(jié)構(gòu)填往vector中的時候，利用的是一種類似前序遍歷的方式順序進(jìn)入的，也就是按照 當(dāng)前節(jié)點(diǎn) -- 當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn) -- 當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)這樣的順序來放入vector中，如下圖


（此圖是借用了Panic所翻譯的《在A*尋路中使用二叉堆》一文中的圖片）

不過根節(jié)點(diǎn)進(jìn)入的時候不要放在0號元素上，vector可以隨便先放進(jìn)一個沒有用的元素，我處理的時候是放了一個NULL型指針進(jìn)去的，也就是說根節(jié)點(diǎn)所在的vector下標(biāo)為1。而這樣的話對于這個vector中非0下標(biāo)的任意一個元素，我們要找他的父節(jié)或者是子節(jié)點(diǎn)就很簡單了，遵循下面一個原則：
具備二叉堆特性的vector中下標(biāo)為n(n!=0)的一個元素：
他的父節(jié)點(diǎn)下標(biāo) = n / 2;(小數(shù)去掉)    比如下標(biāo)為9的元素，他的父節(jié)點(diǎn)下標(biāo)就是4
他的左子節(jié)點(diǎn)下標(biāo) = n * 2;  右子節(jié)點(diǎn)下標(biāo) = n * 2 +1   比如下標(biāo)為3的元素他的左子節(jié)點(diǎn)下標(biāo)為6,右子節(jié)點(diǎn)下標(biāo)為7

   對于我們的A*來說，在把元素放進(jìn)開放列表里面的時候就需要按照二叉堆的添加步驟進(jìn)行操作，而我們在把下標(biāo)1的F值最小的元素取出來并且刪除掉以后，則需要把二叉堆重新維護(hù)下其二叉堆的特性，而在尋路過程中某個開放列表中元素的G值改變以后，我們則需要對這個開放列表再進(jìn)行次維護(hù)，維持他的二叉堆特性。那么綜合以上，我們只需要3個功能函數(shù)，BinaryHeapAdd函數(shù)，BinaryHeapDelete函數(shù)，RetaxisBinaryHeap函數(shù)

BinaryHeapAdd函數(shù)，
1 把新的要進(jìn)入開放列表的元素放進(jìn)vector的末尾，也就是直接push_back進(jìn)去 （這個新加進(jìn)的元素為當(dāng)前處理元素）
2 利用上面所說的父子節(jié)點(diǎn)下標(biāo)關(guān)系，找到當(dāng)前處理元素的父節(jié)點(diǎn)下標(biāo)，然后比較兩個數(shù)，如果新的元素比他的父節(jié)點(diǎn)小，則把這個元素和他的父節(jié)點(diǎn)的位置互換一下，如果產(chǎn)生了互換行為，則針對新位置上的這個當(dāng)前處理元素再次重復(fù)本次動作；
3 直到新的元素大于等于他的父節(jié)點(diǎn)，或者找到的父節(jié)點(diǎn)下標(biāo)為0 ，則新元素的位置確定為找到，這個函數(shù)可以結(jié)束

void AStarBase::BinaryHeapAdd(POINTINFO* indexPoint)
{
    int tmpF = indexPoint->F;

    _openPoint.push_back(indexPoint);        //先把新的元素放在vector最后

    int theNewIndex = _openPoint.size()-1;   //新元素的下標(biāo)
    while (true)
    {
        int theParentIndex = theNewIndex / 2;     //新元素當(dāng)前所在位置的父節(jié)下標(biāo)
        if (theParentIndex != 0)                  
        {
            if (_openPoint[theNewIndex]->F < _openPoint[theParentIndex]->F)   //新元素的F值比他的父節(jié)點(diǎn)值大
            {
                //與父節(jié)點(diǎn)的位置進(jìn)行交換
                POINTINFO* tmpinfo = _openPoint[theParentIndex];
                _openPoint[theParentIndex] = _openPoint[theNewIndex];
                _openPoint[theNewIndex] = tmpinfo;

                _openPoint[theParentIndex]->openIndex = theParentIndex;
                _openPoint[theNewIndex]->openIndex = theNewIndex;

                theNewIndex = theParentIndex;   //置新節(jié)點(diǎn)的處理下標(biāo)為換過位置以后的值
            }
            else
            {
                break;
            }
        }
        else                                    //如果父節(jié)下標(biāo)計算出來為0，則停止查找位置
        {
            break;
        }
    }
}

BinaryHeapDelete函數(shù)
1 把開放列表中1號元素取出并放在最后返回出來使用

2 需要對開放列表進(jìn)行一次2叉堆特性重新維護(hù)，首先把vector中最后一個元素移動到1號下標(biāo)位置，（1號元素為當(dāng)前處理元素）

3 對1號下標(biāo)位置的當(dāng)前處理元素利用父子節(jié)點(diǎn)下標(biāo)計算關(guān)系找出他的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)，然后把這個元素與他的左子節(jié)點(diǎn)元素的F值和右子節(jié)點(diǎn)的F值大小分別做比較，如果子節(jié)點(diǎn)的比他更小，則把他與子節(jié)點(diǎn)的位置進(jìn)行互換，如果兩個子節(jié)點(diǎn)的值都比他小，則與較小的那個子節(jié)點(diǎn)進(jìn)行位置互換，如果產(chǎn)生了互換行為，則針對新位置上的當(dāng)前處理元素再次進(jìn)行本次動作

4 如果子節(jié)點(diǎn)的值都大于或者等于當(dāng)前處理元素的值，或者計算出來的子節(jié)點(diǎn)下標(biāo)已經(jīng)朝出了vector最大元素個數(shù)，則停止排序，函數(shù)可以返回原來存起來的最小值

AStarBase::POINTINFO* AStarBase::BinaryHeapDelete()
{
     if (_openPoint.size() <= 1)   //開放列表里面只剩下開始放進(jìn)去的一個空的POINTINFO指針
     {
          return NULL;
     }

     //先把最后一個元素放到1號位置
     POINTINFO* tmpinfo = _openPoint[1];    //下標(biāo)1位置的元素先存儲起來，函數(shù)結(jié)束的時候要return出去
     _openPoint[1] = _openPoint.back();    //把vector中的最后一個元素放到下標(biāo)1位置
     _openPoint.pop_back();
     _openPoint[1]->openIndex = 1;

     int theSelectIndex = 1;       //要處理元素的下標(biāo)值
     while (true)
     {
         int theLeftChildIndex = theSelectIndex * 2;               //左子節(jié)點(diǎn)下標(biāo)值
         int theRightChildIndex    = theSelectIndex * 2 + 1;          //右子節(jié)點(diǎn)下標(biāo)值
         if (theLeftChildIndex >= _openPoint.size())   //這個數(shù)沒有子節(jié)點(diǎn)，則停止排序
         {
             break;                                   
         }
         else if ( theLeftChildIndex == (_openPoint.size() -1)) //左子節(jié)點(diǎn)正好是vector中最后一個元素，即只有左子節(jié)點(diǎn)，沒有右子節(jié)點(diǎn)
         {
             if (_openPoint[theSelectIndex]->F > _openPoint[theLeftChildIndex]->F)   //如果父節(jié)點(diǎn)的F值比左子節(jié)點(diǎn)更大
             {
                 //交換
                 POINTINFO* tmptmpinfo = _openPoint[theLeftChildIndex];
                 _openPoint[theLeftChildIndex] = _openPoint[theSelectIndex];
                 _openPoint[theSelectIndex] = tmptmpinfo;

                 _openPoint[theLeftChildIndex]->openIndex = theLeftChildIndex;
                 _openPoint[theSelectIndex]->openIndex = theSelectIndex;

                 theSelectIndex = theLeftChildIndex;
             }
             else  //如果小，則停止排序
             {
                 break;
             }
         }
         else if (theRightChildIndex < _openPoint.size())  //既有左子節(jié)點(diǎn)又有右子節(jié)點(diǎn)
         {
             if (_openPoint[theLeftChildIndex]->F <= _openPoint[theRightChildIndex]->F )   //左右子節(jié)點(diǎn)先互相比較 左邊的小
             {
                 if (_openPoint[theSelectIndex]->F > _openPoint[theLeftChildIndex]->F)      //處理的父節(jié)點(diǎn)F值比左子節(jié)點(diǎn)大
                 {
                     //交換(與左子節(jié)點(diǎn))
                     POINTINFO* tmptmpinfo = _openPoint[theLeftChildIndex];
                     _openPoint[theLeftChildIndex] = _openPoint[theSelectIndex];
                     _openPoint[theSelectIndex] = tmptmpinfo;     

                     _openPoint[theLeftChildIndex]->openIndex = theLeftChildIndex;
                     _openPoint[theSelectIndex]->openIndex = theSelectIndex;
              
                     theSelectIndex = theLeftChildIndex;
                 }
                 else
                 {
                     break;
                 }
             }
             else     //右邊的比較小
             {
                 if (_openPoint[theSelectIndex]->F > _openPoint[theRightChildIndex]->F)      //處理的F值比右子節(jié)點(diǎn)大
                 {
                     //交換(與右子節(jié)點(diǎn))
                     POINTINFO* tmptmpinfo = _openPoint[theRightChildIndex];
                     _openPoint[theRightChildIndex] = _openPoint[theSelectIndex];
                     _openPoint[theSelectIndex] = tmptmpinfo;

                     _openPoint[theRightChildIndex]->openIndex = theRightChildIndex;
                     _openPoint[theSelectIndex]->openIndex = theSelectIndex;
   
                     theSelectIndex = theRightChildIndex;
                 }
                 else
                 {
                     break;
                 }    
             }
         }

     }
     return tmpinfo;
}

大家可以看到，上面的兩個函數(shù)所做的添加和刪除操作，可以保證開放列表里，1號位置的元素的F值肯定是最小的，而其他地方的大小位置關(guān)系，我們可以不需要理會，我們只要保持一個原則，2叉堆里的父節(jié)點(diǎn)元素F值不能比子節(jié)點(diǎn)大，就可以了

而尋路過程中由于F值重計算而導(dǎo)致的重排序，其實(shí)和添加操作的原理是一樣的，我們只需要把那個改過F值的元素，把他和他的父節(jié)點(diǎn)的F值進(jìn)行比較，如果改過的值小，則互換，如果并不小或者沒有了父節(jié)點(diǎn)，則停止
void AStarBase::RetaxisBinaryHeap(int index)
{
    int theNewIndex = index;   //當(dāng)前處理的下標(biāo)
    while (true)
    {
        int theParentIndex = theNewIndex / 2;     //當(dāng)前處理節(jié)點(diǎn)的父節(jié)點(diǎn)下標(biāo)值
        if (theParentIndex != 0)
        {
            if (_openPoint[theNewIndex]->F < _openPoint[theParentIndex]->F)   //新進(jìn)來的F值比他的父節(jié)點(diǎn)值大
            {
                //進(jìn)行交換
                POINTINFO* tmpinfo = _openPoint[theParentIndex];
                _openPoint[theParentIndex] = _openPoint[theNewIndex];
                _openPoint[theNewIndex] = tmpinfo;

                _openPoint[theParentIndex]->openIndex = theParentIndex;
                _openPoint[theNewIndex]->openIndex = theNewIndex;

                theNewIndex = theParentIndex;
            }
            else
            {
                break;
            }
        }
        else
        {
            break;
        }
    }
}

利用上面3個操作函數(shù)所算出來的尋路結(jié)果，與一開始使用在無序開放列表里每次利用比較法找出最小F值所得到的結(jié)果是一樣的，
POINT(2,2)尋路到 POINT(398,398)



好吧，其實(shí)我們用他的目的是什么？就是要看看他消耗的速度而已，讓我們來看一下性能分析表


大家可以看到，在整個程序中這3個函數(shù)所消耗的時間為 0.963394 + 0.437735 + 0.271655 = 1.672784毫秒，是無序找最小值方法所使用時間的十分之一左右，是使用正常一些全排序方法消耗速度的六分之一左右，這還是在路徑非常簡單的情況下，而一旦障礙更多，路徑更復(fù)雜，開放列表里的元素更多的時候，Binary Heap方法能體現(xiàn)他更大的速度優(yōu)勢

以上代碼沒有經(jīng)過任何優(yōu)化工作，僅僅是實(shí)現(xiàn)了下二叉堆的功能，各位將就著看了 ^O^

如果對A*尋路基礎(chǔ)算法原理不清楚并且有興趣的朋友，可以去gameres上看一下這篇文章
http://data.gameres.com/message.asp?TopicID=25439