Astar寻路初探

AStar算法总结与实现（附Demo）关于A Star AlgorithmA star算法最早可追溯到1968年，在，是把启发式⽅法（heuristic approaches）如BFS，和常规⽅法如Dijsktra算法结合在⼀起的算法。

有点不同的是，类似BFS的启发式⽅法经常给出⼀个近似解⽽不是保证最佳解。

然⽽，尽管A star基于⽆法保证最佳解的启发式⽅法，A star却能保证找到⼀条最短路径。

公式表⽰为：f(n)=g(n)+h(n)f(n)是节点n从初始点到⽬标点的估价函数g(n)是在状态空间中从初始节点到n节点的实际代价h(n)是从n到⽬标节点最佳路径的估计代价观察A*寻路算法的运⾏轨迹假设起点为A（浅蓝⾊的个字）终点为B（深蓝⾊的格⼦）红⾊代表该格⼦为障碍物地图为20x20的格⼦显⽰FGH值的格⼦代表经过A*算法搜索并⽣成路径的格⼦有透明度变化的格⼦代表该格⼦有被搜索。

绿⾊格⼦代表的是搜索完成后A*得到的最优的路径A直接抵达B的情况下A越过直线障碍到达BA越过U型障碍到达BB为障碍物所包围着，A到达不了B的情况下总结与思考由4组图可以得到1.A*的消耗是⼀个及其不稳定的过程，消耗的最⼩值不低于直线路径上的消耗，消耗的最⼤值不⾼于遍历整张地图的消耗。

2.A*的消耗主要在搜索的搜索格⼦，以及对其FGH的操作上。

3.由1，2可以得出，在对运⾏速率和效率有要求的场景下，A*可能不是⼀个⽐较好选择。

算法步骤横向纵向的格⼦的单位消耗为10，对⾓单位消耗为14。

定义⼀个OpenList，⽤于存储和搜索当前最⼩值的格⼦。

定义⼀个CloseList，⽤于标记已经处理过的格⼦，以防⽌重复搜索。

开始搜索寻路1.将起点加⼊OpenList2.从OpenList中弹出F值最⼩的点作为当前点3.获取当前点九空格（除去⾃⼰）内所有的⾮障碍且不在CloseList内的邻居点4.遍历上⼀步骤得到的邻居点的集合，每个邻居点执⾏以下逻辑如果邻居点在OpenList中计算当前值的G与该邻居点的G值如果G值⽐该邻居点的G值⼩将当前点设置为该邻居点的⽗节点更新该邻居点的GF值若不在计算并设置当前点与该邻居点的G值计算并设置当前点与该邻居点的H值计算并设置该邻居点的F值将当前点设置为该邻居点的⽗节点5.判断终点是否在OpenList中，如果已在OpenList中，则返回该点，其⽗节点连起来的路径就是A*搜索的路径。

实验二：A*算法姓名班级：学号：一、实验目的掌握A*算法的原理,并会使用A*算法.二、实验仪器Pc vc6.0三、实验原理及过程A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。

公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)小于等于n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低，但能得到最优解。

如果估价值大于实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

寻路问题常见于各类游戏中角色寻路、三维虚拟场景中运动目标的路径规划、机器人寻路等多个应用领域。

迷宫寻路问题是在以方格表示的地图场景中，对于给定的起点、终点和障碍物（墙），如何找到一条从起点开始避开障碍物到达终点的最短路径。

四、实验结果五、实验心得本次实验感觉比较难，特别是算法的理解，虽然新建了工程，但基本没什么改动。

用mfc做的界面还是花了些功夫的。

在做之前看了许多相关的资料，但是核心的算法还不算很懂，自己写无法写出来。

但是关于核心语句以及相关功能还是了解的，读代码的能力也有所提高。

