对A*算法的路径进行优化

如果你没有看过上一个文章的代码,请到这个传送门:A*算法的实现

注:优化最终路径,必然会对算法耗时造成一定的影响。

 

针对上一篇文章,我提到的设想,对路径进行分段处理,每一小段再进行一次A*,那么我们需要新增一个SearchEx接口,并对原本的Search接口进行修改。

Search新增一个参数,用来代替原本的BREAK_GAP常量宏,修改后的源代码如下:

 

 

[cpp][/cpp] view plaincopy

  1. bool CAStar::Search(int X, int Y, std::list<POINT> &lResult, double dbGapBreak)
  2. {
  3.     if(X < 0 || Y < 0
  4.         || X > m_dwMapWidth || Y > m_dwMapWidth ||
  5.         m_dwDestinationX < 0 || m_dwDestinationX < 0 ||
  6.         m_dwDestinationX > m_dwMapWidth || m_dwDestinationY > m_dwMapHeight)
  7.     {
  8.         //_outf(“坐标或地图参数错误!”);
  9.         return false;
  10.     }
  11.     LPAPOINT p = new APOINT;
  12.     p->x = X;
  13.     p->y = Y;
  14.     p->parent = NULL;
  15.     p->dbGap = _p2g(X, Y, m_dwDestinationX, m_dwDestinationY);
  16.     m_lOpen.push_front(p);//起始节点加入到开启列表
  17.     m_lSafe.push_back(p);//加入到公共容器,任何新分配的节点,都要加入到这里,便于算法执行完后清理
  18.     std::list<LPAPOINT>::iterator it;
  19.     DWORD dwTime = clock();
  20.     while(!m_lOpen.empty())
  21.     {
  22.         //这里就是反复遍历开启列表选择距离最小的节点
  23.         it = GetMingapNode();
  24.         if((*it)->dbGap <= dbGapBreak)
  25.             break;
  26.         p = *it;
  27.         GenerateSuccessors(it);
  28.     }
  29.     if(!m_lOpen.empty())
  30.     {
  31.         //如果列表不为空,从最后一个节点开始拷贝路径到返回值中
  32.         //_outf(“最终寻路到:%X, %X”, p->x, p->y);
  33.         POINT point;
  34.         while(p)
  35.         {
  36.             point.x = p->x;
  37.             point.y = p->y;
  38.             lResult.push_front(point);
  39.             p = p->parent;
  40.         }
  41.     }
  42.     for(it = m_lSafe.begin(); it != m_lSafe.end(); ++it)
  43.     {
  44.         //清理内存
  45.         if(*it != NULL)
  46.         {
  47.             m_pMap[(*it)->y][(*it)->x] = 1;
  48.             delete (*it);
  49.             *it = NULL;
  50.         }
  51.     }
  52.     m_lSafe.clear();//清空容器
  53.     //_outf(“耗时:%d 毫秒”, clock() – dwTime);
  54.     if(m_lOpen.empty())
  55.     {
  56.         //_outf(“寻路失败”);
  57.         return false;
  58.     }
  59.     m_lOpen.clear();//清空开启列表
  60.     //_outf(“寻路成功,节点数:%d”, lResult.size());
  61.     return true;
  62. }

 

 

 

新增的SearchEx源代码如下:

nBeginSift 参数为循环初始值,nEndSift为循环结束值,其实就是一个for循环的起始值与结束值。

这个循环的引用计数,最终会被 乘于 10 来作为距离分段选择路径进行路线优化

nBeginSift 与 nEndSift的间距越大,并不表示最终路径就越好,最终优化出来的路径,还是会和地形有关。

其实最好路径优化算法是按照角度的变化来选择路径优化,但是预计开销会比较大,有了这个优化方式作为基础,你可以自己去写根据角度变化来优化的算法。

 

[cpp][/cpp] view plaincopy

  1. bool CAStar::SearchEx(int X, int Y, std::list<POINT> &lResult, double dbGapBreak, int nBeginSift, int nEndSift)
  2. {
  3.     DWORD dwTime = clock();
  4.     if(!Search(X, Y, lResult, dbGapBreak))
  5.         return false;
  6.     std::list<POINT>::iterator it = lResult.begin();
  7.     std::list<POINT>::iterator it2 = it;
  8.     std::list<POINT> l2;
  9.     for(int i = nBeginSift; i < nEndSift; i++)
  10.     {
  11.         it = lResult.begin();
  12.         it2 = it;
  13.         for(;it != lResult.end(); ++it)
  14.         {
  15.             if(_p2g(it2->x, it2->y, it->x, it->y) > (double)(i * 10))
  16.             {
  17.                 SetDestinationPos(it->x, it->y);
  18.                 l2.clear();
  19.                 if(Search(it2->x, it2->y, l2, 0.0))
  20.                 {
  21.                     it = lResult.erase(it2, it);
  22.                     lResult.insert(it, (l2.begin()), (l2.end()));
  23.                 }
  24.                 it2 = it;
  25.             }
  26.         }
  27.     }
  28.     _outf(“耗时:%d 毫秒”, clock() – dwTime);
  29.     return true;
  30. }

 

 

 

 

以下为 nBeginSift = 6      nEndSift = 15 的优化结果。

测试时间结果:

[3368] 耗时:47 毫秒

 

标签