game.cpp

设计一类peg jump问题的求解系统

// game.cpp: implementation of the game class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "game.h"


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
void game::setBoard(struct Node *b,int type)
{
	int initData[8][7][7]={
		{	{2,2,0,0,0,2,2},	
			{2,2,0,1,0,2,2},
			{0,0,1,1,1,0,0},
			{0,0,0,1,0,0,0},
			{0,0,0,1,0,0,0},
			{2,2,0,0,0,2,2},
			{2,2,0,0,0,2,2}	},//cross 

		{	{2,2,0,0,0,2,2},	
			{2,2,0,1,0,2,2},
			{0,0,0,1,0,0,0},
			{0,1,1,1,1,1,0},
			{0,0,0,1,0,0,0},
			{2,2,0,1,0,2,2},
			{2,2,0,0,0,2,2}	},//plus 

		{	{2,2,1,1,1,2,2},	
			{2,2,1,1,1,2,2},
			{0,0,1,1,1,0,0},
			{0,0,1,0,1,0,0},
			{0,0,0,0,0,0,0},
			{2,2,0,0,0,2,2},
			{2,2,0,0,0,2,2}	},//fireplace 

		{	{2,2,0,1,0,2,2},	
			{2,2,1,1,1,2,2},
			{0,1,1,1,1,1,0},
			{0,0,0,1,0,0,0},
			{0,0,0,1,0,0,0},
			{2,2,1,1,1,2,2},
			{2,2,1,1,1,2,2}	},//uparrow

		{	{2,2,0,0,0,2,2},	
			{2,2,0,1,0,2,2},
			{0,0,1,1,1,0,0},
			{0,1,1,1,1,1,0},
			{1,1,1,1,1,1,1},
			{2,2,0,0,0,2,2},
			{2,2,0,0,0,2,2}	},//5

		{	{2,2,0,1,0,2,2},	
			{2,2,1,1,1,2,2},
			{0,1,1,1,1,1,0},
			{1,1,1,1,1,1,1},
			{0,1,1,1,1,1,0},
			{2,2,1,1,1,2,2},
			{2,2,0,1,0,2,2}	},//6

		{	{2,2,1,1,1,2,2},	
			{2,2,1,1,1,2,2},
			{1,1,1,1,1,1,1},
			{1,1,1,0,1,1,1},
			{1,1,1,1,1,1,1},
			{2,2,1,1,1,2,2},
		{2,2,1,1,1,2,2}	},//7

		{	{2,2,0,0,0,2,2},	
			{2,2,0,0,0,2,2},
			{0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0},
			{2,2,0,0,0,2,2},
			{2,2,0,0,0,2,2}	}//8
	};
	int i ,j,num=0;


	for(i=0; i<7; i++)
	{
		for(j=0; j<7; j++)
		{
			b->m_data[i][j]=initData[type][i][j];
			if(initData[type][i][j]==1)
				num++;
		}
	}
	b->m_num=num;
	b->m_parent=NULL;
}
game::game()
{
	m_searchType=DFS;
	m_board=new node;
	m_boardType = 0;
	m_iStepCount = 0;
	setBoard(m_board,m_boardType);
	m_bAutoRun = false;
	m_solutionFlag =false;
	m_nodeNum = 0;
	m_iTime = 0;
//	m_opened.push_back(m_board);

}

game::~game()
{
	node *pnode=NULL;
}