六、主要代码AstarTest.cpp#include "stdafx.h"#include "AstarTest.h"#include "AstarTestDlg.h"#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE[] = __FILE__;#endif/////////////////////////////////////////////////////////////////////////////// CAstarTestAppBEGIN_MESSAGE_MAP(CAstarTestApp, CWinApp)//{{AFX_MSG_MAP(CAstarTestApp)// NOTE - the ClassWizard will add and remove mapping macros here.// DO NOT EDIT what you see in these blocks of generated code!//}}AFX_MSGON_COMMAND(ID_HELP, CWinApp::OnHelp)END_MESSAGE_MAP()/////////////////////////////////////////////////////////////////////////////// CAstarTestApp constructionCAstarTestApp::CAstarTestApp(){// TODO: add construction code here,// Place all significant initialization in InitInstance}/////////////////////////////////////////////////////////////////////////////// The one and only CAstarTestApp objectCAstarTestApp theApp;/////////////////////////////////////////////////////////////////////////////// CAstarTestApp initializationBOOL CAstarTestApp::InitInstance(){AfxEnableControlContainer();// Standard initialization// If you are not using these features and wish to reduce the size// of your final executable, you should remove from the following// the specific initialization routines you do not need.#ifdef _AFXDLLEnable3dControls(); // Call this when using MFC in a shared DLL #elseEnable3dControlsStatic(); // Call this when linking to MFC statically#endifCAstarTestDlg dlg;m_pMainWnd = &dlg;int nResponse = dlg.DoModal();if (nResponse == IDOK){// TODO: Place code here to handle when the dialog is// dismissed with OK}else if (nResponse == IDCANCEL){// TODO: Place code here to handle when the dialog is// dismissed with Cancel}// Since the dialog has been closed, return FALSE so that we exit the// application, rather than start the application's message pump.return FALSE;}AstarTestDlg.cpp#include "stdafx.h"#include "AstarTest.h"#include "AstarTestDlg.h"#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE[] = __FILE__;#endif#include "AstarPathfinder.h"/////////////////////////////////////////////////////////////////////////////// CAboutDlg dialog used for App About#define INV ALID_POINT (CPoint(-1,-1)) //无效点,用作起始点和目标点的初值#define MIN(x,y) ( ( ( x ) <= ( y ) ) ? (x) : ( y ) )const int MARGIN = 20;class CAboutDlg : public CDialog{public:CAboutDlg();// Dialog Data//{{AFX_DATA(CAboutDlg)enum { IDD = IDD_ABOUTBOX };//}}AFX_DATA// ClassWizard generated virtual function overrides//{{AFX_VIRTUAL(CAboutDlg)protected:virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support //}}AFX_VIRTUAL// Implementationprotected://{{AFX_MSG(CAboutDlg)//}}AFX_MSGDECLARE_MESSAGE_MAP()};CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD){//{{AFX_DATA_INIT(CAboutDlg)//}}AFX_DATA_INIT}void CAboutDlg::DoDataExchange(CDataExchange* pDX){CDialog::DoDataExchange(pDX);//{{AFX_DATA_MAP(CAboutDlg)//}}AFX_DATA_MAP}BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)//{{AFX_MSG_MAP(CAboutDlg)// No message handlers//}}AFX_MSG_MAPEND_MESSAGE_MAP()/////////////////////////////////////////////////////////////////////////////// CAstarTestDlg dialogCAstarTestDlg::CAstarTestDlg(CWnd* pParent /*=NULL*/): CDialog(CAstarTestDlg::IDD, pParent){// Note that LoadIcon does not require a subsequent DestroyIcon in Win32m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);m_map = m_path = NULL;m_size = 16 ;m_intervals = 0;InitData();void CAstarTestDlg::DoDataExchange(CDataExchange* pDX){CDialog::DoDataExchange(pDX);//{{AFX_DATA_MAP(CAstarTestDlg)// DDX_Control(pDX, IDC_Y, m_y);// DDX_Control(pDX, IDC_X, m_x);//}}AFX_DATA_MAP}BEGIN_MESSAGE_MAP(CAstarTestDlg, CDialog)//{{AFX_MSG_MAP(CAstarTestDlg)ON_WM_SYSCOMMAND()ON_WM_PAINT()ON_WM_QUERYDRAGICON()ON_WM_LBUTTONDOWN()ON_WM_LBUTTONUP()ON_WM_MOUSEMOVE()ON_WM_SIZE()ON_WM_RBUTTONDOWN()ON_BN_CLICKED(IDC_FINDPA TH, OnFindpath)ON_BN_CLICKED(IDC_INIT, OnInit)//}}AFX_MSG_MAPEND_MESSAGE_MAP()/////////////////////////////////////////////////////////////////////////////// CAstarTestDlg message handlersBOOL CAstarTestDlg::OnInitDialog(){CDialog::OnInitDialog();// Add "About..." menu item to system menu.// IDM_ABOUTBOX must be in the system command range.ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);ASSERT(IDM_ABOUTBOX < 0xF000);CMenu* pSysMenu = GetSystemMenu(FALSE);if (pSysMenu != NULL){CString strAboutMenu;strAboutMenu.LoadString(IDS_ABOUTBOX);if (!strAboutMenu.IsEmpty()){pSysMenu->AppendMenu(MF_SEPARATOR);pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);}}// Set the icon for this dialog. The framework does this automatically// when the application's main window is not a dialogSetIcon(m_hIcon, TRUE); // Set big iconSetIcon(m_hIcon, FALSE); // Set small icon// TODO: Add extra initialization herereturn TRUE; // return TRUE unless you set the focus to a control}void CAstarTestDlg::OnSysCommand(UINT nID, LPARAM lParam){if ((nID & 0xFFF0) == IDM_ABOUTBOX){CAboutDlg dlgAbout;dlgAbout.DoModal();}else{CDialog::OnSysCommand(nID, lParam);}}// If you add a minimize button to your dialog, you will need the code below// to draw the icon. For MFC applications using the document/view model,// this is automatically done for you by the framework.void CAstarTestDlg::OnPaint(){if (IsIconic()){CPaintDC dc(this); // device context for paintingSendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);// Center icon in client rectangleint cxIcon = GetSystemMetrics(SM_CXICON);int cyIcon = GetSystemMetrics(SM_CYICON);CRect rect;GetClientRect(&rect);int x = (rect.Width() - cxIcon + 1) / 2;int y = (rect.Height() - cyIcon + 1) / 2;// Draw the icondc.DrawIcon(x, y, m_hIcon);}else{CDialog::OnPaint();}//绘制地图和基本元素(起始点目标点中间点)DrawMap();}// The system calls this to obtain the cursor to display while the user drags// the minimized window.HCURSOR CAstarTestDlg::OnQueryDragIcon(){return (HCURSOR) m_hIcon;}void CAstarTestDlg::OnLButtonDown(UINT nFlags, CPoint point){// TODO: Add your message handler code here and/or call defaultm_isLButtonDown = true;CPoint pt = point ;if( PointInMap(pt) && !IsEndPoint(pt)){CClientDC dc(this);//确定当前操作是设置还是清除障碍//1、鼠标左键按下时，鼠标所在位置如果为障碍则当前操作确定为清除障碍//2、鼠标左键按下时，鼠标所在位置如果为空且不是路径端点(起始点和目标点)// 则当前操作确定为设置障碍m_isDrawBlock = IsEmpty(m_map, pt) ;//设置障碍是要清除路点，清除障碍时避免清除路点,SetBlockOnMap(m_path, pt, !m_isDrawBlock && IsPathPoint(m_path,pt)) ;SetBlockOnMap(m_map, pt, m_isDrawBlock) ;DrawElement(&dc, pt) ;}CDialog::OnLButtonDown(nFlags, point);void CAstarTestDlg::OnLButtonUp(UINT nFlags, CPoint point){// TODO: Add your message handler code here and/or call defaultm_isLButtonDown = false ;CDialog::OnLButtonUp(nFlags, point);}void CAstarTestDlg::OnMouseMove(UINT nFlags, CPoint point){// TODO: Add your message handler code here and/or call defaultCPoint pt = point;if(m_isLButtonDown){if(PointInMap(pt) && !IsEndPoint(pt) ){CClientDC dc(this);//设置障碍是要清除路点，清除障碍时避免清除路点,SetBlockOnMap(m_path, pt, !m_isDrawBlock && IsPathPoint(m_path,pt)) ;SetBlockOnMap(m_map, pt, m_isDrawBlock);DrawElement(&dc, pt);}}CDialog::OnMouseMove(nFlags, point);}void CAstarTestDlg::OnSize(UINT nType, int cx, int cy){CDialog::OnSize(nType, cx, cy);// TODO: Add your message handler code here//计算地图单元格宽度m_intervals = ( MIN(cx, cy) - 2 * MARGIN ) / m_size ;}void CAstarTestDlg::OnRButtonDown(UINT nFlags, CPoint point){// TODO: Add your message handler code here and/or call defaultCPoint old_pt, pt = point;//该点在地图中且不是障碍和路点if( PointInMap(pt) && IsEmpty(m_map, pt) && !IsPathPoint(m_path, pt) ) {MAP_TYPE type;if(nFlags & MK_CONTROL) //Ctrl+RightClic设置目标点type = DEST;else //RightClic设置起始点type = SRC;switch(type){case DEST:old_pt = m_dst ;m_dst = pt ;break;case SRC:old_pt = m_src ;m_src = pt ;break;}CClientDC dc(this);//擦除旧点if(!(old_pt == INV ALID_POINT )){SetBlockOnMap(m_path, old_pt, false);DrawElement(&dc, old_pt);}//绘制新点SetBlockOnMap(m_path, pt, true);DrawElement(&dc, pt);}CDialog::OnRButtonDown(nFlags, point);}BOOL CAstarTestDlg::DestroyWindow(){// TODO: Add your specialized code here and/or call the base classif(m_map ) delete [] m_map ;if(m_path) delete [] m_path;return CDialog::DestroyWindow();//判断鼠标位置(pt)是否位于地图中//如果是则返回true, 并将pt转化为地图中坐标//否则返回false, pt保持原值bool CAstarTestDlg::PointInMap(CPoint& pt){int x, y;x = pt.x;y = pt.y;pt.x -= MARGIN ;pt.y -= MARGIN ;if(pt.x > 0 && pt.x < (m_size) * m_intervals&& pt.y > 0 && pt.y < (m_size) * m_intervals){char buf[128];pt.x = pt.x / m_intervals;pt.y = pt.y / m_intervals;//用于在屏幕中显示地图坐标和鼠标坐标对(主要用于调试)wsprintf(buf,"%2d(%3d)", pt.x, x);// m_x.SetWindowText(buf);wsprintf(buf,"%2d(%3d)", pt.y, y);// m_y.SetWindowText(buf);return true;}return false;}//利用A*寻径算法搜寻路径//目标点可达时，在路点地图中标记路径并在屏幕上显示//目标点不可达时，出错提示并返回void CAstarTestDlg::OnFindpath(){// TODO: Add your control notification handler code hereif( m_src == INV ALID_POINT || m_dst == INV ALID_POINT ){MessageBox(_T("请设置起始点和目标点!"),_T("AstarTest"),MB_OK);return ;}ClearPath(); //清除旧路径try{AstarPathfinder astar ;CClientDC dc(this) ;CPoint pt ;astar.InitAstarTileMap(m_map,m_size,m_size);astar.NewPath(m_src.x, m_src.y, m_dst.x, m_dst.y);while(!astar.ReachedGoal()){astar.PathNextNode();pt.x = astar.NodeGetX();pt.y = astar.NodeGetY() ;SetBlockOnMap(m_path, pt, true);DrawElement(&dc, pt );}}catch(NoWay){MessageBox("目标点不可达!","错误",MB_OK);}}void CAstarTestDlg::OnInit(){InitData();Invalidate();}void CAstarTestDlg::InitData(){m_isLButtonDown = false ;m_isDrawBlock = false ;m_src = m_dst = INV ALID_POINT ;if(m_map ) delete []m_map ;if(m_path) delete []m_path ;m_map = new BYTE[ (m_size * m_size + 7) / 8 ];m_path = new BYTE[ (m_size * m_size + 7) / 8 ];//初始化地图和路点(PathPoint)信息for(int i = 0; i < (m_size * m_size + 7) / 8; i++)m_map[i] = m_path[i] = 0x00;}void CAstarTestDlg::DrawMap(){CClientDC dc(this);for(int x = 0; x < m_size; x++ ){for(int y = 0; y < m_size; y++){CPoint pt(x, y) ;DrawElement(&dc, pt);}}}void CAstarTestDlg::ClearPath(){CClientDC dc(this);//循环遍历整个地图for(int x = 0; x < m_size; x++ ){for(int y = 0; y < m_size; y++){CPoint pt(x, y);//如果该点是路点且在路径中间, 则清除if(IsPathPoint(m_path, pt) && MID ==GetMapOrElementType(pt)){SetBlockOnMap(m_path, pt, false);DrawElement(&dc, pt);}}}}//判断pt是否是端点(起始点和目标点)bool CAstarTestDlg::IsEndPoint(CPoint pt){if(pt == m_src || pt == m_dst)return true;return false;}//判断pt是否是在路径上bool CAstarTestDlg::IsPathPoint(BYTE *pmap, CPoint pt){return !IsEmpty(pmap, pt);}//判断地图中该点是否为障碍，返回true表示不是障碍bool CAstarTestDlg::IsEmpty(BYTE * pMap, CPoint pt){BYTE tmp;int r, c;r = ((pt.y * m_size ) + pt.x) / 8;c = ((pt.y * m_size ) + pt.x) % 8;tmp = pMap[r] >> (7-c);if(tmp & 0x01)return false;return true;}//函数功能:在地图中设置或清除某位//参数含义:// 1、pmap为地图指针, pmap = m_map 时表示地形地图// pmap = m_path时表示路点地图// 2、pt地图中的某点// 3、bSet为true置位，为false清除void CAstarTestDlg::SetBlockOnMap(BYTE * pMap, CPoint pt, bool bSet) {int r, c;BYTE tmp1 = 0x01, tmp2 = 0xff;r = ((pt.y * m_size ) + pt.x) / 8;c = ((pt.y * m_size ) + pt.x) % 8;tmp1 = tmp1 << (7-c);if(bSet)pMap[r] |= tmp1 ; //设置elsepMap[r] &= tmp1^tmp2 ; //清除}MAP_TYPE CAstarTestDlg::GetMapOrElementType(CPoint pt){MAP_TYPE type;if( IsEmpty(m_map, pt) ){if(IsPathPoint(m_path, pt)){if(pt == m_src) type = SRC;else if (pt == m_dst) type = DEST;else type = MID;}else type = EMPTY;}else type = BLOCK;return type ;}void CAstarTestDlg::DrawElement(CDC *pdc, CPoint pt){COLORREF rgb[] = { RGB(255, 0, 0), //起始点颜色RGB( 0, 255, 0), //目标点颜色RGB(0, 0, 0), //中间点颜色RGB(0, 100, 0), //障碍块颜色RGB(255, 255, 255), //地图背景色};MAP_TYPE type = GetMapOrElementType(pt);CRect rect;CPen pen( PS_SOLID, 1, RGB(0,0,0) );CPen *pOldPen;CBrush brush( rgb[type] ), BKbrush( rgb[EMPTY] );CBrush *pOldBrush;rect.left = MARGIN + pt.x * m_intervals ;rect.top = MARGIN + pt.y * m_intervals ;rect.right = MARGIN + (pt.x + 1) * m_intervals + 1 ;rect.bottom = MARGIN + (pt.y + 1) * m_intervals + 1 ;pOldPen = pdc->SelectObject(&pen);switch(type){case EMPTY:case BLOCK:pOldBrush = pdc->SelectObject(&brush);pdc->Rectangle(&rect);pdc->SelectObject(pOldBrush);break;case SRC:case DEST:case MID://绘制背景pOldBrush = pdc->SelectObject(&BKbrush);pdc->Rectangle(&rect);//绘制路点pOldBrush = pdc->SelectObject(&brush);rect.DeflateRect(m_intervals/4, m_intervals/4);pdc->Ellipse(&rect);pdc->SelectObject(pOldBrush);break;}pdc->SelectObject(pOldPen);}AstarPathFinder.cpp#include "StdAfx.h"#include "AstarPathFinder.h"//#include "DirectDrawClass.h"////////////////////////////////////////////////////////////////////////////////// Constructor Destructor // ////////////////////////////////////////////////////////////////////////////////AstarPathfinder::AstarPathfinder(){Stack = ( STACK* )calloc(1,sizeof( STACK ));isPath = FALSE;OPEN = NULL;CLOSED = NULL;PATH = NULL;TileMap = NULL; // Sets the A* Tilemap append on CDXMap}////////////////////////////////////////////////////////////////////////////////AstarPathfinder::~AstarPathfinder(){FreeNodes();free(Stack);if (TileMap != NULL){ delete TileMap;TileMap = NULL;}}////////////////////////////////////////////////////////////////////////////////// Public Member Functions // ////////////////////////////////////////////////////////////////////////////////void AstarPathfinder::InitAstarTileMap(BYTE *pMap, int w,int h){COLS = w; // 障碍图的宽度ROWS = h; // 障碍图的高度TOTAL_TILES = ROWS * COLS; // 障碍图的尺寸unsigned long BufSize;BufSize = (TOTAL_TILES + 7) >> 3;if(TileMap != NULL){ delete TileMap;TileMap = NULL;}TileMap = new BYTE[BufSize];memcpy(TileMap, pMap, BufSize);}////////////////////////////////////////////////////////////////////////////////BOOL AstarPathfinder::NewPath(int sx,int sy, int dx,int dy){if ( FreeTile(dx,dy)&&FreeTile(sx,sy) //起始点和目标点不在障碍上&& (TileNum(sx,sy)!=TileNum(dx,dy)) ) //起始点和目标点坐标不同{FreeNodes(); // clear node listsFindPath(sx,sy,dx,dy); //寻找路径, 成功的话正常结束,否则抛出NoWay异常return (isPath=TRUE);}else //否则, 不存在路径return (isPath=FALSE);}////////////////////////////////////////////////////////////////////////////////BOOL AstarPathfinder::ReachedGoal(void) // check it's return value before getting { // the node entriesif ( !isPath ) return TRUE; // this looks a little bit strangeif ( PATH->Parent != NULL ) // but prevents illegal calls of ::PathNextNode() return FALSE; // or ::PathGet*()elsereturn TRUE;}////////////////////////////////////////////////////////////////////////////////int AstarPathfinder::TileNum(int x, int y){ if (x<0 || x>=COLS || y<0 || y>=ROWS) return 0;return (y*COLS + x); // The reason I add COLS+1 to// tile number is because I want the tile number to start at the 2nd// the column and the 2nd row. Because if we do this we don't have to have// a special case to test if at a boundary. In the function BoundaryTiles// I place 1's around the boundary, in this way when I call the function// FreeTile() it returns false because we can't go there.}////////////////////////////////////////////////////////////////////////////////int AstarPathfinder::FreeTile(int x, int y){ // returns 1 if tile is free(nothing on it).// Note: if TileMap[equation]==0 it means free so just !(not) it.if (x<0 || x>=COLS || y<0 || y>=ROWS) //边界检查{ return 0;}else //点(x, y)合法{ int bytes, bits, val, index;index = y * COLS + x;bytes = index >> 3; //计算字节地图中表示该点的位bits = index & 0x07;val = TileMap[bytes] >> (7 - bits);if((val & 0x01) == 0){ return 1;}else{ return 0;}}}////////////////////////////////////////////////////////////////////////////////// Private Member Functions // ////////////////////////////////////////////////////////////////////////////////void AstarPathfinder::FreeNodes(void){ NODE *Node, *OldNode;if ( OPEN != NULL ){ Node = OPEN->NextNode;while ( Node != NULL ){ OldNode = Node;Node = Node->NextNode;free(OldNode);}}if ( CLOSED != NULL ){ Node = CLOSED->NextNode;while ( Node != NULL ){ OldNode = Node;Node = Node->NextNode;free(OldNode);}}}////////////////////////////////////////////////////////////////////////////////// A* Algorithm // ////////////////////////////////////////////////////////////////////////////////void AstarPathfinder::FindPath(int sx, int sy, int dx, int dy){NODE *Node, *BestNode;int TileNumDest;TileNumDest = TileNum(sx, sy);OPEN =( NODE* )calloc(1,sizeof( NODE ));CLOSED =( NODE* )calloc(1,sizeof( NODE ));Node=( NODE* )calloc(1,sizeof( NODE ));Node->g = 0; //实际走过的距离Node->h = (dx-sx)*(dx-sx) + (dy-sy)*(dy-sy); //当前点到达目标点的估计距离// should really use sqrt().Node->f = Node->g + Node->h; //启发式函数, f值小的点优先试探f(n) = g(n) + h(n).Node->NodeNum = TileNum(dx, dy);Node->x = dx;Node->y = dy;OPEN->NextNode=Node; // make Open List point to first node for (;;){BestNode=ReturnBestNode();if (BestNode->NodeNum == TileNumDest) // if we've found the end, break and finishbreak;GenerateSuccessors(BestNode,sx,sy);}PATH = BestNode;}////////////////////////////////////////////////////////////////////////////////AstarPathfinder::NODE*AstarPathfinder::ReturnBestNode(void){NODE *tmp;if ( OPEN->NextNode == NULL ){/*char message[128];sprintf(message,"No more nodes on OPEN: Perhaps tilenum destination not reachable!");MessageBox(0, message, "Error A* Pathfinder", MB_OK | MB_ICONERROR);PostQuitMessage(0);*///在测试程序中直接PostQuitMessage(0)结束会导致异常//故采用c++中的异常异常机制处理寻径失败的情况//OPEN为空,寻径失败,抛出异常throw NoWayException();}// Pick Node with lowest f, in this case it's the first node in list// because we sort the OPEN list wrt lowest f. Call it BESTNODE.//从OPEN中取BestNode(取f值最小Node,不一定为唯一)tmp = OPEN->NextNode; // point to first node on OPENOPEN->NextNode = tmp->NextNode; // Make OPEN point to nextnode or NULL.// Next take BESTNODE (or temp in this case) and put it on CLOSED//将BestNode插入CLOSED集tmp->NextNode = CLOSED->NextNode;CLOSED->NextNode = tmp;return(tmp);}//////////////////////////////////////////////////////////////////////////////////依次探测点n(BestNode)周围的八个方向上的点,生成后继集M//算法将该点到相邻八个方向上的点的距离都认定为1//这样作简化了计算, 但会出现不符合常识的寻径结果//本算也没有处理切墙角的情况,会导致穿越墙角void AstarPathfinder::GenerateSuccessors(AstarPathfinder::NODE *BestNode, int dx, int dy) {int x, y;//从目标点回推起始点, 方向设置就如下标注, dx, dy 为起始点坐标// Upper-Leftif ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y-TILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);// Upperif ( FreeTile(x=BestNode->x, y=BestNode->y-TILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);// Upper-Rightif ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y-TILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);// Rightif ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y) )GenerateSucc(BestNode,x,y,dx,dy);// Lower-Rightif ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y+TILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);// Lowerif ( FreeTile(x=BestNode->x, y=BestNode->y+TILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);// Lower-Leftif ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y+TILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);// Leftif ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y) )//////////////////////////////////////////////////////////////////////////////////算法中的核心部分//对点n的后继点集合M中的每个点m, 分情况逐一考虑:// 1.m在OPEN集中// 如果通过点n到达点m会使点m的g更小, 则修改点m的parent指针指向点n.// 2.m在CLOSE集中// 1) 如果通过点n到达点m会使点m的g更小, 则修改点m的parent指针指向点n. // 2) 对修改过的点m, (利用深度优先算法)遍历其子节点// (该A*算法利用栈记录f值变化过--变小--的节点,只遍历受影响的子节点),// 如果通过m到达其子节点具有更小的g值,则修改该子节点的g值和f值// 并使其回指父节点. (确保回指一条最短的路径)// 3.m是新点(既不在OPEN集中也不在CLOSE集中)// 生成新节点加入OPEN集,插入时确保按节点的f值排序.void AstarPathfinder::GenerateSucc(AstarPathfinder::NODE *BestNode,int x, int y, int dx, int dy) {int g, TileNumS, c = 0;NODE *Old, *Successor;g = BestNode->g+1; // g(Successor)=g(BestNode)+cost of getting from BestNode to SuccessorTileNumS = TileNum(x,y); // identification purposes// if equal to NULL then not in OPEN list, else it returns the Node in Oldif ( (Old=CheckOPEN(TileNumS)) != NULL ){for( c = 0; c < 8; c++)// Add Old to the list of BestNode's Children (or Successors).if( BestNode->Child[c] == NULL )break;BestNode->Child[c] = Old;// if our new g value is < Old's then reset Old's parent to point to BestNodeif ( g < Old->g ){Old->Parent = BestNode;Old->g = g;Old->f = g + Old->h;}}// if equal to NULL then not in OPEN list, else it returns the Node in Oldelse if ( (Old=CheckCLOSED(TileNumS)) != NULL ){ for( c = 0; c< 8; c++)// Add Old to the list of BestNode's Children (or Successors).if ( BestNode->Child[c] == NULL )BestNode->Child[c] = Old;// if our new g value is < Old's then reset Old's parent to point to BestNodeif ( g < Old->g ){Old->Parent = BestNode;Old->g = g;Old->f = g + Old->h;// Since we changed the g value of Old, we need downwards, i.e.// to propagate this new value do a Depth-First traversal of the tree!PropagateDown(Old);}}else{Successor = ( NODE* )calloc(1,sizeof( NODE ));Successor->Parent = BestNode;Successor->g = g;Successor->h = (x-dx)*(x-dx) + (y-dy)*(y-dy); // should do sqrt()Successor->f = g+Successor->h;// care about the distance but just which branch looks// better this should suffice. Anyayz it's faster.Successor->x = x;Successor->y = y;Successor->NodeNum = TileNumS;Insert(Successor); // Insert Successor on OPEN list wrt ffor( c =0; c < 8; c++)// Add Old to the list of BestNode's Children (or Successors).if ( BestNode->Child[c] == NULL )break;BestNode->Child[c] = Successor;}}////////////////////////////////////////////////////////////////////////////////AstarPathfinder::NODE*AstarPathfinder::CheckOPEN(int tilenum){NODE *tmp;tmp = OPEN->NextNode;while ( tmp != NULL ){if ( tmp->NodeNum == tilenum )elsetmp = tmp->NextNode;}return(NULL);}////////////////////////////////////////////////////////////////////////////////AstarPathfinder::NODE*AstarPathfinder::CheckCLOSED(int tilenum){NODE *tmp;tmp = CLOSED->NextNode;while ( tmp != NULL ){if ( tmp->NodeNum == tilenum )return(tmp);elsetmp = tmp->NextNode;}return(NULL);}//////////////////////////////////////////////////////////////////////////////////将节点按f值大小插入OPEN集void AstarPathfinder::Insert(AstarPathfinder::NODE *Successor) {NODE *tmp1, *tmp2;int f;if ( OPEN->NextNode == NULL ){OPEN->NextNode = Successor;return;}// insert into OPEN successor wrt ff = Successor->f;tmp1 = OPEN;tmp2 = OPEN->NextNode;while ( (tmp2 != NULL) && (tmp2->f < f) ){tmp2 = tmp2->NextNode;}Successor->NextNode = tmp2;tmp1->NextNode = Successor;}//////////////////////////////////////////////////////////////////////////////////遍历节点old的所有g值变小的子节点，修改其g值和f值//深度优先遍历过程中用栈记录该g值变小的节点void AstarPathfinder::PropagateDown(AstarPathfinder::NODE *Old){int c, g;NODE *Child, *Father;g = Old->g; // alias.for ( c = 0; c < 8; c++){if ( (Child=Old->Child[c]) == NULL ) // create alias for faster access.break;if ( g+1 < Child->g){ Child->g = g+1;Child->f = Child->g + Child->h;Child->Parent = Old; // reset parent to new path.Push(Child); // Now the Child's branch need to be } // checked out. Remember the new cost must be propagated down.}while ( Stack->NextStackPtr != NULL ){Father = Pop();for (c = 0; c<8; c++){// we may stop the propagation 2 ways: eitherif ( (Child=Father->Child[c]) == NULL )break;// there are no children, or that the g value of// the child is equal or better than the cost we're propagatingif ( Father->g+1 < Child->g ){Child->g = Father->g+1;Child->f = Child->g+Child->h;Child->Parent = Father;Push(Child);}}}////////////////////////////////////////////////////////////////////////////////// STACK FUNCTIONS // //////////////////////////////////////////////////////////////////////////////////栈用于记录需要遍历的节点void AstarPathfinder::Push(AstarPathfinder::NODE *Node){STACK *tmp;tmp =( STACK* )calloc(1,sizeof( STACK ));tmp->NodePtr = Node;tmp->NextStackPtr = Stack->NextStackPtr;Stack->NextStackPtr = tmp;}////////////////////////////////////////////////////////////////////////////////AstarPathfinder::NODE*AstarPathfinder::Pop(void){NODE *tmp;STACK *tmpSTK;tmpSTK = Stack->NextStackPtr;tmp = tmpSTK->NodePtr;Stack->NextStackPtr = tmpSTK->NextStackPtr;free(tmpSTK);return(tmp);}。

