maze.cpp

迷宫算法.rar

///////////////////////////////////////////////////////////////////////////////
//	Maze.cpp
//	Date: 2004-8-5 21:16
//	A moving ball.
//
///////////////////////////////////////////////////////////////////////////////

#include <assert.h>
#include "Maze.h"

#define	ID_TIMER	1

///////////////////////////////////////////////////////////////////////////////
// My global variable

// Define the maze structure 8 row * 8 column
				// Column from 0 to 7
int	gnArrMaze[ 8 ][ 8 ] = {	{ 1, 1, 2, 1, 1, 1, 1, 1 },	/* Row 0 */
				{ 1, 0, 0, 1, 0, 0, 0, 1 },	/* Row 1 */
				{ 1, 1, 0, 0, 0, 1, 1, 1 },	/* Row 2 */
				{ 1, 0, 0, 1, 0, 0, 0, 1 },	/* Row 3 */
				{ 1, 1, 1, 1, 0, 1, 1, 1 },	/* Row 4 */
				{ 1, 0, 0, 0, 0, 0, 0, 1 },	/* Row 5 */
				{ 1, 0, 1, 0, 1, 0, 0, 1 },	/* Row 6 */
				{ 1, 1, 1, 3, 1, 1, 1, 1 } };	/* Row 7 */

BOOL	bPass[ 8 ][ 8 ] = { FALSE };

BOOL	bStart = FALSE,
	bSearch = FALSE;

enum Direction { right, left, forward, back };

const moveRight = 1;
const moveLeft = -1;
const moveForward = 1;
const moveBack = -1;

int	gnRow = 0,
	gnColumn = 0;

void Search( const HWND& hWnd, HBITMAP& hbmpBall );
void Start( const HWND& hWnd, const HBITMAP& hbmpBall );
BOOL CanMove( int nRow, int nColumn, int nDirection );

Node* ptrFirst = NULL;
Node* ptrLast = NULL;
Node* ptr = NULL;

///////////////////////////////////////////////////////////////////////////////

int WINAPI WinMain( HINSTANCE hInst, HINSTANCE hPrevInst, char* cmdParam, int cmdShow )
{
	char className[] = "Maze";

	MovingBall MovingBallClass( WindowsProcedure, className, hInst );
	MovingBallClass.Register();

	WinMaker win( "Maze", className, hInst );
	win.Show( cmdShow );

	MSG msg;
	int status;

	while( ( status = ::GetMessage( & msg, NULL, 0, 0 ) ) != 0 )
	{
		if ( status == -1 )
			return -1;
		::TranslateMessage( & msg );
		::DispatchMessage( & msg );
	}

	return msg.wParam;
}

///////////////////////////////////////////////////////////////////////////////

MovingBall::MovingBall( WNDPROC wndProc, const char* className, HINSTANCE hInstance )
{
	_class.style = 0;
	_class.lpfnWndProc = wndProc;		// Windows procedure: mandatory
	_class.cbClsExtra = 0;
	_class.cbWndExtra = 0;
	_class.hInstance = hInstance;
	_class.hIcon = 0;			// Owner of class: mandatory
	_class.hCursor = ::LoadCursor( 0, IDC_ARROW );
	_class.hbrBackground = (HBRUSH) ( COLOR_WINDOW + 1 );	// Optional
	_class.lpszMenuName = 0;
	_class.lpszClassName = className;	// Mandatory	
}

WinMaker::WinMaker( const char* szCaption, const char* className, HINSTANCE hInstance )
{
	DWORD	dwStyle = WS_OVERLAPPEDWINDOW;
	dwStyle &= ~WS_SIZEBOX;
	dwStyle &= ~WS_MAXIMIZEBOX;
	dwStyle &= ~WS_MINIMIZEBOX;

	_hWnd = ::CreateWindow(
			className,		// Name of a registered window class
			szCaption,		// Window caption
			dwStyle,		// Window style
			CW_USEDEFAULT,		// x position
			CW_USEDEFAULT,		// y position
			40 * 8,			// width
			40 * 10,		// height
			0,			// Handle to parent window
			0,			// Handle to menu
			hInstance,		// Application instance
			0 );			// Window creation data
}

///////////////////////////////////////////////////////////////////////////////

