📄 water.cpp

📁 寻径算法演示平台~~提供给计算机博弈爱好者参考学习
💻 CPP
字号:
// Water.cpp: implementation of the CWater class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"

#include "SearchPath.h"
#include "Water.h"



#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

extern map[Height][Width];



//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CWater::CWater()
{
	for(int i=0;i<Height;i++)
	{
		for(int j=0;j<Width;j++)
		{
			m_map[i][j]=-1;//把m_map数组初始化成极大值
		}
	}
	for(i=0;i<Height;i++)
	{
		for(int j=0;j<Width;j++)
		{
			m_value[i][j]=0;
		}
	}
	head=new node;
	for(i=0;i<Height;i++)
	{
		for(int j=0;j<Width;j++)
		{
			if(map[i][j]==0)
			{
				m_map[i][j]=0;//把起点坐标估值初始化为0

				head->x=i;
				head->y=j;
				head->next=NULL;
				m_value[i][j]=1;
				startX=j;
				startY=i;
			}
			else if(map[i][j]==-3)
			{
				targetX=j;
				targetY=i;
			}
		}
	}

}

CWater::~CWater()
{

}


int CWater::writeNumber()
{
	//map是记录了地图的数组，而m_map是记录了每个格子的价值的数组
	while(head!=NULL)
	{
		
		node *s,*p,*newHead=NULL,*newS,*newP;
		s=p=head;
		
		while(s!=NULL)
		{
			
			int i=s->x,j=s->y;
			
			if((map[i+1][j]!=-1)&&(m_value[i+1][j]==0))
			{
				if(map[i+1][j]==-3)
				{
					m_map[i+1][j] = m_map[i][j]+1;
					//找到路径删除所有动态申请的内存
					node *p=s;
					while(s->next!=NULL)
					{
						s = s->next;
						delete p;
						p = s;
					}
					delete s;
					
					p = newHead;
					if(newHead!=NULL)
					{
						while(newHead->next!=NULL)
						{
							newHead = newHead->next;
							delete p;
							p = newHead;
						}
						delete newHead;
					}
					return m_map[i][j]+1;
				}
				m_map[i+1][j]=m_map[i][j]+1;
				m_value[i+1][j]=1;
				
				newS=new node;
				newS->x=i+1;
				newS->y=j;
				newS->next=NULL;
				if(newHead==NULL)
				{
					newHead=newS;
					newP=newS;
				}
				else
				{
					newP->next=newS;
					newP=newS;
				}
				
			}
			
			if((map[i-1][j]!=-1)&&(m_value[i-1][j]==0))
			{
				if(map[i-1][j]==-3)
				{
					m_map[i-1][j] = m_map[i][j]+1;
					//找到路径删除所有动态申请的内存
					node *p=s;
					while(s->next!=NULL)
					{
						s = s->next;
						delete p;
						p = s;
					}
					delete s;
					
					p = newHead;
					if(newHead!=NULL)
					{
						while(newHead->next!=NULL)
						{
							newHead = newHead->next;
							delete p;
							p = newHead;
						}
						delete newHead;
					}
					return m_map[i][j]+1;
				};
				m_map[i-1][j]=m_map[i][j]+1;
				m_value[i-1][j]=1;
				
				
				newS=new node;
				newS->x=i-1;
				newS->y=j;
				newS->next=NULL;
				if(newHead==NULL)
				{
					newHead=newS;
					newP=newS;
				}
				else
				{
					newP->next=newS;
					newP=newS;
				}
			}
			
			if((map[i][j+1]!=-1)&&(m_value[i][j+1]==0))
			{
				if(map[i][j+1]==-3)
				{
					m_map[i][j+1] = m_map[i][j]+1;
					//找到路径删除所有动态申请的内存
					node *p=s;
					while(s->next!=NULL)
					{
						s = s->next;
						delete p;
						p = s;
					}
					delete s;
					
					p = newHead;
					if(newHead!=NULL)
					{
						while(newHead->next!=NULL)
						{
							newHead = newHead->next;
							delete p;
							p = newHead;
						}
						delete newHead;
					}
					return m_map[i][j]+1;
				};
				m_map[i][j+1]=m_map[i][j]+1;
				m_value[i][j+1]=1;
				
				
				newS=new node;
				newS->x=i;
				newS->y=j+1;
				newS->next=NULL;
				if(newHead==NULL)
				{
					newHead=newS;
					newP=newS;
				}
				else
				{
					newP->next=newS;
					newP=newS;
				}
			}
			
			if((map[i][j-1]!=-1)&&(m_value[i][j-1]==0))
			{
				if(map[i][j-1]==-3)
				{
					m_map[i][j-1] = m_map[i][j]+1;
					//找到路径删除所有动态申请的内存
					node *p=s;
					while(s->next!=NULL)
					{
						s = s->next;
						delete p;
						p = s;
					}
					delete s;
					
					p = newHead;
					if(newHead!=NULL)
					{
						while(newHead->next!=NULL)
						{
							newHead = newHead->next;
							delete p;
							p = newHead;
						}
						delete newHead;
					}
					return m_map[i][j]+1;
				};
				m_map[i][j-1]=m_map[i][j]+1;
				m_value[i][j-1]=1;
				
				
				newS=new node;
				newS->x=i;
				newS->y=j-1;
				newS->next=NULL;
				if(newHead==NULL)
				{
					newHead=newS;
					newP=newS;
				}
				else
				{
					newP->next=newS;
					newP=newS;
				}
			}
			
			
			p=s;
			s=s->next;
			delete p;
			p=s;
			
		}
		head=newHead;
	}
	return NULL;
}


