概述：
广度优先算法：
是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
A星算法：
A*搜寻算法俗称A星算法。A*算法是比较流行的启发式搜索算法之一，被广泛应用于路径优化领域[。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息，对当前节点距终点的距离做出估计，并作为评价该节点处于最短路线上的可能性的量度。
算法实现原理：
广度优先算法：
前置条件：
1.一个初始化数组存储地形所有点位，例如N*N的正方形地形，每个点位记录是否未墙面（不可通行）
grid = new int[N, N];//当grid[,]=0标识可以通行，1标识不行
2.构造点位信息解析类
public class Node
{
public int[] pos;//经纬度
public bool finded;//是否寻找过
public Node parent;//父节点
public GameObject cube;//当前节点
}
算法步骤：
1.起点NodeA存入openList集合，
1.起点NodeA，终点NodeB；获取openList中的点位（第一次进入获取的是起点），从A点遍历A点周围4个点上，下，左，右（如果追求经确定可以8个点上，下，左，右及斜上斜点），找到可以抵达（是否可抵达通过点位结构数据中finded=1判断，0未）的点位（C1,C2,C3...Ci）放入集合tempList，注意在将C点位存入tempList之前必须记录C点的父节点A（用于步骤4中寻找最终路径）；
2.第一轮遍历完成后，清空openList，再将tempList赋值给openList，为下一轮遍历做准备
2.接下来再次执行openList中所有的点位C1,C1...Ci,重复1中的步骤
3.当最终执行到tempList中的点位N1,N2..Ni中有一个点位等于终点B点时，循环结束
4.最终通过反向通过链表结构查找父节点， B->B.parent.....一直找到A.parent=null截止；
5.至此整个广度遍历路径方式完成，效果如下（简书网络问题~~~~上传不了后期补上，下同）
A星算法：
前置条件：
1.一个初始化数组存储地形所有点位，例如N*N的正方形地形，每个点位记录是否未墙面（不可通行）
grid = new int[N, N];//当grid[,]=0标识可以通行，1标识不行
2.构造点位信息解析类
/// <summary>
/// 初始化构造点位数据信息
/// </summary>
public class Node
{
public int[] pos;//经纬度
public bool finded;//是否寻找过
public Node parent;//父节点
public GameObject cube;//当前节点
public float FValue;//最终权值（F=G+H）
public float GValue;//当前节点距离终点的曼哈顿距离
public Node (int x, int y)//构造点位函数
{
pos = new int[] { x, y };
finded = false;
}
}
算法步骤：
1.起点NodeA存入openList集合，NodeB放入CloseList集合表，
1.起点NodeA，终点NodeB；获取openList中的点位（第一次进入获取的是起点），从A点遍历A点周围4个点上，下，左，右（如果追求经确定可以8个点上，下，左，右及斜上斜点），找到可以抵达（是否可抵达通过点位结构数据中finded=1判断，0未）的点位C;将C点存入openList集合；注意在将C点位存入tempList之前必须记录C点的父节点A（用于步骤4中寻找最终路径）；
2.利用点位C，通过A星算法基本公式F(最终估值)=G（C点距离目标B点的曼哈顿距离）+H（C点距离父节点起点距离），计算估值F
3.寻找openList中点位估值F最小点位，将其从openList表中取出，放入closeList表
4.以closeList表的最后节点closeList[closeList.Count - 1]作为新的起点，进行新一轮的（1,2,3）步骤操作
5.当最终执行到closeList[closeList.Count - 1]等于重点NodeB时，循环结束
7.最终通过反向通过链表结构查找父节点， B->B.parent.....一直找到A.parent=null截止；
8.至此整个A星算法路径方式完成，效果如下
说明：A星算法效率比较高，但是最终输出的路径并不是closeList表中点位路径，因存在冗余点位存入closeList表中，及无效但合理的点位；所以最终正确的路径应该通过 B->B.parent.....反向找到路径，这点通过详细操作算法可以感觉到
后期我将效果图及算法源码公布，谢谢
网友评论