前言

A star算法也叫A星(A*)算法，这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或网络游戏的BOT的移动计算上

该算法综合了最良优先搜索和Dijkstra算法的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（基于评估函数）。

A star算法

在A star算法中，如果我们要计算两点之间的距离，例如上图中起点到终点的距离，这时我们把两点之间的直线距离用f(n)表示，而两点之间的水平距离+竖直距离=曼哈顿距离(这个后面会用到，使用曼哈顿距离可以提高运算的速度，如果使用f(n)那么需要不断的计算三角函数)

关于曼哈顿距离的百度解释

实现思路

如图，首先假设我们要从绿色的点走到红色的点，蓝色的点表示障碍物。
那么：
首先我们定义两个队列open和close，open表示正在处理或者准备处理的点，close表示已经处理过或者不处理的点

1. 绿色点周围的8个点就是我们第一步可以走的位置
2. 首先我们假设左边的水平方向和竖直方向的距离都是10，那么45度方向距离就是14(即√200)，
3. 所以我们在每个方块的左下角标一个数字g(n)，它代表这个方块距离起始点的距离
4. 然后在每个方块的右下角标一个数字h(n)，它代表这个方块距离终点的曼哈顿距离(先不考虑障碍物)。
5. 所以我们可以大致估算出，每个方块所在路径到终点的大致距离，就是f(n)=g(n)+h(n)
6. 现在我们将起始点周围的8个点加入到open队列中去，表示接下来要处理这8个点，然后将起始点加到close队列中，表示起始点已经处理过了

7. 然后我们依照f(n)对open队列进行从小到大进行排序，取出f(n)最小的那个点，当作新的起始点，重复上面1-7步，直到到达终点，就可以得到下图

   
   

最后就可以得到路径

代码实现

了解了思路，代码也很简单，首先我们需要定义好坐标对象

1. 坐标对象

public class Coord {
    public int x;
    public int y;

    public Coord(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (obj instanceof Coord) {
            Coord c = (Coord) obj;
            return x == c.x && y == c.y;
        }
        return super.equals(obj);
    }
}

2. 方块对象,这里实现了Comparable接口是为了第6步的排序，如果想通过别的方式进行排序也可以不实现

public class Node implements Comparable<Node>{
    public Coord coord;
    public Node parent;
    public int g;//g(n)是已经走过的距离
    public int h;//h(n)是没有走过的曼哈顿距离

    public Node(int x,int y){
        this.coord=new Coord(x,y);
    }

    public Node(Coord coord, Node parent, int g, int h) {
        this.coord = coord;
        this.parent = parent;
        this.g = g;
        this.h = h;
    }
    //实现排序
    @Override
    public int compareTo( Node  o) {
       if(o==null) return -1;
        if(g+h>o.g+o.h){
            return 1;
        }else if(g+h<o.g+o.h){
            return -1;
        }

        return 0;
    }
}

3. 定义一个简单的二维数组表示地图

public class MapInfo {
    public int[][] map;
    public int width;
    public int hight;
    public Node start;
    public Node end;

    public MapInfo(int[][] map, int width, int hight, Node start, Node end) {
        this.map = map;
        this.width = width;
        this.hight = hight;
        this.start = start;
        this.end = end;
    }
}

4. 以上3步都是准备工作，接下来就是AStar算法的具体实现了，根据思路实现，其实也不难
   定义好open和close队列

//PriorityQueue这里用PriorityQueue是可以避免自己在手动调用一次List中的sort方法进行第6步的排序
Queue<Node> openList = new PriorityQueue<Node>();
//close队列不需要排序，只需要查询，所以用线性表效率较高
List<Node> closeList = new ArrayList<Node>();

5. 定义好几个变量

//障碍物
public final static int BAR = Integer.MAX_VALUE;
//径路
public final static int PATH = 1;
//横竖上的移动代价
public final static int DIRECT_VALUE = 10;
//斜移动的代价
public final static int OBLIQUE_VALUE = 14;

6. 开始做寻路算法

 /**
  * start方法更多的是在做一些校验工作，然后开始循环
  */
