A* 寻路算法演示程序和源码

/*------------------------------------------- | CGetPath.cpp | A-Star寻路算法相关处理功能具体代码 | ---------------------------------------------*/ #include <windows.h> #include <math.h> #include "CGetPath.h" #define SafeDeletePath(p) {DeletePath(p);p=NULL;} /************************************************************ * 函数名: CGetPath(...) 属于CGetPath类的成员 * 功能: 构造函数 * *************************************************************/ CGetPath::CGetPath( LONG SquareC, LPVOID lpSquare, DWORD SceW, DWORD SceH, RECT MonsterRt ) { lSquareC = SquareC;//获得格子的宽度 lHarfSquC = lSquareC/2; //获得场景格子数组首地址 Square = (LPWORD)lpSquare; lCount =0; SceneW = SceW; SceneH = SceH; SceSquareW = SceneW/lSquareC; SceSquareH = SceneH/lSquareC; MonsterRect = MonsterRt; //根据怪物激活区的大小求出最大搜索步数 LONG w=MonsterRect.right-MonsterRect.left; LONG h=MonsterRect.bottom-MonsterRect.top; lMaxStep = (w/lSquareC)*(h/lSquareC); } /************************************************************ * 函数名: CGetPath(...) 属于CGetPath类的成员 * 功能: 构造函数重载 * *************************************************************/ CGetPath::CGetPath( void ) { lSquareC = 30;//获得格子的宽度 lHarfSquC = lSquareC/2; //场景格子数组首地址置为NULL,以后可 //以通过调用Set_Square成员获得地址 Square = NULL; lCount =0; SceneW = 1024;//默认的场景宽度 SceneH = 768;//默认的场景高度 SceSquareW = SceneW/lSquareC; SceSquareH = SceneH/lSquareC; //默认的怪物激活区的大小为1000*800 MonsterRect.left =0; MonsterRect.right =1000; MonsterRect.top =0; MonsterRect.bottom=800; //根据怪物激活区的大小求出最大搜索步数 LONG w=MonsterRect.right-MonsterRect.left; LONG h=MonsterRect.bottom-MonsterRect.top; lMaxStep = (w/lSquareC)*(h/lSquareC); } /******************************************************* * 函数名: MakeSquare(...) 属于CGetPath类的成员 * 功能 : 求两维方式所表达的方块 * ********************************************************/ inline LONG CGetPath::MakeSquare(LONG y, LONG x) { if( y>=SceSquareH || y<0 ) return -1; if( x>=SceSquareW || x<0 ) return -1; return y*SceSquareW+x; } /************************************************************ * 函数名: GetSquareFromPos(...) 属于CGetPath类的成员 * 功能: 求出指定位置所对应的方块 * *************************************************************/ inline LONG CGetPath::GetSquareFromPos( POINT Pos ) { return MakeSquare( Pos.y / lSquareC, Pos.x / lSquareC); } /************************************************************ * 函数名: GetPosFromSquare(...) 属于CGetPath类的成员 * 功能: 求出指定方块的中央位置 * *************************************************************/ inline POINT CGetPath::GetPosFromSquare( LONG lSqu ) { LONG y = lSqu/SceSquareW; LONG x = lSqu-y*SceSquareW; POINT pos; pos.x = lHarfSquC +x*lSquareC; pos.y = lHarfSquC +y*lSquareC; return pos; } /************************************************************ * 函数名: Distance(...) 属于CGetPath类的成员 * 功能: 求两个位置间的距离 * *************************************************************/ inline LONG CGetPath::Distance(POINT StartPos, POINT DestPos ) { LONG dx=StartPos.x-DestPos.x; LONG dy=StartPos.y-DestPos.y; return (LONG)sqrtf((FLOAT)(dx*dx+dy*dy)); } /************************************************************ * 函数名: Distance(...) 属于CGetPath类的成员 * 功能: 重载，求两个方块间的距离 * *************************************************************/ inline LONG CGetPath::Distance(LONG StartSquare, LONG DestSquare) { POINT StartPos=GetPosFromSquare(StartSquare); POINT DestPos=GetPosFromSquare(DestSquare); return Distance(StartPos,DestPos); } /******************************************************* * 函数名: AdjustPos(...) 属于CGetPath类的成员 * 功能 : 调整指定位置，使其处于所在方块的中央 * ********************************************************/ inline POINT CGetPath::AdjustPos( POINT P ) { return GetPosFromSquare(GetSquareFromPos(P)); } /************************************************************ * 函数名: GetAroundSquare(...) 属于CGetPath类的成员 * 功能: 获得指定位置的四周方块,其返回值是八个 * 元素的数组首地址。 * *************************************************************/ inline LPLONG CGetPath::GetAroundSquare( POINT Pos ) { static LONG lpAroSqu[8]; LONG lSquare = GetSquareFromPos(Pos); //求以两维方式表达的方块行号 LONG Index = lSquare/SceSquareW; //求以两维方式表达的方块列号 LONG leave = lSquare - Index*SceSquareW; //场景左上角的方块 if( lSquare==0 ) { lpAroSqu[0]=-1; lpAroSqu[1]=-1; lpAroSqu[2]=-1; lpAroSqu[3]=1; lpAroSqu[4]=SceSquareW+1; lpAroSqu[5]=SceSquareW; lpAroSqu[6]=-1; lpAroSqu[7]=-1; } //场景右上角的方块 else if( lSquare==SceSquareW-1 ) { lpAroSqu[0]=-1; lpAroSqu[1]=-1; lpAroSqu[2]=-1; lpAroSqu[3]=-1; lpAroSqu[4]=-1; lpAroSqu[5]=lSquare+SceSquareW; lpAroSqu[6]=lSquare+SceSquareW-1; lpAroSqu[7]=lSquare-1; } //场景右下角的方块 else if( lSquare==SceSquareH*SceSquareW-1 ) { lpAroSqu[0]=lSquare-SceSquareW-1; lpAroSqu[1]=lSquare-SceSquareW; lpAroSqu[2]=-1; lpAroSqu[3]=-1; lpAroSqu[4]=-1; lpAroSqu[5]=-1; lpAroSqu[6]=-1; lpAroSqu[7]=lSquare-1; } //场景左下角的方块 else if( Index==SceSquareH-1 && leave==0 ) { lpAroSqu[0]=-1; lpAroSqu[1]=lSquare-SceSquareW; lpAroSqu[2]=lSquare-SceSquareW+1; lpAroSqu[3]=lSquare+1; lpAroSqu[4]=-1; lpAroSqu[5]=-1; lpAroSqu[6]=-1; lpAroSqu[7]=-1; } //场景左边界上的方块 else if( leave==0 ) { lpAroSqu[0]=-1; lpAroSqu[1]=lSquare-SceSquareW; lpAroSqu[2]=lSquare-SceSquareW+1; lpAroSqu[3]=lSquare+1; lpAroSqu[4]=lSquare+SceSquareW+1; lpAroSqu[5]=lSquare+SceSquareW; lpAroSqu[6]=-1; lpAroSqu[7]=-1; } //场景上边界上的方块 else if( Index==0 ) { lpAroSqu[0]=-1; lpAroSqu[1]=-1; lpAroSqu[2]=-1; lpAroSqu[3]=lSquare+1; lpAroSqu[4]=lSquare+SceSquareW+1; lpAroSqu[5]=lSquare+SceSquareW; lpAroSqu[6]=lSquare+SceSquareW-1; lpAroSqu[7]=lSquare-1; } //场景底边界上的方块 else if( Index==SceSquareH-1 ) { lpAroSqu[0]=lSquare-SceSquareW-1; lpAroSqu[1]=lSquare-SceSquareW; lpAroSqu[2]=lSquare-SceSquareW+1; lpAroSqu[3]=lSquare+1; lpAroSqu[4]=-1; lpAroSqu[5]=-1; lpAroSqu[6]=-1; lpAroSqu[7]=lSquare-1; } //场景右边界上的方块 else if( leave==SceSquareW-1 ) { lpAroSqu[0]=lSquare-SceSquareW-1; lpAroSqu[1]=lSquare-SceSquareW; lpAroSqu[2]=-1; lpAroSqu[3]=-1; lpAroSqu[4]=-1; lpAroSqu[5]=lSquare+SceSquareW; lpAroSqu[6]=lSquare+SceSquareW-1; lpAroSqu[7]=lSquare-1; } //不在场景边界上的方块 else { lpAroSqu[0]=lSquare-SceSquareW-1; lpAroSqu[1]=lSquare-SceSquareW; lpAroSqu[2]=lSquare-SceSquareW+1; lpAroSqu[3]=lSquare+1; lpAroSqu[4]=lSquare+SceSquareW+1; lpAroSqu[5]=lSquare+SceSquareW; lpAroSqu[6