⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 asstar.cpp

📁 寻径算法演示平台~~提供给计算机博弈爱好者参考学习
💻 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日
// 需要探讨关于A**算法的内容的，请到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)
					{
						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=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);
				}
			}
		}
		//结束描绘搜索过的点
	}


	//用渐变颜色显示搜索过的点
	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);
				}
			}
		}
	}
//结束描绘渐变色


//描绘最短路径
	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();	
				
//结束描绘最短路径				

	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();
}

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -