astararray.cpp

一个VC写A*寻路的程序库

	LARGE_INTEGER tmp1;
	QueryPerformanceCounter(&tmp1);
	
	//
	for(int y=0;y<HEIGHT;y++)
	{
		for(int x=0;x<WIDTH;x++)
		{
			world[(y<<YSHIFT)+x].terrain_cost=vSetup->world[y][x].terrain_cost;
		}
	}
	
	//
	LARGE_INTEGER tmp2;
	QueryPerformanceCounter(&tmp2);
	bigtick.QuadPart += tmp2.QuadPart - tmp1.QuadPart;
}

// this transfers the all the settings in Setup.cpp to here.
void AStarArray::UpdateSettings()
{
	startyx=vSetup->starty*WIDTH+vSetup->startx;
	endyx=vSetup->endy*WIDTH+vSetup->endx;
	
	use_terrain=vSetup->use_terrain;
	distance_method=vSetup->distance_method;
	iterations_per_frame=vSetup->iterations_per_frame;
	directions=vSetup->directions;

	float cost=vSetup->cost;
	float diagonal_cost=vSetup->diagonal_cost;
	float median_terrain_cost=vSetup->median_terrain_cost;
	
	int n;
	if(use_terrain)
	{
		for(n=0;n<4;n++)
		{
			DXY[n].cost_multiplier=median_terrain_cost;
		}
			for(n=4;n<8;n++)
			{
				DXY[n].cost_multiplier=diagonal_cost*median_terrain_cost;
			}
	}
	else
	{
		for(n=0;n<4;n++)
		{
			DXY[n].cost_multiplier=1.0f*cost;
		}
			for(n=4;n<8;n++)
			{
				DXY[n].cost_multiplier=diagonal_cost*cost;
			}
	}
}



///////////////////////////////////////////////////////////////////////////
// TYPE B
void AStarArray::PackRoute()
{
	if(no_path)
	{
		airoute->count=0;
		return;
	}

	//
	memset(airoute->route,0,MAX_ROUTES); //clear routes

	//
	airoute->active=1;
	airoute->compression=0;

	//
	WORD yx=endyx;
	int start=MAX_ROUTES-1;
	BYTE route=NO_ROUTE;
	while(yx!=startyx)
	{
//		route=DXY[world[yx].route].route;
		route=world[yx].route;
		yx+=DXY[DXY[route].route].yx;
		airoute->route[start]=route;
		if(--start<0) start=MAX_ROUTES-1;
	};
	
	airoute->start=start+1;
	airoute->count=MAX_ROUTES-airoute->start;
	
	//
	airoute->startyx=startyx;
	airoute->endyx=endyx;
	
	//
	airoute->walk_point=airoute->start;
	airoute->walk_runlength_step=0;
	
	//     
	if(airoute->start==0) airoute->count=0;
}






