C++实现8方向A*算法

由两部分组成，my_map.cpp用OpenCV实现读取地图等图像处理操作，main.cpp实现A*算法，经测试500*500的有复杂障碍物的地图一般不超过10秒即可跑完

#include
#include“my_map.h“
#define ABS（x） （ （x）>0?（x）:-（x） ）
#define MIN（a b） （（a） < （b） ? （a） : （b））

//设置起点和终点
//x为从左往右数第几列，y为从上往下数第几行
short start_x = 0 start_y = 0;//起始坐标
short end_x = 499 end_y = 499;//终点坐标

struct Grid//方格结构体
{
	short x y;//方格坐标
	short f g h;
	Grid *parent;//父节点
	Grid *next;//开启列表中的下一个节点
};

Grid *oHead;//开启列表为按从小到大排序的链表，头节点为最小值

//生成当前方格的相邻方格
//root为当前方格，grid为相邻方格，i为从右邻开始逆时针计数的序号，从1到8
void neighbor（Grid *root Grid *grid char i）
{
	grid->x = root->x; grid->y = root->y;
	switch （i）
	{
	case 1:grid->x++; break;
	case 2:grid->x++; grid->y--; break;
	case 3:grid->y--; break;
	case 4:grid->x--; grid->y--; break;
	case 5:grid->x--; break;
	case 6:grid->x--; grid->y++; break;
	case 7:grid->y++; break;
	case 8:grid->x++; grid->y++; break;
	default:break;
	}
}

//检查输入坐标是否在关闭列表中或是否为终点或不可抵达
char test_valid（short x short y）
{
	if （test_obstacle（x y））
		return 1;//障碍物
	if （（x == end_x） && （y == end_y））
		return 2;//终点
	if （test_closelist（x y））
		return 3;//在关闭列表中
	return 0;//坐标有效
}

//检查输入坐标是否在开启列表中
//
char test_open（Grid *grid）
{
	Grid *p = oHead;
	while （p != NULL）
	{
		if （（p->x == grid->x） && （p->y == grid->y））
		{
			grid->g = p->g;
			grid->h = p->h;
			return 4;//在开启列表中
		}
		p = p->next;
	}
	return 0;//坐标有效
}

short function_g（char x）
{
	if （x % 2）
		return 10;
	else
		return 14;
}

//目标点与终点的距离
short block_distance（short point_x short point_y）
{
	short dx = ABS（point_x - end_x）;
	short dy = ABS（point_y - end_y）;
	short ans = 14 * MIN（dx dy） + 10 * ABS（dx - dy）;
	return ans;
}

//将输入节点按从小到大顺序插入开启列表
//relocate为0时只插入节点，为1时用于将已在列表中的节点重新调整位置
void insert_openlist（Grid *gridbool relocate）
{
	if （oHead == NULL）//开启列表为空
	{
		oHead = grid;
		return;
	}
	if （grid->f <= oHead->f）//输入节点插入到列表最前
	{
		grid->next = oHead;
		oHead = grid;
		return;
	}
	Grid *p = oHead;
	bool inserted = 0;
	while （p->next !=NULL）
	{
		if （（!inserted） && （grid->f <= p->next->f））//输入节点在列表中间
		{
			grid->next = p->next;
			p->next = grid;
			if （!relocate）
				return;
			else
				inserted = 1;//先插入再删除的顺序不能乱
		}
		p = p->next;
		if （relocate && inserted && （p->next->x == grid->x） && （p->next->y == grid->y））
		{
			Grid *temp = p->next;
			p->next = temp->next;
			delete temp;
			return;
		}
	}
	p->next = grid;//输入节点在列表最后
}

void output（Grid *grid）
{
	while （grid != NULL）
	{
		draw_point（grid->x grid->y）;
		grid = grid->parent;
	}
	show（）;
}

int main（）
{
	Grid *Start = new Grid;//起点
	Grid *P;//当前方格
	Grid *Normal;//相邻方格
	char status;//用于判断方格状态
	read_map（）;
	Start->x = start_x; Start->y = start_y;
	Start->f = 0; Start->g = 0; Start->h = 0;
	Start->parent = NULL; Start->next = NULL;
	oHead = Start;//起点设为当前方格，加入开启列表
	while （1）
	{
		P = oHead;//将f值最小的方格设为当前方格
		add_closelist（oHead->x oHead->y）;//将当前方格移到关闭列表
		oHead = oHead->next;//将当前方格从开启列表中移出
		for （char i = 1; i <= 8; i++）//遍历当前方格的8个相邻方格
		{
	

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        838  2019-01-06 16:22  my_map.cpp

     文件        238  2019-01-06 15:55  my_map.h

     文件       4899  2019-01-06 16:17  main.cpp

     文件     251078  2014-06-06 15:35  map3.bmp

     文件     251078  2014-06-06 15:35  map4.bmp

     文件     251078  2014-06-06 15:35  map5.bmp

     文件     251078  2014-06-06 15:35  map1.bmp

     文件     251078  2014-06-06 15:35  map2.bmp

----------- ---------  ---------- -----  ----

              1261365                    8