astar
- 格式：doc
- 大小：346.00 KB
- 文档页数：26
实验二：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_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CAstarTestApp
BEGIN_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_MSG
ON_COMMAND(ID_HELP, CWinApp::OnHelp)
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CAstarTestApp construction
CAstarTestApp::CAstarTestApp()
{
// TODO: add construction code here,
// Place all significant initialization in InitInstance
}
/////////////////////////////////////////////////////////////////////////////
// The one and only CAstarTestApp object
CAstarTestApp theApp;
/////////////////////////////////////////////////////////////////////////////
// CAstarTestApp initialization
BOOL 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 _AFXDLL
Enable3dControls(); // Call this when using MFC in a shared DLL
#else
Enable3dControlsStatic(); // Call this when linking to MFC statically
#endif
CAstarTestDlg 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_FILE
static char THIS_FILE[] = __FILE__;
#endif
#include "AstarPathfinder.h"
/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About
#define INVALID_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
// Implementation
protected:
//{{AFX_MSG(CAboutDlg)
//}}AFX_MSG
DECLARE_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_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CAstarTestDlg dialog
CAstarTestDlg::CAstarTestDlg(CWnd* pParent /*=NULL*/)
: CDialog(CAstarTestDlg::IDD, pParent)
{
// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
m_map = m_path = NULL;
m_size = 16 ;
m_intervals = 0;
InitData();
