generic.cpp

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

// Generic.cpp: implementation of the Generic class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Generic.h"

#include "stdio.h" //for sprintf


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Generic::Generic()
{
	Alg=NONE_ALGORITHM;
}

Generic::~Generic()
{
	delete vDevelopment;
	delete vAStar;
	delete vAStarHeapInteger;
	delete vAStarHeap;
	delete vAStarComplete;
	delete vDijkstra;
	delete vAStarArray;
	delete vAStarLinkedList;
	delete vBreadthFirst;
	delete vBestFirst;
	delete vDepthFirst;
}

Generic::Generic(Setup *vSetup)
{
	this->vSetup=vSetup;
	this->Alg=ASTAR_ALGORITHM;
	
	//
	for(int a=0;a<MAX_AIS;a++)
	{
		_AIROUTE *airoute=&AIRoute[a];
		airoute->color=((rand()%0xff)<<16) + ((rand()%0xff)<<8) + (rand()%0xff);
		airoute->count=0;
		airoute->priority=0;
		airoute->active=1;
		airoute->startyx=(rand()%(WIDTH-4)+2) +  ((rand()%(HEIGHT-4)+2)<<YSHIFT); 
		airoute->endyx=(rand()%(WIDTH-4)+2) +  ((rand()%(HEIGHT-4)+2)<<YSHIFT); 
	}

	//
	ai=0;
	
	//
	vDevelopment=new Development(vSetup,&AIRoute[0]);
	vAStar=new AStar(vSetup,&AIRoute[0]);
	vAStarHeapInteger=new AStarHeapInteger(vSetup,&AIRoute[0]);
	vAStarHeap=new AStarHeap(vSetup,&AIRoute[0]);
	vAStarComplete=new AStarComplete(vSetup,&AIRoute[0]);
	vDijkstra=new Dijkstra(vSetup,&AIRoute[0]);
	vAStarArray=new AStarArray(vSetup,&AIRoute[0]);
	vAStarLinkedList=new AStarLinkedList(vSetup,&AIRoute[0]);
	vBreadthFirst=new BreadthFirst(vSetup,&AIRoute[0]);
	vBestFirst=new BestFirst(vSetup,&AIRoute[0]);
	vDepthFirst=new DepthFirst(vSetup,&AIRoute[0]);
	
	//
	bigtick.QuadPart=0;

	//
	gamemode=false;
	routing_view=false;
	
	// make the routing lookup table
	DXY[0].yx=-WIDTH;	DXY[0].route=2;
	DXY[1].yx=1;		DXY[1].route=3;
	DXY[2].yx=WIDTH;	DXY[2].route=0;
	DXY[3].yx=-1;		DXY[3].route=1;
	
	DXY[4].yx=-WIDTH+1;	DXY[4].route=6;
	DXY[5].yx=WIDTH+1;	DXY[5].route=7;
	DXY[6].yx=WIDTH-1;	DXY[6].route=4;
	DXY[7].yx=-WIDTH-1;	DXY[7].route=5;
	
	//in case a NO_ROUTE accidentally is passed for lookup
	DXY[8].yx=0;		DXY[8].route=0;
}




// ////////////////////////////////////////////////////////////////////////
// ////////////////////////////////////////////////////////////////////////
// ////////////////////////////////////////////////////////////////////////
void Generic::Reset()
{
	//
	switch(Alg)
	{
	case DEVELOPMENT_ALGORITHM:			vDevelopment->Reset(&AIRoute[ai]); break;
	case ASTAR_ALGORITHM:				vAStar->Reset(&AIRoute[ai]); break;
	case ASTAR_HEAPINTEGER_ALGORITHM:	vAStarHeapInteger->Reset(&AIRoute[ai]); break;
	case ASTAR_HEAP_ALGORITHM:			vAStarHeap->Reset(&AIRoute[ai]); break;
	case ASTAR_COMPLETE_ALGORITHM:		vAStarComplete->Reset(&AIRoute[ai]); break;
	case DIJKSTRA_ALGORITHM:			vDijkstra->Reset(&AIRoute[ai]); break;
	case ASTAR_ARRAY_ALGORITHM:			vAStarArray->Reset(&AIRoute[ai]); break;
	case ASTAR_LINKEDLIST_ALGORITHM:	vAStarLinkedList->Reset(&AIRoute[ai]); break;
	case BREADTHFIRST_ALGORITHM:		vBreadthFirst->Reset(&AIRoute[ai]); break;
	case BESTFIRST_ALGORITHM:			vBestFirst->Reset(&AIRoute[ai]); break;
	case DEPTHFIRST_ALGORITHM:			vDepthFirst->Reset(&AIRoute[ai]); break;
	}
}