基于改进A_Start算法的地图游戏寻径A_Start（A－SｔAｒ）算法是一种启发式搜索策略，是在静态地图中寻找最短路径的有效方法。

A_Start 算法的估价函数f(x)定义为从起始点到节点ｘ已付出的实际代价与节点ｘ到达目标点的接近程度估计值总和，是代价函数ｇ(x)与启发函数ｈ(x)的折中。

启发函数ｈ(x)的选取直接关系到能否找到最短路径（最优解）。

A_Start算法搜索思想如下：１）新建OPEN表和CLOSED表，初始均为空。

２）在OPEN表中添加起始节点S。

３）若OPEN表为空则失败退出，否则取最小f 值节点作为当前考察点ｘ。

４）将节点ｘ从OPEN表移至CLOSED表。

５）若节点ｘ为目标节点，则最优解找到成功退出，否则，扩展节点ｘ并生成后继节点N。

６）对节点ｘ所有后继节点N 进行考察：第一：对于后继节点N 有ｇ（N）＝ｇ(x)＋ｇ（ｘ，N）。

第二：创建从后继节点N 返回节点ｘ的指针。

第三：若节点N 为OPEN表的旧有节点，将旧有节点记为ｏ，将节点N 添加至ｘ的子节点表中。

如果f（N）＜f（ｏ），则f（ｏ）＝f（N）。

