development.cpp

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

	LARGE_INTEGER tmp1;
	QueryPerformanceCounter(&tmp1);
	
	//
	for(int y=0;y<HEIGHT;y++)
	{
		for(int x=0;x<WIDTH;x++)
		{
			WORD yx=(y<<YSHIFT)+x;
			world[yx].u.state.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 Development::UpdateSettings()
{
	startyx=vSetup->starty*WIDTH+vSetup->startx;
	endyx=vSetup->endy*WIDTH+vSetup->endx;
	
	endx=endyx&XMASK;
	endy=(endyx>>YSHIFT);
	
	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;
	
	//note: fix me somehow to handle diags
	if(use_terrain)
	{
		for(n=0;n<4;n++)
		{
			DXY[n].cost_multiplier=(WORD)median_terrain_cost;
		}
		if(directions==8)
		{
			for(n=4;n<8;n++)
			{
				DXY[n].cost_multiplier=(WORD)(diagonal_cost*median_terrain_cost);
			}
		}
	}
	else
	{
		for(n=0;n<4;n++)
		{
			DXY[n].cost_multiplier=(WORD)cost;
		}
		if(directions==8)
		{
			for(n=4;n<8;n++)
			{
				DXY[n].cost_multiplier=(WORD)(diagonal_cost*cost);
			}
		}
	}
}



///////////////////////////////////////////////////////////////////////////
// TYPE B
void Development::PackRoute()
{
	if(pathing_state&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].u.state.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 Development::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);
		
		//
		int starty=startyx>>YSHIFT;
		int startx=startyx&XMASK;
		int endy=endyx>>YSHIFT;
		int endx=endyx&XMASK;
		
		TCHAR szStatusLine[1024];
		_RGBA *p,*ppush;
		_RGBA *pbegin=(_RGBA *)pwBits;
		const int yxmax=WIDTH*HEIGHT;
		int y,x;
		int yx;
		int n;
		register _RGBA *tmp;
		
		//
		int used_nodes=0;
		WORD smallest_f, smallest_g, smallest_h;
		WORD largest_f, largest_g, largest_h;
		smallest_f = smallest_g = smallest_h = 0xffff; //1048576.0f;
		largest_f = largest_g = largest_h = 1; //0.0001f;
		for(n=1;n<=last_heap_leaf;n++)
		{
			if(heap[n].f>largest_f) largest_f=heap[n].f;
			if(heap[n].f<smallest_f) smallest_f=heap[n].f;
			
			if(heap[n].g>largest_g) largest_g=heap[n].g;
			if(heap[n].g<smallest_g) smallest_g=heap[n].g;
			
			WORD h=heap[n].f-heap[n].g;
			if(h>largest_h) largest_h=h;
			if(h<smallest_h) smallest_h=h;
			
			used_nodes++;
		}
		
		//
		int length=0;
		p=pbegin;
		yx=heap[ROOT_HEAP].node;
		while(yx!=startyx && yx>0 && yx<yxmax)
		{
			yx+=DXY[DXY[world[yx].u.state.route].route].yx;
			length++;
			if(length>MAX_NODE) break;
		}

		
		
		// stats
		GetClientRect(hWnd, &rt);
		sprintf(szStatusLine,
			"-- Development --\nf %d ... %d\ng %d ... %d\nh %d ... %d\n\nstruct size %d bytes\n(heap %d B)\n(world %d B)\n[used heap %d B]\nMAX world %d\n\nBest Node %4d\nf %d\ng %d\nh %d\n\npath found? %s\nlength= %d\n",
			smallest_f,
			largest_f,
			smallest_g,
			largest_g,
			smallest_h,
			largest_h,
			sizeof(world) + sizeof(heap),
			sizeof(heap),
			sizeof(world),
			last_heap_leaf*(sizeof(WORD)),
			MAX_NODE,
			heap[ROOT_HEAP].node,
			heap[ROOT_HEAP].f,
			heap[ROOT_HEAP].g,
			heap[ROOT_HEAP].f-heap[ROOT_HEAP].g,
			pathing_state&NO_PATH?"NO PATH!":(pathing_state&PATH_FOUND?"YES!":"Not yet..."),
			length
			);
		DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_RIGHT);
		
		
		//shortest-path w/ terrain
		GetClientRect(hWnd, &rt);
		rt.top=HEIGHT;
		rt.right=WIDTH;
		sprintf(szStatusLine,"shortest path w/terrain");
		DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
		p=ppush=pbegin;
		for(y=0;y<HEIGHT;y++)
		{
			for(x=0;x<WIDTH;x++)
			{
				BYTE b=(BYTE)(255-(world[y*WIDTH+x].u.state.terrain_cost<<4));
				p->red=b; p->green=b; p->blue=b;
				p++;
			}
			ppush+=clientwidth;
			p=ppush;
		}
		for(y=-1;y<=1;y++) //starting point
		{
			for(x=-1;x<=1;x++)
			{
				tmp=(pbegin+(starty+y)*clientwidth+startx+x);
				tmp->red=255;
				tmp->green=0;
				tmp->blue=0;
			}
		}
		for(y=-1;y<=1;y++) //end/goal point
		{
			for(x=-1;x<=1;x++)
			{
				tmp=(pbegin+(endy+y)*clientwidth+endx+x);
				tmp->red=0;
				tmp->green=255;
				tmp->blue=0;
			}
		}
		p=pbegin;
		yx=closed_yx;
		while(yx!=startyx && yx>0 && yx<yxmax)
		{
			tmp=(p+(yx>>YSHIFT)*clientwidth+(yx&XMASK));
			tmp->red=255;
			tmp->green=0;
			tmp->blue=0;
			yx+=DXY[DXY[world[yx].u.state.route].route].yx;
			if(length>MAX_NODE) break;
		}
		
		
		// open
		int levels=0;
		{
			int b=1;
			int sum=b;
			while(b<=last_heap_leaf)
			{
				b=b<<1;
				sum+=b;
				levels++;
			}
		}
		GetClientRect(hWnd, &rt);
		rt.top=HEIGHT*2+16;
		rt.left=0;
		rt.right=WIDTH;
		sprintf(szStatusLine,"open %d (%d heap levels)",last_heap_leaf,levels);
		DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
		rt.top+=16;
		sprintf(szStatusLine,"f=blue g=green h=red");
		DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
		p=pbegin+(HEIGHT+16)*clientwidth;
		for(n=1;n<=last_heap_leaf;n++)
		{
			WORD node=heap[n].node;
			
			BYTE f=(BYTE)(((float)heap[n].f/(float)largest_f)*255.0f);
			BYTE g=(BYTE)(((float)heap[n].g/(float)largest_g)*255.0f);
			BYTE h=(BYTE)(((float)(heap[n].f-heap[n].g)/(float)largest_h)*255.0f);
			tmp=(p+(node>>YSHIFT)*clientwidth+(node&XMASK));
			tmp->red=h;
			tmp->green=g;
			tmp->blue=f;
		}
		
		
		// visited
		GetClientRect(hWnd, &rt);
		rt.top=HEIGHT;
		rt.left=(WIDTH+4)*2;
		rt.right=(WIDTH+4)*2+WIDTH;
		sprintf(szStatusLine,"visited (green) / impassable (red)");
		DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
		p=pbegin+(WIDTH+4)*2;
		for(y=0;y<HEIGHT;y++)
		{
			for(x=0;x<WIDTH;x++)
			{
				yx=y*WIDTH+x;
				tmp=(p+y*clientwidth+x);
				tmp->green=(BYTE)((world[yx].u.state.visited)?255:0);
				tmp->blue=0;
				tmp->red=(BYTE)((world[yx].u.state.terrain_cost==IMPASSABLE_TERRAIN_COST)?255:0);
			}
		}
		
		
		//routing
		GetClientRect(hWnd, &rt);
		rt.top=HEIGHT*2+16;
		rt.left=(WIDTH+4)*2;
		rt.right=(WIDTH+4)*2+WIDTH;
		sprintf(szStatusLine,"routes");
		DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
		p=pbegin+(WIDTH+4)*2+(HEIGHT+16)*clientwidth;
		for(y=0;y<HEIGHT;y++)
		{
			for(x=0;x<WIDTH;x++)
			{
				tmp=(p+y*clientwidth+x);
				switch(world[(y<<YSHIFT)+x].u.state.route)
				{
				case 0: tmp->red=0;		tmp->green=0;	tmp->blue=255;	break; // n
				case 1: tmp->red=127;	tmp->green=0;	tmp->blue=255;	break; // e
				case 2: tmp->red=255;	tmp->green=0;	tmp->blue=0;	break; // s
				case 3: tmp->red=255;	tmp->green=0;	tmp->blue=127;	break; // w pink
				case 4: tmp->red=0;		tmp->green=255;	tmp->blue=255;	break; // ne
				case 5: tmp->red=127;	tmp->green=255;	tmp->blue=255;	break; // se
				case 6: tmp->red=255;	tmp->green=255;	tmp->blue=0;	break; // sw
				case 7: tmp->red=255;	tmp->green=255;	tmp->blue=127;	break; // nw
				};
			}
		}
	}
}