迷宫view.cpp

迷宫智能A*搜索的算法实现

// 迷宫View.cpp : implementation of the CMyView class
//

#include "stdafx.h"
#include "迷宫.h"

#include "迷宫Doc.h"
#include "迷宫View.h"

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

/////////////////////////////////////////////////////////////////////////////
// CMyView

IMPLEMENT_DYNCREATE(CMyView, CView)

BEGIN_MESSAGE_MAP(CMyView, CView)
	//{{AFX_MSG_MAP(CMyView)
	ON_WM_TIMER()
	ON_COMMAND(ID_RCREATM, OnRcreatm)
	ON_COMMAND(ID_DEEP, OnDeep)
	ON_COMMAND(ID_CHANGEM, OnChangem)
	ON_COMMAND(ID_ASTART, OnAstart)
	ON_COMMAND(ID_STOP, OnStop)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyView construction/destruction

CMyView::CMyView()
{
	// TODO: add construction code here
	map=0;
	width=length=8;
	current=0;
	dlg=new CEDIT;
}

CMyView::~CMyView()
{
}

BOOL CMyView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CMyView drawing

void CMyView::OnDraw(CDC* pDC)
{
	CMyDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
	CDC MemDC;										// 定义一个内存DC（双缓存）
	CBitmap MemBitmap;                              // 定义一个位图对象
	CRect rect;

	GetClientRect(&rect);							// 获得客户区矩形
	MemDC.CreateCompatibleDC(NULL);                 // 建立与屏幕显示兼容的DC
	
	// 建立一个与屏幕显示兼容的位图
	MemBitmap.CreateCompatibleBitmap(pDC, rect.Width(), rect.Height());
	MemDC.SelectObject(&MemBitmap);					// 将位图选入DC

	// 用背景色将位图填充
	MemDC.FillSolidRect(0, 0, rect.Width(), rect.Height(), RGB(255,255,255));
	MemDC.SetBkMode(TRANSPARENT);
	pDC->SetBkMode(TRANSPARENT);



	Drawmaze(&MemDC);
	Drawpath(&MemDC);
	Drawagent(&MemDC,NULL);
	// 然后将内存中的图拷贝到屏幕上进行显示

	pDC->BitBlt(0, 0, rect.Width(), rect.Height(), &MemDC, 0, 0, SRCCOPY);
	
	MemBitmap.DeleteObject();
 	MemDC.DeleteDC();
}

/////////////////////////////////////////////////////////////////////////////
// CMyView printing

BOOL CMyView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CMyView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CMyView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CMyView diagnostics

#ifdef _DEBUG
void CMyView::AssertValid() const
{
	CView::AssertValid();
}

