A星寻路算法

may

來自：  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;
}
}

openList.Remove(curNode);
closeList.Add(curNode);
if(curNode == endNode)
{
return generatePath(startNode, endNode);
}

List<NodeItem> ltNode = m_aCreateMap.getNeibourhood(curNode);
for (int i = 0; i < ltNode.Count; ++i)
{
NodeItem _tempNode = ltNode;
if (_tempNode.bWall || closeList.Contains(_tempNode))
continue;

int newCost = curNode.nGCost + getDistanceNodes(curNode, _tempNode);
if(newCost < _tempNode.nGCost || !openList.Contains(_tempNode))
{
_tempNode.nGCost = newCost;
_tempNode.nHCost = getDistanceNodes(_tempNode, endNode);
_tempNode.parent = curNode;
if(!openList.Contains(_tempNode))
{
openList.Add(_tempNode);
}
}
}

}

return generatePath(startNode, null);
}