void Generic::UpdateWorld()
{
	switch(Alg)
	{
	case DEVELOPMENT_ALGORITHM:			vDevelopment->UpdateWorld(); break;
	case ASTAR_ALGORITHM:				vAStar->UpdateWorld(); break;
	case ASTAR_HEAPINTEGER_ALGORITHM:	vAStarHeapInteger->UpdateWorld(); break;
	case ASTAR_HEAP_ALGORITHM:			vAStarHeap->UpdateWorld(); break;
	case ASTAR_COMPLETE_ALGORITHM:		vAStarComplete->UpdateWorld(); break;
	case DIJKSTRA_ALGORITHM:			vDijkstra->UpdateWorld(); break;
	case ASTAR_ARRAY_ALGORITHM:			vAStarArray->UpdateWorld(); break;
	case ASTAR_LINKEDLIST_ALGORITHM:	vAStarLinkedList->UpdateWorld(); break;
	case BREADTHFIRST_ALGORITHM:		vBreadthFirst->UpdateWorld(); break;
	case BESTFIRST_ALGORITHM:			vBestFirst->UpdateWorld(); break;
	case DEPTHFIRST_ALGORITHM:			vDepthFirst->UpdateWorld(); break;
	}
	//
	bigtick.QuadPart=0;
}

void Generic::UpdateSettings()
{
	switch(Alg)
	{
	case DEVELOPMENT_ALGORITHM:			vDevelopment->UpdateSettings(); break;
	case ASTAR_ALGORITHM:				vAStar->UpdateSettings(); break;
	case ASTAR_HEAPINTEGER_ALGORITHM:	vAStarHeapInteger->UpdateSettings(); break;
	case ASTAR_HEAP_ALGORITHM:			vAStarHeap->UpdateSettings(); break;
	case ASTAR_COMPLETE_ALGORITHM:		vAStarComplete->UpdateSettings(); break;
	case DIJKSTRA_ALGORITHM:			vDijkstra->UpdateSettings(); break;
	case ASTAR_ARRAY_ALGORITHM:			vAStarArray->UpdateSettings(); break;
	case ASTAR_LINKEDLIST_ALGORITHM:	vAStarLinkedList->UpdateSettings(); break;
	case BREADTHFIRST_ALGORITHM:		vBreadthFirst->UpdateSettings(); break;
	case BESTFIRST_ALGORITHM:			vBestFirst->UpdateSettings(); break;
	case DEPTHFIRST_ALGORITHM:			vDepthFirst->UpdateSettings(); break;
	}
}

void Generic::GetOptions()
{
	switch(Alg)
	{
	case DEVELOPMENT_ALGORITHM:			vDevelopment->GetOptions(); break;
	case ASTAR_ALGORITHM:				vAStar->GetOptions(); break;
	case ASTAR_HEAPINTEGER_ALGORITHM:	vAStarHeapInteger->GetOptions(); break;
	case ASTAR_HEAP_ALGORITHM:			vAStarHeap->GetOptions(); break;
	case ASTAR_COMPLETE_ALGORITHM:		vAStarComplete->GetOptions(); break;
	case DIJKSTRA_ALGORITHM:			vDijkstra->GetOptions(); break;
	case ASTAR_ARRAY_ALGORITHM:			vAStarArray->GetOptions(); break;
	case ASTAR_LINKEDLIST_ALGORITHM:	vAStarLinkedList->GetOptions(); break;
	case BREADTHFIRST_ALGORITHM:		vBreadthFirst->GetOptions(); break;
	case BESTFIRST_ALGORITHM:			vBestFirst->GetOptions(); break;
	case DEPTHFIRST_ALGORITHM:			vDepthFirst->GetOptions(); break;
	}
}



