关于A*算法网上介绍的有很多，我只是看了之后对这个算法用c写了一下，并测试无误后上传以分享一下，欢迎指正！下面是我找的一个介绍，并主要根据这个实现的。
寻路算法不止 A* 这一种, 还有递归, 非递归, 广度优先, 深度优先, 使用堆栈等等, 有兴趣的可以研究研究~~
简易地图
如图所示简易地图, 其中绿色方块的是起点 (用 A 表示), 中间蓝色的是障碍物, 红色的方块 (用 B 表示) 是目的地. 为了可以用一个二维数组来表示地图, 我们将地图划分成一个个的小方块.
二维数组在游戏中的应用是很多的, 比如贪吃蛇和俄罗斯方块基本原理就是移动方块而已. 而大型游戏的地图, 则是将各种"地貌"铺在这样的小方块上.
寻路步骤
图中浅绿色描边的方块表示已经加入 "开启列表" 等待检查. 淡蓝色描边的起点 A 表示已经放入 "关闭列表" , 它不需要再执行检查.
从 "开启列表" 中找出相对最靠谱的方块, 什么是最靠谱? 它们通过公式 F=G+H 来计算.
我们假设横向移动一个格子的耗费为10, 为了便于计算, 沿斜方向移动一个格子耗费是14. 为了更直观的展示如何运算 FGH, 图中方块的左上角数字表示 F, 左下角表示 G, 右下角表示 H. 看看是否跟你心里想的结果一样?
从 "开启列表" 中选择 F 值最低的方格 C (绿色起始方块 A 右边的方块), 然后对它进行如下处理:
如图, 我们选中了 C 因为它的 F 值最小, 我们把它从 "开启列表" 中删除, 并把它加入 "关闭列表". 它右边上下三个都是墙, 所以不考虑它们. 它左边是起始方块, 已经加入到 "关闭列表" 了, 也不考虑. 所以它周围的候选方块就只剩下 4 个. 让我们来看看 C 下面的那个格子, 它目前的 G 是14, 如果通过 C 到达它的话, G将会是 10 + 10, 这比 14 要大, 因此我们什么也不做.
然后我们继续从 "开启列表" 中找出 F 值最小的, 但我们发现 C 上面的和下面的同时为 54, 这时怎么办呢? 这时随便取哪一个都行, 比如我们选择了 C 下面的那个方块 D.
D 右边已经右上方的都是墙, 所以不考虑, 但为什么右下角的没有被加进 "开启列表" 呢? 因为如果 C 下面的那块也不可以走, 想要到达 C 右下角的方块就需要从 "方块的角" 走了, 在程序中设置是否允许这样走. (图中的示例不允许这样走)
就这样, 我们从 "开启列表" 找出 F 值最小的, 将它从 "开启列表" 中移掉, 添加到 "关闭列表". 再继续找出它周围可以到达的方块, 如此循环下去...
那么什么时候停止呢? —— 当我们发现 "开始列表" 里出现了目标终点方块的时候, 说明路径已经被找到.
如何找回路径
如上图所示, 除了起始方块, 每一个曾经或者现在还在 "开启列表" 里的方块, 它都有一个 "父方块", 通过 "父方块" 可以索引到最初的 "起始方块", 这就是路径.
以上转自http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html
下面是我的代码(c)：
一共三个文件：Apath.h 、Apath.c 、main.c 代码中有详细注释（我比较懒吧，就不多说了）。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
#include <stdbool.h> #ifndef APATH_H
#define APATH_H
#endif #define TURE 1
#define FAULT 0 //约定：0是可走的，1表示障碍物不可走，2表示起点，3表示终点，4表示路径
#define int_0 0
#define int_1 1
#define int_2 2
#define int_3 3
#define int_4 4 #define MAP_MAX_X 10 //地图边界，二维数组大小
#define MAP_MAX_Y 10 typedef struct LNode {
int data; //对应数组中的数值
int F; //F = G + H;
int G; //G：从起点 A 移动到指定方格的移动代价，沿着到达该方格而生成的路径
int H; //H：从指定的方格移动到终点 B 的估算成本
int x, y; //对应数组中的坐标
bool OPen_flag; //在开放列表中为1，不在为0
bool Close_flag; //在关闭列表中为1，不在为0
struct LNode* next; //用于链表排序
struct LNode* path_next; //用于最终找到的路径
}LNode, *LinkList; LinkList InitList(); //返回一个初始化的链表
LNode** malloc_array2D(int row, int col);
void free_array2D(LNode **arr);
LNode** Translate_array(int array[][], int row, int col); //将一个普通数组翻译为单链表节点的数组
void output(LNode **array, int row, int col); LNode* find_start_LNode(LNode** Arr, int row, int col); //从数组中找到始点
LNode* find_end_LNode(LNode** Arr, int row, int col); //从数组中找到终点 //忘记这些要干嘛了，重写吧
bool isExist_ALNode_in_List(LNode* curLNode, LinkList L_OpenList); //查看节点是否在链表中，在返回ture,不在返回fault
//对关闭列表中的当前节点进行检查，看它周围的节点是否在OpenList链表里，不在:添加进去；在：检查经过它到达起点的G是否最小，是：修改，不是：不修改
//LNode* check_CloseList_curLNode(LNode* curLNode, LNode* endLNode, LinkList L_OpenList, LinkList L_CloseList, LNode** Arr); LNode* pop_OpenList_minNode(LinkList L_OpenList); //返回开放列表中F值最小的节点
void push_OpenList_Node(LinkList L, LNode *elem); //插入一个节点并排序
bool insert_Into_CloseList(LNode* min_Open, LinkList L_CloseList);//插入OpenList中F值最小的节点到CloseList中去 int count_LNode_G(LNode* curLNode, LNode* aheadLNode); //计算节点的G值
int count_LNode_H(LNode* curLNode, LNode* endLNode); //计算节点的H值
int count_LNode_F(LNode* curLNode); //计算节点的F值 bool isExist_openList(LNode* curLNode); //查看节点是否在链表中，在返回ture,不在返回fault
bool isExist_closeList(LNode* curLNode);
bool isobstacle(LNode* curLNode);
void check_around_curNode(LNode* cur, LNode* endLNode, LinkList open_list, LNode** Arr); //检查周围的节点，是否合适加入开放列表
Apath.h
#include "Apath.h" LinkList InitList()
{
LinkList L = (LinkList)malloc(sizeof(LNode));
if (L == NULL)
{
printf("Defeat!");
exit();
}
memset(L,,sizeof(LNode));
return L;
}//LinkList() LNode** malloc_array2D(int row, int col)
{
LNode** map = (LNode**)malloc(row*sizeof(LNode*) + row*col*sizeof(LNode));
LNode* head = (LNode*)(map + row);
for (int i = ; i < row; ++i)
map[i] = head + i*col;
return map;
} LNode** Translate_array(int array[][], int row, int col)
{
LNode **map = malloc_array2D(, );
for (int i = ; i < row; ++i)
for (int j = ; j < col; ++j)
{
(map[i] + j)->data = array[i][j];
(map[i] + j)->G = ;
(map[i] + j)->H = ;
(map[i] + j)->F = ; //(map[i] + j)->G + (map[i] + j)->H;
(map[i] + j)->x = i;
(map[i] + j)->y = j;
(map[i] + j)->Close_flag = ;
(map[i] + j)->OPen_flag = ;
(map[i] + j)->next = NULL;
(map[i] + j)->path_next = NULL;
}
return map;
}//Translate_array() void free_array2D(LNode **arr)
{
free(arr);
} void output(LNode** array, int row, int col) //二维数组的访问必须指明位数，否则编译器不能解析
{
//for (int i = 0; i < row; ++i)
// for (int j = 0; j < col; ++j)
// {
// (array[i] + j)->F = j;
// }
for (int i = ; i < row; ++i)
{
for (int j = ; j < col; ++j)
{
printf("%d\t", (array[i] + j)->data);
}
printf("\n");
}
} LNode* find_start_LNode(LNode** Arr, int row, int col) //从数组中找到始点
{
LNode* start_LNode = NULL;
for (int i = ; i < row; ++i)
{
for (int j = ; j < col; ++j)
{
if ( == (Arr[i] + j)->data)
{
start_LNode = (Arr[i] + j);
//起点H=0,G=0,F=0
start_LNode->G = ;
start_LNode->H = ;
start_LNode->F = ; //起点，则默认所有值为0
return start_LNode; //返回节点
}
}
}
return NULL;
}
LNode* find_end_LNode(LNode** Arr, int row, int col) //从数组中找到终点
{
LNode* end_LNode = NULL;
for (int i = ; i < row; ++i)
{
for (int j = ; j < col; ++j)
{
if ( == (Arr[i] + j)->data)
{
end_LNode = (*(Arr + i) + j);
end_LNode->F = ;
end_LNode->G = ;
end_LNode->H = ;
return end_LNode; //返回节点
}
}
}
return NULL;
} int count_LNode_G(LNode* curLNode, LNode* aheadLNode) //计算节点的G值
{
if (curLNode->x == aheadLNode->y && curLNode->y == aheadLNode->y)
return ;
if (aheadLNode->x - curLNode->x != && aheadLNode->y - curLNode->y !=)
curLNode->G = aheadLNode->G + ;
else
curLNode->G = aheadLNode->G + ;
return curLNode->G;
}
int count_LNode_H(LNode* curLNode, LNode* endLNode) //计算节点的H值
{
curLNode->H = abs(endLNode->x - curLNode->x) * + abs(endLNode->y - curLNode->y) * ;
return curLNode->H;
}
int count_LNode_F(LNode* curLNode) //计算节点的F值
{
curLNode->F = curLNode->G + curLNode->H;
return curLNode->F;
} void push_OpenList_Node(LinkList L, LNode *elem) //按从小到大的顺序
{
LNode *p, *q;
p = q = L;
while (p->next != NULL && p->F < elem->F)
{
q = p;
p = p->next;
}
if (p->F < elem->F) q = p;
elem->next = q->next;
q->next = elem;
//插入成功，更改属性值OPen_flag = 1
elem->OPen_flag = ;
}
LNode* pop_OpenList_minNode(LinkList L_OpenList ) //返回开放列表中F值最小的节点
{
LNode *elem = NULL;
if (L_OpenList->next) //为了安全，防止访问空指针
{
L_OpenList->next->OPen_flag = ;
elem = L_OpenList->next;
L_OpenList->next = L_OpenList->next->next;
elem->next = NULL;
}
else
printf("have a NULL point in pop_OpenList_mimNode()");
return elem;
}
bool insert_Into_CloseList(LNode* min_Open, LinkList L_CloseList)//插入OpenList中F值最小的节点到CloseList中去
{
//对于CloseList中的节点并不需要排序,采用头插法
min_Open->next = L_CloseList->next;
L_CloseList->next = min_Open;
min_Open->Close_flag = ;
return TURE;
} bool isExist_openList(LNode* curLNode)
{
return curLNode->OPen_flag;
}
bool isExist_closeList(LNode* curLNode)
{
return curLNode->Close_flag;
}
bool isobstacle(LNode* curLNode)
{
if (curLNode->data == )
return TURE;
else
return FAULT;
}
bool isJoin(LNode* cur) //该节点是否可以加入开放列表
{
if (cur->x > - && cur->y > -) //边界检测
{
if (!isExist_closeList(cur) && !isobstacle(cur)) //既不在关闭列表里，也不是障碍物
{
return TURE;
}
else
return FAULT;
}
return FAULT;
}
void insert_open(LNode *Node, LNode* ahead, LNode* endLNode, LinkList open_list, LNode** Arr)
{
if (isJoin(Node))
{
if (isExist_openList(Node))
{
if (Node->x - ahead->x != && Node->y - ahead->y != ) {
if (Node->F > (ahead->F + ))
{
count_LNode_G(Node, ahead);
count_LNode_F(Node); //H值没有改变，所以还是原来的值
Node->path_next = ahead; //也不用再插入
}
}
else {
if (Node->F > (ahead->F + ))
{
count_LNode_G(Node, ahead);
count_LNode_F(Node); //H值没有改变，所以还是原来的值
Node->path_next = ahead; //也不用再插入
}
}
}
else {
count_LNode_G(Node, ahead);
count_LNode_H(Node, endLNode);
count_LNode_F(Node);
Node->path_next = ahead;
push_OpenList_Node(open_list, Node);
}
}
}
void check_around_curNode(LNode* cur, LNode* endLNode, LinkList open_list, LNode** Arr)
{
int x = cur->x;
int y = cur->y;
insert_open(Arr[x] + y - , cur, endLNode, open_list, Arr);
insert_open(Arr[x] + y + , cur, endLNode, open_list, Arr);
insert_open(Arr[x + ] + y, cur, endLNode, open_list, Arr);
insert_open(Arr[x + ] + y - , cur, endLNode, open_list, Arr);
insert_open(Arr[x + ] + y + , cur, endLNode, open_list, Arr);
insert_open(Arr[x - ] + y, cur, endLNode, open_list, Arr);
insert_open(Arr[x - ] + y + , cur, endLNode, open_list, Arr);
insert_open(Arr[x - ] + y - , cur, endLNode, open_list, Arr);
}
Apath.c
#include <stdio.h>
//#ifndef APATH_H
#include "Apath.h"
//#endif //为简单，干脆把把下面数组转为链表结构的数组
//约定：0是可走的，1表示障碍物不可走，2表示起点，3表示终点，4表示路径
int array[][] = {
{ , , , , , , , , , },
{ , , , , , , , , , },
{ , , , , , , , , , },
{ , , , , , , , , , },
{ , , , , , , , , , },
{ , , , , , , , , , },
{ , , , , , , , , , },
{ , , , , , , , , , },
{ , , , , , , , , , },
{ , , , , , , , , , } }; int main()
{
int row = MAP_MAX_X, col = MAP_MAX_Y;
printf("hello world!\n");
LNode **map = Translate_array(array,row, col); //这里将数组的地图转为节点map的地图
output(map,,);
LinkList open_List = InitList(); //定义并初始化一个开放列表
LinkList close_List = InitList(); //一个封闭列表
LNode* startLNode = find_start_LNode(map, row, col);
LNode* endLNode = find_end_LNode(map, row, col); LNode* curLNode = startLNode; //当前节点=开始节点
curLNode->G = ; //计算节点的三个值
count_LNode_H(curLNode, endLNode);
count_LNode_F(curLNode);
push_OpenList_Node(open_List, curLNode); //先将开始节点插入开放列表 while (curLNode->data != )
{
//LNode *e = NULL;
curLNode = pop_OpenList_minNode(open_List);
insert_Into_CloseList(curLNode, close_List);
//2、查看起点周围的点是否在开放列表里，不在加入，在检测经过该点F值是否最小等；
check_around_curNode(curLNode, endLNode, open_List, map);
}
while (endLNode->path_next)
{
printf("x:%d---y:%d\n", endLNode->path_next->x,endLNode->path_next->y);
endLNode->path_next = endLNode->path_next->path_next;
}
return ;
}
main.c
测试结果（红线就是要找的路线）：