写个A星寻路算法，主程也不一定能写出来！！！
今天写一下游戏内的寻路算法，A星算法可能是最出名的，
如果一个游戏开发人员不知道A * 寻路算法的话有点说不过去，除非你是棋牌游戏的开发人员。虽然大部分的游戏开发都知道A星，但是能写出来，能理解清楚的也少之又少，今天就来一起学习下实现一下。
1.算法核心公式
A星算法的核心就是挑选消耗最小的点，一直逼近，直到找到目标点
A星算法核心公式就是F值的计算：F = G + H
F - 总的移动代价G - 开始点到当前方块的移动代价H - 当前方块到结束点的预估移动代价
G值是怎么计算的？
假设现在我们在某一格子，邻近有4个格子可走，当我们往上、下、左、右这4个格子走时，我们假设移动的代价是1，则当前节点的G值为上一个节点的G值 加上单位移动的代价（这里使用1）
H值是如何预估出来的？
有多种方式可以预估H值，如曼哈顿距离、欧式距离、对角线估价，
最常用最简单的方法就是使用曼哈顿距离进行预估：H = 当前方块到结束点的水平距离 + 当前方块到结束点的垂直距离
2、解释一下流程
（0，0）的星星表示起点，
（0，5）的星星表示目标点
1、在（0，0）的时候 G = 0,H = (0-0) + 5-0 = 5
2、将（0，0）的可行走节点加入到待访问 节点列表，
(0，1）的消耗为 G = 1 ,H = (0 - 0) + (5 -1) = 4 ,总消耗为 5点
（1,0）的消耗为 G= 1 ，H = (1-0) + (5-0) = 6，总消耗为6点
3、选择消耗最小的点为（0，1）
继续探索，将邻接点加入到待访问节点列表，并计算出所有的消耗
4、依次循环，直到发现结束点已经在待访问节点列表，代表已经有节点可以连接到结束点
5、从结束反向追溯就可以找到来时的路径
3、show you code
先看下节点的定义
package com.example.demo.astar;
import lombok.Data;
import java.util.*;
@Data
public class Pos implements Comparable<Pos> {
//x坐标
private int x;
//y坐标
private int y;
//当前的消耗
private double g;
//预估的消耗
private double h;
//从哪里来的，指向上一个节点
private Pos parent;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Pos o) {
return (int) ((this.g + this.h)- (o.g + o.h));
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Pos pos = (Pos) o;
return x == pos.x && y == pos.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}看下算法的实现：
package org.pdool.astar;
import java.util.*;
/**
* @author 香菜
**/
public class AStar {
// 方向数组，控制上下左右，技巧，不用傻了吧唧的写4个方向
public static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
static List<Pos> openList = new ArrayList<>();
static Set<Pos> closeSet = new HashSet<>();
// 地图数据 0:路 1：障碍
static int[][] map = {
{0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0},
};
/**
* 判断一个节点是不是能走（必须是地图内的点，并且不是障碍）
*
* @param x
* @param y
* @return
*/
public static boolean canWalk(int x, int y) {
int col = map[0].length;
int row = map.length;
//在地图范围外
if (x < 0 || x >= row || y < 0 || y >= col) {
return false;
}
//是障碍
if (map[x][y] == 1) {
return false;
}
return true;
}
/**
* 找到邻接点，遍历周边的点，没有访问过的点
*
* @param remove
* @return
*/
private static List<Pos> findLink(Pos remove) {
int x = remove.getX();
int y = remove.getY();
ArrayList<Pos> linkPosList = new ArrayList<>();
for (int[] dirUnit : dir) {
int nx = dirUnit[0] + x;
int ny = dirUnit[1] + y;
Pos pos = new Pos(nx, ny);
pos.setParent(remove);
if (canWalk(nx, ny) && !closeSet.contains(pos)) {
linkPosList.add(pos);
}
}
return linkPosList;
}
//对角线估价法
private static double diagonal(Pos pos, Pos endPos) {
int dx = Math.abs(endPos.getX() - pos.getX());
int dy = Math.abs(endPos.getY() - pos.getY());
int diag = Math.min(dx, dy);
int straight = dx + dy;
return diag + (straight - 2 * diag);
}
/**
* 计算消耗
*/
private static void calcCost(Pos endPos, Pos pos) {
pos.setH(diagonal(pos, endPos));
double g = pos.getParent() != null ? pos.getParent().getG() : 0D;
pos.setG(g + 1);
}
/**
* 主函数
*/
public static void main(String[] args) {
Pos startPos = new Pos(0, 0);
Pos endPos = new Pos(0, 5);
openList.add(startPos);
while (openList.size() > 0) {
// 排序，去除代价最小的点
Collections.sort(openList);
Pos remove = openList.remove(0);
closeSet.add(remove);
List<Pos> linkList = findLink(remove);
for (Pos pos : linkList) {
calcCost(endPos, pos);
openList.add(pos);
}
if (openList.contains(endPos)) {
int endPosIdx = openList.indexOf(endPos);
endPos = openList.get(endPosIdx);
break;
}
}
Pos parent = endPos.getParent();
while (parent != null) {
System.out.println("-> " + parent.getX() + " - " + parent.getY());
parent = parent.getParent();
}
}
}代码解释：
- 一个记录下所有被考虑来寻找最短路径的方块（称为open 列表）
- 一个记录下不会再被考虑的方块（成为closed列表），因为周边节点已经加入进去了，为了避免open列表遍历周边节点的时候再次加入open列表，导致一直循环，所以需要close列表，避免多次访问
看下运行结果：
从下往上看可以回溯出行走路线。
三种估值算法
1.曼哈顿算法是根据网格走直线，直到目标点所在的水平或垂直平行就拐弯；
2.几何算法实际上就是通过勾股定理，计算两点间的直线距离；
3.对角算法结合了以上二种算法，先按对角线走，一直走到与目标点水平或垂直平行后，再笔直的走。
//曼哈顿估价法
private static double manhattan(Pos pos, Pos endPos) {
return Math.abs(endPos.getX() - pos.getX()) + Math.abs(endPos.getY() - pos.getY());
}
//几何估价法
private static double euclidian(Pos pos, Pos endPos) {
int dx = endPos.getX() - pos.getX();
int dy = endPos.getY() - pos.getY();
return Math.sqrt(dx * dx + dy * dy);
}4、技术点：
1、Pos 节点相等的判断，对equal 和 hashcode 的重写
2、对待选节点的排序，Pos 实现了比较接口，加入到openList之后调用排序
3、提供了三种估值算法的实现
4、closeList节点列表是代表当前邻接点都已经加入到待访问列表，不需要再次访问
openList 是还没访问周边节点的节点
5、优化点：
1、没有注意代码的简洁性，可以对代码进行结构和函数的参数调整
2、现在方法都是static，可以将整个AStar 作为一个类，传入数据，最终输出一个行走点的列表
3、现在输出节点是倒序的，可以使用List，倒序输出
4、可以将地图增加八个方向的移动，修改dir数组即可，即增加 左上，左下，右上，右下四个方向
6、游戏应用：
在游戏中应用的方式，一般是使用地图编辑器，将地图划分为格子，然后由策划进行刷点，通过不同的刷子表示不同的状态，最后导出地图的导航网格数据，服务端在游戏启动的时候只加载网格数据，直接使用导航网格数据进行计算路径，客户端也可以自己寻路。
总结 ：
1)当h(n)=0时，A星算法就转化为了Dijkstra算法，即：每次只考虑到源节点最近的节点。
2)当g(n)=0时，A星算法就转化为了BFS算法，即：每次只考虑到目的节点最近的节点
3)h(n)是一种对当前节点到目的节点的估计值，如果此估计值精确度等于实际值，那么A星算法可以非常高速的找到最优路径(搜索过程中几乎不会走 弯路) ，如果h(n) 经常都比从n节点移动到目的节点的实际代价小或等于，那么A星算法保证能找到一条最短路径。如果h(n) 有时比从n节点移动到目 的节点的实际代价高，则A*不能保证找到一条最短路径，但它运行得更快。