A*搜寻算法俗称A星算法。 

这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。 



A*改变它自己行为的能力基于启发式代价函数，启发式函数在游戏中非常有用。在速度和精确度之间取得折衷将会让你的游戏运行得更快。在很多游戏中，你并不真 

正需要得到最好的路径，仅需要近似的就足够了。而你需要什么则取决于游戏中发生着什么，或者运行游戏的机器有多快。 

假设你的游戏有两种地形，平原和山地，在平原中的移动代价是1而在山地则是3。 

A* is going to search three times as far along flat land as it does along mountainous land. 

这是因为有可能有一条沿着平原到山地的路径。把两个邻接点之间的评估距离设为1.5可以加速A*的搜索过程。然后A*会将3和1.5比较，这并不比把3和1比较差。 



It is not as dissatisfied with mountainous terrain, so it won't spend as much time trying to find a way around it. Alternatively, you can speed up 

up A*'s search by decreasing the amount it searches for paths around mountains―just tell A* that the movement cost on mountains is 2 instead of 3. 

Now it will search only twice as far along the flat terrain as along mountainous terrain. Either approach gives up ideal paths to get something quicker. 



速度和精确度之间的选择前不是静态的。你可以基于CPU的速度、用于路径搜索的时间片数、地图上物体（units）的数量、物体的重要性、组（group）的大小、难度或者其 

他任何因素来进行动态的选择。取得动态的折衷的一个方法是，建立一个启发式函数用于假定通过一个网格空间的最小代价是1，然后建立一个代价函数（cost function）用 

于测量 

（scales）：g’(n) = 1 + alpha * ( g(n) – 1 ) 

如果alpha是0，则改进后的代价函数的值总是1。这种情况下，地形代价被完全忽略，A*工作变成简单地判断一个网格可否通过。如果alpha是1，则最初的代价函数将起作用， 

然后你得到了A*的所有优点。你可以设置alpha的值为0到1的任意值。你也可以考虑对启发式函数的返回值做选择：绝对最小代价或者期望最小代价。例如，如果你的地图大部 

分地形是代价为2的草地，其它一些地方是代价为1的道路，那么你可以考虑让启发式函数不考虑道路，而只返回2*距离。速度和精确度之间的选择并不是全局的。在地图上的 

某些区域，精确度是重要的，你可以基于此进行动态选择。例如，假设我们可能在某点停止重新计算路径或者改变方向，则在接近当前位置的地方，选择一条好的路径则是更重 

要的，因此为何要对后续路径的精确度感到厌烦？或者，对于在地图上的一个安全区域，最短路径也许并不十分重要，但是当从一个敌人的村庄逃跑时，安全和速度是最重要的。 

在游戏中，路径潜在地花费了许多存储空间，特别是当路径很长并且有很多物体需要寻路时。路径压缩，导航点和beacons通过把多个步骤保存为一个较小数据从而减少了空间 

需求。 



Waypoints rely on straight-line segments being common so that we have to store only the endpoints, while beacons rely on there being well-known paths 

calculated beforehand between specially marked places on the map. 



如果路径仍然用了许多存储空间，可以限制路径长度，这就回到了经典的时间-空间折衷法：为了节省空间，信息可以被丢弃，稍后才重新计算它。 



如果你看到这里，好了，这道题你就过了，真的，其实这道题和A星半毛钱关系都没有-_-#，写那么长的目的只有两个，第一，告诉你要敢于读题，不管这题目描述有多长；第二， 

A星算法真的很有用，这里小打下广告，多年以后，如果你做游戏的话，你会感谢我的

这道题是多组测试数据，每组第一行一个整数N，然后是一个N*N的矩阵，由*或者@组成， 

每组输出占一行，输出*的个数和@的个数的差就好。

5
*****
@**@@
**@**
@*@**
*****
4
@***
****
****
***@

13
12