bashumaview.cpp

八数码问题求解

// BashumaView.cpp : implementation of the CBashumaView class
//

#include "stdafx.h"
#include "Bashuma.h"

#include "BashumaDoc.h"
#include "BashumaView.h"
#include "State.h"
#include "SetDlg.h"

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

/////////////////////////////////////////////////////////////////////////////
// CBashumaView
#define WM_DRAWREFRESH (WM_USER+100)

IMPLEMENT_DYNCREATE(CBashumaView, CFormView)

BEGIN_MESSAGE_MAP(CBashumaView, CFormView)
	//{{AFX_MSG_MAP(CBashumaView)
	ON_COMMAND(IDM_SET, OnSet)
	ON_BN_CLICKED(IDC_BEGIN, OnBegin)
	ON_MESSAGE(WM_DRAWREFRESH, OnDrawRefresh)
	ON_WM_PAINT()
	ON_WM_CANCELMODE()
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CFormView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CBashumaView construction/destruction



CList<CState,CState&> OpenList;  //A*算法中的OPEN表
CList<CState,CState&> CloseList;//A*算法中的CLOSE表
CList<CState,CState&> FinalList;  //A*算法中的最终表

CState Beginstate;
CState Goalstate;
int Flag=-1;

CBashumaView::CBashumaView()
	: CFormView(CBashumaView::IDD)
{
	//{{AFX_DATA_INIT(CBashumaView)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// TODO: add construction code here
	pThread=NULL;

}

CBashumaView::~CBashumaView()
{
}

void CBashumaView::DoDataExchange(CDataExchange* pDX)
{
	CFormView::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CBashumaView)
		// NOTE: the ClassWizard will add DDX and DDV calls here
	//}}AFX_DATA_MAP
}

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

	return CFormView::PreCreateWindow(cs);
}

void CBashumaView::OnInitialUpdate()
{
	CFormView::OnInitialUpdate();
	GetParentFrame()->RecalcLayout();
	ResizeParentToFit();

}

/////////////////////////////////////////////////////////////////////////////
// CBashumaView printing

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

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

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

void CBashumaView::OnPrint(CDC* pDC, CPrintInfo* /*pInfo*/)
{
	// TODO: add customized printing code here
}

/////////////////////////////////////////////////////////////////////////////
// CBashumaView diagnostics

#ifdef _DEBUG
void CBashumaView::AssertValid() const
{
	CFormView::AssertValid();
}

void CBashumaView::Dump(CDumpContext& dc) const
{
	CFormView::Dump(dc);
}

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

/////////////////////////////////////////////////////////////////////////////
// CBashumaView message handlers

void CBashumaView::OnDrawRefresh(WPARAM   wparam,    LPARAM     param)
{
	CRect rect(100,180,800,500);
	InvalidateRect(&rect);

}

int EvaluatFunc(CState CurState,int flag)
{//评价每个状态的评价函数,依据每个状态离目标状态总共需要走的步数为评价指标
	int Result=0;
	if(flag==1)	
	{		
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<3;j++)
			{
				if(CurState.m_content[i][j]!=0)
				{
					int Curx=0,Cury=0,Goalx=0,Goaly=0;
					CurState.FindIndex(CurState.m_content[i][j],Curx,Cury);
					Goalstate.FindIndex(CurState.m_content[i][j],Goalx,Goaly);
					Result=Result+abs(Goalx-Curx)+abs(Goaly-Cury); 				
				}			
			}
		}	
		return Result+CurState.m_Depth;
	}	
	else
	{
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<3;j++)
			{
				if(CurState.m_content[i][j]!=0)
				{
					if (CurState.m_content[i][j]!=Goalstate.m_content[i][j])
					{
						Result++;
					}
				}
			}
		}
		return Result+CurState.m_Depth;
	}
}