void game::Init(int style)
{
	m_board = new node;
	setBoard(m_board, style);
	m_bAutoRun = false;
	m_solutionFlag =false;
	m_searchType=DFS;
	m_iStepCount = 0;
//	m_opened.push_back(m_board);
}
void game::DrawBoard(HDC hDC, RECT clientrect)
{
	int cx = clientrect.left  + 30 ;
	int cy = clientrect.top  +40 ;
	int i , j;

	HBRUSH hgirdbkbrush = ::CreateSolidBrush(RGB(255 , 128 , 64));
	HBRUSH hpegbrush = ::CreateSolidBrush(RGB(255 , 255 , 64));
	HBRUSH hbutbrush = ::CreateSolidBrush(RGB(0 , 128 , 255));
	HBRUSH oldbrush = (HBRUSH)::SelectObject(hDC , hgirdbkbrush);
	COLORREF oldbkcolor = SetBkColor(hDC , RGB(0 , 128 , 255));

	RECT rect;

	for (i = 0 ; i < 7 ; i ++)
	{
		for ( j = 0 ; j < 7 ; j ++)
		{
			if(m_board->m_data[i][j]==1|| m_board->m_data[i][j]==0)
			{
				SetRect(&rect , 0 , 0 , 30 , 30);
				OffsetRect(&rect , j * 30 + cx, i * 30 + cy);
				Rectangle(hDC , rect.left , rect.top , rect.right , rect.bottom);
				if(m_board->m_data[i][j]==1)
				{
					SelectObject(hDC,hpegbrush);
					Ellipse(hDC, rect.left+5, rect.top+5,rect.right-5, rect.bottom-5);
					SelectObject(hDC,hgirdbkbrush);
				}
			}

		}
	}

	SelectObject(hDC , hbutbrush);

	cx = clientrect.right  - 100 ;
	cy += 20;
	SetRect(&rect , 0 , 0 , 80 , 20);
	OffsetRect(&rect , cx - 10 , cy);
	Rectangle(hDC , rect.left , rect.top , rect.right , rect.bottom);
	char nodeNum[100];
	sprintf(nodeNum , "%d" , m_nodeNum);
	rect.top += 2;
	DrawText(hDC ,nodeNum , strlen(nodeNum) , &rect , DT_CENTER);





	// draw step rect
	cx = clientrect.right  - 100 ;
	cy += 30;
	SetRect(&rect , 0 , 0 , 80 , 20);
	OffsetRect(&rect , cx - 10 , cy);
	Rectangle(hDC , rect.left , rect.top , rect.right , rect.bottom);
	char step[100];
	sprintf(step , "%d" , m_iStepCount);
	rect.top += 2;

	DrawText(hDC ,step , strlen(step) , &rect , DT_CENTER);


	// draw time rect
	cx = clientrect.right  - 100 ;
	cy += 30;
	SetRect(&rect , 0 , 0 , 80 , 20);
	OffsetRect(&rect , cx - 10 , cy);
	Rectangle(hDC , rect.left , rect.top , rect.right , rect.bottom);
	char time[100];
	sprintf(time , "%d ms" , m_iTime);
	rect.top += 2;

	DrawText(hDC ,time , strlen(time) , &rect , DT_CENTER);



	
/*	
	// draw AutoPlay button
	cx = clientrect.right  - 90 ;
	cy += 50;
	SetRect(&m_rAutoButton , 0 , 0 , 80 , 20);
	OffsetRect(&m_rAutoButton , cx - 10 , cy);
	Rectangle(hDC , m_rAutoButton.left , m_rAutoButton.top , m_rAutoButton.right , m_rAutoButton.bottom);
	char msg2[] = "AutoPlay";
	m_rAutoButton.top += 2;
	DrawText(hDC ,msg2 , strlen(msg2) , &m_rAutoButton , DT_CENTER);
*/

	SetBkColor(hDC , oldbkcolor);
	::SelectObject(hDC , oldbrush);
	DeleteObject(hgirdbkbrush);
	DeleteObject(hbutbrush);
}



void game::PegSolution()
{
	m_opened.push_back(m_board);
	node *pb = NULL;
	node *pfb = NULL;
	m_nodeNum =0 ;

	while(!m_opened.empty())
	{
//		if(m_searchType == DFS)
		{
			pb=(node*)m_opened.front();
			m_opened.pop_front();
		}
//		else if(m_searchType == BFS)
//		{
//			pb=(node*)m_opened.back();
//			m_opened.pop_back();
//		}
		m_closed.push(pb);
		if(pb->m_num==1)
		{
			m_closed.pop();

			m_solutionFlag=true;
			m_solution.push_front(pb);

			pfb=(node *)pb->m_parent;
			while(pfb)
			{
				m_solution.push_front(pfb);
				pfb=(node *)pfb->m_parent;
			}


			break;
		}
		else
		{
			for(int i=0; i<7; i++)
			{
				for(int j=0; j<7; j++)
				{
					if(pb->m_data[i][j]==1)
					{
						if( (j>=2) && (pb->m_data[i][j-1]==1) && (pb->m_data[i][j-2]==0))//left
						{
							movepeg(pb,i,j,0);
							m_nodeNum ++;
						}
						if((i>=2) && (pb->m_data[i-1][j]==1) && (pb->m_data[i-2][j]==0))//top
						{
							movepeg(pb,i,j,1);
							m_nodeNum ++;
						}

						if((i<=4) && (pb->m_data[i+1][j]==1) && (pb->m_data[i+2][j]==0))//bottom
						{
							movepeg(pb,i,j,3);
							m_nodeNum ++;
						}
						if((j<=4) && (pb->m_data[i][j+1]==1)&& (pb->m_data[i][j+2]==0))//right
						{
							movepeg(pb,i,j,2);
							m_nodeNum ++;
						}

					}
				}
			}

			
		}
	}

}





