最近给几位程序猿同仁教了一下A*搜索。鉴于同仁们在实现A*的过程中各种蛋疼的问题，特发此贴，希望对我IT民工党有所帮助。
A*搜寻算法俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。（拷自百度百科）是常用搜索算法中，能够以最短时间来求得最短路径的一种启发式搜索算法。兼具广搜和深搜的优点，那么比较起广搜和深搜这些盲目搜索，A*有什么特点呢？A*搜索的效率就在于：以深搜的形式来扩展已知结点中的最优结点，而最优结点的定位又类似于广搜。
估计大家现在也不知道我在乱七八糟说些什么。下面正式开始介绍A*算法。
在构建A*搜索函数主体之前，我们需要一个估价函数（ f ），来评估通过当前到目标状态的代价（大家可以理解为，通过这条路走到目的地有多长的路程）
其中 f（估价函数值） = actual（已消耗的实际代价）+ estimate（还可能再消耗的预估代价）actual 无需多说，便是从搜索起始结点到当前扩展结点的代价（距离）总和； estimate 的确定，需要用到曼哈顿距离（Manhattan Distance）， 在简单的二维地图中，我们可以认为，上下左右4个方向上的代价为10，而斜向的4个方向的代价为14（√(200) 的近似值 [1] ）
而在 8 连通图 中
// C++ 代码
#define STRAIGHT 10 // 上下左右4个方向上的代价为10
#define OBLIQUE 14 // 斜向的4个方向的代价为14
#define Manhattan(i) ( ( ((int)i) % 2 ) ? (OBLIQUE) : (STRAIGHT) ) // 曼哈顿距离
signed int Estimate( const Node* curr, const Node* end ) // 预估值计算函数
{
int x = abs( curr->x - end->x );
int y = abs( curr->y - end->y );
int le = max( x, y );
int se = min( x, y );
return se * STRAIGHT + ( le - se ) * OBLIQUE ;
}在A*搜索所使用到的结点的结构：
x、y 坐标值（也是结点唯一性的标识）[2]
actual 上面提到的“真实值”
estimate 预估值
father 父结点地址（也可以是 父结点的坐标值 或 被拓展的方向 ）
在此补充一下结点状态
活结点：尚未扩展的结点
死结点：已扩展完的结点
扩展结点：当前正在扩展的结点
// C++ 代码
struct Node
{
int x;
int y;
unsigned int actual;
unsigned int estimate;
Node* father;
};此外还需要两个表（open、close）来记录，在 C++ 中可以用标准库中的 list 实现（特点：O(1)时间复杂度内插入结点）
// C++ 代码
std::list<Node*> open; // 存放活结点 std::list<Node*> close;// 存放死结点，搜索成功后，其中存有最优路径
下面给出A*算法的主步骤
（1）将 targetNode（目标结点）放入 open 表，actual = 0; estimate = Esitimate( &startNode, &targetNode )。[3]
（2）进入循环，重复下列过程；如果 open 表为空，则搜索失败，既：target 与 Start 之间不存在通路。
（3）遍历 open 表，将最小的 f 值（actual + Esitimate）选为 bestNode，并从 open 表中删除，放入 close 表。
（4）判断 bestNode 是否为 startNode ，若是，则成功搜索到了最短路径。
（5）若不是，开始遍历 8个方向，扩展 bestNode。
（a）根据方向和 bestNode 的坐标计算子结点坐标，子结点的 actual = bestNode 的 actual + 10（上向左右）或 14（斜向），
estimate = Estimate( &子结点, &startNode )，father = bestNode。
（b）判断 bestNode 的子结点 是否在 close 表中，若是，loop （5）。
（c）若不是，判断子结点是否在 open 表中，若是，开始（i），否则执行（d）；
（i） 再判断 open 表中记录的结点的 actual 值是否大于 当前子结点的 actual 值（新旧路径代价比较）；
（ii）若是，令 open 表中记录的结点的 actual = 当前子结点的 actual，令 open 表中记录的结点的 father 指向bestNode。loop （5）。
（d）否则（子结点既不在 open 表中，又不在 close 表中），将子结点记入 open 表，loop（5）。
（6）loop （2）
// C++ 代码
enum Direct // 8 方向
{
Up,
Right_Up,
Right,
Right_Down,
Down,
Left_Down,
Left,
Left_Up
};
#define stepLength 10 // 步长为 10 [4]
bool AStarSearch()
{
struct Point
{
int y;
int x;
};
//子结点相对于父节点的坐标偏移，x~j，y~i
static Point offset[8] = {
{ -1, -1 },
{ -1, 0 },
{ -1, +1 },
{ 0, -1 },
{ 0, +1 },
{ +1, -1 },
{ +1, 0 },
{ -1, +1 }
};
// 将 targetNode（目标结点）放入 open 表
targetNode.actual = 0;
targetNode.estimate = Estimate( &targetNode, &startNode );
targetNode.father = NULL;
open.push_back(&targetNode);
//如果 open 表为空，则搜索失败，既：target 与 Start 之间不存在通路。
while(!open.empty())
{
// 遍历 open 表，将最小的 f 值（actual + Esitimate）选为 bestNode [5]
std::list<Node*>::iterator bestIt = open.begin();
for( std::list<Node*>::iterator it = open.begin(); it!=open.end(); ++it )
if( (*it)->actual + (*it)->estimate < (*bestIt)->actual + (*bestIt)->estimate )
bestIt = it;
// 将 bestIt 从 open 表中删除，放入 close 表
close.push_front(*bestIt);
open.erase(bestIt);
bestIt = close.begin(); // 重新获取失效的迭代器
// 判断 bestNode 是否为 startNode ，若是，则成功搜索到了最短路径
if(abs((*bestIt)->x-startNode.x)<stepLength&&abs((*bestIt)->y-startNode.y)<stepLength)
{
// 搜索成功
ClearTable( open ); // 清空表
return true;
}
// 开始遍历 8个方向，扩展 bestNode
for( Direct i = Up; i<=Left_Up; i=(Direct)(i+1) )
{
// 根据方向和 bestNode 的坐标计算子结点坐标
int x = (*bestIt)->x + offset[i].x * stepLength;
int y = (*bestIt)->y + offset[i].y * stepLength;
// 越界检测和碰撞检测
if(x<0||x>=Col||y<0||y>=Row||!IsCollision(x,y))
continue;
bool inTable = false;
// 判断子结点是否在 close 表中
for( std::list<Node*>::iterator it = close.begin(); it!=close.end(); ++it )
{
if( (*it)->x == x && (*it)->y == y )
{
inTable = true;
break;
}
}
if(inTable)
continue;
// 计算子结点的实际值
unsigned int actual = (*bestIt)->actual + Manhattan(i);
// 判断子结点是否在 open 表中
for( std::list<Node*>::iterator it = open.begin(); it!=open.end(); ++it )
{
if( (*it)->x == x && (*it)->y == y )
{
if( (*it)->actual > actual )// 新旧路径代价比较
{
// 记录较优路径
(*it)->actual = actual;
(*it)->father = *bestIt;
}
inTable = true;
break;
}
}
//子结点既不在 open 表中，又不在 close 表中，将子结点记入 open 表
if( ! inTable )
{
Node* childNode = new Node;
childNode->x = x;
childNode->y = y;
childNode->actual = actual;
childNode->estimate = Estimate( childNode, &startNode );
childNode->father = *bestIt;
open.push_back( childNode );
}
}// for( Direct i = Up; i<=Left_Up; i=(Direct)(i+1) )
}// while( ! open.empty() )
// 搜索失败
close.pop_back(); // 将栈底的 targetNode 的指针（指向非栈区内存）出栈，防止 ClearTable 出错
ClearTable( close ); // 清空表
return false;
}
注意要点 ：
[1] 千万不要做开方运算，因为这是在循环中计算的，开方会严重降低程序效率，直接使用14;另外推荐使用10和14，
而非 1.0 和 1.4，因为浮点运算的效率也低于整形运算，且浮点数比较有精度问题，如：5.0在计算机中可能有4.9999
和5.0001等多种可能，估比较运算只能使用 abs(4.9999-5.0001)<某极小值
[2] 注意 x，y 与 j，i 之间的对应关系；这里是很容易误将 x 对应 i（行），y 对应 j（列），而出数组越界、路径翻转等各种
奇葩错误
[3] 从目的结点（鼠标右击的位置）搜索到起始结点（人物所在的位置），因为每次扩展都记录的父结点。最后在“走”
的这一过程中，是从起始结点开始行走，沿其父结点一路走到目的结点（搜与走为互逆过程）。若从起始结点搜到目的
结点，则还要再将路径反置一次 ，这就是多次一举了
[4] 切勿逐像素搜索，这是导致搜索低下的主要原因之一。例如，当游戏窗口为600*800时。玩家长距离点击的长度一般
为对角线的 4/5 = 800，粗略估计逐像素查找所需遍历的像素量为 800*800*π*0.5 ≈ 1 005 310，而十像素步长搜索只
有 80*80*π*0.5 ，效率高出 100 倍 ，当然这会造成一定的精度损失。（碰撞检测函数 IsCollision 当然也要以这种思路
设计，可采用在人物双脚范围上进行 “九点检测”）
[5] 此处不要使用对 open 链表排序的方式来查找最优活结点，这是另一个导致搜索低下的主要原因。因为即使是快排，在
每次循环时都要耗费 O(nlogn) 的时间复杂度，而遍历只需要 O(n)。但可以考虑在每次向 open 表插入元素时使用插入排
序，但由于链表的特性。是无法通过二分查找来定位插入的位置，只能通过遍历来插入。因此插入的时间复杂度同样还是
O(n)。
版权申明:本文出自 Mayfly，原文地址: http://user.qzone.qq.com/463994042/blog/1421066548