UINT Search(LPVOID param )
{	
	//开始把初始状态放入OPEN表，并计算f(S0)	
	Beginstate.EvalueResult=EvaluatFunc(Beginstate,Flag);
	OpenList.AddHead(Beginstate);
	
	HDC hDc = GetDC((HWND)param);
	CDC* pDC = CDC::FromHandle(hDc);
	pDC->SetBkColor(14215660);
	pDC->TextOut(120,150,"当前扩展结点:");
	
	int count=0;

	while (!OpenList.IsEmpty()) 
	{
		count++;
		if (count>50)
		{
			AfxMessageBox("无法达到目标状态!");
			return 0;
		}

		Sleep(200);
		::PostMessage((HWND)param, WM_DRAWREFRESH, 0, 0);
		//把OPEN表的第一个结点取出，并放入CLOSE表
		CState CurrentS=OpenList.RemoveHead();
		CurrentS.m_BSelect=TRUE;
		CloseList.AddHead(CurrentS);
		CPoint pt;
		pt.x=150;
		pt.y=180;
		CurrentS.DrawState(pDC,pt,RGB(0,255,0));
	   
		//该结点是否为目标结点，如果是则成功退出
		if(CurrentS.CompareState(CurrentS,Goalstate))
		{
			CString str;
			str.Format("当前搜索深度为%d",CurrentS.m_Depth);
			Flag=-1;
			AfxMessageBox("已经到达目标状态！""\r"+str);
			
			pDC->TextOut(60,370," 最终搜索路径如下:");
			//建立FinalList
			FinalList.AddHead(Goalstate);
			while (CurrentS.m_Depth>=1)
			{
				CurrentS=*(CurrentS.PreState);
				FinalList.AddHead(CurrentS);
			}
			
			//FinalList.AddHead(Beginstate);
			CPoint pt1;
			pt1.x=60;
			pt1.y=390;
			int n=0;

			POSITION pos = FinalList.GetHeadPosition();
			while (pos!=NULL)
			{	
				n++;
				CState stateTemp=OpenList.GetAt(pos);			
						
				stateTemp.DrawState(pDC,pt1,RGB(0,0,255));	
				pt1.x+=70;
				if (n%6==0) 
				{
					pt1.y+=70;
					pt1.x=60;
				}
				
				FinalList.GetNext(pos);
			}
			return 0;
		}
		
		//否则，对该节点进行扩展，如果不能扩展，则while循环	
		//如果可以扩展，则扩展该结点，并计算每个结点的评估值，并按评估值的大小从小到大依次放入OPEN
		//的首部，还要为每个子节点配置指向正在扩展结点的指针
	
		CState LeftState =CurrentS;
		CState upState =CurrentS;
		CState RightState =CurrentS;
		CState DownState =CurrentS;

		BOOL RF=FALSE;
		BOOL LF=FALSE;
		BOOL UF=FALSE;
		BOOL DF=FALSE;
		pDC->TextOut(120,280,"其扩展的结点:");
		pt.x=120;
		pt.y=300;
		
		if (LeftState.MoveLeft())
		{
			LeftState.PreState=&CloseList.GetHead();
			LeftState.m_moveDirection=Left;
			LeftState.m_Depth=CurrentS.m_Depth+1;
			LeftState.EvalueResult=EvaluatFunc(LeftState,Flag);
			LeftState.m_BSelect=FALSE;
			LeftState.DrawState(pDC,pt,RGB(0,0,255));
			pt.x+=75;
			
			OpenList.AddHead(LeftState);
			LF=TRUE;
		}

		if (upState.MoveUp())
		{
			//upState.PreState=&CurrentS;
			upState.PreState=&CloseList.GetHead();
			upState.m_moveDirection=Up;
			upState.m_Depth=CurrentS.m_Depth+1;
			upState.EvalueResult=EvaluatFunc(upState,Flag);
			upState.m_BSelect=FALSE;
			upState.DrawState(pDC,pt,RGB(0,0,255));
			pt.x+=75;
			if (!LF || upState.EvalueResult<=LeftState.EvalueResult) 
			{
				OpenList.AddHead(upState);
			}
			else
			{
				OpenList.InsertAfter(OpenList.GetHeadPosition(),upState);					
			}
			UF=TRUE;
		}

		if (RightState.MoveRight())
		{
			//RightState.PreState=&CurrentS;
			RightState.PreState=&CloseList.GetHead();
			RightState.m_moveDirection=Right;
			RightState.m_Depth=CurrentS.m_Depth+1;
			RightState.EvalueResult=EvaluatFunc(RightState,Flag);
			RightState.m_BSelect=FALSE;
			RightState.DrawState(pDC,pt,RGB(0,0,255));
			pt.x+=75;
			if ((!LF && !UF)|| RightState.EvalueResult <= OpenList.GetAt(OpenList.GetHeadPosition()).EvalueResult) 
			{
				OpenList.AddHead(RightState);
			}
			else
			{
				POSITION pos = OpenList.GetHeadPosition();
				POSITION posTemp;
				int max=0;
				while (pos!=NULL)
				{	
					CState stateTemp=OpenList.GetAt(pos);
					max= stateTemp.EvalueResult;
					if (max <=RightState.EvalueResult && 
						OpenList.GetAt(pos).m_Depth==RightState.m_Depth) 
					{ 
						posTemp=pos;
					}
					OpenList.GetNext(pos);			
				}
				OpenList.InsertAfter(posTemp,RightState);				
			}
			RF=TRUE;
		}

	
		if (DownState.MoveDown())
		{
			//DownState.PreState=&CurrentS;
			DownState.PreState=&CloseList.GetHead();
			DownState.m_moveDirection=Down;
			DownState.m_Depth=CurrentS.m_Depth+1;
			DownState.EvalueResult=EvaluatFunc(DownState,Flag);
			DownState.m_BSelect=FALSE;
			DownState.DrawState(pDC,pt,RGB(0,0,255));
			pt.x+=75;
			if ((!LF && !UF && !RF)|| DownState.EvalueResult <= OpenList.GetAt(OpenList.GetHeadPosition()).EvalueResult) 
			{
				OpenList.AddHead(DownState);
			}
			else
			{
				POSITION pos = OpenList.GetHeadPosition();
				POSITION posTemp;
				int max=0;
				while (pos!=NULL)
				{
					if ((OpenList.GetAt(pos)).m_Depth!=DownState.m_Depth) 
					{
						break;
					}
					max=(OpenList.GetAt(pos)).EvalueResult;
					if (max <= DownState.EvalueResult) 
					{ 
						posTemp=pos;
					}
					OpenList.GetNext(pos);			
				}
				OpenList.InsertAfter(posTemp,DownState);						
			}
			DF=TRUE;
		}
		
	}
	
	if (OpenList.IsEmpty())
	{
		AfxMessageBox("无法达到目标状态!");
	}
	Flag=-1;
	return 0;
}

