[科普中国]-A*搜寻算法

算法描述

A*改变它自己行为的能力基于启发式代价函数，启发式函数在游戏中非常有用。在速度和精确度之间取得折衷将会让你的游戏运行得更快。在很多游戏中，你并不真正需要得到最好的路径，仅需要近似的就足够了。而你需要什么则取决于游戏中发生着什么，或者运行游戏的机器有多快。 假设你的游戏有两种地形，平原和山地，在平原中的移动代价是1而在山地的是3，那么A星算法就会认为在平地上可以进行三倍于山地的距离进行等价搜寻。 这是因为有可能有一条沿着平原到山地的路径。把两个邻接点之间的评估距离设为1.5可以加速A*的搜索过程。然后A*会将3和1.5比较，这并不比把3和1比较差。然而，在山地上行动有时可能会优于绕过山脚下进行行动。所以花费更多时间寻找一个绕过山的算法并不经常是可靠的。 同样的，想要达成这样的目标，你可以通过减少在山脚下的搜索行为来打到提高A星算法的运行速率。若想如此可以将A星算法的山地行动耗费从3调整为2即可。这两种方法都会给出可靠地行动策略。

用C语言实现A*最短路径搜索算法，作者 Tittup frog(跳跳蛙)。

#include #include #define MaxLength 100 //用于优先队列（Open表）的数组#define Height 15 //地图高度#define Width 20 //地图宽度#define Reachable 0 //可以到达的结点#define Bar 1 //障碍物#define Pass 2 //需要走的步数#define Source 3 //起点#define Destination 4 //终点#define Sequential 0 //顺序遍历#define NoSolution 2 //无解决方案#define Infinity 0xfffffff#define East (1 cur->y; for (i = 0; i cur->sur & (1 cur->x; curY = p->cur->y; if (!p->H) { return Sequential; } for (i = 0; i cur->sur & (1 from; return &(close[srcX][srcY]); case NoSolution: return NULL; } return NULL;}static Close *start;static int shortestep;int printShortest(){ Close *p; int step = 0; p = getShortest(); start = p; if (!p) { return 0; } else { while (p->from) { graph[p->cur->x][p->cur->y].value = Pass; printf("（%d，%d）→\n", p->cur->x, p->cur->y); p = p->from; step++; } printf("（%d，%d）\n", p->cur->x, p->cur->y); graph[srcX][srcY].value = Source; graph[dstX][dstY].value = Destination; return step; }}void clearMap(){ // Clear Map Marks of Steps Close *p = start; while (p) { graph[p->cur->x][p->cur->y].value = Reachable; p = p->from; } graph[srcX][srcY].value = map[srcX][srcY]; graph[dstX][dstY].value = map[dstX][dstY];}void printDepth(){ int i, j; for (i = 0; i