///////////////////////////////////////////////////////////////////////////
void Generic::Paint(LPBYTE pwBits,HDC hdctmp,HWND hWnd)
{
	if(routing_view)
		Paint_All(pwBits,hdctmp,hWnd);
	else
	{
		switch(Alg)
		{
		case DEVELOPMENT_ALGORITHM:			vDevelopment->Paint(pwBits,hdctmp,hWnd); break;
		case ASTAR_ALGORITHM:				vAStar->Paint(pwBits,hdctmp,hWnd); break;
		case ASTAR_HEAPINTEGER_ALGORITHM:	vAStarHeapInteger->Paint(pwBits,hdctmp,hWnd); break;
		case ASTAR_HEAP_ALGORITHM:			vAStarHeap->Paint(pwBits,hdctmp,hWnd); break;
		case ASTAR_COMPLETE_ALGORITHM:		vAStarComplete->Paint(pwBits,hdctmp,hWnd); break;
		case DIJKSTRA_ALGORITHM:			vDijkstra->Paint(pwBits,hdctmp,hWnd); break;
		case ASTAR_ARRAY_ALGORITHM:			vAStarArray->Paint(pwBits,hdctmp,hWnd); break;
		case ASTAR_LINKEDLIST_ALGORITHM:	vAStarLinkedList->Paint(pwBits,hdctmp,hWnd); break;
		case BREADTHFIRST_ALGORITHM:		vBreadthFirst->Paint(pwBits,hdctmp,hWnd); break;
		case BESTFIRST_ALGORITHM:			vBestFirst->Paint(pwBits,hdctmp,hWnd); break;
		case DEPTHFIRST_ALGORITHM:			vDepthFirst->Paint(pwBits,hdctmp,hWnd); break;
		}
	}
}

bool Generic::PathFound()
{
	switch(Alg)
	{
	case DEVELOPMENT_ALGORITHM:			return vDevelopment->path_found; break;
	case ASTAR_ALGORITHM:				return vAStar->path_found; break;
	case ASTAR_HEAPINTEGER_ALGORITHM:	return vAStarHeapInteger->path_found; break;
	case ASTAR_HEAP_ALGORITHM:			return vAStarHeap->path_found; break;
	case ASTAR_COMPLETE_ALGORITHM:		return vAStarComplete->path_found; break;
	case DIJKSTRA_ALGORITHM:			return vDijkstra->path_found; break;
	case ASTAR_ARRAY_ALGORITHM:			return vAStarArray->path_found; break;
	case ASTAR_LINKEDLIST_ALGORITHM:	return vAStarLinkedList->path_found; break;
	case BREADTHFIRST_ALGORITHM:		return vBreadthFirst->path_found; break;
	case BESTFIRST_ALGORITHM:			return vBestFirst->path_found; break;
	case DEPTHFIRST_ALGORITHM:			return vDepthFirst->path_found; break;
	}
	return false;
}

bool Generic::NoPath()
{
	switch(Alg)
	{
	case DEVELOPMENT_ALGORITHM:			return vDevelopment->no_path; break;
	case ASTAR_ALGORITHM:				return vAStar->no_path; break;
	case ASTAR_HEAPINTEGER_ALGORITHM:	return vAStarHeapInteger->no_path; break;
	case ASTAR_HEAP_ALGORITHM:			return vAStarHeap->no_path; break;
	case ASTAR_COMPLETE_ALGORITHM:		return vAStarComplete->no_path; break;
	case DIJKSTRA_ALGORITHM:			return vDijkstra->no_path; break;
	case ASTAR_ARRAY_ALGORITHM:			return vAStarArray->no_path; break;
	case ASTAR_LINKEDLIST_ALGORITHM:	return vAStarLinkedList->no_path; break;
	case BREADTHFIRST_ALGORITHM:		return vBreadthFirst->no_path; break;
	case BESTFIRST_ALGORITHM:			return vBestFirst->no_path; break;
	case DEPTHFIRST_ALGORITHM:			return vDepthFirst->no_path; break;
	}
	return false;
}