void CMyView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CMyDoc* CMyView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CMyDoc)));
	return (CMyDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CMyView message handlers

void CMyView::InitialMap(int newlength,int newwidth)
{
	if(map){
		for(int xx=0;xx<2*width+1;xx++)
			delete [] map[xx];
	//	delete [] map;
	}
	width=newwidth;
	length=newlength;
	static int seed=0;
	map=new int* [2*width+1];
	for(int i=0;i<=2*width+1;i++)
		map[i]=new int [2*length+2];
	for(i=0;i<=2*width+1;i++)
		for(int j=0;j<=2*length+1;j++)
			if(i==0||j==0||i==2*width+1||j==2*length+1)
				map[i][j]=-1;
				else
					map[i][j]=1;

	bool **node=new bool*[width];
	for(i=0;i<=width;i++)
		node[i]=new bool[length];
	for(i=0;i<=width;i++)
		for(int j=0;j<=length;j++)
			node[i][j]=false;
	node[0][0]=true;
	
	vector<int> x;
	vector<int> y;
	x.push_back(0);
	y.push_back(0);
	int tempx;
	int tempy;
	while(!x.empty()&&!y.empty()){
		srand(time(NULL));
		vector<int>::iterator itor1=x.begin(),itor2=y.begin();
		for(int t=0;t<rand()%x.size();t++){
			itor1++;
			itor2++;
		}
		tempx=*itor1;
		tempy=*itor2;
		x.erase(itor1);
		y.erase(itor2);
		map[tempy*2+1][tempx*2+1]=0;
		int movx[4]={0,0,-1,1};//选择怎么移动
		int movy[4]={-1,1,0,0};
		int sel;
		for(int i=4;i>=1;i--){
			sel=rand()%i;
			if(tempx+movx[sel]<length&&tempx+movx[sel]>=0&&tempy+movy[sel]>=0&&tempy+movy[sel]<width&&!node[tempy+movy[sel]][tempx+movx[sel]]){
				node[tempy+movy[sel]][tempx+movx[sel]]=true;//标志结点访问过
				x.insert(x.begin(),(tempx+movx[sel]));//压入栈中
				y.insert(y.begin(),(tempy+movy[sel]));
				map[tempy*2+1][tempx*2+1]=0;
				map[(tempy*2+1+movy[sel])][(tempx*2+1+movx[sel])]=0;
				map[(tempy+movy[sel])*2+1][(tempx+movx[sel])*2+1]=0;
			}
			int temp=movx[sel];
		 	movx[sel]=movx[i-1];
			movx[i-1]=temp;
			temp=movy[sel];
			movy[sel]=movy[i-1];
			movy[i-1]=movy[sel];
			seed+=3;	
		}
	}
	map[width*2-1][length*2]=0;
	Invalidate();
}

CState* CMyView::Move(CState* x, int i)
{
	CState*	newstate=new	CState;
	int	movx[4]={1,0,-1,0};
	int	movy[4]={0,-1,0,1};
	*newstate=*x;
	newstate->father=x;
	if(i==0){
		newstate->D=(x->D+1)%4;
		newstate->cost=x->cost+1;
		if(map[newstate->R+movy[newstate->D]][newstate->C+movx[newstate->D]])
			return	0;
	}
	if(i==1){
		newstate->D=(x->D+3)%4;
		newstate->cost=x->cost+1;
		if(map[newstate->R+movy[newstate->D]][newstate->C+movx[newstate->D]])
			return	0;
	}	
	if(i==2){
		newstate->C+=movx[x->D];	
		newstate->R+=movy[x->D];
		newstate->cost=x->cost+2;
	}
	if(map[newstate->R][newstate->C])
		return	0;
	return newstate;
}
bool CMyView::Deepfirstscan()
{
	CState*	s0=new CState(1,0,0);
	CState*	sf=new CState(width*2-1,length*2,0);
	open.push_back(s0);
	while(!open.empty()){
		CState*	sn=new	CState;
		sn=open.back();
		closed.push_back(sn);
		if(*sn==*sf)
			return	true;
		open.pop_back();
		for(int i=0;i<3;i++){
			CState* newone=Move(sn,i);
			if(newone){
				if(i==0||i==1){
					CState*	forward=Move(newone,2);
					open.push_back(forward);
				}
				else
					open.push_back(newone);
				sn->son.push_back(open.back());
			}
		}
	}
	if(open.empty())
		return	false;
}

/*bool CMyView::Astar()
{
	CState*	s0=new CState(1,0,0);
	CState*	sf=new CState(width*2-1,length*2,0);
	open.push_back(s0);
	while(!open.empty()){
		CState*	sn=new	CState;
		sn=open.back();
		closed.push_back(sn);
		if(*sn==*sf)
			return true;
		open.pop_back();
	
		int v[3]={0,0,0};
		CState*	extend[3]={0,0,0};
		for(int i=0;i<3;i++){
			CState* newone=Move(sn,i);
			if(newone){
				if(i==0||i==1){
					CState*	forward=Move(newone,2);
					extend[i]=forward;
				}
				else
					extend[i]=newone;
				v[i]=Value(extend[i]);
			}
		}

		for(i=0;i<3;i++)
			for(int j=i+1;j<3;j++){
				if(v[i]<v[j]){
					int tempv=v[i];
					v[i]=v[j];
					v[j]=tempv;

					CState*	temps=extend[i];
					extend[i]=extend[j];
					extend[j]=temps;
				}
			}
		for(i=0;i<3;i++)
			if(extend[i]){
				open.push_back(extend[i]);
				sn->son.push_back(open.back());
			}
	}
	if(open.empty())
		return false;
}*/
bool CMyView::Astar()
{
	CState*	s0=new CState(1,0,0);
	CState*	sf=new CState(width*2-1,length*2,0);
	open.push_back(s0);
	while(!open.empty()){
		CState*	sn=new	CState;
		int i;
		sn=open.back();
		closed.push_back(sn);
		if(sn->father )
			sn->father->son.insert(sn->father->son.begin(),sn); 
		if(*sn==*sf)
			return true;
		open.pop_back();
		for(i=0;i<3;i++){
			CState* newone=Move(sn,i);
			if(newone){
				if(i==0||i==1){
					CState*	forward=Move(newone,2);
					//sn.son.push_back(sn);
					forward->father=sn;
					open.push_back(forward);
				}
				else
					open.push_back(newone);
			}
		}
		int num=open.size();
		int* v=new int[num];
		CState** extend=new CState*[num];
		for(i=0;i<num;i++){
			extend[i]=open.back();
			v[i]=Value(extend[i]);
			open.back()->son.clear();
			open.pop_back();
		}
		for(i=0;i<num;i++)
			for(int j=i+1;j<num;j++){
				if(v[i]<v[j]){
					int tempv=v[i];
					v[i]=v[j];
					v[j]=tempv;

					CState*	temps=extend[i];
					extend[i]=extend[j];
					extend[j]=temps;
				}
			}
		for(i=0;i<num;i++)
			open.push_back(extend[i]);
	}
	if(open.empty())
		return false;
}
bool CMyView::Widefirstscan()
{
	CState*	s0=new CState(1,0,0);
	CState*	sf=new CState(width*2-1,length*2,0);
	open.push_back(s0);
	while(!open.empty()){
		CState*	sn=new	CState;
		sn=open.back();
		closed.push_back(sn);
		if(*sn==*sf)
			return	true;
		open.pop_back();
		for(int i=0;i<3;i++){
			CState* newone=Move(sn,i);
			if(newone){
				if(i==0||i==1){
					CState*	forward=Move(newone,2);
					open.insert(open.begin(),forward);
				}
				else
					open.insert(open.begin(),newone);
			}
		}
	}
	if(open.empty())
		return	false;
}

void CMyView::Drawpath(CDC *pDC)
{
	if(closed.size()==0)
		return;
	int wide;
	CRect	Rect;
	GetWindowRect(&Rect);

	if( Rect.Width() / (2*width+1)>Rect.Height() / (2*length+1))
		wide=Rect.Height() / (2*length+1);
		else
			wide=Rect.Width() / (2*width+1);
	
	CPen	road(PS_SOLID,1,RGB(255	,0,0));
	CPen*	oldpen=pDC->SelectObject(&road);
	CState*	temp=closed.back();
	pDC->MoveTo(temp->C*wide+wide/2,temp->R*wide+wide/2);
	while(temp)
	{
		pDC->LineTo(temp->C*wide+wide/2,temp->R*wide+wide/2);
		temp=temp->father;
	}
}

void CMyView::Drawmaze(CDC *pDC)
{	
	if(!map)
		return;
	CBrush	wallpen;
	wallpen.CreateSolidBrush(RGB(0,120,0));

	CPen	wall(PS_SOLID,0,RGB(0,120,0));
	CBrush	passed;
	passed.CreateSolidBrush(RGB(200,200,230));
	CRect	Rect;
	GetWindowRect(&Rect);

	pDC->SelectObject(&wallpen);
	pDC->SelectObject(&wall);
	int wide;
	if( Rect.Width() / (2*width+1)>Rect.Height() / (2*length+1))
		wide=Rect.Height() / (2*length+1);
		else
			wide=Rect.Width() / (2*width+1);
	for(int i=0;i<2*width+1;i++)
		for(int j=0;j<2*length+1;j++)
			if(!(i==width*2-1&&j==length*2)&&!(i==1&&j==0))
				if((map[i][j]==1||map[i][j]==-1))
					pDC->Rectangle(wide*j,wide*i,wide*j+wide,wide*i+wide);
				else	if(map[i][j]==2){
					CBrush* oldbrush=pDC->SelectObject(&passed);
					pDC->Rectangle(wide*j,wide*i,wide*j+wide,wide*i+wide);
					pDC->SelectObject(oldbrush);
				} 
}
int CMyView::Value(CState* x)
{
	return	x->cost+(width*2-1 - x->C)+(length*2 - x->R);
}

void CMyView::Drawagent(CDC *pDC,CState* x)
{
	int wide;
	CRect	Rect;
	GetWindowRect(&Rect);
	if( Rect.Width() / (2*width+1)>Rect.Height() / (2*length+1))
		wide=Rect.Height() / (2*length+1);
		else
			wide=Rect.Width() / (2*width+1);
	CPen	road(PS_SOLID,1,RGB(255	,0,0));
	CPen*	oldpen=pDC->SelectObject(&road);
	if(current){
		pDC->Ellipse(current->C*wide,current->R*wide,current->C*wide+wide,current->R*wide+wide);
		pDC->SelectObject(oldpen);
		pDC->MoveTo(current->C*wide+wide/2,current->R*wide+wide/2);
		switch(current->D){
		case	0:	pDC->LineTo(current->C*wide+wide,current->R*wide+wide/2) ;
					break;
		case	1:	pDC->LineTo(current->C*wide+wide/2,current->R*wide); 
					break;
		case	2:	pDC->LineTo(current->C*wide,current->R*wide+wide/2);
					break;
		case	3:	pDC->LineTo(current->C*wide+wide/2,current->R*wide+wide);
					break;	
		}
	}
}

CState* CMyView::Next(CState *x)
{
	if(x->son.size()==0)
		return x->father;
	CState*	y=x->son.back();
	x->son.pop_back();
	return y;
}

void CMyView::OnTimer(UINT nIDEvent) 
{
	// TODO: Add your message handler code here and/or call default
	if(drawing){
			CState	sf=CState(width*2-1,length*2,0);
			if(current){
				if(*current==sf){
					CString	str;
					str.Format("共负出代价: %d",current->cost);
					drawing=false;
					MessageBox(str);
					return;
				}
				map[current->R][current->C]=2;
				current=Next(current);
				allcost+=current->cost; 
			}
		Invalidate(false);
	}
	CView::OnTimer(nIDEvent);
}

void CMyView::OnRcreatm() 
{
	// TODO: Add your command handler code here
	InitialMap(width,length);
}

void CMyView::OnDeep() 
{
	// TODO: Add your command handler code here
	if(!map){
		MessageBox("请先生成迷宫");
		return;
	}
	for(int i=1;i<=width*2;i++)
		for(int j=1;j<=length*2;j++)
			if(map[i][j]==2)
				map[i][j]=0;
	open.clear();
	closed.clear();
	bool haveapath;
	haveapath=Deepfirstscan();
	if(!haveapath){
		MessageBox("没有通路");
		return;
	}
	current=closed.front();
	drawing=true;
	SetTimer(1,100,NULL);
	allcost=0;
}

void CMyView::OnChangem() 
{
	// TODO: Add your command handler code here
	dlg->DoModal();
	InitialMap(dlg->m_L ,dlg->m_W );
}

void CMyView::OnAstart() 
{
	// TODO: Add your command handler code here
		if(!map){
		MessageBox("请先生成迷宫");
		return;
	}
	for(int i=1;i<=width*2;i++)
		for(int j=1;j<=length*2;j++)
			if(map[i][j]==2)
				map[i][j]=0;
	open.clear();
	closed.clear();

	bool haveapath;
	haveapath=Astar();
	if(!haveapath){
		MessageBox("没有通路");
		return;
	}
	current=closed.front();
	drawing=true;
	SetTimer(1,100,NULL);
	allcost=0;
}

void CMyView::OnStop() 
{
	// TODO: Add your command handler code here
	drawing=false;
}