LRESULT CALLBACK WindowsProcedure( HWND hWnd, UINT uMessage, WPARAM wParam, LPARAM lParam )
{
	static	int	cxClient, cyClient;
	static	HBITMAP	hbmpBall = NULL,
			hbmpTile = NULL;

	int		i = 0, j = 0;	// For the loop operation

	HDC		hdc = NULL,
			hdcMem = NULL;
	HINSTANCE 	hInst = NULL;

	PAINTSTRUCT	ps;

	switch( uMessage )
	{
		case WM_CREATE:
			hInst = ( (LPCREATESTRUCT) lParam )->hInstance;
			assert( hInst );
			hbmpBall = ::LoadBitmap( hInst, TEXT( "ball" ) );
			assert( hbmpBall );
			hbmpTile = ::LoadBitmap( hInst, TEXT( "tile" ) );
			assert( hbmpTile );

			::SetTimer( hWnd, ID_TIMER, 150, NULL );
			return 0;

		case WM_SIZE:
			cxClient = LOWORD( lParam );
			cyClient = HIWORD( lParam );
			return 0;

		case WM_PAINT:
			hdc = ::BeginPaint( hWnd, & ps );
			assert( hdc );
			hdcMem = ::CreateCompatibleDC( hdc );
			assert( hdcMem );

			::SelectObject( hdcMem, hbmpTile );
			for ( i = 0; i < 8; i++ )
				for ( j = 0; j < 8; j++ )
				{
					if ( gnArrMaze[ i ][ j ] == 1 )
						::BitBlt(
							hdc,
							j * 40, i * 40,
							40, 40,
							hdcMem,
							0, 0,
							SRCCOPY );
				}
			i = 0;
			j = 0;
			::DeleteDC( hdcMem );
			::EndPaint( hWnd, & ps );

		case WM_KEYDOWN:
			if ( (int) wParam == VK_F1 )
			{
				bStart = TRUE;
				bSearch = FALSE;
			}
			return 0;

		case WM_TIMER:
			if ( bStart )
				Start( hWnd, hbmpBall );
			if ( bSearch )
				Search( hWnd, hbmpBall );
			return 0;
			
		case WM_DESTROY:
			// Release the resource for the simulated stack
			for ( Node* p = ptrFirst; p; )
			{
				assert( p );
				ptrFirst = p->next;
				delete p;
				
				p = ptrFirst;
			}
		
			::DeleteObject( hbmpBall );
			::DeleteObject( hbmpTile );
			::KillTimer( hWnd, ID_TIMER );

			::PostQuitMessage( 0 );
			return 0;
	}

	return ::DefWindowProc( hWnd, uMessage, wParam, lParam );
}

///////////////////////////////////////////////////////////////////////////////
//	Search
//	Result: void
//	Parameters
//		pNode& pMazeEntry: The entry of the maze
//		HWND& hWnd: The HWND of the current window. 
//		HBITMAP& hbmpball: The handle to the ball bitmap
//
///////////////////////////////////////////////////////////////////////////////

void Search( const HWND& hWnd, HBITMAP& hbmpBall )
{
	HDC	hdc = NULL,
		hdcMem = NULL;
	hdc = ::GetDC( hWnd );
	assert( hdc );
	hdcMem = ::CreateCompatibleDC( hdc );
	assert( hdcMem );
	::SelectObject( hdcMem, hbmpBall );

	::BitBlt(
		hdc,
		gnColumn * 40,  gnRow * 40,
		40, 40,
		hdcMem,
		0, 0,
		WHITENESS );

	if ( CanMove( gnRow, gnColumn, right ) )
	{
		gnColumn += moveRight;

		bPass[ gnRow ][ gnColumn ] = TRUE;
		
		ptr = new Node;
		ptr->nRow = gnRow;
		ptr->nColumn = gnColumn;
		ptr->next = NULL;
		ptr->previou = NULL;

		assert( ptrLast );
		ptrLast->next = ptr;
		ptr->previou = ptrLast;
		ptrLast = ptr;
		
		//char str[ 128 ];
		//wsprintf( str, "row %d column %d", gnRow, gnColumn );
		//MessageBox( NULL, str, NULL, MB_OK );
	}
	else  if ( CanMove( gnRow, gnColumn, left ) )
	{
		gnColumn += moveLeft;

		bPass[ gnRow ][ gnColumn ] = TRUE;

		ptr = new Node;
		ptr->nRow = gnRow;
		ptr->nColumn = gnColumn;
		ptr->next = NULL;
		ptr->previou = NULL;

		assert( ptrLast );
		ptrLast->next = ptr;
		ptr->previou = ptrLast;
		ptrLast = ptr;

		//char str[ 128 ];
		//wsprintf( str, "row %d column %d", gnRow, gnColumn );
		//MessageBox( NULL, str, NULL, MB_OK );	
	}
	else if ( CanMove( gnRow, gnColumn, forward ) )
	{
		gnRow += moveForward;

		bPass[ gnRow ][ gnColumn ] = TRUE;

		ptr = new Node;
		ptr->nRow = gnRow;
		ptr->nColumn = gnColumn;
		ptr->next = NULL;
		ptr->previou = NULL;

		assert( ptrLast );
		ptrLast->next = ptr;
		ptr->previou = ptrLast;
		ptrLast = ptr;
	
		//char str[ 128 ];
		//wsprintf( str, "row %d column %d", gnRow, gnColumn );
		//MessageBox( NULL, str, NULL, MB_OK );
	}
	else if ( CanMove( gnRow, gnColumn, back ) )
	{
		gnRow += moveBack;

		bPass[ gnRow ][ gnColumn ] = TRUE;

		ptr = new Node;
		ptr->nRow = gnRow;
		ptr->nColumn = gnColumn;
		ptr->next = NULL;
		ptr->previou = NULL;

		assert( ptrLast );
		ptrLast->next = ptr;
		ptr->previou = ptrLast;
		ptrLast = ptr;
	
		//char str[ 128 ];
		//wsprintf( str, "row %d column %d", gnRow, gnColumn );
		//MessageBox( NULL, str, NULL, MB_OK );
	}
	else if ( bPass[ gnRow ][ gnColumn ] )
	{

		assert( ptrLast );
		if ( ptrLast )
		{
			gnRow = ptrLast->nRow;
			gnColumn = ptrLast->nColumn;
			// Becareful, if the ptrLast is the only node...
			ptrLast = ptrLast->previou;
			if ( ptrLast )
				delete ( ptrLast->next );
		}
	}
	
	if ( ! ptrLast )
	{
		bSearch = FALSE;
	}

	if ( gnArrMaze[ gnRow ][ gnColumn ] == 3 )
	{
		bSearch = FALSE;
	}

	::BitBlt(
		hdc,
		gnColumn * 40,  gnRow * 40,
		40, 40,
		hdcMem,
		0, 0,
		SRCCOPY );
		
	::ReleaseDC( hWnd, hdc );
	::DeleteDC( hdcMem );
}