//
void Generic::ResetAI()
{
	if(gamemode) bigtick.QuadPart=0;
	ai=0;
}

//
bool Generic::isDone()
{
	if(gamemode)
		return (ai>=MAX_AIS);
	else
		return (PathFound() || NoPath());
}


//
void Generic::FindPath()
{
	if(!isDone())
	{
		//
		switch(Alg)
		{
		case DEVELOPMENT_ALGORITHM:			vDevelopment->FindPath(); break;
		case ASTAR_ALGORITHM:				vAStar->FindPath(); break;
		case ASTAR_HEAPINTEGER_ALGORITHM:	vAStarHeapInteger->FindPath(); break;
		case ASTAR_HEAP_ALGORITHM:			vAStarHeap->FindPath(); break;
		case ASTAR_COMPLETE_ALGORITHM:		vAStarComplete->FindPath(); break;
		case DIJKSTRA_ALGORITHM:			vDijkstra->FindPath(); break;
		case ASTAR_ARRAY_ALGORITHM:			vAStarArray->FindPath(); break;
		case ASTAR_LINKEDLIST_ALGORITHM:	vAStarLinkedList->FindPath(); break;
		case BREADTHFIRST_ALGORITHM:		vBreadthFirst->FindPath(); break;
		case BESTFIRST_ALGORITHM:			vBestFirst->FindPath(); break;
		case DEPTHFIRST_ALGORITHM:			vDepthFirst->FindPath(); break;
		}
		
		//
		if(!gamemode)
		{
			if(PathFound() || NoPath())
			{
				LARGE_INTEGER tick;
				switch(Alg)
				{
				case DEVELOPMENT_ALGORITHM:			tick.QuadPart=vDevelopment->bigtick.QuadPart; break;
				case ASTAR_ALGORITHM:				tick.QuadPart=vAStar->bigtick.QuadPart; break;
				case ASTAR_HEAPINTEGER_ALGORITHM:	tick.QuadPart=vAStarHeapInteger->bigtick.QuadPart; break;
				case ASTAR_HEAP_ALGORITHM:			tick.QuadPart=vAStarHeap->bigtick.QuadPart; break;
				case ASTAR_COMPLETE_ALGORITHM:		tick.QuadPart=vAStarComplete->bigtick.QuadPart; break;
				case DIJKSTRA_ALGORITHM:			tick.QuadPart=vDijkstra->bigtick.QuadPart; break;
				case ASTAR_ARRAY_ALGORITHM:			tick.QuadPart=vAStarArray->bigtick.QuadPart; break;
				case ASTAR_LINKEDLIST_ALGORITHM:	tick.QuadPart=vAStarLinkedList->bigtick.QuadPart; break;
				case BREADTHFIRST_ALGORITHM:		tick.QuadPart=vBreadthFirst->bigtick.QuadPart; break;
				case BESTFIRST_ALGORITHM:			tick.QuadPart=vBestFirst->bigtick.QuadPart; break;
				case DEPTHFIRST_ALGORITHM:			tick.QuadPart=vDepthFirst->bigtick.QuadPart; break;
				default: tick.QuadPart=0;
				}
				if(bigtick.QuadPart==0.0)
					bigtick.QuadPart=tick.QuadPart;
				else if(tick.QuadPart<bigtick.QuadPart)
					bigtick.QuadPart=tick.QuadPart;
			}
		}
		else
		{
			if(ai<MAX_AIS && (PathFound() || NoPath()) )
			{
				//
				switch(Alg)
				{
				case DEVELOPMENT_ALGORITHM:			bigtick.QuadPart+=vDevelopment->bigtick.QuadPart; break;
				case ASTAR_ALGORITHM:				bigtick.QuadPart+=vAStar->bigtick.QuadPart; break;
				case ASTAR_HEAPINTEGER_ALGORITHM:	bigtick.QuadPart+=vAStarHeapInteger->bigtick.QuadPart; break;
				case ASTAR_HEAP_ALGORITHM:			bigtick.QuadPart+=vAStarHeap->bigtick.QuadPart; break;
				case ASTAR_COMPLETE_ALGORITHM:		bigtick.QuadPart+=vAStarComplete->bigtick.QuadPart; break;
				case DIJKSTRA_ALGORITHM:			bigtick.QuadPart+=vDijkstra->bigtick.QuadPart; break;
				case ASTAR_ARRAY_ALGORITHM:			bigtick.QuadPart+=vAStarArray->bigtick.QuadPart; break;
				case ASTAR_LINKEDLIST_ALGORITHM:	bigtick.QuadPart+=vAStarLinkedList->bigtick.QuadPart; break;
				case BREADTHFIRST_ALGORITHM:		bigtick.QuadPart+=vBreadthFirst->bigtick.QuadPart; break;
				case BESTFIRST_ALGORITHM:			bigtick.QuadPart+=vBestFirst->bigtick.QuadPart; break;
				case DEPTHFIRST_ALGORITHM:			bigtick.QuadPart+=vDepthFirst->bigtick.QuadPart; break;
				}
				
				//
				ai++;
				if(ai<MAX_AIS)
				{
					vSetup->set_start(AIRoute[ai].startyx>>YSHIFT,AIRoute[ai].startyx&XMASK);
					vSetup->set_end(AIRoute[ai].endyx>>YSHIFT,AIRoute[ai].endyx&XMASK);
					UpdateSettings();
					Reset();
				}
			}
		}
	}
}


