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

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, 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);

    }

}