A*寻路算法——一种寻找从起点A到终点B的有效路径的算法，游戏设计中的角色移动经常会采用这种算法来实现。

说明：由于是初学者，对算法的理解还不够透彻，下面的分析过程，只考虑最简单的情况——平面四个方向（上，下，左，右）的搜索。

下图中的  S  代表起点（start），  E  代表终点（E），中间有填充色的区域为  障碍  ——不可穿过，需绕行。

1、[ 开始分析算法前，先了解几个算法中要用到的量 ]  

• 1、下图中每一个  方格  定义为一个节点，每个节点包含以下几个属性
  • 横向的  x   坐标（左上角方格为 0，横向移动x不变，纵向移动x进行加减 1）
  • 纵向的  y   坐标（左上角方格为 0，纵向移动y不变，横向移动y进行加减 1）
  • F的值--->  F=G+H  ，这个F的值，用来判断接下来要选择哪个方格来走的作用。
  • G的值--->当前点距离起点的步数，也就是当前点从起点出发已经走了的步数。

    • G的计算规则：由 方格（节点）A  移动到  方格（节点）B  ===>  G=G+1 

  • H的值--->当前点距离终点的步数，也就是当前点到终点的话，接下来可能会走的步数。

    • H的计算规则：由 方格（节点）A  移动到  方格（节点）B  ===>  H=H+1 

  • parent--->用来存储当前节点的父亲节点，作用是为后续的寻路结果做标记。
• 2、利用两个链表来分别存储  [ 已经走过的方格（节点） ]  和  [ 将要选择经过的方格（节点） ]  
  • openlist--->将要选择经过的方格
    • 一旦终点 方格（节点） 进入openlist链表，说明寻路结束
    • 利用F值的大小决定先选择走哪个 方格（节点） 
  • closelist--->已经走过的方格
    • 判定 方格（节点） 是否已经走过——即是否有效时使用

2、[ 算法分析 ]

1. 将   起点方格（节点）   加入  openlist   链表中，作为寻路开始的起点；
2. 循环执行以下步骤，直到   openlist   链表为空结束或者  终点（节点） 加入到  openlist  中：
   1. 在   openlist   中找到   F值   最小的那个节点（如果有相等的情况，就选择最先找到的那个节点）  作为  [ 当前节点 ]；
   2. 在   openlist   中将第1步找到的那个F值最小的节点，从   openlist   中删除掉；
   3. 在   closelist   中将第1步找到的那个F值最小的节点，加入   closelist   中；
   4. 围绕第1步找到的那个F值最小的 [ 当前节点 ] ，找到与它相邻的 四个方向（上下左右） 上的节点，这里要判断邻居节点的有效性，看 邻居节点 是否满足以下条件：
      1. 邻居节点是否越界——节点的  x  或者  y  是否在可视范围内；
      2. 邻居节点是否为障碍方格（节点）——比如本程序中的  MAZE[i][j]=1 即为障碍，MAZE[i][j]=0  即为可用；
      3. 邻居节点是否已经在   openlist  链表中或者   closelist  链表中；
      4. 以上都满足就抛弃不要，否则这个邻居节点就要留下来，并进行初始化：
         1. 指定  [当前节点]  为这个  [邻居节点]  的父节点；
         2. 计算  [邻居节点]  的G值；
         3. 计算  [邻居节点]  的H值；
         4. 计算  [邻居节点]  的F值；
      5. 初始化完毕，将  [邻居节点]  加入  openlist  中；
3. 如果找到了可寻的路径，利用节点的  parent  属性，回溯打印输出路径即可。

简单的代码实现：

import java.util.ArrayList;
import java.util.List;//A*寻路算法简单实现————>四方向（上下左右）public class AStarSearch {//简单的迷宫模拟——利用二维数组，其中 1 表示障碍，不可通过。public static final int[][] MAZE= {{0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 1, 0, 0, 0},{0, 0, 0, 1, 0, 0, 0},{0, 0, 0, 1, 0, 0, 0},{0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 1, 0, 0, 0},};//定义 方格节点——gridstatic class Grid{public int x;public int y;public int f;public int g;public int h;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;}else{this.g=1;}//计算h的大小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 stubArrayList<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 stubfor(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 stubGrid 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 stubGrid startgrid=new Grid(2,1);Grid endgrid=new Grid(2,5);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;}//打印输出当前寻路路径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("*, ");}else{System.out.print(MAZE[i][j]+ ", ");}}System.out.println();}}}