若节点N 不在OPEN表中，则判断它是否在CLOSED表中。

第四：若节点N 为CLOSED表的旧有节点，将旧有节点记为ｏ，将节点N 添加至ｘ的子节点表中。

如果f（N）＜f（ｏ），则f（ｏ）＝f（N）。

否则将它添加至OPEN表和ｘ的后继节点表。

第五：计算f 值，返回步骤３）继续判断。

A_Start搜索算法的游戏寻径策略高效，但仍有一些不足之处。

首先，在寻径过程中，随着节点的扩展，会对OPEN表进行反复遍历；在大规模游戏中，反复遍历会严重影响搜索效率。

其次，在寻路过程中，根据A_Start算法的搜索策略，会对具有相同f 值节点进行对比考察；但是只有靠近目标的节点才是最优节点，导致产生大量对非最优节点的考察，直接影响搜索效率。

A_Start算法改进1、混合数据结构A_Start寻路过程中，随着节点的扩展，会对OPEN表进行反复遍历，本研究针对反复遍历OPEN表问题，使用混合数据结构对OPEN表节点进行存储和标记。

混合astar算法摘要：1.混合A*算法的概述2.混合A*算法的基本原理3.混合A*算法的优缺点4.混合A*算法的应用实例5.混合A*算法的未来发展正文：一、混合A*算法的概述混合A*算法（Hybrid A* Algorithm）是一种基于A*算法的改进算法，主要用于寻路和图形搜索。

