?

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

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

?

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

Search新增一个参数，用来代替原本的BREAK_GAP常量宏，在Search中，清理内存时，将地图数据恢复。

修改后的源代码如下：

?

?

[cpp]
bool CAStar::Search(int X, int Y, std::list &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::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 &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::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循环的起始值与结束值。