eightnumview.cpp

八数码小游戏

// EightNumView.cpp : implementation of the CEightNumView class
//

#include "stdafx.h"
#include "EightNum.h"

#include "EightNumDoc.h"
#include "EightNumView.h"
#include ".\eightnumview.h"

#include <afxstr.h>
#include <atlimage.h>

#include "SetupDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif


// CEightNumView

IMPLEMENT_DYNCREATE(CEightNumView, CView)

BEGIN_MESSAGE_MAP(CEightNumView, CView)
	ON_COMMAND(ID_ACTION_SEARCH, OnActionSearch)
	ON_COMMAND(ID_ACTION_SHOWSTEPS, OnActionShowsteps)
	ON_WM_TIMER()
	ON_UPDATE_COMMAND_UI(ID_ACTION_SEARCH, OnUpdateActionSearch)
	ON_UPDATE_COMMAND_UI(ID_ACTION_SHOWSTEPS, OnUpdateActionShowsteps)
	ON_COMMAND(ID_ACTION_NEWDESTINATION, OnActionNewdestination)
	ON_UPDATE_COMMAND_UI(ID_ACTION_NEWDESTINATION, OnUpdateActionNewdestination)
	ON_COMMAND(ID_SETUP_PREFERENCES, OnSetupPreferences)
END_MESSAGE_MAP()

// CEightNumView construction/destruction

CEightNumView::CEightNumView()
{
	// TODO: add construction code here
	interval = 500; // default parameters

	srand((unsigned)time(NULL)); // seed the random number generator
	inited = true;
	found = false;
	showing = false;
	showImmediate = FALSE;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			initState.num[i][j] = 3 * i + j;

	// generate the destination state and insert it into Open
	RandomDest();
	Open.HeadInsert(&destState);
	currentState = &initState;
}

CEightNumView::~CEightNumView()
{
}

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

	return CView::PreCreateWindow(cs);
}

// CEightNumView drawing

void CEightNumView::OnDraw(CDC* pDC)
{
	CEightNumDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	if (!pDoc)
		return;

	// TODO: add draw code for native data here
	CString filename;
	HDC hdc = pDC->GetSafeHdc();
	CImage image;

	image.Destroy();
	image.Load("bmp\\fr.bmp");
	image.BitBlt(hdc, 144, 0, 6, 152, 0, 0);
	image.BitBlt(hdc, 344, 0, 6, 152, 0, 0);
	image.Destroy();
	image.Load("bmp\\fb.bmp");
	image.BitBlt(hdc, 0, 144, 144, 8, 0, 0);
	image.BitBlt(hdc, 200, 144, 144, 8, 0, 0);
	// paint the current state
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			int number = currentState->num[i][j];
			if (number != 0)
			{
				filename.Format("bmp\\%d.bmp", number);
				image.Destroy();
				image.Load(filename);
				image.BitBlt(hdc, 48 * j, 48 * i, 48, 48, 0, 0);
			}
			else
			{
				pDC->SelectStockObject(GRAY_BRUSH);
				pDC->Rectangle(48 * j, 48 * i, 48 * (j + 1), 48 * (i + 1));
			}
		}
	}

	// a line between current and dest state.
	pDC->MoveTo(172, 0);
	pDC->LineTo(172, 150);

	// paint the destination state
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			int number = destState.num[i][j];
			if (number != 0)
			{
				filename.Format("bmp\\%d.bmp", number);
				image.Destroy();
				image.Load(filename);
				image.BitBlt(hdc, 200 + 48 * j, 48 * i, 48, 48, 0, 0);
			}
			else
			{
				pDC->SelectStockObject(GRAY_BRUSH);
				pDC->Rectangle(200 + 48 * j, 48 * i, 200 + 48 * (j + 1), 48 * (i + 1));
			}
		}
	}

	CString str = "current State                          Destination State";
	pDC->TextOut(30, 157, str);
	str = "Find some useful info from 'Help' menu.";
	pDC->MoveTo(40, 188);
	pDC->LineTo(310, 188);
	pDC->TextOut(45, 193, str);
}


// CEightNumView diagnostics

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

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

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


// CEightNumView message handlers

