实验三：A*算法
一、实验目的
掌握游戏中寻路算法尤其是目前产用的A*算法原理
二、实验仪器
Microsoft Visual Studio2019
三、实验原理及过程
//描述A*的算法原理
//描述程序实现时的思路包括对每个调用的API进行详细说明
A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。注意——是最有效的直接搜索算法，之后涌现了很多预处理算法（如ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。
公式表示为： f*(n)=g*(n)+h*(n),
其中， f*(n) 是从初始状态经由状态n到目标状态的最小代价估计，
g*(n) 是在状态空间中从初始状态到状态n的最小代价，
h*(n) 是从状态n到目标状态的路径的最小估计代价。
（对于路径搜索问题，状态就是图中的节点，代价就是距离）
真实h(n)的选取：
保证找到最短路径（最优解的）条件，关键在于估价函数f(n)的选取（或者说h(n)的选取）。
以h(n)表达状态n到目标状态估计的距离，那么h(n)的选取大致有如下三种情况：
1.如果h(n)< h*(n)，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
2.如果h(n)=h*(n)，此时的搜索效率是最高的。
3.如果 h(n)>h*(n)，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
例：
编辑
步骤1.从起点A开始，把A作为一个等待检查的方格，放入到“开启列表”中，开启列表就是一个存放等待检车方格的列表
步骤2.寻找起点A周围可以到达的方格（最多八个），将它们放入到“开启列表”，并设置它们的父方格为A
步骤3.从“开启列表”中删除点A,并将A放入到“关闭列表”中，“关闭列表”存放的是不再需要检查的方格
步骤4.计算每个方格的F值
F=G+H:
G 表示从起点A移动到指定方格的移动消耗，我们假设横向移动一个格子消耗10，斜向移动一个格子消耗14（具体值可以根据情况修改）
H 表示从指定的方格移动到目标B点的预计消耗，我们假设H的计算方法，忽略障碍物，只可以纵横向计算
步骤5.从“开启列表”中选择F值最低的方格C，将其从“开启列表”中删除，放入到“关闭列表”中
步骤6.检查C所有临近并且可达的方格（障碍物和“关闭列表”中的方格不考虑），如果这些方格还不在“开启列表”中的话，将它们加入到开启列表，并且计算这些方格的F值，并设置父方格为C。
步骤7.如果某相邻的方格D已经在“开启列表”，计算新的路径从A到达方格D（即经过C的路径），G值是否更低一点，如果新的G值更低，则修改父方格为方格C，重新计算F值，H值不需要改变，因为方格到达目标点的预计消耗是固定的。但如果新的G值比较高，则说明新的路径消耗更高，则值不做改变。
步骤8.继续从“开启列表”中找出F值最小的，从“开启列表”中删除，添加到“关闭列表”，再继续找出周围可以到达的方块，如此循环
步骤9.当“开启列表”中出现目标方块B时，说明路径已经找到。除了起始方块A，每一个曾经或者现在还在“开启列表”中的方块，都存在一个“父方格”，可以从目标点B通过父方格索引到起始方块，这就是路径。
四、实验结果
这里通过简单的java代码来实现A*算法
编辑
编辑
五、实验心得(需包括有何不足如何改进)
//你认为目前的A*算法有什么不足之处,如何改进
A*算法通过比较当前路径栅格的8个邻居的启发式函数值F来逐步确定下一个路径栅格，当存在多个最小值时A*算法不能保证搜索的路径最优。
有些资料介绍将稀疏A-Star算法扩展到三维空间，提出了一种动态的稀疏A-Star算法。
A*算法的搜索效率很大程度上取决于估价函数h(n)。一般来说，在满足h(n) <=h* (n)的前提下，
h(n)的值越大越好。h(n) 的值越大，说明它携带的启发性信息越多，A*算法搜索时扩展的节点就越
少，搜索效率也越高。这-特性称为信息性。
通过本次实验，学习到了A*算法原理，以及能更好的明白游戏中的寻路算法，收获颇多，对今后的学习有了进一步的帮助。
六、主要代码
//本次实验主要main代码
#pragma warning (disable:4786)
#include <windows.h>
#include <time.h>
//need to include this for the toolbar stuff
#include <commctrl.h>
#pragma comment(lib, "comctl32.lib")
#include "constants.h"
#include "misc/utils.h"
#include "Time/PrecisionTimer.h"
#include "Pathfinder.h"
#include "resource.h"
#include "misc/Cgdi.h"
#include "misc/WindowUtils.h"
//need to define a custom message so that the backbuffer can be resized to
//accomodate the toolbar
#define UM_TOOLBAR_HAS_BEEN_CREATED (WM_USER + 33)
//--------------------------------- Globals ------------------------------
//
//------------------------------------------------------------------------
const char* g_szApplicationName = "PathFinder";
const char* g_szWindowClassName = "MyWindowClass";
Pathfinder* g_Pathfinder;
//global toolbar handle
HWND g_hwndToolbar;
//------------------------- RedrawDisplay ---------------------------------
//
// Call this to refresh the client window
//------------------------------------------------------------------------
void RedrawDisplay(HWND hwnd)
{
InvalidateRect(hwnd, NULL, TRUE);
UpdateWindow(hwnd);
}
//----------------------- ResizeToCorrectClientArea ---------------------------
//
// resizes the client are taking into account any toolbars and any menus
//-----------------------------------------------------------------------------
void ResizeToCorrectClientArea(HWND hwnd, int AccumulativeToolbarHeight, RECT ClientArea)
{
AdjustWindowRectEx(&ClientArea,
WS_OVERLAPPED | WS_VISIBLE | WS_CAPTION | WS_SYSMENU,
true,
NULL);
SetWindowPos(hwnd,
NULL,
0,
0,
ClientArea.right,
ClientArea.bottom + AccumulativeToolbarHeight,
SWP_NOMOVE|SWP_NOZORDER);
}
//---------------------------- WindowProc ---------------------------------
//
// This is the callback function which handles all the windows messages
//-------------------------------------------------------------------------
LRESULT CALLBACK WindowProc (HWND hwnd,
UINT msg,
WPARAM wParam,
LPARAM lParam)
{
//these hold the dimensions of the client window area
static int cxClient, cyClient;
//used to create the back buffer
static HDC hdcBackBuffer;
static HBITMAP hBitmap = NULL;
static HBITMAP hOldBitmap = NULL;
static int ToolBarHeight;
//to grab filenames
static TCHAR szFileName[MAX_PATH],
szTitleName[MAX_PATH];
static RECT rectClientWindow;
static int CurrentSearchButton = 0;
switch (msg)
{
//A WM_CREATE msg is sent when your application window is first
//created
case WM_CREATE:
{
//seed random number generator
srand((unsigned) time(NULL));
//---------------create a surface to render to(backbuffer)
//create a memory device context
hdcBackBuffer = CreateCompatibleDC(NULL);
//get the DC for the front buffer
HDC hdc = GetDC(hwnd);
hBitmap = CreateCompatibleBitmap(hdc,
cxClient,
cyClient);
//select the bitmap into the memory device context
hOldBitmap = (HBITMAP)SelectObject(hdcBackBuffer, hBitmap);
//don't forget to release the DC
ReleaseDC(hwnd, hdc);
//create the controller
g_Pathfinder = new Pathfinder();
CheckMenuItemAppropriately(hwnd, IDM_VIEW_TILES, g_Pathfinder->isShowTilesOn());
CheckMenuItemAppropriately(hwnd, IDM_VIEW_GRAPH, g_Pathfinder->isShowGraphOn());
}
break;
case UM_TOOLBAR_HAS_BEEN_CREATED:
{
//get the height of the toolbar
RECT rectToolbar;
GetWindowRect(g_hwndToolbar, &rectToolbar);
ToolBarHeight = abs(rectToolbar.bottom - rectToolbar.top);
rectClientWindow.left = 0;
rectClientWindow.right = ClientWidth;
rectClientWindow.top = 0;
rectClientWindow.bottom = ClientHeight + InfoWindowHeight;
ResizeToCorrectClientArea(hwnd, ToolBarHeight, rectClientWindow);
//let the toolbar know about the resize
SendMessage(g_hwndToolbar, WM_SIZE, wParam, lParam);
//this defines the area to be redrawn (to prevent the toolbar flickering)
GetClientRect(hwnd, &rectClientWindow);
rectClientWindow.bottom = ClientHeight - ToolBarHeight - 1;
//create a memory device context
hdcBackBuffer = CreateCompatibleDC(NULL);
//get the DC for the front buffer
HDC hdc = GetDC(hwnd);
hBitmap = CreateCompatibleBitmap(hdc,
rectClientWindow.right,
rectClientWindow.bottom);
//select the bitmap into the memory device context
hOldBitmap = (HBITMAP)SelectObject(hdcBackBuffer, hBitmap);
//don't forget to release the DC
ReleaseDC(hwnd, hdc);
}
break;
case WM_KEYUP:
{
switch(wParam)
{
case VK_ESCAPE:
SendMessage(hwnd, WM_DESTROY, NULL, NULL); break;
case 'G':
g_Pathfinder->ToggleShowGraph(); break;
case 'T':
g_Pathfinder->ToggleShowTiles(); break;
}//end switch
RedrawWindowRect(hwnd, false, rectClientWindow);
}
break;
case WM_LBUTTONDOWN:
{
g_Pathfinder->PaintTerrain(MAKEPOINTS(lParam));
RedrawWindowRect(hwnd, false, rectClientWindow);
}
break;
case WM_MOUSEMOVE:
{
switch(wParam)
{
case MK_LBUTTON:
{
g_Pathfinder->PaintTerrain(MAKEPOINTS(lParam));
RedrawWindowRect(hwnd, false, rectClientWindow);
}
break;
}
}
case WM_COMMAND:
{
switch(wParam)
{
case ID_BUTTON_STOP:
g_Pathfinder->ChangeBrush(Pathfinder::target);
break;
case ID_BUTTON_START:
g_Pathfinder->ChangeBrush(Pathfinder::source);
break;
case ID_BUTTON_OBSTACLE:
g_Pathfinder->ChangeBrush(Pathfinder::obstacle);
break;
case ID_BUTTON_WATER:
g_Pathfinder->ChangeBrush(Pathfinder::water);
break;
case ID_BUTTON_MUD:
g_Pathfinder->ChangeBrush(Pathfinder::mud);
break;
case ID_BUTTON_NORMAL:
g_Pathfinder->ChangeBrush(Pathfinder::normal);
break;
case ID_BUTTON_DFS:
g_Pathfinder->CreatePathDFS(); CurrentSearchButton = ID_BUTTON_DFS; break;
break;
case ID_BUTTON_BFS:
g_Pathfinder->CreatePathBFS(); CurrentSearchButton = ID_BUTTON_BFS; break;
break;
case ID_BUTTON_DIJKSTRA:
g_Pathfinder->CreatePathDijkstra(); CurrentSearchButton = ID_BUTTON_DIJKSTRA; break;
break;
case ID_BUTTON_ASTAR:
g_Pathfinder->CreatePathAStar(); CurrentSearchButton = ID_BUTTON_ASTAR; break;
break;
case ID_MENU_LOAD:
FileOpenDlg(hwnd, szFileName, szTitleName, "pathfinder files (*.map)", "map");
if (strlen(szTitleName) > 0)
{
g_Pathfinder->Load(szTitleName);
}
//uncheck the current search toolbar button
SendMessage(g_hwndToolbar,
TB_CHECKBUTTON,
(WPARAM) CurrentSearchButton,
(LPARAM) false);
break;
case ID_MENU_SAVEAS:
FileSaveDlg(hwnd, szFileName, szTitleName, "pathfinder files (*.map)", "map");
if (strlen(szTitleName) > 0)
{
g_Pathfinder->Save(szTitleName);
}
break;
case ID_MENU_NEW:
//create the graph
g_Pathfinder->CreateGraph(NumCellsX, NumCellsY);
//uncheck the current search toolbar button
SendMessage(g_hwndToolbar,
TB_CHECKBUTTON,
(WPARAM) CurrentSearchButton,
(LPARAM) false);
break;
case IDM_VIEW_GRAPH:
if (GetMenuState(GetMenu(hwnd), IDM_VIEW_GRAPH, MFS_CHECKED) && MF_CHECKED)
{
ChangeMenuState(hwnd, IDM_VIEW_GRAPH, MFS_UNCHECKED);
g_Pathfinder->SwitchGraphOff();
}
else
{
ChangeMenuState(hwnd, IDM_VIEW_GRAPH, MFS_CHECKED);
g_Pathfinder->SwitchGraphOn();
}
break;
case IDM_VIEW_TILES:
if (GetMenuState(GetMenu(hwnd), IDM_VIEW_TILES, MFS_CHECKED) && MF_CHECKED)
{
ChangeMenuState(hwnd, IDM_VIEW_TILES, MFS_UNCHECKED);
g_Pathfinder->SwitchTilesOff();
}
else
{
ChangeMenuState(hwnd, IDM_VIEW_TILES, MFS_CHECKED);
g_Pathfinder->SwitchTilesOn();
}
break;
}//end switch
RedrawWindowRect(hwnd, false, rectClientWindow);
}
case WM_PAINT:
{
PAINTSTRUCT ps;
BeginPaint (hwnd, &ps);
//fill the backbuffer with white
BitBlt(hdcBackBuffer,
0,
0,
cxClient,
cyClient,
NULL,
NULL,
NULL,
WHITENESS);
gdi->StartDrawing(hdcBackBuffer);
g_Pathfinder->Render();
gdi->StopDrawing(hdcBackBuffer);
//now blit backbuffer to front
BitBlt(ps.hdc, 0, 0, cxClient, cyClient, hdcBackBuffer, 0, 0, SRCCOPY);
EndPaint (hwnd, &ps);
}
break;
case WM_SIZE:
{
cxClient = LOWORD(lParam);
cyClient = HIWORD(lParam);
//now to resize the backbuffer accordingly. First select
//the old bitmap back into the DC
SelectObject(hdcBackBuffer, hOldBitmap);
//don't forget to do this or you will get resource leaks
DeleteObject(hBitmap);
//get the DC for the application
HDC hdc = GetDC(hwnd);
//create another bitmap of the same size and mode
//as the application
hBitmap = CreateCompatibleBitmap(hdc,
rectClientWindow.right,
rectClientWindow.bottom);
ReleaseDC(hwnd, hdc);
//select the new bitmap into the DC
SelectObject(hdcBackBuffer, hBitmap);
}
break;
case WM_DESTROY:
{
//clean up our backbuffer objects
SelectObject(hdcBackBuffer, hOldBitmap);
DeleteDC(hdcBackBuffer);
DeleteObject(hBitmap);
DeleteObject(hOldBitmap);
// kill the application, this sends a WM_QUIT message
PostQuitMessage (0);
}
break;
}//end switch
//this is where all the messages not specifically handled by our
//winproc are sent to be processed
return DefWindowProc (hwnd, msg, wParam, lParam);
}
//----------------------------- CreateToolBar ----------------------------
//------------------------------------------------------------------------
HWND CreateToolBar(HWND hwndParent, HINSTANCE hinstMain)
{
const int NumButtons = 11;
//load in the common ctrls from the dll
INITCOMMONCONTROLSEX cc;
cc.dwSize = sizeof(INITCOMMONCONTROLSEX);
cc.dwICC = ICC_BAR_CLASSES;
if (!InitCommonControlsEx(&cc))
{
MessageBox(NULL, "Failed to load common ctrls!", "Error!", MB_OK);
return 0;
}
//create the toolbar
HWND hwndToolBar = CreateWindowEx(NULL,
TOOLBARCLASSNAME,
(LPSTR) NULL,
WS_CHILD | WS_VISIBLE | CCS_BOTTOM,
0,
0,
0,
0,
hwndParent,
(HMENU) IDR_TOOLBAR1,
hinstMain,
NULL);
//make sure the window creation has gone OK
if(!hwndToolBar)
{
MessageBox(NULL, "CreateWindowEx Failed!", "Error!", 0);
}
//let the toolbar know the size of the buttons to be added
SendMessage(hwndToolBar, TB_BUTTONSTRUCTSIZE, (WPARAM)sizeof(TBBUTTON), 0);
//add bitmaps to the buttons
TBADDBITMAP tb;
tb.hInst = NULL;
tb.nID = (UINT_PTR)LoadBitmap((HINSTANCE)GetWindowLong(hwndParent, GWL_HINSTANCE),MAKEINTRESOURCE(IDR_TOOLBAR1));
int idx = SendMessage (hwndToolBar, TB_ADDBITMAP, NumButtons, (LPARAM)&tb);
//create the buttons
TBBUTTON button[NumButtons];
button[0].iBitmap = 0;
button[0].idCommand = ID_BUTTON_STOP;
button[0].fsState = TBSTATE_ENABLED;
button[0].fsStyle = TBSTYLE_CHECKGROUP;
button[0].dwData = NULL;
button[0].iString = NULL;
button[1].iBitmap = 1;
button[1].idCommand = ID_BUTTON_START;
button[1].fsState = TBSTATE_ENABLED;
button[1].fsStyle = TBSTYLE_CHECKGROUP;
button[1].dwData = NULL;
button[1].iString = NULL;
button[2].iBitmap = 2;
button[2].idCommand = ID_BUTTON_OBSTACLE;
button[2].fsState = TBSTATE_ENABLED;
button[2].fsStyle = TBSTYLE_CHECKGROUP;
button[2].dwData = NULL;
button[2].iString = NULL;
button[3].iBitmap = 3;
button[3].idCommand = ID_BUTTON_MUD;
button[3].fsState = TBSTATE_ENABLED;
button[3].fsStyle = TBSTYLE_CHECKGROUP;
button[3].dwData = NULL;
button[3].iString = NULL;
button[4].iBitmap = 4;
button[4].idCommand = ID_BUTTON_WATER;
button[4].fsState = TBSTATE_ENABLED;
button[4].fsStyle = TBSTYLE_CHECKGROUP;
button[4].dwData = NULL;
button[4].iString = NULL;
button[5].iBitmap = 5;
button[5].idCommand = ID_BUTTON_NORMAL;
button[5].fsState = TBSTATE_ENABLED;
button[5].fsStyle = TBSTYLE_CHECKGROUP;
button[5].dwData = NULL;
button[5].iString = NULL;
//this creates a separater
button[6].iBitmap = 265;
button[6].idCommand = 0;
button[6].fsState = NULL;
button[6].fsStyle = TBSTYLE_SEP;
button[6].dwData = NULL;
button[6].iString = NULL;
button[7].iBitmap = 6;
button[7].idCommand = ID_BUTTON_DFS;
button[7].fsState = TBSTATE_ENABLED;
button[7].fsStyle = TBSTYLE_CHECKGROUP;
button[7].dwData = NULL;
button[7].iString = NULL;
button[8].iBitmap = 7;
button[8].idCommand = ID_BUTTON_BFS;
button[8].fsState = TBSTATE_ENABLED;
button[8].fsStyle = TBSTYLE_CHECKGROUP;
button[8].dwData = NULL;
button[8].iString = NULL;
button[9].iBitmap = 8;
button[9].idCommand = ID_BUTTON_DIJKSTRA;
button[9].fsState = TBSTATE_ENABLED;
button[9].fsStyle = TBSTYLE_CHECKGROUP;
button[9].dwData = NULL;
button[9].iString = NULL;
button[10].iBitmap = 9;
button[10].idCommand = ID_BUTTON_ASTAR;
button[10].fsState = TBSTATE_ENABLED;
button[10].fsStyle = TBSTYLE_CHECKGROUP;
button[10].dwData = NULL;
button[10].iString = NULL;
//add the buttons to the toolbar
SendMessage(hwndToolBar, TB_ADDBUTTONS, (WPARAM)NumButtons, (LPARAM)(LPTBBUTTON)&button);
return hwndToolBar;
}
//-------------------------------- WinMain -------------------------------
//
// The entry point of the windows program
//------------------------------------------------------------------------
int WINAPI WinMain (HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPSTR szCmdLine,
int iCmdShow)
{
//handle to our window
HWND hWnd;
//our window class structure
WNDCLASSEX winclass;
// first fill in the window class stucture
winclass.cbSize = sizeof(WNDCLASSEX);
winclass.style = CS_HREDRAW | CS_VREDRAW;
winclass.lpfnWndProc = WindowProc;
winclass.cbClsExtra = 0;
winclass.cbWndExtra = 0;
winclass.hInstance = hInstance;
winclass.hIcon = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_ICON1));
winclass.hCursor = LoadCursor(NULL, IDC_ARROW);
winclass.hbrBackground = NULL;
winclass.lpszMenuName = MAKEINTRESOURCE(IDR_MENU1);
winclass.lpszClassName = g_szWindowClassName;
winclass.hIconSm = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_ICON1));
//register the window class
if (!RegisterClassEx(&winclass))
{
MessageBox(NULL, "Registration Failed!", "Error", 0);
//exit the application
return 0;
}
//create the window
hWnd = CreateWindowEx (NULL, // extended style
g_szWindowClassName, // window class name
g_szApplicationName, // window caption
WS_OVERLAPPED | WS_VISIBLE | WS_CAPTION | WS_SYSMENU, // window style
GetSystemMetrics(SM_CXSCREEN)/2 - WindowWidth/2,
GetSystemMetrics(SM_CYSCREEN)/2 - WindowHeight/2,
WindowWidth, // initial x size
WindowHeight, // initial y size
NULL, // parent window handle
NULL, // window menu handle
hInstance, // program instance handle
NULL); // creation parameters
//make sure the window creation has gone OK
if(!hWnd)
{
MessageBox(NULL, "CreateWindowEx Failed!", "Error!", 0);
}
//create the toolbar
g_hwndToolbar = CreateToolBar(hWnd, hInstance);
SendMessage(hWnd, UM_TOOLBAR_HAS_BEEN_CREATED, NULL, NULL);
//create the graph
g_Pathfinder->CreateGraph(NumCellsX, NumCellsY);
//enter the message loop
//this will hold any windows messages
MSG msg;
//entry point of our message handler
while (GetMessage (&msg, NULL, 0, 0))
{
TranslateMessage (&msg);
DispatchMessage (&msg);
}
delete g_Pathfinder;
UnregisterClass( g_szWindowClassName, winclass.hInstance );
return msg.wParam;
}
//这里是关于A*算法的简单的java代码
import java.util.ArrayList;
import java.util.List;
//A*寻路算法简单实现————>四方向（上下左右）
publicclass Maze_A_ManHaDun {
//简单的迷宫模拟——利用二维数组，其中 1 表示障碍，不可通过。
publicstaticfinalint[][] MAZE= {
{0, 1, 0, 0, 0, 0, 0},//7
{0, 0, 1, 0, 0, 0, 0},
{1, 0, 0, 1, 0, 0, 0},
{0, 1, 0, 1, 1, 1, 1},
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 1, 0},
//7
};
//定义 方格节点——grid
staticclass Grid{
publicint x;//结点
publicint y;
publicint f;//fn
publicint g;//gn
publicint h;//hn
public Grid parent;
public Grid(int x,int y) {
this.x=x;
this.y=y;
}
//实例化一个方格节点
publicvoid initGrid(Grid parent, Grid end) {
//parent赋值
this.parent=parent;
//计算g的大小
if(parent!=null) {
this.g=parent.g+1;
//this.g=0;
}
else
{
this.g=1;
}
//计算h的大小
this.h=Math.abs(this.x-end.x)+Math.abs(this.y-end.y);
//this.h=Math.abs(this.x-end.x)*Math.abs(this.y-end.y);
//计算f的大小
this.f=this.g+this.h;
}
}
//寻路算法核心实现过程
publicstatic Grid aStarSearch(Grid start, Grid end) {
//准备两个链表，分别存储 将要选择的节点 和 已经走过的节点
ArrayList<Grid> openlist=new ArrayList<Grid>();
ArrayList<Grid> closelist=new ArrayList<Grid>();
//将起点加入链表，准备开始寻路。
openlist.add(start);
//只要链表不为空，就重复这个寻路的过程
while(openlist.size()>0) {
//找到 openlist中 F值最小的那个 方格（节点）
Grid currentgrid=findMinGrid(openlist);
//从 openlist中删除找到的那个 F值 最小的那个节点
openlist.remove(currentgrid);
//将这个 F值 最小的节点，加入到 closelist 中
closelist.add(currentgrid);
//寻找 当前找到的这个 F值最小的节点的 邻居节点 ——上下左右，四个方向上的节点，要判断它们是否为合法可用的节点。
List<Grid> neighbors=findNeighbors(currentgrid, openlist, closelist);
//对合法可用的邻居节点进行初始化，并加入到 openlist中
for(Grid grid : neighbors) {
if(!openlist.contains(grid)) {
grid.initGrid(currentgrid,end);
openlist.add(grid);
}
}
//邻居节点加入 openlist 后，判断openlist中，是否包含 终点节点，如果包含终点，直接返回并退出。
for(Grid grid : openlist) {
if((grid.x==end.x) && (grid.y==end.y)) {
return grid;
}
}
}
returnnull;
}
//寻找邻居节点的方法，返回值为 链表 ——创建一个合理的邻居链表
privatestatic ArrayList<Grid> findNeighbors(Grid grid, List<Grid> openlist, List<Grid> closelist) {
// TODO Auto-generated method stub
ArrayList<Grid> gridlist=new ArrayList<Grid>();
//判断上下左右邻居节点的合理性，没问题就加入到邻居链表中。
if(isValidGrid(grid.x, grid.y-1, openlist, closelist)) {//下
gridlist.add(new Grid(grid.x, grid.y-1));
}
if(isValidGrid(grid.x, grid.y+1, openlist, closelist)) {//上
gridlist.add(new Grid(grid.x, grid.y+1));
}
if(isValidGrid(grid.x-1, grid.y, openlist, closelist)) {//左
gridlist.add(new Grid(grid.x-1, grid.y));
}
if(isValidGrid(grid.x+1, grid.y, openlist, closelist)) {//右
gridlist.add(new Grid(grid.x+1, grid.y));
}
return gridlist;
}
//判断当前位置的节点是否合理
privatestaticboolean isValidGrid(int x, int y, List<Grid> openlist, List<Grid> closelist) {
// TODO Auto-generated method stub
//当前节点是否越界，不再MAZE数组范围内了，注意二位数组的长度计算方法及含意
//MAZE。length表示行的长度
//MAZE[0]。length表示列的长度
if(x<0 || x>=MAZE.length || y<0 || y>=MAZE[0].length) {
returnfalse;
}
//当前节点是否为障碍节点
if(MAZE[x][y]==1) {
returnfalse;
}
//判断当前节点是否在 openlist中
if(containgrid(openlist, x, y)) {
returnfalse;
}
//判断当前节点是否在 closelist中
if(containgrid(closelist, x, y)) {
returnfalse;
}
returntrue;
}
//判断当前链表中是否包含当前的节点
privatestaticboolean containgrid(List<Grid> grids, int x, int y) {
// TODO Auto-generated method stub
for(Grid grid : grids) {
if((grid.x==x) && (grid.y==y)) {
returntrue;
}
}
returnfalse;
}
//寻找当前链表中的节点F值 最小的那个节点，并返回这个节点。
privatestatic Grid findMinGrid(ArrayList<Grid> openlist) {
// TODO Auto-generated method stub
Grid tempgrid=openlist.get(0);
for(Grid grid : openlist) {
if(grid.f<tempgrid.f) {
tempgrid=grid;
}
}
return tempgrid;
}
publicstaticvoid main(String[] args) {
// TODO Auto-generated method stub
int b1=0,b2=0;//起始坐标
int c1=0,c2=6;
Grid startgrid=new Grid(b2,b1);
System.out.println("起点坐标为:"+"("+b1+","+b2+")");
Grid endgrid=new Grid(c2,c1);
System.out.println("终点坐标为:"+"("+c1+","+c2+")");
Grid resultgrid=aStarSearch(startgrid,endgrid);
//创建回溯链表
ArrayList<Grid> path=new ArrayList<Grid>();
while(resultgrid!=null) {
path.add(new Grid(resultgrid.x, resultgrid.y));
resultgrid=resultgrid.parent;
}
//打印输出当前寻路路径
int count=0;
for(int i=0; i<MAZE.length; i++) {
for(int j=0; j<MAZE[0].length; j++) {
if(containgrid(path, i, j)) {
System.out.print("走, ");
count++;
}
else
{
System.out.print(MAZE[i][j]+ ", ");
}
}
System.out.println();
}
System.out.println("最短路径长度为："+count);
}
}
