SDK实现迷宫算法（C++版）

/////////////////////////////////////////////////////////////////////////////// // 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 ( ! pt