程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 對A*算法的路徑進行優化

對A*算法的路徑進行優化

編輯：C++入門知識

如果你沒有看過上一個文章的代碼，請到這個傳送門：A*算法的實現

注：優化最終路徑，必然會對算法耗時造成一定的影響。

針對上一篇文章，我提到的設想，對路徑進行分段處理，每一小段再進行一次A*，那麼我們需要新增一個SearchEx接口，並對原本的Search接口進行修改。

Search新增一個參數，用來代替原本的BREAK_GAP常量宏，在Search中，清理內存時，將地圖數據恢復。

修改後的源代碼如下：

[cpp]
bool CAStar::Search(int X, int Y, std::list<POINT> &lResult, double dbGapBreak)
{
    if(X < 0 || Y < 0
        || X > m_dwMapWidth || Y > m_dwMapWidth ||
        m_dwDestinationX < 0 || m_dwDestinationX < 0 ||
        m_dwDestinationX > m_dwMapWidth || m_dwDestinationY > m_dwMapHeight)
    {
        //_outf("坐標或地圖參數錯誤！");
        return false;
    }

    LPAPOINT p = new APOINT;
    p->x = X;
    p->y = Y;
    p->parent = NULL;
    p->dbGap = _p2g(X, Y, m_dwDestinationX, m_dwDestinationY);
    m_lOpen.push_front(p);//起始節點加入到開啟列表
    m_lSafe.push_back(p);//加入到公共容器，任何新分配的節點，都要加入到這裡，便於算法執行完後清理

    std::list<LPAPOINT>::iterator it;
    DWORD dwTime = clock();
    while(!m_lOpen.empty())
    {
        //這裡就是反復遍歷開啟列表選擇距離最小的節點
        it = GetMingapNode();
        if((*it)->dbGap <= dbGapBreak)
            break;
        p = *it;
        GenerateSuccessors(it);
    }

    if(!m_lOpen.empty())
    {
        //如果列表不為空，從最後一個節點開始拷貝路徑到返回值中
        //_outf("最終尋路到：%X, %X", p->x, p->y);
        POINT point;
        while(p)
        {
            point.x = p->x;
            point.y = p->y;
            lResult.push_front(point);
            p = p->parent;
        }
    }

    for(it = m_lSafe.begin(); it != m_lSafe.end(); ++it)
    {
        //清理內存
        if(*it != NULL)
        {
            m_pMap[(*it)->y][(*it)->x] = 1;//會被添加到m_lSafe的節點，一定是最初為1的節點，所以可以在這裡恢復地圖數據
            delete (*it);
            *it = NULL;
        }
    }

    m_lSafe.clear();//清空容器

    //_outf("耗時：%d 毫秒", clock() - dwTime);

    if(m_lOpen.empty())
    {
        //_outf("尋路失敗");
        return false;
    }

    m_lOpen.clear();//清空開啟列表
    //_outf("尋路成功，節點數：%d", lResult.size());
    return true;
}