int CWater::searchThePath()
{
	return writeNumber();
}

void CWater::showThePath(CDC *pDC , int showMode)
{     

	//SearchThePath();

	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(m_map[i][j]>=1)
				{
					memDC.SelectObject(&bm3);
					pDC->BitBlt(j*bmMetric1.bmHeight, i*bmMetric1.bmWidth,bmMetric1.bmWidth,bmMetric1.bmHeight,&memDC,0,0,SRCCOPY);
					//char buf[4];
					//sprintf(buf,"%d", m_map[i][j]);
					//pDC->TextOut(j*bmMetric2.bmWidth+5,i*bmMetric2.bmHeight+5,buf);
				}
			}
		}
		//结束描绘搜索过的点
	}



	//用渐变颜色显示搜索过的点
	if(showMode == 2)
	{
		const int colorBeg = 70;
		int totalStep = (255 - colorBeg) * 5;
		double max = m_map[targetY][targetX];
		int R, G, B, temp;
		for(int i=0;i<Height;i++)
		{
			for(int j=0;j<Width;j++)
			{
				if(m_map[i][j] >= 1)
				{
					int curStep = (int)(m_map[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(m_map[i][j]!=0)
	{
		int min=20000;
		int k=i,l=j;
		if((m_map[i+1][j]>=0)&&(m_map[i+1][j]<min))
		{
			min=m_map[i+1][j];
			k=i+1;
			l=j;
		}
		if((m_map[i-1][j]>=0)&&(m_map[i-1][j]<min))
		{
			min=m_map[i-1][j];
			k=i-1;
			l=j;
		}
		if((m_map[i][j+1]>=0)&&(m_map[i][j+1]<min))
		{
			min=m_map[i][j+1];
			k=i;
			l=j+1;
		}
		if((m_map[i][j-1]>=0)&&(m_map[i][j-1]<min))
		{
			min=m_map[i][j-1];
			k=i;
			l=j-1;
		}
		i=k;
		j=l;
		pDC->LineTo(j * bmMetric2.bmWidth+bmMetric2.bmWidth/2 , i * bmMetric2.bmHeight+bmMetric2.bmHeight/2);
	}
	
	pDC->LineTo(startX * bmMetric2.bmWidth+bmMetric2.bmWidth/2 , startY * bmMetric2.bmHeight+bmMetric2.bmHeight/2);
	pDC->SelectObject(p_pen);
	pen.DeleteObject();	
				
//结束描绘最短路径				
			
	
/*
//显示搜索过的点离起点的值
	CFont *poldfont,*newfont=new CFont;
	TEXTMETRIC tm;
	newfont->CreateFont(10,0,0,0,FW_NORMAL,0,0,0,GB2312_CHARSET,OUT_DEFAULT_PRECIS,CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,DEFAULT_PITCH,"宋体");
	poldfont=pDC->SelectObject(newfont);
	pDC->GetTextMetrics(&tm);
	
	for(i=0;i<Height;i++)
	{
		for(int j=0;j<Width;j++)
		{
			if(m_map[i][j]>=1)
			{
				char buf[4];
				sprintf(buf,"%d", m_map[i][j]);
				pDC->TextOut(j*bmMetric2.bmWidth+5,i*bmMetric2.bmHeight+5,buf);
			}
		}
	}

	pDC->SelectObject(poldfont);
	newfont->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();
}
💿 文件大小 164 K
👤 上传用户 smellteen
📂 所属分类数据结构
🏷️ 相关标签

#径算法 #计算机
⌨️ 快捷键说明

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