astar实现代码（c）

Astar 最短路径寻优的代码实现，使用的是C语言

/*
 * 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）\