动画演示
//伪码
void FindPath(_start, _target)
{
start = _start;
target = _target;
gCost = 0;//从起始节点到当前节点的路径的成本，
hCost = 0;//启发值，用于估算从当前节点到目标节点成本最低的路径。
fCost = gCost + hCost;
List seachPath = new List();//记录最短路径的搜索规模
List path = new List();//记录最短路径
List closeSet = new List();//已评估的节点集合
List openSet = new List();//将要被评估的节点集合
openSet.Add(start);//初始只包含 start
while(openSet.Count > 0)//当将被估算的节点存在时，执行循环
{
currentNode = openSet[0];
for (int i = 1; i < openSet.Count; i++)
{ //在将被估计的集合中找到 fCost 最小的节点 currentNode
//如果有两个或多个 fCost 值相同，就选 hCost 最小的节点
if (openSet[i].fCost < currentNode.fCost ||
(openSet[i].fCost == currentNode.fCost &&
openSet[i].hCost < currentNode.hCost))
currentNode = openSet[i];
}
openSet.Remove(currentNode);//将 currentNode 节点从将被估算的节点中删除
closeSet.Add(currentNode);//将 currentNode节点插入已经被估算的节点
if(currentNode == target)
{//如果到达终点，退出循环，并输出最短路径和搜索规模
print(seachPath);
print(path);
return;
}
//获取 currentNode 相邻的8个方向节点
List neighbours = GetNeighbours(currentNode);
for (int i = 0; i < neighbours.Count; i++)
{//循环遍历与 currentNode 相邻的节点
neighbour = neighbours[i];
//如果是障碍物，或者已估值，跳过
if (!neighbour.walkable || closeSet.Contains(neighbour))
continue;
else//如果以上都不是，认定为搜索规模路径
seachPath.Add(neighbour);
//计算从起点到节点 neighbour 的距离
gCostToNeighbour = currentNode.gCost +
BetweenDistance(currentNode, neighbour);
if (gCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))
{//如果起点到 neighbour 的距离小于 neighbour 的实际距离
//或者 neighbour 不是将被估算的节点
neighbour.gCost = gCostToNeighbour;//更新起始节点到当前节点距离
//估计 neighbour 到终点的距离
neighbour.hCost = BetweenDistance(neighbour, target);
path.Add(currentNode);//认定最短路径节点
}
//将 neighbour 插入将被估算的节点中
if (!openSet.Contains(neighbour))
openSet.Add(neighbour);
}
}
}
List GetNeighbours( _node)
{//获取与 Cell 相邻的 W,N,E,S 和 N.W, N.E, S.W, S.E 八个方向的节点
/*N.W N N.E
\ | /
\ | /
W---- Cell ----E
/ | \
/ | \
S.W S S.E*/
List neighbours = new List();
for (int x = -1; x <= 1; x++)
{
for (int y = -1; y <= 1; y++)
{
if (x == 0 && y == 0) continue;//自身(Cell)，跳过
checkX = _node.girdX + x;
checkY = _node.girdY + y;
if (checkX >= 0 && checkX < gridSizeX &&
checkY >= 0 && checkY < gridSizeY)
{
neighbours.Add(grid[checkX][checkY]);
}
}
}
return neighbours;
}
float BetweenDistance(_start, _target)
{
//常见的评估函数有——对角线距离，欧几里得距离，曼哈顿距离，切比雪夫距离
/*启发式可用于控制 A* 的行为。
A*的美妙之处在于它支持各种启发式方法，因此您可以尝试不同的方法，直到获得您想要的结果。
启发式函数可以根据其速度，效率和其他各种标准而有所不同。*/
}
//其中 D 是 W,N,E,S 移动成本，D2 是 N.W, N.E, S.W, S.E 对角移动成本
//对角线距离
dstX = Abs(_start.girdX - _target.girdX);
dstY = Abs(_start.girdY - _target.girdY);
if (dstX > dstY)
return D2 * dstY + D * (dstX - dstY);
return D2 * dstX + D * (dstY - dstX);
对角线距离
//欧几里得距离
//<欧几里得距离>比<对角线距离>运行时间长，并且也可以获得最短路径
//绿色范围越大，算法运行越慢
//算法的时间复杂度和启发式函数息息相关
dstX = Abs(_start.girdX - _target.girdX);
dstY = Abs(_start.girdY - _target.girdY);
return D * Sqrt(dstX * dstX + dstY * dstY);
欧几里得距离
//欧几里得，平方
dstX = Abs(_start.girdX - _target.girdX);
dstY = Abs(_start.girdY - _target.girdY);
return D * (dstX * dstX + dstY * dstY);
欧几里得，平方
我已经看过几个 A* 网页建议您避免<欧几里德距离>中昂贵的平方根(Sqrt)，改为使用<欧几里得，平方>。
不要这样做！当 A* 在计算 fCost = gCost + hCost 时，hCost 将远远高于 gCost，那么这时只有 hCost 发挥作用，并且 A* 将降级为贪婪的最佳优先搜索。
并不能求出最短路径。
网友评论