游戏人工智能——A*算法

悠悠 2023-10-01 15:59 29阅读 0赞

## **实验三：****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)，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

例：

![2bb96aa586384a3aa497dea0f0682fea.png][]

步骤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\*算法

![db3bf249d4c14b66b8d1e7b447d88126.png][]

![03f8714bbbec41bfaf3cbafe883bb804.png][]

###  ###

### **五、实验心得****(****需包括有何不足如何改进****)** ###

//你认为目前的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,

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,

cxClient,

cyClient,

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,

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\*寻路算法简单实现————>四方向（上下左右）

**public** **class** Maze\_A\_ManHaDun \{

//简单的迷宫模拟——利用二维数组，其中 1 表示障碍，不可通过。

**public** **static** **final** **int**\[\]\[\] ***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, 1, 1, 1, 0\},

//7

\};

//定义 方格节点——grid

**static** **class** Grid\{

**public** **int** x;//结点

**public** **int** y;

**public** **int** f;//fn

**public** **int** g;//gn

**public** **int** h;//hn

**public** Grid parent;

**public** Grid(**int** x,**int** y) \{

**this**.x=x;

**this**.y=y;

//实例化一个方格节点

**public** **void** 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;

//寻路算法核心实现过程

**public** **static** 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;

**return** **null**;

//寻找邻居节点的方法，返回值为 链表 ——创建一个合理的邻居链表

**private** **static** 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;

//判断当前位置的节点是否合理

**private** **static** **boolean** 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) \{

**return** **false**;

//当前节点是否为障碍节点

**if**(***MAZE***\[x\]\[y\]==1) \{

**return** **false**;

//判断当前节点是否在 openlist中

**if**(*containgrid*(openlist, x, y)) \{

**return** **false**;

//判断当前节点是否在 closelist中

**if**(*containgrid*(closelist, x, y)) \{

**return** **false**;

**return** **true**;

//判断当前链表中是否包含当前的节点

**private** **static** **boolean** containgrid(List<Grid> grids, **int** x, **int** y) \{

// **TODO** Auto-generated method stub

**for**(Grid grid : grids) \{

**if**((grid.x==x) && (grid.y==y)) \{

**return** **true**;

**return** **false**;

//寻找当前链表中的节点F值 最小的那个节点，并返回这个节点。

**private** **static** 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;

**public** **static** **void** 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);

[2bb96aa586384a3aa497dea0f0682fea.png]: https://img-blog.csdnimg.cn/2bb96aa586384a3aa497dea0f0682fea.png
[db3bf249d4c14b66b8d1e7b447d88126.png]: https://img-blog.csdnimg.cn/db3bf249d4c14b66b8d1e7b447d88126.png
[03f8714bbbec41bfaf3cbafe883bb804.png]: https://img-blog.csdnimg.cn/03f8714bbbec41bfaf3cbafe883bb804.png