///////////////////////////////////////////////////////////////////////////
void Generic::Switch_Algorithms(int Alg)
{
	this->Alg=Alg;
	
	GetOptions();
	UpdateSettings();
	UpdateWorld();
	Reset();
}


///////////////////////////////////////////////////////////////////////////
void Generic::set_GameMode(bool state)
{
	gamemode=state;
	
	GetOptions();
	UpdateSettings();
	UpdateWorld();
	Reset();
}





///////////////////////////////////////////////////////////////////////////

//
void Generic::Paint_All(LPBYTE pwBits, HDC hdc,HWND hWnd)
{
	if(pwBits)
	{
		//
		RECT rt;
		GetClientRect(hWnd, &rt);
		int clientwidth = (rt.right-rt.left);
		int clientheight = (rt.bottom-rt.top);
		
		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);
		
		//
		_RGBA *pbegin=(_RGBA *)pwBits+(clientwidth>>1)-(WIDTH)+ ((clientheight>>1)-(HEIGHT))*clientwidth;
		_RGBA *pend=pbegin+clientwidth*(HEIGHT<<1);
		DWORD *tmp;
		
		// draw world map
		_RGBA *ppush;
		int y,x;
		ppush=pbegin;
		tmp=(DWORD *)pbegin;
		for(y=0;y<HEIGHT;y++)
		{
			for(x=0;x<WIDTH;x++)
			{
				BYTE b=(BYTE)(255-(vSetup->world[y][x].terrain_cost<<4));
				DWORD d=(b<<16) | (b<<8) | b;
				*tmp=d;
				*(tmp+1)=d;
				*(tmp+clientwidth)=d;
				*(tmp+clientwidth+1)=d;
				tmp+=2;
			}
			ppush+=(clientwidth<<1);
			tmp=(DWORD *)ppush;
		}
		
		// draw all know ai routes
		int maxai=gamemode?MAX_AIS:1;
		for(int a=0;a<maxai;a++)
		{
			AIROUTE *airoute=&AIRoute[a];
			
			if(airoute->count>0)
			{
				//
				int yx=airoute->startyx;
				int count=airoute->count;
				int start=airoute->start;
				while(count--)
				{
					tmp=(DWORD *)(pbegin+(yx>>YSHIFT)*(clientwidth<<1)+((yx&XMASK)<<1));
					if(tmp>(DWORD *)pbegin && tmp<(DWORD *)pend)
					{
						*tmp=airoute->color;
						*(tmp+1)=airoute->color;
						*(tmp+clientwidth)=airoute->color;
						*(tmp+clientwidth+1)=airoute->color;
					}
					
					yx+=DXY[airoute->route[start]].yx;
					start++;
				}
			}
		}
	}
}