///////////////////////////////////////////////////////////////////////////////
//	Start
//	Result: void
//	Parameters
//		pNode& pMazeEntry: The entry of the maze
//		HWND& hWnd: The HWND of the current window. 
//		HBITMAP& hbmpball: The handle to the ball bitmap
//
///////////////////////////////////////////////////////////////////////////////

void Start( const HWND& hWnd, const HBITMAP& hbmpBall )
{
	HDC	hdc = NULL,
		hdcMem = NULL;
	hdc = ::GetDC( hWnd );
	assert( hdc );
	hdcMem = ::CreateCompatibleDC( hdc );
	assert( hdcMem );
	::SelectObject( hdcMem, hbmpBall );

	for ( int i = 0; i < 8; i++ )
		for ( int j = 0; j < 8; j++ )
			if ( gnArrMaze[ i ][ j ] == 2 )
			{
				::BitBlt(
					hdc,
					j * 40, i * 40,
					40, 40,
					hdcMem,
					0, 0,
					SRCCOPY );
				gnRow = i;
				gnColumn = j;
				break;
			}
	bStart = FALSE;
	bSearch = TRUE;

	bPass[ gnRow ][ gnColumn ] = TRUE;

	Node* ptr = new Node;
	ptr->nRow = gnRow;
	ptr->nColumn = gnColumn;
	ptr->next = NULL;
	ptr->previou = NULL;		

	assert( ptrFirst == NULL );
	assert( ptrLast == NULL );
	ptrFirst = ptrLast = ptr;	

	::ReleaseDC( hWnd, hdc );
	::DeleteDC( hdcMem );
}

///////////////////////////////////////////////////////////////////////////////
//	CanMove
//	Result:	BOOL.
//		TRUE: The ball can move in this direction
//		FALSE: The ball can't move int this direction
//	Parameters:
//		int	nRow: The row status of the ball
//		int	nColumn: The column status of the ball.
//		int	nDirection:
//			left = back = -1, right = forward = 1;
//
///////////////////////////////////////////////////////////////////////////////

BOOL CanMove( int nRow, int nColumn, int nDirection )
{
	BOOL bResult = FALSE;

	switch( nDirection )
	{
		case right:
			if ( ( nColumn + moveRight ) > 7 )
				bResult = FALSE;
			else if ( gnArrMaze[ nRow ][ nColumn + moveRight ] == 1 )
				bResult = FALSE;
			else if ( ! bPass[ nRow ][ nColumn + moveRight ] )
				bResult = TRUE;
			break;

		case left:
			if ( ( nColumn + moveLeft ) < 0 )
				bResult = FALSE;
			else if ( gnArrMaze[ nRow ][ nColumn + moveLeft ] == 1 )
				bResult = FALSE;
			else if ( ! bPass[ nRow ][ nColumn + moveLeft ] )
				bResult = TRUE;
			break;

		case forward:
			if ( ( nRow + moveForward ) > 7 )
				bResult = FALSE;
			else if ( gnArrMaze[ nRow + moveForward ][ nColumn ] == 1 )
				bResult = FALSE;
			else if ( ! bPass[ nRow + moveForward ][ nColumn ] )
				bResult = TRUE;
			break;

		case back:
			if ( ( nRow + moveBack ) < 0 )
				bResult = FALSE;
			else if ( gnArrMaze[ nRow + moveBack ][ nColumn ] == 1 )
				bResult = FALSE;
			else if ( ! bPass[ nRow + moveBack ][ nColumn ] )
				bResult = TRUE;
			break;
	}

	return bResult;
}