///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
/*
This is the function that paints the graphics to the screen.
Called by PathFinder.
Localized to respective Setup classes v1.6.
*/
//
void AStarArray::Paint(LPBYTE pwBits, HDC hdc,HWND hWnd)
{
	if(pwBits)
	{
		//
		RECT rt;
		GetClientRect(hWnd, &rt);
		int clientwidth = (rt.right-rt.left);
		
		COLORREF background;
		COLORREF foreground;
		vSetup->get_colorscheme_colors(background,foreground);
		HBRUSH hbrBkGnd = CreateSolidBrush(background);
		FillRect(hdc, &rt, hbrBkGnd);
		DeleteObject(hbrBkGnd);
		SetBkColor(hdc,background);
		SetTextColor(hdc,foreground);
		
		//
		TCHAR szStatusLine[1024];
		_RGBA *p,*ppush;
		_RGBA  *pbegin=(_RGBA *)pwBits;
		register _RGBA *tmp;
		int yx;
		int y,x;
		int n;
		
		//
		float smallest_f, smallest_g, smallest_h;
		float largest_f, largest_g, largest_h;
		smallest_f = smallest_g = smallest_h = 1048576.0f;
		largest_f = largest_g = largest_h = 0.0001f;
		for(int node=1;node<=last_node;node++)
		{
			if(nodes[node].f>largest_f) largest_f=nodes[node].f;
			if(nodes[node].f<smallest_f) smallest_f=nodes[node].f;
			if(nodes[node].g>largest_g) largest_g=nodes[node].g;
			if(nodes[node].g<smallest_g) smallest_g=nodes[node].g;
			if(nodes[node].h>largest_h) largest_h=nodes[node].h;
			if(nodes[node].h<smallest_h) smallest_h=nodes[node].h;
		}
		
		//
		int count=0;
		int tmpnode=current_node;
		while(tmpnode!=EMPTY_NODE)
		{
			tmpnode=nodes[tmpnode].ancestor;
			count++;
		}
		
		
		// statistics
		GetClientRect(hWnd, &rt);
		sprintf(szStatusLine,
			"-- A* Array (v1) --\nf %f ... %f\ng %f ... %f\nh %f ... %f\n\nNodes %d (MAX %d)\nCurrent Node %d\nLast Open Node %d\nLast Index %d\n\npath found? %s\nlength= %d\n\nstart -> current\nf %f -> %f\ng %f -> %f\nh %f -> %f\n%s\n",
			smallest_f, largest_f,
			smallest_g, largest_g,
			smallest_h, largest_h,
			last_node,
			MAX_NODES,
			current_node,
			open_nodes,
			last_index,
			no_path?"NO PATH!":(path_found?"YES!":"Not yet..."),
			count,
			nodes[1].f,nodes[current_node].f,
			nodes[1].g,nodes[current_node].g,
			nodes[1].h,nodes[current_node].h,
			(nodes[current_node].f<=nodes[1].f)?"ADMISSIBLE":"not admissible"
			);
		DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_RIGHT);
		
		
		// composite
		GetClientRect(hWnd, &rt);
		rt.top=HEIGHT;
		rt.right=WIDTH;
		sprintf(szStatusLine,"shortest path");
		DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
		p=ppush=pbegin;
		for(y=0;y<HEIGHT;y++)
		{
			for(x=0;x<WIDTH;x++)
			{
				yx=(y<<YSHIFT)+x;
				BYTE b=(BYTE)(255-(world[yx].terrain_cost<<4));
				p->red=b; p->green=b; p->blue=b;
				p++;
			}
			ppush+=clientwidth;
			p=ppush;
		}
		p=pbegin;
		for(y=-1;y<=1;y++)
		{
			for(x=-1;x<=1;x++)
			{
				tmp=(p+((startyx>>YSHIFT)+y)*clientwidth+(startyx&XMASK)+x);
				tmp->red=255;
				tmp->green=0;
				tmp->blue=0;
			}
		}
		for(y=-1;y<=1;y++)
		{
			for(x=-1;x<=1;x++)
			{
				tmp=(p+((endyx>>YSHIFT)+y)*clientwidth+(endyx&XMASK)+x);
				tmp->red=0;
				tmp->green=255;
				tmp->blue=0;
			}
		}
		p=pbegin;
		node=current_node;
		while(node!=EMPTY_NODE)
		{
			tmp=(p+(nodes[node].yx>>YSHIFT)*clientwidth+(nodes[node].yx&XMASK));
			tmp->red=255;
			tmp->green=0;
			tmp->blue=0;
			node=nodes[node].ancestor;
		}
		
		
		// f
		GetClientRect(hWnd, &rt);
		rt.top=HEIGHT;
		rt.left=WIDTH+4;
		rt.right=WIDTH+4+WIDTH;
		sprintf(szStatusLine,"f (red closed/blue open)");
		DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
		p=pbegin+WIDTH+4;
		for(n=1;n<=last_node;n++)
		{
			if(nodes[n].open)
			{
				tmp=(p+(nodes[n].yx>>YSHIFT)*clientwidth+(nodes[n].yx&XMASK));
				BYTE f=(BYTE)(((float)nodes[n].f/(float)largest_f)*255.0f);
				tmp->red=0;
				tmp->green=0;
				tmp->blue=f;
			}
		}
		for(n=1;n<=last_node;n++)
		{
			if(!nodes[n].open)
			{
				tmp=(p+(nodes[n].yx>>YSHIFT)*clientwidth+(nodes[n].yx&XMASK));
				BYTE f=(BYTE)(((float)nodes[n].f/(float)largest_f)*255.0f);
				tmp->red=f;
				tmp->green=0;
				tmp->blue=0;
			}
		}
		
		
		// open
		GetClientRect(hWnd, &rt);
		rt.top=HEIGHT*2+16;
		rt.left=0;
		rt.right=WIDTH;
		sprintf(szStatusLine,"open nodes %d",open_nodes);
		DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
		p=pbegin+(HEIGHT+16)*clientwidth;
		for(n=1;n<=last_node;n++)
		{
			if(nodes[n].open)
			{
				BYTE g=(BYTE)(((float)nodes[n].g/(float)largest_g)*255.0f);
				BYTE h=(BYTE)(((float)nodes[n].h/(float)largest_h)*255.0f);
				BYTE f=(BYTE)(((float)nodes[n].f/(float)largest_f)*255.0f);
				tmp=(p+(nodes[n].yx>>YSHIFT)*clientwidth+(nodes[n].yx&XMASK));
				tmp->red=h;
				tmp->green=g;
				tmp->blue=f;
			}
		}
		
		
		// closed
		GetClientRect(hWnd, &rt);
		rt.top=HEIGHT*2+16;
		rt.left=WIDTH+4;
		rt.right=WIDTH+4+WIDTH;
		sprintf(szStatusLine,"closed nodes %d",closed_nodes);
		DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
		p=pbegin+WIDTH+4+(HEIGHT+16)*clientwidth;
		for(n=1;n<=last_node;n++)
		{
			if(!nodes[n].open)
			{
				BYTE g=(BYTE)(((float)nodes[n].g/(float)largest_g)*255.0f);
				BYTE h=(BYTE)(((float)nodes[n].h/(float)largest_h)*255.0f);
				BYTE f=(BYTE)(((float)nodes[n].f/(float)largest_f)*255.0f);
				tmp=(p+(nodes[n].yx>>YSHIFT)*clientwidth+(nodes[n].yx&XMASK));
				tmp->red=h;
				tmp->green=g;
				tmp->blue=f;
			}
		}
		
	
		// successors
		GetClientRect(hWnd, &rt);
		rt.top=HEIGHT*2+16;
		rt.left=(WIDTH+4)*2;
		rt.right=(WIDTH+4)*2+WIDTH;
		sprintf(szStatusLine,"successors");
		DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
		p=pbegin+(WIDTH+4)*2+(HEIGHT+16)*clientwidth;
		int diff=(directions==8)?31:63;
		for(node=1;node<=last_node;node++)
		{
			int successors=0;
			for(int i=0;i<directions;i++)
			{
				if(nodes[node].successor[i]!=EMPTY_NODE)
					successors+=diff;
			}
			tmp=(p+(nodes[node].yx>>YSHIFT)*clientwidth+(nodes[node].yx&XMASK));
			tmp->red=(BYTE)successors;
			tmp->green=0;
			tmp->blue=0;
		}
	}
	
}