维基百科的说法:
A搜索算法，俗称A星算法*。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或在线游戏的BOT的移动计算上。
A* 算法最常用作求游戏地图两点间的最短距离，rpg游戏用得最多，往往是客户端处理人物自动寻路，服务器处理怪物的自动寻路。当然A*是一个比较通用的算法，并不局限于游戏地图里面。
启发式搜索
从起点一步一步接近终点，每一步都有一个距离的评估结果，每一次选择估值最高的开始下一步，避免了穷举搜索；f(n) = g(n) + h(n)
f(n)就是对每个结点的评估函数，g(n)是起点到结点n的实际代价，h(n)是结点n到终点的评估值,g(n)需要g(1),g(2)...g(n-1)累积计算;结点
把地图划分为多个结点组成，目的是方便计算，一个地图分得结点越多，计算结果自然就更准确,图1就是把地图划分为一个个正方形结点,一个正方形格子就是一个计算单位，表示一条路线就是多个格子组合起来；堆排序
将计算的结果用二叉堆排序；
定义数据结构
- 先定义地图：
0 为可以通过，3 为障碍物,选中作为路线的结点赋值为 1
int map[20][20] =
{
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,3,3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,3,3,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,3,3,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,3,0,0,3,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,3,0,0,3,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,3,0,0,3,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,3,0,0,3,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0},
};
- 定义结点:
typedef struct star_node_t {
int x;
int y;
int g;
int h;
int f;
} Star;
- 定义一个二叉堆：
typedef struct heap_t {
Star *arr;//这是一个数组指针
int length;//当前堆长度
bool (*func)(Star,Star);//比较函数
} Heap;
如何实现？
A*算法的搜索过程需要两张表，一个open表(用最小堆实现)，用于存放发现的待比较的结点，一个close表(在本文里就是将map[x][y] = 1)，存放已经判断过得结点
流程:
- 把起始格(如果用图1表示就是绿格)添加到open列表。
- 重复如下的工作：
a) 寻找open列表中f值最低的格子。我们称它为当前格。
b) 把它切换到close列表。
c) 对相邻的8格中的每一个可通过且不在close表中不在open表中的结点添加进去。把当前格作为添加结点的父节点。记录这一格的f,g,和h值,如果它已经在open列表中，用g值为参考检查新一轮算出的g值是否更好,更低的g值意味着更好的路径(因为g值是累加值，所以不同的时候算出的g值可能会不一样)。如果是这样，就把这个结点的父节点改成当前格，并且重新计算这个结点的g和f值。如果你保持你的open列表按f值排序，改变之后你可能需要重新对开启列表排序。
d) 停止，当你排序得到的最优结点加入了close列表，这时候路径被找到，保存路径。从终点开始，沿着每个结点的父节点移动直到回到起点,这就是你的路径。
为什么要用最小二叉堆?
每一轮最后都要找出open列表里的f最小值结点，也就是说需要一个高效的排序算法，但是又不需要把所有的值都排序，只要每一次就找到一个最小值即可，所以选择 插入删除后保持根结点最小 的二叉堆(没有用堆排序，只是利用二叉堆的性质)
二叉堆的实现:
二叉堆一般用数组来表示,如果存储数组的下标基于0，那么下标为 i 的节点的子节点是2i + 1与2i + 2；其父节点的下标是⌊(i − 1) ∕ 2⌋,
当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。
- 现在构造一个最小堆:
int leftChild(int i) {
return (i+1) * 2 -1;
}
int rightChild(int i) {
return (i+1) *2;
}
int parent(int i) {
return floor((i-1)/2);
}
bool min_heap_compare(Star node1,Star node2) {
return (node1.f < node2.f);
} //比较函数
Heap *open_heap;//声明一个最小堆
Star star[300];//最小堆是数组储存的
createHeap(open_heap,star,0,min_heap_compare);//构造函数
- 构造函数:
void createHeap(Heap *hp,Star *p,int length,bool (*function)(Star,Star)){
hp -> arr = p;
hp -> length = length;
hp -> func = function;
}
- 插入函数:
void insert(Heap *hp,Star star) {
int n = hp ->length;
hp ->arr[n] = star;
hp ->length = n + 1;
filterUp(hp,n);//重下往上替换,见下文
}
- 更新函数:
void update(Heap *hp,Star star) {
for (int i=0;i< hp->length;i++){
if (star.x == hp->arr[i].x && star.y == hp->arr[i].y) {
hp->arr[i].g = star.g;
hp->arr[i].h = star.h;
int f = hp->arr[i].f;
hp->arr[i].f = star.f;
if (f < star.f){
filterDown(hp,i);//从上往下替换，见下文
}else{
filterUp(hp,i);
}
}
}
}
- 删除函数:
Star pop(Heap *hp) {
Star star = hp ->arr[0];
swap(hp,0,hp ->length -1);
hp ->length = hp ->length -1;
filterDown(hp,0);
return star;
}
- 交换函数:
void swap(Heap *hp,int index1,int index2) {
if (index1 != index2)
{
Star tmp;
tmp = hp->arr[index1];
hp ->arr[index1] = hp->arr[index2];
hp ->arr[index2] = tmp;
}
}
- filterUp函数:
我们知道插入一个结点就是将结点放入堆的最后，再和父节点比较，如果更下就交换，递归比较，一直到不再比父节点小或者比较到了根结点，这样就保持根节点最小，其中用到了fileterUp函数
void filterUp(Heap *hp,int node) {
for(int i = parent(node);
i >= 0 && hp -> func(hp ->arr[node],hp ->arr[i]);
node = i,i= parent(node))
swap(hp,node,i);
}
- filterDown函数:
这个函数是从根节点往子结点比较，pop函数删除根节点，一般的作法是用最后一个值替换根节点，然后调用filterDown函数找到更小的子结点替换
void filterDown(Heap *hp, int node) {
int l = leftChild(node);
int r = rightChild(node);
int largest = 0;
int heapMaxI = hp -> length - 1;
if (l <= heapMaxI && hp ->func(hp ->arr[l],hp ->arr[node]))
largest = l;
else
largest = node;
if (r <= heapMaxI && hp ->func(hp ->arr[r],hp ->arr[largest]))
largest = r;
if (largest != node) {
swap(hp,largest,node);
filterDown(hp,largest);
}else{
return;
}
}
寻路实现:
- 先定义开始结束结点
Star begin_star ={0,0,0,0,0};
Star end_star = {19,19,0,0,0};
- 一个open表的索引
每一次从堆里读取太慢，open索引表存结点g值
int in_open[20][20];
- 开始寻路:
首先就要将开始点放入open堆里
void find_path(Star begin,Star end,int map[20][20],Heap *open_heap,int in_open[20][20]) {
insert(open_heap,begin);
find_next_point(begin,end,map,open_heap,in_open);
}
- 计算结点g,f,h值
Star get_star(int i,int j,Star now,Star end) {
int addg;
if (i != now.x && j != now.y) {
addg = 14;
}else{
addg = 10;
}
Star star;
star.x = i;
star.y = j;
star.g = now.g + addg;
star.h = abs(i-end.x)*10 + abs(j -end.y)*10;
star.f = star.g + star.h;
return star;
}
- 寻找下一个结点
只要不是终点就会递归执行，找到选择结点的周围8个结点，判断是否加入open堆里，之后又在堆里找到最小f值的结点加入close表,在这里是map[x][y]=1
void find_around_star(Star now,Star end,int map[20][20], Heap *open_heap,int in_open[20][20]) {
int x = now.x;
int y = now.y;
for (int i = x-1;i<=x+1;i++){
for (int j = y-1;j<=y+1;j++) {
if ( i >= 0 && j>=0 && !(i==x && j==y) && i <=19 && j<=19 && map[i][j] == 0){
Star star = get_star(i,j,now,end);
if (in_open[i][j] != 0) {//如果该结点已经在open表里就判断g值,如果更小就更新
if (in_open[i][j] > star.g){
in_open[i][j]=star.g;
update(open_heap,star);
}
}else{
in_open[i][j]= star.g;
insert(open_heap,star);
}
}
}
}
}
void find_next_point(Star now,Star end,int map[20][20],Heap *open_heap,int in_open[20][20]) {
if (now.x != end.x || now.y!=end.y){
map[now.x][now.y]=1;
find_around_star(now,end,map,open_heap,in_open);
Star minStar = pop(open_heap);
find_next_point(minStar,end,map,open_heap,in_open);
}
}
最后如果将map二维数组打印出来应该是这样：
o 代表路线即map[x][y]==1的结点, # 代表障碍即map[x][y]==3的结点,其余的为map[x][y]==0的结点
o - - - - - - - - - - - - - - - - - - -
- o - - - - - - - - - - - - - - - - - -
- - o - - - - - - - - - - - - - - - - -
- - - o - - - - - - - - - - - - - - - -
- - - - o - - - - - - - - - - - - - - -
- - - - - o - - - - - - - - - - - - - -
- - - - - - o o - - - - - - - - - - - -
- - # # # # # # o o o - - - - - - - - -
- - - - - - - - o # # o - - - - - - - -
- - - - - - - - - # # - o - - - - - - -
- - - - - - - - - # - - - o - - - - - -
- - - - - - - - - # - - - - o - - - - -
- - - - - - - - - # - - # - - o - - - -
- - - - - - - - - # - - # - - - o - - -
- - - - - - - - - # - - # - - - - o - -
- - - - - - - - - # - - # - - - - - o -
- - - - - - - - - - - - # - - - - - - o
- - - - - - - - - - - - # - - - - - - o
- - - - - - - - - - - - # - - - - - - o
- - - - - - - - - - - - # - - - - - - -