unsigned __stdcall MoveChessThread(LPVOID pParam)
{

	node* psolve;
	game * pGame = (game *)pParam;
	RECT rect;
	pGame->m_iStepCount = 0;
	::GetClientRect(pGame->m_hClientWin , &rect);
/*	for ( ; !pGame->m_solution.empty() ; pGame->m_solution.pop_front())
	{
		psolve=(node*)pGame->m_solution.front();
		pGame->m_board=psolve;
		pGame->m_iStepCount ++;
		InvalidateRect( pGame->m_hClientWin , &rect , false);
		Sleep(600);
		delete psolve;
	}
	*/
	for (list<node*>::iterator pos =pGame->m_solution.begin()  ; pos != pGame->m_solution.end() ;++pos)
	{
		psolve=*pos;
		pGame->m_board=psolve;
		pGame->m_iStepCount ++;
		InvalidateRect( pGame->m_hClientWin , &rect , false);
		Sleep(600);
	}

	char msg[100];
	sprintf(msg , "^_^ ! 搞定了!\r\n计算步骤用时%d毫秒" , pGame->m_iTime);
	MessageBox(NULL , msg , "~_~" , 0);
	pGame->m_bAutoRun = false;
	return 0L;
}

void game::OnAutoplay(HWND hWin)
{
	despath();
	clock_t tim = clock();
	PegSolution();
	m_iTime=clock()-tim;
	if(m_solutionFlag==false)
	{
		MessageBox(NULL,"not solution!", 0, 0);
		return;
	}
	if (m_bAutoRun) return;
	m_bAutoRun = true;
	
	m_hClientWin = hWin;
	

	HANDLE hThread;
	unsigned threadID;
	hThread = (HANDLE)_beginthreadex( NULL, 0, &MoveChessThread, this, 0, &threadID);
//	CWinThread *pT = AfxBeginThread((AFX_THREADPROC)MoveChessThread,  (void*)threadID);
//	hThread = pT->m_hThread;




}




void game::movepeg(node* pf,int x, int y, int dir)
{
	node * pChildNode= new node;
	for(int i=0; i<7; i++)
	{
		for(int j=0; j<7; j++)
		{
			pChildNode->m_data[i][j]=pf->m_data[i][j];
		}
	}
	pChildNode->m_data[x][y]=0;
	switch(dir)
	{
	case 0:
		pChildNode->m_data[x][y-1]=0;
		pChildNode->m_data[x][y-2]=1;
		break;
	case 1:
		pChildNode->m_data[x-1][y]=0;
		pChildNode->m_data[x-2][y]=1;
		break;
	case 2:
		pChildNode->m_data[x][y+1]=0;
		pChildNode->m_data[x][y+2]=1;
		break;
	case 3:
		pChildNode->m_data[x+1][y]=0;
		pChildNode->m_data[x+2][y]=1;
		break;
	default:
		break;
	}

	pChildNode->m_num=pf->m_num-1;
	pChildNode->m_parent=pf;
	if(m_searchType == DFS)
	{
		m_opened.push_front(pChildNode);
	}
	else
	{
		m_opened.push_back(pChildNode);
	}


}

void game::despath()
{
	node *pnode=NULL;
	while(!m_opened.empty())
	{
		pnode=(node *)m_opened.front();
		delete pnode;
		m_opened.pop_front();

	}
	while(!m_closed.empty())
	{
		pnode=(node *)m_closed.front();
		if(pnode != NULL)
			delete pnode;
		m_closed.pop();
	}
	while(!m_solution.empty())
	{
		m_solution.pop_back();
	}

}

void game::ResetBoardType(int style)
{

	despath();
	m_board = new node;
	setBoard(m_board, style);
	m_bAutoRun = false;
	m_solutionFlag =false;
	m_searchType=DFS;
	m_opened.push_back(m_board);

}