随笔档案

   大家都知道，对于A*算法，围绕着开放列表的操作是很多的，开始的时候需要把当前处理点的周围8个点里，除了障碍点，已在开放列表里和关闭列表的点以外的其他点，计算G,F值以后都放进开放列表里，如果已经在开启列表里的，还得对它进行一次G值的重检测，从开放列表里每次要找出新的F值最低的点作为当前要处理的点，并且要把他从开放列表里面删除，所以，对于开放列表的操作的速度，是影响A*寻路速度的第一个关卡

   最简单的一种做法，也是我一开始所使用的方法，刚开始的点按照访问顺序逐一push_back进代表开放列表的vector中，（我所用的开放列表用vector来担当），在取最小值的时候，使用一个简单的算法找出开放列表中具有最小F值的那一个元素，然后把这个元素做为当前处理的点，并从开放列表里删除，进入关闭列表，

int AStarBase::FindMinFValue()     //在开放列表中寻找F值最小的(返回的是下标值),并且从开放列表里面删除
{
     if ( _openPoint.empty())
     {
         return -1;
     }
     else
     {
         int id = 0;
         int minIndex = _openPoint[0]->index ;                 
         int theMinF =  _openPoint[0]->F;                      //以第一个点的F值做为参考值

         for (size_t i = 0;i< _openPoint.size();i++)
         {
             if (theMinF > _openPoint[i]->F)                 //如果找到比他更小的F值,则把新的F值做为当前参考值
             {
                  id = i;
                  minIndex = _openPoint[i]->index;
                  theMinF = _openPoint[i]->F;
             }
         }
         _openPoint.erase(_openPoint.begin() + id);        //删除所找到的元素

         return minIndex;                                
     }
}

   这真的是最容易实现的方法了，他唯一的一点好处是由于开放列表里的所有元素一直都是无序的状态，所以在后期出现开放列表里某个元素的G值被改变的时候，开放列表不需要重新排序，但是他的执行速度呢？大家可以看一下我的第一篇A*随笔里所贴的图片，从POINT(2,2)点寻路到POINT(398,398)的位置，下标元素从802开始寻找到159598，这么多个点，消耗在开放列表寻值的时间是多少呢？
  
   正好，我们的Visual studio给我们提供了一个程序性能分析工具，可以具体的分析出程序中每一个函数的调用情况，我们可以用他大概的查看一下我们的这个函数的执行情况


上图中的可看出，整个寻路过程中，花费在每次找出最小值FindMinFValue()这个函数的总时间为16.60毫秒。恩，这个貌似是很快的么，不是么，才16.6豪秒而已，人类根本是察觉不出这样的时间花费的，OK,那让我们接着往下看吧

恩，如果不想每次都花费死工夫在无序的开放列表里面找F最小的元素，那么我们一开始在往里面放东西的时候，就让他们排好序不就行了吗？从小到大排序，那么每次具有最小F值的那个元素肯定在首位了，每次取他就行了。 恩，其实有现成的自动排序的STL容器可以用，但我不想用他，用自己的排序方法去维护开放列表好了。

对于排序算法，网上现成的算法有很多了，什么选择啊，冒泡啊，快速啊，恩，我自己稍微写了一下，用的还是一种比较死的方法，就是每次在往开放列表里放新元素的时候，找好了位置再放，保证放过以后开放列表里面的所有元素都是按F从小到大进行排列的。
void AStarBase::InsertToOpenList(POINTINFO* indexPoint)    //利用插入法往开放列表里放点(F值从小到大)
{
     int tmpF = indexPoint->F;
   
     if (_openPoint.empty())
     {
         _openPoint.push_back(indexPoint);
         return;
     }
     for (AStarBase::PixelContain::iterator it = _openPoint.begin();it != _openPoint.end();it++)
     {
         if ( (*it)->F >= tmpF)   //找到比F值大的了，就插在他的前面
         {
             _openPoint.insert(it,indexPoint);
             return;
         }
     }

     _openPoint.push_back(indexPoint);  
}

其实比他快的方法还有很多，比如先push_back，再利用快速排序对整个开放列表进行排序,但这里我这里也就简单的写写了，好吧，我们看下这种方法的结果，不过很可惜，仅仅这么做得到的是错误的结果，


   为什么说他是错误的呢，因为在寻路过程中少做了一步针对开放列表的重排序，因为在有一个步骤中，开放列表里的有些点的G值会经过重新计算可以得到一个更小的G值，而F值也会更小，所以这时候需要对开放列表做下重排序，重排序其实也很简单，只要找到这个改过g值的元素在开放列表里的位置，然后把他和处于他前面的元素进行下比较，把他重新放在一个合适他的位置就可以保持开放列表的有序了，这一步我就没有做了，我仅仅想看一下这个每次插入排序所用的时间消耗
  

大家可以看到，这个函数总共耗时在6.7毫秒，而这个程序中并没有处理F值改变时候的开放列表重排序问题，不过我估计，如果把这个处理函数加进去，他的消耗也不会比上面这个函数所用的时间更多，估计大概在不到5毫秒左右的时间，也就是说，针对开放列表进行排序维护的话，总时间消耗大概在12毫秒左右，如果使用一些小的技巧，一些好的常用排序算法针对排序进行优化的话，这个时间还能缩短到10毫秒以内,很不错的不是吗？在维护开放列哦上的效率能提高的接近50%呢。

（呵呵，这里有些偷懒，并没有针对常用的排序方法把这里做完，只是弄了一个错误的东西上来估计了一下，大家莫怪，其实这些肯定是大家早已经研究过很多次的地方了，而我想谈论的重点，也并不在于此）


以上只是一个A*初学者对于A*的一些想法，还请高手多多指正
如果对A*寻路基础算法原理不清楚并且有兴趣的朋友，可以去gameres上看一下这篇文章
http://data.gameres.com/message.asp?TopicID=25439