bool CAStar::Search(int X, int Y, std::list<POINT> &lResult, double dbGapBreak)
{
if(X < 0 || Y < 0
  || X > m_dwMapWidth || Y > m_dwMapWidth ||
  m_dwDestinationX < 0 || m_dwDestinationX < 0 ||
  m_dwDestinationX > m_dwMapWidth || m_dwDestinationY > m_dwMapHeight)
{
  //_outf("坐標或地圖參數錯誤！");
  return false;
}

LPAPOINT p = new APOINT;
p->x = X;
p->y = Y;
p->parent = NULL;
p->dbGap = _p2g(X, Y, m_dwDestinationX, m_dwDestinationY);
m_lOpen.push_front(p);//起始節點加入到開啟列表
m_lSafe.push_back(p);//加入到公共容器，任何新分配的節點，都要加入到這裡，便於算法執行完後清理

std::list<LPAPOINT>::iterator it;
DWORD dwTime = clock();
while(!m_lOpen.empty())
{
  //這裡就是反復遍歷開啟列表選擇距離最小的節點
  it = GetMingapNode();
  if((*it)->dbGap <= dbGapBreak)
   break;
  p = *it;
  GenerateSuccessors(it);
}

if(!m_lOpen.empty())
{
  //如果列表不為空，從最後一個節點開始拷貝路徑到返回值中
  //_outf("最終尋路到：%X, %X", p->x, p->y);
  POINT point;
  while(p)
  {
   point.x = p->x;
   point.y = p->y;
   lResult.push_front(point);
   p = p->parent;
  }
}

for(it = m_lSafe.begin(); it != m_lSafe.end(); ++it)
{
  //清理內存
  if(*it != NULL)
  {
   m_pMap[(*it)->y][(*it)->x] = 1;//會被添加到m_lSafe的節點，一定是最初為1的節點，所以可以在這裡恢復地圖數據
   delete (*it);
   *it = NULL;
  }
}

m_lSafe.clear();//清空容器

//_outf("耗時：%d 毫秒", clock() - dwTime);

if(m_lOpen.empty())
{
  //_outf("尋路失敗");
  return false;
}

m_lOpen.clear();//清空開啟列表
//_outf("尋路成功，節點數：%d", lResult.size());
return true;
}

新增的SearchEx源代碼如下：

nBeginSift 參數為循環初始值，nEndSift為循環結束值，其實就是一個for循環的起始值與結束值。

這個循環的引用計數，最終會被乘於 10 來作為距離分段選擇路徑進行路線優化

nBeginSift 與 nEndSift的間距越大，並不表示最終路徑就越好，最終優化出來的路徑，還是會和地形有關。

其實最好路徑優化算法是按照角度的變化來選擇路徑優化，但是預計開銷會比較大，有了這個優化方式作為基礎，你可以自己去寫根據角度變化來優化的算法。

[cpp]
bool CAStar::SearchEx(int X, int Y, std::list<POINT> &lResult, double dbGapBreak, int nBeginSift, int nEndSift)
{
    DWORD dwTime = clock();
    if(!Search(X, Y, lResult, dbGapBreak))
        return false;
    std::list<POINT>::iterator it = lResult.begin();
    std::list<POINT>::iterator it2 = it;

    std::list<POINT> l2;
    for(int i = nBeginSift; i < nEndSift; i++)
    {
        it = lResult.begin();
        it2 = it;
        for(;it != lResult.end(); ++it)
        {
            if(_p2g(it2->x, it2->y, it->x, it->y) > (double)(i * 10))
            {
                SetDestinationPos(it->x, it->y);
                l2.clear();
                if(Search(it2->x, it2->y, l2, 0.0))
                {
                    it = lResult.erase(it2, it);
                    lResult.insert(it, (l2.begin()), (l2.end()));
                }
                it2 = it;
            }
        }
    }

    _outf("耗時：%d 毫秒", clock() - dwTime);
    return true;
}

bool CAStar::SearchEx(int X, int Y, std::list<POINT> &lResult, double dbGapBreak, int nBeginSift, int nEndSift)
{
DWORD dwTime = clock();
if(!Search(X, Y, lResult, dbGapBreak))
  return false;
std::list<POINT>::iterator it = lResult.begin();
std::list<POINT>::iterator it2 = it;

std::list<POINT> l2;
for(int i = nBeginSift; i < nEndSift; i++)
{
  it = lResult.begin();
  it2 = it;
  for(;it != lResult.end(); ++it)
  {
   if(_p2g(it2->x, it2->y, it->x, it->y) > (double)(i * 10))
   {
    SetDestinationPos(it->x, it->y);
    l2.clear();
    if(Search(it2->x, it2->y, l2, 0.0))
    {
     it = lResult.erase(it2, it);
     lResult.insert(it, (l2.begin()), (l2.end()));
    }
    it2 = it;
   }
  }
}

_outf("耗時：%d 毫秒", clock() - dwTime);
return true;
}