void CBashumaView::OnSet() 
{
	// TODO: Add your command handler code here
	CSetDlg dlg;

	
	if (pThread!=NULL)
		{
			pThread->SuspendThread();	
			OpenList.RemoveAll();			
			CloseList.RemoveAll();
			FinalList.RemoveAll();
			
			pThread=NULL;
		}
	
	

	CRect rect(48,48,212,112);
	InvalidateRect(&rect);
		
	if(IDOK==dlg.DoModal())
	{
		CDC *pDC=GetDC();
		pDC->SetBkColor(14215660);
		pDC->TextOut(50,30,"初始状态");
		pDC->TextOut(150,30,"目标状态");
		CPoint ptB;
		ptB.x=50;
		ptB.y=50;
		Beginstate.DrawState(pDC,ptB, RGB(255,0,0));

		CPoint ptG;
		ptG.x=150;
		ptG.y=50;
		Goalstate.DrawState(pDC,ptG, RGB(255,0,0));

		ReleaseDC(pDC);	

		if (pThread==NULL) 
		{
			HWND hWnd = GetSafeHwnd();
			pThread = AfxBeginThread(Search, hWnd, THREAD_PRIORITY_NORMAL,0,
				CREATE_SUSPENDED);	
			CWnd* pBtn = GetDlgItem( IDC_BEGIN);
			pBtn->SetWindowText("开始");
		}
	}
}


void CBashumaView::OnBegin() 
{
	// TODO: Add your control notification handler code here
	
	if (pThread==NULL)
	{
		return;
	}
	
	CWnd* pBtn = GetDlgItem( IDC_BEGIN);
	CString strText;
	pBtn->GetWindowText( strText );
	static BOOL bFirst=TRUE;
	if (bFirst)
	{
		pThread->ResumeThread();
		bFirst=FALSE;
	}
	
	if ( strText == "暂停" )
	{
		pBtn->SetWindowText("开始");
		pThread->SuspendThread();
	}
	else
	{
		pBtn->SetWindowText("暂停");
		pThread->ResumeThread();
	}
	
}

































































void CBashumaView::OnPaint() 
{
	CPaintDC dc(this); // device context for painting
	
	// TODO: Add your message handler code here
	
	// Do not call CFormView::OnPaint() for painting messages
}

void CBashumaView::OnCancelMode() 
{
	CFormView::OnCancelMode();
	
	// TODO: Add your message handler code here
	
}