#include
#include“my_map.h“
#define?ABS（x）?（?（x）>0?（x）:-（x）?）
#define?MIN（a?b）?（（a）?
//設(shè)置起點和終點
//x為從左往右數(shù)第幾列，y為從上往下數(shù)第幾行
short?start_x?=?0?start_y?=?0;//起始坐標
short?end_x?=?499?end_y?=?499;//終點坐標

struct?Grid//方格結(jié)構(gòu)體
{
	short?x?y;//方格坐標
	short?f?g?h;
	Grid?*parent;//父節(jié)點
	Grid?*next;//開啟列表中的下一個節(jié)點
};

Grid?*oHead;//開啟列表為按從小到大排序的鏈表，頭節(jié)點為最小值

//生成當(dāng)前方格的相鄰方格
//root為當(dāng)前方格，grid為相鄰方格，i為從右鄰開始逆時針計數(shù)的序號，從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;
	}
}

//檢查輸入坐標是否在關(guān)閉列表中或是否為終點或不可抵達
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;//在關(guān)閉列表中
	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;
}

//將輸入節(jié)點按從小到大順序插入開啟列表
//relocate為0時只插入節(jié)點，為1時用于將已在列表中的節(jié)點重新調(diào)整位置
void?insert_openlist（Grid?*gridbool?relocate）
{
	if?（oHead?==?NULL）//開啟列表為空
	{
		oHead?=?grid;
		return;
	}
	if?（grid->f?<=?oHead->f）//輸入節(jié)點插入到列表最前
	{
		grid->next?=?oHead;
		oHead?=?grid;
		return;
	}
	Grid?*p?=?oHead;
	bool?inserted?=?0;
	while?（p->next?!=NULL）
	{
		if?（（!inserted）?&&?（grid->f?<=?p->next->f））//輸入節(jié)點在列表中間
		{
			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;//輸入節(jié)點在列表最后
}

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;//當(dāng)前方格
	Grid?*Normal;//相鄰方格
	char?status;//用于判斷方格狀態(tài)
	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;//起點設(shè)為當(dāng)前方格，加入開啟列表
	while?（1）
	{
		P?=?oHead;//將f值最小的方格設(shè)為當(dāng)前方格
		add_closelist（oHead->x?oHead->y）;//將當(dāng)前方格移到關(guān)閉列表
		oHead?=?oHead->next;//將當(dāng)前方格從開啟列表中移出
		for?（char?i?=?1;?i?<=?8;?i++）//遍歷當(dāng)前方格的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