老外牛逼A*寻路算法

A*及多种寻路算法的实现，效率高.各种图形算法的效率对比，代码实现。老外写的。

// 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个文件信息