void CEightNumView::Expand()
{
	// Delete the first node in Open and insert it into Closed
	CState* node = Open.HeadDelete();
	Closed.HeadInsert(node);

	bool sortNeeded = false;
	for (int i = 0; i < 4; i++)
	{
		CState* child = NULL;
		if (!node->NewChild(i, &initState, child))
			continue;

		// is the destination state reached?
		if (::Distance(child, &initState) == 0)
		{
			// let current node be the initial state's parent
			initState.parent = node;
			initState.g = child->g;
			initState.h = 0;
			node->childNum--;
			delete child;
			throw initState.g; // use exception to notify discovery
		}

		CState* existed;
		/* first search Closed, for there must be a new node duplicate with 
		   its ancestor */
		if (Closed.Search(child, existed) || Open.Search(child, existed))
		{
			if (existed->g > child->g)
			{
				sortNeeded = true; // need re-sort, for the heuristic information
								   // may be modified.
				existed->UpdateChildren(child->g - existed->g);
				existed->parent->RemoveChild(existed);
				node->child[node->childNum - 1] = existed;
				existed->parent = node;
			}
			else
				node->childNum--;

			delete child;
		}
		else // a true new node, insert it into Open.
			Open.OrderInsert(child);
	}
	if (sortNeeded)
		Open.Sort();
}

void CEightNumView::OnActionSearch()
{
	// TODO: Add your command handler code here

	/* just delete a node from Open and expand it, the 
	   mechanism generating the destination ensures that 
	   the path exists. 
	   Catch the exception and we know that path found and
	   the number of steps is also known. */
	BeginWaitCursor();

	try {
		while (true)
		{
			Expand();
		}
	}
	catch(int steps)
	{
		EndWaitCursor();

		inited = false;
		found = true;
		CString str;
		str.Format("Got it! %d steps total.", steps);
		if (showImmediate)
			str += "\nI'll show you now!";
		MessageBox(str);
		if (showImmediate)
			OnActionShowsteps();
	}
}

void CEightNumView::OnActionShowsteps()
{
	// TODO: Add your command handler code here

	// to show the steps clearly, use a timer
	found = false; // initialize for a new round
	showing = true;
	SetTimer(1, interval, NULL);
}

void CEightNumView::OnTimer(UINT nIDEvent)
{
	// TODO: Add your message handler code here and/or call default

	// get next state on the path
	CState* nextState = currentState->parent;
	// is path end?
	if (!nextState)
	{
		showing = false;
		KillTimer(1); // kill the timer
		destState.Free(); // release memory
		Open.Free();
		Closed.Free();
		return;
	}

	/* the code below is for an effect of animation.
	   just help to see clearer, no relation with
	   the core algorithm */
	int r0, c0, r1, c1;
	currentState->GetPos(0, r0, c0);
	nextState->GetPos(0, r1, c1);
	CRect newBlank;
	newBlank = CRect(48 * c1, 48 * r1, 48 * (c1 + 1), 48 * (r1 + 1));

	int x = c1 * 48;
	int y = r1 * 48;
	CString filename;
	CClientDC dc(this);
	HDC hdc = dc.GetSafeHdc();
	CImage image;
	filename.Format("bmp\\%d.bmp", currentState->num[r1][c1]);
	image.Load(filename);
	for (int i = 0; i < 4; i++)
	{
		dc.SelectStockObject(GRAY_BRUSH);
		dc.Rectangle(newBlank);
		x += (c0 - c1) * 12;
		y += (r0 - r1) * 12;
		image.BitBlt(hdc, x, y, 48, 48, 0, 0);
		Sleep(50); // delay 50 milliseconds
	}
	currentState = nextState;

	CView::OnTimer(nIDEvent);
}

void CEightNumView::OnUpdateActionSearch(CCmdUI *pCmdUI)
{
	// TODO: Add your command update UI handler code here
	pCmdUI->Enable(inited && !found);
}

void CEightNumView::OnUpdateActionShowsteps(CCmdUI *pCmdUI)
{
	// TODO: Add your command update UI handler code here
	pCmdUI->Enable(found);
}

void CEightNumView::RandomDest()
{
	/***********************************************************************
	Generate new destination until it's EVEN state.
	That ensures the two states are mutually communicable.
	***********************************************************************/
	destState = initState;
	destState.parent = NULL;
	destState.g = 0;
	int r;
	do {
		bool used[9] = {false};
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
			{
				do {
					r = rand() % 9;
				} while (used[r]);
				used[r] = true;
				destState.num[i][j] = r;
			}
	} while (!destState.IsEvenState());
}

void CEightNumView::OnActionNewdestination()
{
	// TODO: Add your command handler code here
	RandomDest();
	inited = true;
	Open.HeadInsert(&destState);
	currentState = &initState;
	Invalidate();
}

void CEightNumView::OnUpdateActionNewdestination(CCmdUI *pCmdUI)
{
	// TODO: Add your command update UI handler code here
	pCmdUI->Enable(!inited && !found && !showing);
}

void CEightNumView::OnSetupPreferences()
{
	// TODO: Add your command handler code here
	CSetupDlg dlg;
	dlg.m_iInterval = interval;
	dlg.m_bShow = showImmediate;
	if (dlg.DoModal() == IDOK)
	{
		interval = dlg.m_iInterval;
		showImmediate = dlg.m_bShow;
	}
}