A*算法是一种启发式搜索算法，它能够在搜索过程中根据启发式函数的值来选择下一个节点，从而快速找到最短路径。

然而，在复杂环境中，A*算法可能会陷入局部最优解，因此，混合A*算法应运而生，它结合了多种策略，以提高搜索效率和准确性。

二、混合A*算法的基本原理混合A*算法的核心思想是在A*算法的基础上，引入局部搜索算法和模拟退火算法等策略，以提高搜索效果。

具体来说，混合A*算法主要包括以下几个步骤：1.初始化：设置起始节点和目标节点，构建待搜索的图形环境。

2.选择节点：根据A*算法的规则，选择具有最小启发式函数值的节点作为当前节点。

3.局部搜索：在当前节点的基础上，使用局部搜索算法（如模拟退火算法）进行搜索，找到若干个可行的邻居节点。

4.扩展：根据启发式函数的值，选择一个最优的邻居节点作为新的当前节点，并更新待搜索的图形环境。

5.回溯：当新当前节点为目标节点时，搜索成功，回溯得到最短路径；否则，回到第2 步继续搜索。

6.重复：在搜索过程中，当待搜索的图形环境发生变化时，可能需要重新初始化或调整搜索策略。

三、混合A*算法的优缺点混合A*算法的优点主要体现在以下几个方面：1.具有较强的适应性：混合A*算法能够根据不同的环境和任务，灵活地选择和调整搜索策略。

