?? asstar.cpp
字號:
#include "stdafx.h"
#include "SearchPath.h"
#include "ASStar.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
extern map[Height][Width];
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
// A** Algorithm
// Made by: Gardon_TDZL 2005,3,17
// my site about A** : tdzl.gameres.com
// 為他人編寫的尋路演示提供的A**算法類。
// 本代碼作者：天地之靈，完成日期：2005年3月17日
// 需要探討關(guān)于A**算法的內(nèi)容的，請到tdzl.gameres.com
// My QQ:150277814.
// My e-mail:tdzl2003.126.com
//////////////////////////////////////////////////////////////////////
CASStar::CASStar()
{
int i,j;
this->Size=Height*Width;
for(i=0;i<Height;i++)
{
for(j=0;j<Width;j++)
{
if(map[i][j]==0)
{
startX=j;
startY=i;
}
else if(map[i][j]==-3)
{
targetX=j;
targetY=i;
}
}
}
}
CASStar::~CASStar()
{
}
int CASStar::searchThePath()
{
int i,j;
int bx,by,ex,ey;
int bx1,by1,ex1,ey1;
for (i=0;i<Height;i++)
for (j=0;j<Width;j++)
Value[i][j]=-1;
Value[startY][startX]=1;
bx=startX;by=startY;ex=startX;ey=startY;
while (bx>=0)
{
bx1=-1;by1=-1;ex1=-1;ey1=-1;
for (i=by;i<=ey;i++)
for (j=bx;j<=ex;j++)
if (Value[i][j]!=-1 && map[i][j]!=-1)
{
if ((Value[i][j+1]==-1 || Value[i][j]+1<Value[i][j+1]) && (j<Width-1))
{
Value[i][j+1]=Value[i][j]+1;
if (j==ex) ex++;
if (by1<0)
{
bx1=j+1;by1=i;
ex1=bx1;ey1=i;
}else
{
if (j+1>ex1) ex1=j+1;
if (j+1<bx1) bx1=j+1;
if (i>ey1) ey1=i;
if (i<by1) by1=i;
}
}
if ((Value[i+1][j]==-1 || Value[i][j]+1<Value[i+1][j]) && (i<Height-1))
{
Value[i+1][j]=Value[i][j]+1;
if (i==ey) ey++;
if (bx1<0)
{
bx1=j;by1=i+1;
ex1=j;ey1=by1;
}else
{
if (j>ex1) ex1=j;
if (j<bx1) bx1=j;
if (i+1>ey1) ey1=i+1;
if (i+1<by1) by1=i+1;
}
}
}
for (i=by;i<=ey;i++)
for (j=ex;j>=bx;j--)
if (Value[i][j]!=-1 && map[i][j]!=-1)
{
if ((Value[i][j-1]==-1 || Value[i][j]+1<Value[i][j-1]) && (j>0))
{
Value[i][j-1]=Value[i][j]+1;
if (j==bx) bx--;
if (by1<0)
{
ex1=bx1;ey1=i;
}else
{
if (j-1>ex1) ex1=j-1;
if (j-1<bx1) bx1=j-1;
if (i>ey1) ey1=i;
if (i<by1) by1=i;
}
}
if ((Value[i+1][j]==-1 || Value[i][j]+1<Value[i+1][j]) && (i<Height-1))
{
Value[i+1][j]=Value[i][j]+1;
if (i==ey) ey++;
if (bx1<0)
{
bx1=j;by1=i+1;
ex1=j;ey1=by1;
}else
{
if (j>ex1) ex1=j;
if (j<bx1) bx1=j;
if (i+1>ey1) ey1=i+1;
if (i+1<by1) by1=i+1;
}
}
}
for (i=ey;i>=by;i--)
for (j=bx;j<=ex;j++)
if (Value[i][j]!=-1 && map[i][j]!=-1)
{
if ((Value[i][j+1]==-1 || Value[i][j]+1<Value[i][j+1]) && (j<Width-1))
{
Value[i][j+1]=Value[i][j]+1;
if (j==ex) ex++;
if (by1<0)
{
bx1=j+1;by1=i;
ex1=bx1;ey1=i;
}else
{
if (j+1>ex1) ex1=j+1;
if (j+1<bx1) bx1=j+1;
if (i>ey1) ey1=i;
if (i<by1) by1=i;
}
}
if ((Value[i-1][j]==-1 || Value[i][j]+1<Value[i-1][j]) && (i>0))
{
Value[i-1][j]=Value[i][j]+1;
if (i==ey) ey++;
if (bx1<0)
{
bx1=j;by1=i-1;
ex1=j;ey1=by1;
}else
{
if (j>ex1) ex1=j;
if (j<bx1) bx1=j;
if (i-1>ey1) ey1=i-1;
if (i-1<by1) by1=i-1;
}
}
}
for (i=ey;i>=by;i--)
for (j=ex;j>=bx;j--)
if (Value[i][j]!=-1 && map[i][j]!=-1)
{
if ((Value[i][j-1]==-1 || Value[i][j]+1<Value[i][j-1]) && (j>0))
{
Value[i][j-1]=Value[i][j]+1;
if (j==ex) ex++;
if (by1<0)
{
bx1=j-1;by1=i;
ex1=bx1;ey1=i;
}else
{
if (j-1>ex1) ex1=j-1;
if (j-1<bx1) bx1=j-1;
if (i>ey1) ey1=i;
if (i<by1) by1=i;
}
}
if ((Value[i-1][j]==-1 || Value[i][j]+1<Value[i-1][j]) && (i>0))
{
Value[i-1][j]=Value[i][j]+1;
if (i==ey) ey++;
if (bx1<0)
{
bx1=j-1;by1=i;
ex1=bx1;ey1=i;
}else
{
if (j>ex1) ex1=j;
if (j<bx1) bx1=j;
if (i-1>ey1) ey1=i-1;
if (i-1<by1) by1=i-1;
}
}
}
bx=bx1;by=by1;ex=ex1;ey=ey1;
// if (Value[targetY][targetX]>=0) break;
}
return 1;
}
void CASStar::showThePath(CDC *pDC , int showMode)
{
CBitmap bm1,bm2,bm3,bm5,bm6, *pbm;
BITMAP bmMetric1,bmMetric2;
bm1.LoadBitmap(IDB_BITMAP7);
bm2.LoadBitmap(IDB_BITMAP8);
bm3.LoadBitmap(IDB_BITMAP11);
bm5.LoadBitmap(IDB_BITMAP12);//起點
bm6.LoadBitmap(IDB_BITMAP13);//終點
bm1.GetBitmap(&bmMetric1);
bm2.GetBitmap(&bmMetric2);
CDC memDC;
memDC.CreateCompatibleDC(pDC);
pbm = memDC.SelectObject(&bm1);
if(showMode == 1)
{
//描繪搜索過的點
for(int i=0;i<Height;i++)
{
for(int j=0;j<Width;j++)
{
if(Value[i][j]>=0)
{
memDC.SelectObject(&bm3);
pDC->BitBlt(j*bmMetric1.bmHeight, i*bmMetric1.bmWidth,bmMetric1.bmWidth,bmMetric1.bmHeight,&memDC,0,0,SRCCOPY);
}
}
}
//結(jié)束描繪搜索過的點
}
//用漸變顏色顯示搜索過的點
if(showMode == 2)
{
const int colorBeg = 70;
int totalStep = (255 - colorBeg) * 5;
double max = Value[targetY][targetX];
int R, G, B, temp;
for(int i=0;i<Height;i++)
{
for(int j=0;j<Width;j++)
{
if(Value[i][j] >= 0)
{
int curStep = (int)(Value[i][j]/max * totalStep);
if(curStep > (temp = (255 - colorBeg) * 4))
{
R = curStep - temp + colorBeg;
G = colorBeg;
B = 255;
}
else if(curStep > (temp = (255 - colorBeg) * 3))
{
R = colorBeg;
G = 255 - (curStep - temp);
B = 255;
}
else if(curStep > (temp = (255 - colorBeg) * 2))
{
R = colorBeg;
G = 255;
B = curStep - temp + colorBeg;
}
else if(curStep > (temp = (255 - colorBeg)))
{
R = 255 - (curStep - temp);
G = 255;
B = colorBeg;
}
else
{
R = 255;
G = curStep + colorBeg;
B = colorBeg;
}
CRect tempRect(j*bmMetric2.bmWidth,i*bmMetric2.bmHeight,(j+1)*bmMetric2.bmWidth,(i+1)*bmMetric2.bmHeight);
CBrush brushBg;
brushBg.CreateSolidBrush(RGB(R,G,B));
pDC->FillRect(&tempRect,&brushBg);
}
}
}
}
//結(jié)束描繪漸變色
//描繪最短路徑
CPen pen,*p_pen;
pen.CreatePen(PS_SOLID,2,RGB(0,0,255));
p_pen = pDC->SelectObject(&pen);
pDC->MoveTo(targetX * bmMetric2.bmWidth+bmMetric2.bmWidth/2 , targetY * bmMetric2.bmHeight+bmMetric2.bmHeight/2);
int i=targetY;
int j=targetX;
while(Value[i][j]>0)
{
if (j<Width-1 && Value[i][j+1]<Value[i][j] && map[i][j+1]!=-1)
{
j++;
}else
if (i<Height-1 && Value[i+1][j]<Value[i][j] && map[i+1][j]!=-1)
{
i++;
}
else
if (j>0 && Value[i][j-1]<Value[i][j] && map[i][j-1]!=-1)
{
j--;
}
else
if (i>0 && Value[i-1][j]<Value[i][j] && map[i-1][j]!=-1)
{
i--;
}
else
{
break;
}
pDC->LineTo(j * bmMetric2.bmWidth+bmMetric2.bmWidth/2 , i * bmMetric2.bmHeight+bmMetric2.bmHeight/2);
}
pDC->SelectObject(p_pen);
pen.DeleteObject();
//結(jié)束描繪最短路徑
for(i = 0; i < Height; i ++)
{
for(int j = 0; j < Width; j ++)
{
if(map[i][j]==-1)
{
memDC.SelectObject(&bm1);
pDC->BitBlt(j*bmMetric1.bmHeight, i*bmMetric1.bmWidth,bmMetric1.bmWidth,bmMetric1.bmHeight,&memDC,0,0,SRCCOPY);
}
else if(map[i][j]==0)
{
memDC.SelectObject(&bm5);
pDC->BitBlt(j*bmMetric2.bmHeight, i*bmMetric2.bmWidth,bmMetric2.bmWidth,bmMetric2.bmHeight,&memDC,0,0,SRCCOPY);
}
else if(map[i][j]==-3)
{
memDC.SelectObject(&bm6);
pDC->BitBlt(j*bmMetric2.bmHeight, i*bmMetric2.bmWidth,bmMetric2.bmWidth,bmMetric2.bmHeight,&memDC,0,0,SRCCOPY);
}
}
}
memDC.SelectObject(pbm);
bm1.DeleteObject();
bm2.DeleteObject();
memDC.DeleteDC();
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -