For a maze generated by this task, write a function that finds (and displays) the shortest path between two cells. Note that because these mazes are generated by the Depth-first search algorithm, they contain no circular paths, and a simple depth-first tree search can be used.
Generator and solver combined. The generator is the same found in Maze generation
#include <windows.h> #include <iostream> #include <string> //-------------------------------------------------------------------------------------------------- using namespace std; //-------------------------------------------------------------------------------------------------- const int BMP_SIZE = 512, CELL_SIZE = 8; //-------------------------------------------------------------------------------------------------- enum directions { NONE, NOR = 1, EAS = 2, SOU = 4, WES = 8 }; //-------------------------------------------------------------------------------------------------- class myBitmap { public: myBitmap() : pen( NULL ) {} ~myBitmap() { DeleteObject( pen ); DeleteDC( hdc ); DeleteObject( bmp ); } bool create( int w, int h ) { BITMAPINFO bi; ZeroMemory( &bi, sizeof( bi ) ); bi.bmiHeader.biSize = sizeof( bi.bmiHeader ); bi.bmiHeader.biBitCount = sizeof( DWORD ) * 8; bi.bmiHeader.biCompression = BI_RGB; bi.bmiHeader.biPlanes = 1; bi.bmiHeader.biWidth = w; bi.bmiHeader.biHeight = -h; HDC dc = GetDC( GetConsoleWindow() ); bmp = CreateDIBSection( dc, &bi, DIB_RGB_COLORS, &pBits, NULL, 0 ); if( !bmp ) return false; hdc = CreateCompatibleDC( dc ); SelectObject( hdc, bmp ); ReleaseDC( GetConsoleWindow(), dc ); width = w; height = h; return true; } void clear() { ZeroMemory( pBits, width * height * sizeof( DWORD ) ); } void setPenColor( DWORD clr ) { if( pen ) DeleteObject( pen ); pen = CreatePen( PS_SOLID, 1, clr ); SelectObject( hdc, pen ); } void saveBitmap( string path ) { BITMAPFILEHEADER fileheader; BITMAPINFO infoheader; BITMAP bitmap; DWORD wb; GetObject( bmp, sizeof( bitmap ), &bitmap ); DWORD* dwpBits = new DWORD[bitmap.bmWidth * bitmap.bmHeight]; ZeroMemory( dwpBits, bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD ) ); ZeroMemory( &infoheader, sizeof( BITMAPINFO ) ); ZeroMemory( &fileheader, sizeof( BITMAPFILEHEADER ) ); infoheader.bmiHeader.biBitCount = sizeof( DWORD ) * 8; infoheader.bmiHeader.biCompression = BI_RGB; infoheader.bmiHeader.biPlanes = 1; infoheader.bmiHeader.biSize = sizeof( infoheader.bmiHeader ); infoheader.bmiHeader.biHeight = bitmap.bmHeight; infoheader.bmiHeader.biWidth = bitmap.bmWidth; infoheader.bmiHeader.biSizeImage = bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD ); fileheader.bfType = 0x4D42; fileheader.bfOffBits = sizeof( infoheader.bmiHeader ) + sizeof( BITMAPFILEHEADER ); fileheader.bfSize = fileheader.bfOffBits + infoheader.bmiHeader.biSizeImage; GetDIBits( hdc, bmp, 0, height, ( LPVOID )dwpBits, &infoheader, DIB_RGB_COLORS ); HANDLE file = CreateFile( path.c_str(), GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL ); WriteFile( file, &fileheader, sizeof( BITMAPFILEHEADER ), &wb, NULL ); WriteFile( file, &infoheader.bmiHeader, sizeof( infoheader.bmiHeader ), &wb, NULL ); WriteFile( file, dwpBits, bitmap.bmWidth * bitmap.bmHeight * 4, &wb, NULL ); CloseHandle( file ); delete [] dwpBits; } HDC getDC() const { return hdc; } int getWidth() const { return width; } int getHeight() const { return height; } private: HBITMAP bmp; HDC hdc; HPEN pen; void *pBits; int width, height; }; //-------------------------------------------------------------------------------------------------- class mazeGenerator { public: mazeGenerator() { _world = 0; _bmp.create( BMP_SIZE, BMP_SIZE ); _bmp.setPenColor( RGB( 0, 255, 0 ) ); } ~mazeGenerator() { killArray(); } BYTE* getMaze() const { return _world; } void create( int side ) { _s = side; generate(); } private: void generate() { killArray(); _world = new BYTE[_s * _s]; ZeroMemory( _world, _s * _s ); _ptX = rand() % _s; _ptY = rand() % _s; carve(); } void carve() { while( true ) { int d = getDirection(); if( d < NOR ) return; switch( d ) { case NOR: _world[_ptX + _s * _ptY] |= NOR; _ptY--; _world[_ptX + _s * _ptY] = SOU | SOU << 4; break; case EAS: _world[_ptX + _s * _ptY] |= EAS; _ptX++; _world[_ptX + _s * _ptY] = WES | WES << 4; break; case SOU: _world[_ptX + _s * _ptY] |= SOU; _ptY++; _world[_ptX + _s * _ptY] = NOR | NOR << 4; break; case WES: _world[_ptX + _s * _ptY] |= WES; _ptX--; _world[_ptX + _s * _ptY] = EAS | EAS << 4; } } } int getDirection() { int d = 1 << rand() % 4; while( true ) { for( int x = 0; x < 4; x++ ) { if( testDir( d ) ) return d; d <<= 1; if( d > 8 ) d = 1; } d = ( _world[_ptX + _s * _ptY] & 0xf0 ) >> 4; if( !d ) return -1; switch( d ) { case NOR: _ptY--; break; case EAS: _ptX++; break; case SOU: _ptY++; break; case WES: _ptX--; break; } d = 1 << rand() % 4; } } bool testDir( int d ) { switch( d ) { case NOR: return ( _ptY - 1 > -1 && !_world[_ptX + _s * ( _ptY - 1 )] ); case EAS: return ( _ptX + 1 < _s && !_world[_ptX + 1 + _s * _ptY] ); case SOU: return ( _ptY + 1 < _s && !_world[_ptX + _s * ( _ptY + 1 )] ); case WES: return ( _ptX - 1 > -1 && !_world[_ptX - 1 + _s * _ptY] ); } return false; } void killArray() { if( _world ) delete [] _world; } BYTE* _world; int _s, _ptX, _ptY; myBitmap _bmp; }; //-------------------------------------------------------------------------------------------------- class mazeSolver { public: mazeSolver() { _bmp.create( BMP_SIZE, BMP_SIZE ); _pts = 0; } ~mazeSolver() { killPoints(); } void solveIt( BYTE* maze, int size, int sX, int sY, int eX, int eY ) { _lastDir = NONE; _world = maze; _s = size; _sx = sX; _sy = sY; _ex = eX; _ey = eY; for( int y = 0; y < _s; y++ ) for( int x = 0; x < _s; x++ ) _world[x + _s * y] &= 0x0f; _world[_sx + _s * _sy] |= NOR << 4; killPoints(); _pts = new BYTE[_s * _s]; ZeroMemory( _pts, _s * _s ); findTheWay(); _sx = sX; _sy = sY; display(); } private: int invert( int d ) { switch( d ) { case NOR: return SOU; case SOU: return NOR; case WES: return EAS; case EAS: return WES; } return NONE; } void updatePosition( int d ) { switch( d ) { case NOR: _sy--; break; case EAS: _sx++; break; case SOU: _sy++; break; case WES: _sx--; } } void findTheWay() { while( true ) { int d = getDirection(); if( d < NOR ) return; _lastDir = invert( d ); _world[_sx + _s * _sy] |= d; _pts[_sx + _s * _sy] = d; updatePosition( d ); if( _sx == _ex && _sy == _ey ) return; _world[_sx + _s * _sy] |= _lastDir << 4; } } int getDirection() { int d = 1 << rand() % 4; while( true ) { for( int x = 0; x < 4; x++ ) { if( testDirection( d ) ) return d; d <<= 1; if( d > 8 ) d = 1; } d = ( _world[_sx + _s * _sy] & 0xf0 ) >> 4; if( !d ) return -1; _pts[_sx + _s * _sy] = 0; updatePosition( d ); _lastDir = invert( d ); d = 1 << rand() % 4; } } bool testDirection( int d ) { if( d == _lastDir || !( _world[_sx + _s * _sy] & d ) ) return false; switch( d ) { case NOR: return _sy - 1 > -1 && !( _world[_sx + _s * ( _sy - 1 )] & 0xf0 ); case EAS: return _sx + 1 < _s && !( _world[_sx + 1 + _s * _sy] & 0xf0 ); case SOU: return _sy + 1 < _s && !( _world[_sx + _s * ( _sy + 1 )] & 0xf0 ); case WES: return _sx - 1 > -1 && !( _world[_sx - 1 + _s * _sy] & 0xf0 ); } return false; } void display() { _bmp.setPenColor( RGB( 0, 255, 0 ) ); _bmp.clear(); HDC dc = _bmp.getDC(); for( int y = 0; y < _s; y++ ) { int yy = y * _s; for( int x = 0; x < _s; x++ ) { BYTE b = _world[x + yy]; int nx = x * CELL_SIZE, ny = y * CELL_SIZE; if( !( b & NOR ) ) { MoveToEx( dc, nx, ny, NULL ); LineTo( dc, nx + CELL_SIZE + 1, ny ); } if( !( b & EAS ) ) { MoveToEx( dc, nx + CELL_SIZE, ny, NULL ); LineTo( dc, nx + CELL_SIZE, ny + CELL_SIZE + 1 ); } if( !( b & SOU ) ) { MoveToEx( dc, nx, ny + CELL_SIZE, NULL ); LineTo( dc, nx + CELL_SIZE + 1, ny + CELL_SIZE ); } if( !( b & WES ) ) { MoveToEx( dc, nx, ny, NULL ); LineTo( dc, nx, ny + CELL_SIZE + 1 ); } } } drawEndPoints( dc ); _bmp.setPenColor( RGB( 255, 0, 0 ) ); for( int y = 0; y < _s; y++ ) { int yy = y * _s; for( int x = 0; x < _s; x++ ) { BYTE d = _pts[x + yy]; if( !d ) continue; int nx = x * CELL_SIZE + 4, ny = y * CELL_SIZE + 4; MoveToEx( dc, nx, ny, NULL ); switch( d ) { case NOR: LineTo( dc, nx, ny - CELL_SIZE - 1 ); break; case EAS: LineTo( dc, nx + CELL_SIZE + 1, ny ); break; case SOU: LineTo( dc, nx, ny + CELL_SIZE + 1 ); break; case WES: LineTo( dc, nx - CELL_SIZE - 1, ny ); break; } } } _bmp.saveBitmap( "f:\\rc\\maze_s.bmp" ); BitBlt( GetDC( GetConsoleWindow() ), 10, 60, BMP_SIZE, BMP_SIZE, _bmp.getDC(), 0, 0, SRCCOPY ); } void drawEndPoints( HDC dc ) { RECT rc; int x = 1 + _sx * CELL_SIZE, y = 1 + _sy * CELL_SIZE; SetRect( &rc, x, y, x + CELL_SIZE - 1, y + CELL_SIZE - 1 ); FillRect( dc, &rc, ( HBRUSH )GetStockObject( WHITE_BRUSH ) ); x = 1 + _ex * CELL_SIZE, y = 1 + _ey * CELL_SIZE; SetRect( &rc, x, y, x + CELL_SIZE - 1, y + CELL_SIZE - 1 ); FillRect( dc, &rc, ( HBRUSH )GetStockObject( WHITE_BRUSH ) ); } void killPoints() { if( _pts ) delete [] _pts; } BYTE* _world, *_pts; int _s, _sx, _sy, _ex, _ey, _lastDir; myBitmap _bmp; }; //-------------------------------------------------------------------------------------------------- int main( int argc, char* argv[] ) { ShowWindow( GetConsoleWindow(), SW_MAXIMIZE ); srand( GetTickCount() ); mazeGenerator mg; mazeSolver ms; int s; while( true ) { cout << "Enter the maze size, an odd number bigger than 2 ( 0 to QUIT ): "; cin >> s; if( !s ) return 0; if( !( s & 1 ) ) s++; if( s >= 3 ) { mg.create( s ); int sx, sy, ex, ey; while( true ) { sx = rand() % s; sy = rand() % s; ex = rand() % s; ey = rand() % s; if( ex != sx || ey != sy ) break; } ms.solveIt( mg.getMaze(), s, sx, sy, ex, ey ); cout << endl; } system( "pause" ); system( "cls" ); } return 0; } //--------------------------------------------------------------------------------------------------
Content is available under GNU Free Documentation License 1.2.