2.较高的搜索效率：通过引入局部搜索算法和模拟退火算法等策略，混合A*算法能够在较短的时间内找到最短路径。

3.能够避免局部最优解：混合A*算法通过引入多种策略，可以有效地跳出局部最优解，找到全局最优解。

然而，混合A*算法也存在一些缺点：1.计算复杂度较高：由于需要同时考虑多种策略，混合A*算法的计算复杂度相对较高。

A*算法原理简介A*（A-Star)算法是一种静态路网中求解最短路最有A star算法在静态路网中的应用效的方法。

公式表示为： f(n)=g(n)+h(n),其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。

但能得到最优解。

如果估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

估价值与实际值越接近估价函数取得就越好例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。

明显优于Dijstra算法的毫无无方向的向四周搜索。

conditions of heuristicOptimistic (must be less than or equal to the real cost)As close to the real cost as possible详细内容主要搜索过程伪代码如下：创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。

算起点的估价值;将起点放入OPEN表;while(OPEN!=NULL){从OPEN表中取估价值f最小的节点n;if(n节点==目标节点){break;}for(当前节点n 的每个子节点X){算X的估价值;if(X in OPEN){if( X的估价值小于OPEN表的估价值 ){把n设置为X的父亲;更新OPEN表中的估价值; //取最小路径的估价值}}if(X inCLOSE) {if( X的估价值小于CLOSE表的估价值 ){把n设置为X的父亲;更新CLOSE表中的估价值;把X节点放入OPEN //取最小路径的估价值}}if(X not inboth){把n设置为X的父亲;求X的估价值;并将X插入OPEN表中; //还没有排序}}//end for将n节点插入CLOSE表中;按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。

易语言摇杆寻路算法易语言摇杆寻路算法可以使用A*算法实现。

A*算法是一种基于启发式搜索的寻路算法，通过在地图上搜索最短路径，即从起点到终点的最短路径。

下面是使用易语言编写的A*算法的摇杆寻路示例程序：pascal判断一个点是否在地图范围内func InMap(x, y, map_width, map_height) {return x >= 0 && x < map_width && y >= 0 && y < map_height; }计算两点之间的曼哈顿距离func ManhattanDistance(x1, y1, x2, y2) {return x2 - x1 + y2 - y1 ;}A*算法寻路函数func AStar(start_x, start_y, end_x, end_y, map_width, map_height,map_data) {创建开放列表和关闭列表open_list = [[start_x, start_y]];close_list = [];创建用于记录父节点和G、H、F值的辅助数组parent_nodes = [[[start_x, start_y], -1, -1]]; 父节点、G值、H值、F 值创建移动方向的数组directions = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]];开始循环直到找到路径或者无法找到路径while !isempty(open_list) {在开放列表中找到F值最小的节点作为当前节点min_f_value = 9999;current_index = -1;for i = 0 to len(open_list)-1 {f_value = parent_nodes[open_list[i]][3];if f_value < min_f_value {min_f_value = f_value;current_index = i;}}将当前节点从开放列表移除，并加入关闭列表current_node = open_list[current_index];open_list - = [current_node];close_list + = [current_node];curr_x = current_node[0];curr_y = current_node[1];找到目标节点，构建路径并返回if curr_x = end_x && curr_y = end_y {path = [];while parent_nodes[current_node][0] != -1 {path = [current_node] + path;current_node = parent_nodes[current_node][0];}return path;}遍历当前节点的邻居节点for direction in directions {next_x = curr_x + direction[0];next_y = curr_y + direction[1];判断下一个节点是否在地图范围内if !InMap(next_x, next_y, map_width, map_height) { continue;}判断下一个节点是否为障碍物if map_data[next_x][next_y] = 1 {continue;}计算下一个节点的G、H、F值G_value = parent_nodes[current_node][1] + 1;H_value = ManhattanDistance(next_x, next_y, end_x, end_y); F_value = G_value + H_value;判断下一个节点是否已经在关闭列表中if [next_x, next_y] in close_list {continue;}如果下一个节点已经在开放列表中，判断是否更新G值和F值if [next_x, next_y] in open_list {if G_value < parent_nodes[[next_x, next_y]][1] {parent_nodes[[next_x, next_y]][0] = current_node;parent_nodes[[next_x, next_y]][1] = G_value;parent_nodes[[next_x, next_y]][3] = F_value;}} else {将下一个节点加入开放列表open_list + = [[next_x, next_y]];parent_nodes + = [[current_node, G_value, H_value, F_value]];}}}无法找到路径，返回空路径return [];}使用示例定义地图数据，0表示可以通过的路径，1表示障碍物map_data = [[0, 0, 0, 0, 0],[0, 1, 1, 1, 0],[0, 0, 0, 0, 0],[0, 1, 1, 1, 0],[0, 0, 0, 0, 0]];从(0, 0)点到(4, 4)点寻路start_x = 0;start_y = 0;end_x = 4;end_y = 4;path = AStar(start_x, start_y, end_x, end_y, len(map_data),len(map_data[0]), map_data);print("Path:", path);输出结果：Path: [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [1, 4], [2, 4], [3, 4], [4, 4]]以上就是使用易语言编写的A*算法的摇杆寻路示例程序。

人工智能作业：A*算法最优性A*算法，作为启发式搜索算法中的一种，是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。

A*算法最为核心的部分，就在于它的一个估值函数的设计上：f(n)=g(n)+h(n)其中f(n)是每个可能试探点的估值，它有两部分组成：一部分，为g(n)，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。

另一部分，即h(n)，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值，h(n)设计的好坏，直接影响着具有此种启发式函数的启发式算法的是否能称为A*算法。

一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是：1、搜索树上存在着从起始点到终了点的最优路径。

2、问题域是有限的。

3、所有结点的子结点的搜索代价值>0。

4、h(n)=<h*(n) （h*(n)为实际问题的代价值）。

当此四个条件都满足时，一个具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法，并一定能找到最优解。

证明A*算法的最优性：定理：A*算法是可采纳的，即若存在从初始节点S0到目标节点Sg 的路径，则A*算法必能结束在最佳路径上。

证明A*算法只能终止在最佳路径上（反证法）。

假设A*算法未能终止在最佳路径上，而是终止在某个目标节点t 处，则有但由引理，在A*算法结束前，必有最佳路径上的一个节点n’在Open 表中，且有)()()(0*t f S f n f <≤' ，这时，A*算法一定会选择n’来扩展，而不可能选择t ，从而也不会去测试目标节点t ，这就与假设A*算法终止在目标节点t 相矛盾。

因此，A*算法只能终止在最佳路径上。

A*算法的搜索效率很大程度上取决于估价函数h(n)。

一般说来，在满足h(n)≤h*(n)的前提下，h(n)的值越大越好。

h(n)的值越大，说明它携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索的效率就越高。

混合astar算法摘要：一、混合A*算法简介1.A*算法的原理2.混合A*算法的提出二、混合A*算法的优化1.路径平滑2.启发式函数改进3.局部搜索策略三、混合A*算法的应用领域1.路径规划2.机器学习四、混合A*算法的优缺点1.优点a.计算速度快b.搜索效率高c.适用范围广2.缺点a.可能会陷入局部最优解b.启发式函数的选择影响搜索效果正文：混合A*算法是一种将A*算法与其他搜索算法相结合的优化算法，旨在提高搜索效率和计算速度。

A*算法是一种广泛应用于寻路和路径规划的算法，其基本思想是以目标点为中心，扩展周围节点，并逐步向外围扩展，直到找到目标节点或达到最大搜索深度。

混合A*算法在A*算法的基础上进行优化，主要体现在路径平滑、启发式函数改进和局部搜索策略方面。

路径平滑是指在搜索过程中，对节点进行评分时考虑路径的平滑程度，以减少搜索树中的节点数量，从而提高搜索效率。

启发式函数改进是通过选择更合适的启发式函数来引导搜索过程，从而减少搜索的盲目性，提高搜索效果。

局部搜索策略是在搜索过程中，根据当前节点的状态，采取不同的搜索策略，以提高搜索效率。

混合A*算法广泛应用于路径规划、机器学习等领域。

在路径规划方面，混合A*算法可以有效地解决寻路问题，如游戏中的智能寻路、无人驾驶中的路径规划等。

在机器学习方面，混合A*算法可以用于解决组合优化问题，如旅行商问题（TSP）、装载问题等。

混合A*算法的优点在于计算速度快、搜索效率高、适用范围广。

然而，它也存在一些缺点，如可能会陷入局部最优解、启发式函数的选择影响搜索效果等。

astar和泛洪填充算法
A*（A-star）算法和泛洪填充算法都是计算机图形学和计算机视觉中常用的路径查找和图形填充算法。

1.A*算法：
A算法是一种启发式搜索算法，用于在图中寻找从起始点到目标点的最短路径。

它结合了最佳优先搜索和Dijkstra算法的特性。

A算法使用一个启发式函数来估计从当前节点到目标节点的代价，这个函数通常基于节点与目标节点之间的实际距离。

由于这个原因，A*算法通常比其他基于距离的搜索算法（如Dijkstra算法）更高效。

A*算法的工作原理如下：
•开始时，将起始节点加入到优先队列中。

•从优先队列中取出具有最小F值的节点（F = G + H，其中G是从起始点到当前节点的实际距离，H是从当前节点到目标节点的启发式估计）。

•对取出的节点进行展开，检查其邻居节点。

如果邻居节点不在已访问节点的集合中，就计算从起始点到该邻居节点的距离（G值），并将该邻居节点加入到优先队列中。

•重复这个过程，直到找到目标节点或者优先队列为空。

2.泛洪填充算法：
泛洪填充算法通常用于图形填充操作，如绘制区域、颜色填充等。

该算法从一个指定的起始点开始，向其所有相邻的未填充的像素点进行“泛洪”，即标记这些点为已填充状态。

这个过程会一直进行，直到没有更多的像素点可以被填充。

泛洪填充算法的工作原理如下：
•开始时，将起始点标记为已填充状态。

•遍历与已填充状态相连的所有未填充像素点，将它们标记为已填充状态。

•重复这个过程，直到没有更多的像素点可以被标记为已填充状态。

这两个算法在实际应用中具有广泛的应用，例如在游戏开发、机器人导航、图像处理等领域。