标题: A星寻路算法 [打印本页] 作者: may 时间: 2018-12-31 19:48 标题: A星寻路算法
來自： sheng2008
A星是常见的寻路算法。主要的思路是：
把场景设计成大小一致的单元格。每个单元格都用表示可以行走或者阻挡的标志。你可以理解为一个二维数组。数组的下标表示格子的索引。数组的值1表示可以行走。1表示阻挡
假设起始点是S。终点为E。每个单元格都用一个值F。表示当前路径下。选择走该方格的代价值，A星最核心的就是F的计算
F = G + H；
G：表示S到该点的代价。这个值是确定的。G = 父节点的G值+父节点到当前点的代价
H:当前点到目标点预估移动代价。之所以称为预估。是因为不知道当前点到目标的具体路径。所以才需要预估。通常的预估方法有曼哈顿距离、欧式距离、对角线距离。一般采用的是曼哈顿距离。因为如果要走对角线的话。需要做特殊的边角处理。不然角色移动可能穿墙。所以只上下左右移动
H = 当前点到终点的水平距离+当前点到终点的垂直距离
寻找到终点的时候。需要方向遍历获得路径。所以每个节点都要记录父节点。所以节点类可以这样设计
public class NodeItem
{
public int x; //在二维数组中的索引
public int y; //在二维数组中的索引
public int nGCost;
public int nHCost;
public int AllCost
{
get { return nGCost + nHCost; }
}
public bool bWall; //是否为墙。即阻挡
public Vector2 vPos; //坐标值
public NodeItem parent; //父节点
public NodeItem(bool isWall, Vector3 pos, int x, int y)
{
this.bWall = isWall;
this.vPos = pos;
this.x = x;
this.y = y;
}
}
下面的方法是用曼哈顿距离获取两个节点之间的距离
int getDistanceNodes(NodeItem a, NodeItem b) //曼哈顿距离获取两个节点之间的距离
{
int cntX = Mathf.Abs(a.x - b.x);
int cntY = Mathf.Abs(a.y - b.y);
return (cntX + cntY);
}
A星算法是用一个Open和一个Close两个列表来分别存放将要访问的节点和已经访问过的节点。步骤如下：
1、把S点放进Open列表里面。并且计算S点的G、H值
2、如果Open列表不为空：
取出Open列表里面的H值最小的点做为当前要访问的节点。并把该点从Open列表移除。放入到Close列表里面
如果当前点即E点。则寻路完成。否则取出当前点的相邻节点。并判断该点是否为阻挡或者已经在Close列表里面。如果都不是。则重新计算相邻节点的G值和H值。如果该点没有在Open列表里。则在Open列表中加入该点。如果该点在Open列表里。但是新计算的G值比之前的小。则更新该点是G值和H值
3、重复步骤2.直到找到终点E。或者Open列表为空。结束查找
具体代码如下：
public List<NodeItem> FindingPath(NodeItem startNode, NodeItem endNode)
{
List<NodeItem> openList = new List<NodeItem>();
List<NodeItem> closeList = new List<NodeItem>();
openList.Add(startNode);
startNode.nGCost = 0;
startNode.nHCost = getDistanceNodes(startNode, endNode);
while (openList.Count > 0)
{
NodeItem curNode = openList[0];
for(int i = 1; i < openList.Count; ++i)
{
if(openList.AllCost < curNode.AllCost)
{
curNode = openList;
}
}