/*
?*?author:	Atom
*?date:		2012/12/03
*?file:		Astar.c
*/
#include?“Astar.h“

#define?SPEED	10

long?euclidean_distance（int?int?int?int）;		/*?歐氏距離?*/
long?manhattan_distance（int?int?int?int）;		/*?曼哈頓距離?*/
long?chebyshew_distance（int?int?int?int）;		/*?切比雪夫距離?*/

int?main（int?argc?char*?argv[]）
{
	struct?tile_map?tmap;
	tmap.row?=?35;
	tmap.column?=?35;
	
	printf（“euclidean?distance:\n“）;
	init_map（&tmap）;
	gen_wall（&tmap）;
	astar（&tmap?2?1??30?30?euclidean_distance）;
	destory_map（&tmap）;

	printf（“manhattan?distance:\n“）;
	init_map（&tmap）;
	gen_wall（&tmap）;
	astar（&tmap?3?3??30?30?manhattan_distance）;
	destory_map（&tmap）;
	
	printf（“chebyshew?distance:\n“）;
	init_map（&tmap）;
	gen_wall（&tmap）;
	astar（&tmap?3?3??30?30?chebyshew_distance）;
	destory_map（&tmap）;

	return?（0）;
}

/*?搜索路徑?*/
void?astar（struct?tile_map*?tmap?int?st_x?int?st_y?int?end_x
																?int?end_y?distance_t?distance）
{
	struct?Bheap?*o_heap?=?NULL?*c_heap?=?NULL;
	struct?map_node?*fnode?=?NULL;
	struct?Bheap_node?*inode?=?NULL?*onode?=?NULL;
	struct?map_node?*omnode?=?NULL;
	int?fx?=?0?fy?=?0;
	
	if?（（NULL?==?tmap）?||?（st_x?<=?0）?||?（st_y?<=?0）?||?（end_x?<=?0）?||?（end_y?<=?0））
		return;
	
	if?（!is_reachable（tmap?st_x?st_y）?||?!is_reachable（tmap?end_x?end_y））
	{
		printf（“開始節點或結束節點錯誤，無法到達!\n“）;
		return;
	}
	o_heap?=?Bheap_create（128?BHEAP_TYPE_SMALL）;
	c_heap?=?Bheap_create（128?BHEAP_TYPE_SMALL）;
	Bheap_init（o_heap）;
	Bheap_init（c_heap）;
	
	tmap->map[st_x][st_y]?=?START;
	tmap->map[end_x][end_y]?=?END;
	
	if?（NULL?==?（fnode?=?MALLOC（struct?map_node?1）））
	{
		fprintf（stderr?“malloc?fnode?error!\n“）;
		return;
	}
	if?（NULL?==?（inode?=?MALLOC（struct?Bheap_node?1）））
	{
		fprintf（stderr?“malloc?inode?error!\n“）;
		return;
	}
	
	memset（fnode?0x00?sizeof（struct?map_node））;
	memset（fnode?0x00?sizeof（struct?Bheap_node））;
	
	fnode->x?=?st_x;
	fnode->y?=?st_y;
	fnode->g?=?0;
	fnode->h?=?distance（st_x?st_y?end_x?end_y）;
	fnode->f?=?fnode->g?+?fnode->h;
	fnode->parent?=?NULL;
	
	inode->value?=?fnode;
	Bheap_push（o_heap?inode?_comp）;

#if?0
	print_map（tmap）;
#endif

	for?（?;?;?）
	{
		omnode?=?NULL;
		if?（NULL?==?（onode?=?Bheap_pop（o_heap?_comp）））
		{
			break;
		}
		else
		{
			omnode?=?（struct?map_node*）onode->value;
			if?（is_arrived（tmap?omnode））
					break;
			Bheap_push（c_heap?onode?_comp）;
			
			/*上*/
			fx?=?omnode->x;
			fy?=?omnode->y?-?1;
			if?（is_reachable（tmap?fx?fy））
			{
				if（1?==?deal_child（tmap?o_heap?c_heap?fx?fy
																		?omnode?distance?end_x?end_y））
					continue;
			}
			/*右上*/
			fx?=?omnode->x?+?1;
			fy?=?omnode->y?-?1;
			if?（is_reachable（tmap?fx?fy））
			{	
				if（1?==?deal_child（tmap?o_heap?c_heap?fx?fy
																		?omnode?distance?end_x?end_y））
					continue;
			}
			
			/*右*/
			fx?=?omnode->x?+?1;
			fy?=?omnode->y;
			if?（is_reachable（tmap?fx?fy））
			{
				if（1?==?deal_child（tmap?o_heap?c_heap?fx?fy
																		?omnode?distance?end_x?end_y））
					

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????9800??2012-12-18?08:46??astar實現代碼（c）\Astar.c
?????文件????????1336??2012-12-18?08:39??astar實現代碼（c）\Astar.h
?????文件?????????228??2012-12-05?05:42??astar實現代碼（c）\Makefile
?????文件????????6779??2012-12-05?05:42??astar實現代碼（c）\bheap.h
?????文件????????1745??2012-12-19?10:40??astar實現代碼（c）\slist.h
?????目錄???????????0??2012-12-19?10:41??astar實現代碼（c）\