public void start(MapInfo mapInfo) {
    //先判断地图是否存在
    if (mapInfo == null) return;
    //清空上一次操作的结果
    openList.clear();
    closeList.clear();
    //开始搜索
    //1.把开始节点加入到open表
    openList.add(mapInfo.start);
    //2.目标判定
    moveNodes(mapInfo);
}

7. 开始循环

/**
 * 用来移动当前结点
 */
private void moveNodes(MapInfo mapInfo) {
    while (!openList.isEmpty()) {
        if (isCoordInClose(mapInfo.end.coord)) {//如果终点进入了close表示结束
            //表示，结果在mapInfo中
           return；
        }
        //把open中的第一个节点取出来放到close中
        Node current = openList.poll();
        closeList.add(current);
        //3.开始从current开始的地方找邻近的能走的节点
        addNeighborNodeInOpen(mapInfo, current);
    }
}  

 /**
  * 进行八次操作,将周围的8个点加到open队列中
  */
private void addNeighborNodeInOpen(MapInfo mapInfo, Node current) {
    int x = current.coord.x;
    int y = current.coord.y;
    //左
    addNeighborNodeInOpen(mapInfo, current, x - 1, y, DIRECT_VALUE);
    //上
    addNeighborNodeInOpen(mapInfo, current, x, y - 1, DIRECT_VALUE);
    //右
    addNeighborNodeInOpen(mapInfo, current, x + 1, y, DIRECT_VALUE);
    //下
    addNeighborNodeInOpen(mapInfo, current, x, y + 1, DIRECT_VALUE);
    //左上
    addNeighborNodeInOpen(mapInfo, current, x - 1, y - 1, OBLIQUE_VALUE);
    //右上
    addNeighborNodeInOpen(mapInfo, current, x + 1, y - 1, OBLIQUE_VALUE);
    //左下
    addNeighborNodeInOpen(mapInfo, current, x - 1, y + 1, OBLIQUE_VALUE);
    //右下
    addNeighborNodeInOpen(mapInfo, current, x + 1, y + 1, OBLIQUE_VALUE);
}

7. 注意，在将点加到open队列时，必须判断当前点是否可以走(不是障碍物)，当前点是否已经处理过(在close队列中),已经当前点是否在open队列中，比如先左走，再上走和直接左上走，如果发现这种绕路的情况，就更新f(n)路径，保证f(n)路径最小

/*
 * 添加点到open队列中
 */
private void addNeighborNodeInOpen(MapInfo mapInfo, Node current, int x, int y, int value) {
    if (canAddNodeToOpen(mapInfo, x, y)) {//判断当前节点是否可以添加（不在close,也不是墙）
        Node end = mapInfo.end;
        Coord coord = new Coord(x, y);
        int g = current.g + value;//计算当前点到开始点的距离
        Node child = findNodeInOpen(coord);//查找当前点是否在open中
        if (child == null) {//不在open中
            //这个if中表示都是从来没搜过的路
            int h = calcManhattan(end.coord, coord);//计算曼哈顿距离
            if (isEndNode(end.coord, coord)) {
                child = end;
                child.parent = current;
                child.g = g;
                child.h = h;
            } else {
                child = new Node(coord, current, g, h);
            }
            openList.add(child);
        } else if(child.g>g){//如果在open中(只需要判断两个节点的G值 ,用小的换了
            child.g=g;
            child.parent=current;
            openList.add(child);
        }
    }
}

/**
 * 判断点是否可以走(在地图中，不是障碍物)，是否已经处理过(在close队列中)
 */
private boolean canAddNodeToOpen(MapInfo mapInfo, int x, int y) {
    //是否在地图中
    if (x < 0 || x >= mapInfo.width || y < 0 || y >= mapInfo.hight) {
        return false;
    }
    //判断是否是不可通过的位置
    if (mapInfo.map[y][x] == BAR) {
        return false;
    }
    //判断是否在close表中
    if (isCoordInClose(x, y)) {
        return false;
    }
    return true;
}

/**
 * 判断当前点是否在open队列中，如果在就要更新f(n)，保证f(n)使用的值是最小的值，避免绕路
 */
private Node findNodeInOpen(Coord coord) {
    if (coord == null || openList.isEmpty()) return null;
    for (Node node : openList) {
        if (node.coord.equals(coord)) {
            return node;
        }
    }
    return null;
}