-
大小: 4.45MB文件類型: .zip金幣: 2下載: 0 次發(fā)布日期: 2023-11-07
- 語言: C/C++
- 標(biāo)簽: C++??尋路算法??數(shù)據(jù)結(jié)構(gòu)??
資源簡介
A*算法，A*（A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問題的有效算法。算法中的距離估算值與實際值越接近，最終搜索速度越快。c++語言實現(xiàn)
代碼片段和文件信息
//?ConsoleApplication3.cpp?:?定義控制臺應(yīng)用程序的入口點。
//
#include?“stdafx.h“
#include?“iostream“
#include?
#include??
#include?
#define?STEP??10
#define?ANGLE?14
#define?ROW???10
#define?COL???10
using?namespace?std;
struct?Point
{??
Point（int?xint?y）
??{
??X=x;
??Y=y;
??F=0;
??G=0;
??H=0;
??parent=NULL;
??}
??Point（）
??{
??}
??void?CalcF（）
??{
??F=G+H;
??}
bool?operator<（Point?p2）??
{??
if?（F
return?false;??
}??
??Point?*parent;
??int?F;
??int?G;
??int?H;
??int?X;
??int?Y; ?
};
class?CFindPath
{
public:
CFindPath（）;
CFindPath（int?map[][COL]）;
~CFindPath（）;
Point?*GetPath（Point?startPoint?endbool?isAagle）;//獲取路徑鏈表;
list?GetSurroundPoint（Point?&bool）;//獲取周圍可到達(dá)的點;
bool?IsCanReach（int?xint?y）;//判斷是否是墻壁;
void?ChangePoint（Point?startPoint?point）;//改變已在開啟列表的點;
void?AddPoint（Point?startPoint?endPoint?point）;//添加不在開啟列表的點;
int?CalculateG（PointPoint?）;//計算G
int?CalculateH（Point?endPoint?point）;//計算H
bool?IsCanReach（Point?startint?xint?ybool?isAngle）;//判斷是否可到達(dá);
Point?*FindOpenListPoint（Point?p）;
Point?*FindColseListPoint（Point?p）;
Point?*FPoint（Point?p）;
private:
list?openList;//開啟列表;
list?colseList;//關(guān)閉列表;
list?temList;
int?points[ROW][COL];
};
CFindPath::CFindPath（）
{
}
CFindPath::CFindPath（int?map[][COL]）
{
for（int?i=0;i
}
CFindPath::~CFindPath（）
{
delete?points;
}
Point*?CFindPath::GetPath（Point?startPoint?endbool?isAngle）//核心算法A*路徑查找isAngle表示是否可以越過拐角;
{???
openList.push_back（start）;
while?（!openList.empty（））
{??
openList.sort（）;//根據(jù)F值由小到大排序;
Point?temp=openList.front（）;//取出F值最小的;
????colseList.push_back（temp）;//加入到關(guān)閉列表;
openList.pop_front（）;//開啟列表中刪除F值最小的;
list?surroundPoints=GetSurroundPoint（tempisAngle）;//取出周圍可到達(dá)的點;??????
while?（!surroundPoints.empty（））//對每個可到達(dá)的周圍的點進(jìn)行判斷;
{
?Point?point=surroundPoints.front（）;
if（FindOpenListPoint（point））//若開啟列表中存在這個點;
?ChangePoint（temppoint）;//判斷是否是最優(yōu)路徑如果是改變父結(jié)點若不是則什么也不做;
else
?????AddPoint（tempendpoint）;//若不在開啟列表則加入;
surroundPoints.pop_front（）;
}
???if（FindOpenListPoint（end））
return?FindOpenListPoint（end）;
}
??return?FindOpenListPoint（end）;
}
void?CFindPath::ChangePoint（Point?startPoint?point）//改變點的父結(jié)點重新計算F值;
{
int?G=CalculateG（startpoint）;
if（G
point.G=G;
point.CalcF（）;
}
}
void?CFindPath::AddPoint（Point?startPoint?endPoint?point）//添加點到開啟列表;
{???
point.parent=new?Point（start）;
point.G=CalculateG（startpoint）;
point.H=CalculateH（endpoint）;
point.CalcF（）;
openList.push_back（point）;
}
int??CFindPath::CalculateG（Point?startPoint?point）//計算G值
{???
int?parentG=0;
int?G=（abs（point.X-start.X）+abs（point.Y-start.Y））!=2?STEP:
?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2016-01-28?15:12??A星尋路算法c++\
?????目錄???????????0??2016-01-27?14:49??A星尋路算法c++\ConsoleApplication3\
?????文件?????9699328??2016-01-28?15:12??A星尋路算法c++\ConsoleApplication3.sdf
?????文件?????????924??2016-01-27?14:49??A星尋路算法c++\ConsoleApplication3.sln
?????文件???????31232??2016-01-28?15:12??A星尋路算法c++\ConsoleApplication3.v11.suo
?????文件????????6679??2016-01-28?15:11??A星尋路算法c++\ConsoleApplication3\ConsoleApplication3.cpp
?????文件????????4546??2016-01-27?14:49??A星尋路算法c++\ConsoleApplication3\ConsoleApplication3.vcxproj
?????文件????????1323??2016-01-27?14:49??A星尋路算法c++\ConsoleApplication3\ConsoleApplication3.vcxproj.filters
?????目錄???????????0??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\
?????文件????????1782??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\cl.command.1.tlog
?????文件???????14836??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\CL.read.1.tlog
?????文件????????1372??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\CL.write.1.tlog
?????文件??????????89??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\ConsoleApplication3.lastbuildstate
?????文件????????2518??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\ConsoleApplication3.log
?????文件??????415320??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\ConsoleApplication3.obj
?????文件?????1245184??2016-01-27?14:49??A星尋路算法c++\ConsoleApplication3\Debug\ConsoleApplication3.pch
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
?????文件???????????2??2016-01-28?15:01??A星尋路算法c++\ConsoleApplication3\Debug\li
............此處省略132個文件信息
評論
共有 條評論
川公網(wǎng)安備 51152502000135號