//?AStar.cpp:?implementation?of?the?AStar?class.
//
//////////////////////////////////////////////////////////////////////

#include?“stdafx.h“
#include?“AStar.h“

#include?“math.h“?//sqrt
#include?“stdio.h“?//for?sprintf

//#pragma?optimize（?“yawgt“?on?）

//////////////////////////////////////////////////////////////////////
//?Construction/Destruction
//////////////////////////////////////////////////////////////////////

AStar::AStar（）
{
	vSetup=NULL;
	airoute=NULL;
}

AStar::AStar（Setup?*vSetup?AIROUTE?*airoute）
{
	this->vSetup=vSetup;
	this->airoute=airoute;
	
	GetOptions（）;
	UpdateSettings（）;
	UpdateWorld（）;
	Reset（airoute）;
	
	//?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;
}

AStar::~AStar（）
{
	
}

void?AStar::Reset（AIROUTE?*airoute）
{
	//
	bigtick.QuadPart=0;
	LARGE_INTEGER?tmp1;
	QueryPerformanceCounter（&tmp1）;
	
	this->airoute=airoute;
	airoute->count=0;
	
	//?opt?me
	_WORLD?*?pworld=world;
	int?n=WIDTH*HEIGHT;
	do?{
		pworld->u.raw&=0xf;
		pworld++;
	}?while（--n>0）;
	
	//
	frame=0;
	
	pathing_state=FINDING;
	path_found=false;
	no_path=false;
	
	//
	closed_yx=EMPTY_NODE;
	
	//
	heap[0].node=EMPTY_NODE;
	heap[0].f=0;
	heap[0].g=0;
	
	last_heap_leaf=1;
	heap[last_heap_leaf].node=startyx;
	
	heap[last_heap_leaf].g=0;
	heap[last_heap_leaf].f=heap[last_heap_leaf].g+distance（startyx）*DXY[4].cost_multiplier;
	world[startyx].u.state.route=NO_ROUTE;
	
	//
	LARGE_INTEGER?tmp2;
	QueryPerformanceCounter（&tmp2）;
	bigtick.QuadPart?+=?tmp2.QuadPart?-?tmp1.QuadPart;
}





///////////////////////////////////////////////////////////////////////////
//?heap?priority?queue?code
//?note:?make?non-recursive
inline?int?AStar::LEFT（int?k）
{
	return?k<<1;?//k*2;
}
inline?int?AStar::RIGHT（int?k）
{
	return?（k<<1）+1;?//k*2+1;
}
inline?int?AStar::PARENT（int?k）
{
	return?（k>>1）;?//k/2;
}
inline?bool?AStar::NOTEMPTY_UP（int?k）
{
	return?k!=0;
}
inline?bool?AStar::NOTEMPTY_DOWN（int?k）
{
	return?k<=last_heap_leaf;
}
inline?void?AStar::swap_heap（const?int?k1?const?int?k2）
{?//?swaps?nodef?and?g?as?quickly?as?possible
	register?_HEAP?*heap1=&heap[k1];
	register?_HEAP?*heap2=&heap[k2];
	register?WORD?tmpnode;
	register?DWORD?tmp;
	
	tmpnode=heap1->node;
	tmp=*（DWORD?*）heap1;?//swap?f?&?g?at?same?time
	
	heap1->node=heap2->node;
	*heap1=*heap2;
	
	heap2->node=tmpnode;
	*（DWORD?*）heap2=tmp;
}
//?note:?slowest?function?speed?up
inline?void?AStar::remove_root_from_heap（）
{
	//?move?last?leaf?to?the?root?and?delete?the?last?leaf
	heap[ROOT_HEAP]=heap[last_heap_leaf--];
	
	//move?

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????326??2003-06-10?13:23??PathFinder2D\arrow.cur

?????文件??????16866??2003-07-17?22:32??PathFinder2D\Astar.cpp

?????文件???????2830??2003-07-11?18:04??PathFinder2D\AStar.h

?????文件??????16266??2009-09-15?16:36??PathFinder2D\AStarArray.cpp

?????文件???????2308??2003-07-10?20:14??PathFinder2D\AStarArray.h

?????文件??????21929??2009-09-15?16:35??PathFinder2D\AStarComplete.cpp

?????文件???????2757??2003-07-05?13:44??PathFinder2D\AStarComplete.h

?????文件??????20604??2009-09-15?16:35??PathFinder2D\AStarHeap.cpp

?????文件???????2555??2003-07-13?14:59??PathFinder2D\AStarHeap.h

?????文件??????21009??2009-09-15?16:35??PathFinder2D\AStarHeapInteger.cpp

?????文件???????2607??2003-07-13?14:59??PathFinder2D\AStarHeapInteger.h

?????文件??????21064??2009-09-15?16:34??PathFinder2D\AStarlinkedList.cpp

?????文件???????2663??2003-07-10?20:04??PathFinder2D\AStarlinkedList.h

?????文件??????36281??2003-07-05?01:52??PathFinder2D\author.tga

?????文件??????17047??2009-09-15?16:34??PathFinder2D\BestFirst.cpp

?????文件???????2441??2003-07-13?14:58??PathFinder2D\BestFirst.h

?????文件??????43997??2003-07-17?18:56??PathFinder2D\braid_maze.tga

?????文件??????11782??2003-07-13?17:31??PathFinder2D\BreadthFirst.cpp

?????文件???????1421??2003-07-13?19:22??PathFinder2D\BreadthFirst.h

?????文件??????46395??2003-07-17?19:49??PathFinder2D\cavern_maze.tga

?????文件??????26093??2003-07-05?01:28??PathFinder2D\chi.tga

?????文件??????39339??2003-07-05?16:41??PathFinder2D\circle_maze.tga

?????文件??????15725??2003-07-05?01:28??PathFinder2D\clutter.tga

?????文件??????48513??2003-07-17?19:37??PathFinder2D\crack_maze.tga

?????文件??????13071??2003-07-17?20:17??PathFinder2D\cretan_labyrinth.tga

?????文件??????12176??2003-07-13?20:26??PathFinder2D\DepthFirst.cpp

?????文件???????1370??2003-07-13?20:29??PathFinder2D\DepthFirst.h

?????文件??????17050??2003-07-13?15:36??PathFinder2D\Development.cpp

?????文件???????2719??2003-07-07?19:58??PathFinder2D\Development.h

?????文件????????383??2003-06-27?00:30??PathFinder2D\DFS.cpp

............此處省略63個文件信息