Thread: Converting 2D Maze Generator to 3D

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    216

    Converting 2D Maze Generator to 3D

    Hey Cboard,

    I want to make a 3D maze generator, and after searching google for a little bit I found a 2D maze generator that works quite well. I found it here: Maze generation - Rosetta Code

    I've been able to use this code to render mazes in Allegro 5 as a test, and it works nicely, however, I did some initial tests with Irrlicht3D and the results were unpleasant on the eyes. Here is the Allegro version:

    Code:
    #include <windows.h>
    #include <iostream>
    #include <string>
    
    // link with gdi32
    
    #include <allegro5/allegro.h>
    #include <allegro5/allegro_primitives.h>
    
    //--------------------------------------------------------------------------------------------------
    using namespace std;
    
    //--------------------------------------------------------------------------------------------------
    const int BMP_SIZE = 512, CELL_SIZE = 15;
    
    //--------------------------------------------------------------------------------------------------
    enum directions { NONE, NOR = 1, EAS = 2, SOU = 4, WES = 8 };
    
    //--------------------------------------------------------------------------------------------------
    class mazeGenerator
    {
    public:
        mazeGenerator()
        {
    	_world = 0;
    	///_bmp.create( BMP_SIZE, BMP_SIZE );
    	///_bmp.setPenColor( RGB( 0, 255, 0 ) );
        }
    
        ~mazeGenerator() { killArray(); }
    
        void create( int side )
        {
    	_s = side;
    	generate();
    	display();
        }
    
    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;
    	    }
    	}
        }
    
        void display()
        {
    	///_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 );
    
    		    al_draw_line( nx, ny, nx + CELL_SIZE, ny, al_map_rgb(255, 0, 0), 1);
    		}
    		if( !( b & EAS ) )
    		{
    		    ///MoveToEx( dc, nx + CELL_SIZE, ny, NULL );
    		    ///LineTo( dc, nx + CELL_SIZE, ny + CELL_SIZE + 1 );
    
    		    al_draw_line( nx + CELL_SIZE, ny, nx + CELL_SIZE, ny + CELL_SIZE, al_map_rgb(255, 0, 0), 1);
    		}
    		if( !( b & SOU ) )
    		{
    		    ///MoveToEx( dc, nx, ny + CELL_SIZE, NULL );
    		    ///LineTo( dc, nx + CELL_SIZE + 1, ny + CELL_SIZE );
    
    		    al_draw_line( nx, ny + CELL_SIZE, nx + CELL_SIZE, ny + CELL_SIZE, al_map_rgb(255, 0, 0), 1);
    		}
    		if( !( b & WES ) )
    		{
    		    ///MoveToEx( dc, nx, ny, NULL );
    		    ///LineTo( dc, nx, ny + CELL_SIZE + 1 );
    
    		    al_draw_line( nx, ny, nx, ny + CELL_SIZE, al_map_rgb(255, 0, 0), 1);
    		}
    		///al_flip_display(); //for testing purposes
            ///system("pause");
    	    }
    	}
    
    	//_bmp.saveBitmap( "f:\\rc\\maze.bmp" );
    	///BitBlt( GetDC( GetConsoleWindow() ), 10, 60, BMP_SIZE, BMP_SIZE, _bmp.getDC(), 0, 0, SRCCOPY );
        }
    
        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;
    };
    //--------------------------------------------------------------------------------------------------
    
    //--------------------------------------------------------------------------------------------------
    
    
    int main(void)
    {
      ALLEGRO_DISPLAY *display = NULL;
    
      if(!al_init())
          return -1;
    
      display = al_create_display(640, 480);
    
      if(!display)
          return -1;
    
      al_init_primitives_addon();
    
      srand( GetTickCount() );
    
        mazeGenerator mg;
        int s;
        while(true)
        {
            cout << "Enter the maze size, an odd number bigger than 2 ( 0 to QUIT ): "; cin >> s;
            if( !s )
            {
                al_destroy_display(display);
    
                return 0;
            }
    
            if( !( s & 1 ) ) s++;
            if( s >= 3 ) mg.create( s );
            cout << endl;
    
            al_flip_display();
            al_clear_to_color( al_map_rgb(0, 0, 0));
        }
    
    
      al_destroy_display(display);
    
      return 0;
    }
    Here is my initial Irrlicht version:

    Code:
    #include <windows.h>
    #include <iostream>
    #include <string>
    
    // link with gdi32
    
    #include <irrlicht.h>
    
    using namespace irr;
    
    using namespace core;
    using namespace scene;
    using namespace video;
    using namespace io;
    using namespace gui;
    
    //--------------------------------------------------------------------------------------------------
    using namespace std;
    
    //--------------------------------------------------------------------------------------------------
    const int BMP_SIZE = 512, CELL_SIZE = 8;
    float cubeSize = 4;
    
    //--------------------------------------------------------------------------------------------------
    enum directions { NONE, NOR = 1, EAS = 2, SOU = 4, WES = 8 };
    
    int CreateMazeNode(IVideoDriver *driver, ISceneManager *smgr, ISceneNode* node, float x, float y, float z);
    
    IVideoDriver *driver;
    ISceneManager *smgr;
    
    //--------------------------------------------------------------------------------------------------
    class mazeGenerator
    {
    public:
        mazeGenerator()
        {
    	_world = 0;
    	///_bmp.create( BMP_SIZE, BMP_SIZE );
    	///_bmp.setPenColor( RGB( 0, 255, 0 ) );
        }
    
        ~mazeGenerator() { killArray(); }
    
        void create( int side )
        {
    	_s = side;
    	generate();
    	display();
        }
    
    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;
    	    }
    	}
        }
    
        void display()
        {
    	///_bmp.clear();
    	///HDC dc = _bmp.getDC();
    	ISceneNode *mazeNode[(_s * _s)];
    	int nodeCount = 0;
    
    	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 );
    
    		    CreateMazeNode(driver, smgr, mazeNode[nodeCount], nx, 0, ny);
                nodeCount++;
    
    		    ///LineTo( dc, nx + CELL_SIZE + 1, ny );
    
                CreateMazeNode(driver, smgr, mazeNode[nodeCount], nx + CELL_SIZE + cubeSize, 0, ny);
                nodeCount++;
    		}
    		if( !( b & EAS ) )
    		{
    		    ///MoveToEx( dc, nx + CELL_SIZE, ny, NULL );
    
    		    CreateMazeNode(driver, smgr, mazeNode[nodeCount], nx + CELL_SIZE, 0, ny);
                nodeCount++;
    
    		    ///LineTo( dc, nx + CELL_SIZE, ny + CELL_SIZE + 1 );
    
                CreateMazeNode(driver, smgr, mazeNode[nodeCount], nx + CELL_SIZE, 0, ny + CELL_SIZE + cubeSize);
                nodeCount++;
    		}
    		if( !( b & SOU ) )
    		{
    		    ///MoveToEx( dc, nx, ny + CELL_SIZE, NULL );
    
    		    CreateMazeNode(driver, smgr, mazeNode[nodeCount], nx, 0, ny + CELL_SIZE);
                nodeCount++;
    
    		    ///LineTo( dc, nx + CELL_SIZE + 1, ny + CELL_SIZE );
    
                CreateMazeNode(driver, smgr, mazeNode[nodeCount], nx + CELL_SIZE + cubeSize, 0, ny + CELL_SIZE + cubeSize);
                nodeCount++;
    		}
    		if( !( b & WES ) )
    		{
    		    ///MoveToEx( dc, nx, ny, NULL );
    
    		    CreateMazeNode(driver, smgr, mazeNode[nodeCount], nx, 0, ny);
                nodeCount++;
    
    		    ///LineTo( dc, nx, ny + CELL_SIZE + 1 );
    
                CreateMazeNode(driver, smgr, mazeNode[nodeCount], nx, 0, ny + CELL_SIZE + cubeSize);
                nodeCount++;
    		}
    		///al_flip_display(); //for testing purposes
            ///system("pause");
    	    }
    	}
    
    	//_bmp.saveBitmap( "f:\\rc\\maze.bmp" );
    	///BitBlt( GetDC( GetConsoleWindow() ), 10, 60, BMP_SIZE, BMP_SIZE, _bmp.getDC(), 0, 0, SRCCOPY );
        }
    
        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;
    };
    //--------------------------------------------------------------------------------------------------
    
    //--------------------------------------------------------------------------------------------------
    
    
    int main(void)
    {
        IrrlichtDevice *device = createDevice(EDT_DIRECT3D9, dimension2d<u32>(640, 480), 16, false, false, false, 0);
    
        if(!device)
            return 1;
    
        device->setWindowCaption(L"Maze Generator");
    
        driver = device->getVideoDriver();
        smgr = device->getSceneManager();
    
        srand( GetTickCount() );
    
        mazeGenerator mg;
        int s;
    
        cout << "Enter the maze size, an odd number bigger than 2 ( 0 to QUIT ): "; cin >> s;
        if( !s )
        {
            device->drop();
    
            return 0;
        }
    
        if( !( s & 1 ) ) s++;
        if( s >= 3 ) mg.create( s );
        cout << endl;
    
        smgr->addCameraSceneNodeFPS();
    
        s32 lastFPS = -1;
    
        while(device->run())
        {
            driver->beginScene(true, true, SColor(255,0,0,0));
    
            smgr->drawAll();
    
            driver->endScene();
    
            const s32 fps = driver->getFPS();
    
            if (lastFPS != fps)
            {
                core::stringw str = L"Maze Generator  [";
                str += driver->getName();
                str += "] FPS:";
                str += fps;
    
                device->setWindowCaption(str.c_str());
                lastFPS = fps;
            }
        }
    
        device->drop();
    
        return 0;
    }
    
    int CreateMazeNode(IVideoDriver *driver, ISceneManager *smgr, ISceneNode* node, float x, float y, float z)
    {
        node = smgr->addCubeSceneNode( cubeSize, 0, -1,  core::vector3df(0, 0, 0),  core::vector3df(0, 0, 0),  core::vector3df(1.0f, 1.0f, 1.0f));
        if(node)
        {
            driver->setTextureCreationFlag(video::ETCF_CREATE_MIP_MAPS, false);
    
            node->setPosition(core::vector3df(x, y, z));
            node->setMaterialTexture(0, driver->getTexture("hedge_texture.jpg"));
            node->setMaterialFlag(video::EMF_LIGHTING, false);
            node->setMaterialFlag(video::EMF_ANISOTROPIC_FILTER, true);
            node->setMaterialFlag(video::EMF_ANTI_ALIASING, true);
    
            driver->setTextureCreationFlag(video::ETCF_CREATE_MIP_MAPS, true);
    
            return 1;
        }
        else
            return 0;
    
    }
    My question is, what must you take into account when going 3D? Obviously there is the z axis, which I believe I have covered, and the y axis will just be how tall the maze is.

    I have a couple years of C experience, but I'm pretty basic when it comes to C++, so go easy on me! Any help is appreciated, thanks in advance!

  2. #2
    Registered User
    Join Date
    Mar 2011
    Posts
    216
    Just another thought, since the 2D maze generator was using lines as the walls, and I want to use cubes for the walls, does the thickness of the cube need to be accounted for? For example, when drawing the cubes, do I need to draw to the x + cubeSize and z + cubeSize to account for this?

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I think some images of the original 2D output and your 3D output would help a lot in understanding the problem.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Mar 2011
    Posts
    216
    Sure, thanks for your interest! Although it generates a different maze every time, preventing a direct comparison, I've made both generate 11x11 mazes, with different "cell sizes" in between.

    Allegro Screenshot
    Converting 2D Maze Generator to 3D-allegro-2d-maze-png

    Irrlicht Screenshot
    Converting 2D Maze Generator to 3D-irrlicht-3d-maze-jpg

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,532
    > Although it generates a different maze every time, preventing a direct comparison,
    Perhaps comment out the call to srand() then. If the algorithm is the same, then you should end up with different graphical representations of the same maze.

    Or perhaps
    if ( argc > 1 ) srand( atoi(argv[1]) );

    The only thing wrong with the Irrlicht one is that the walls lack any sense of height. With appropriate textures and shading, it could look a lot better.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Mar 2011
    Posts
    216
    Here are two more images, with srand commented out on both. There are some similarities if you rotate the images around I suppose.

    Allegro Maze
    Converting 2D Maze Generator to 3D-allegro-maze-png

    Irrlicht Maze (I forgot to mention before that I moved the camera up in the program to show a top down view)
    Converting 2D Maze Generator to 3D-irrlicht-maze-jpg

    Right now I just want the maze to be one cube high, and later on once it works, and I can do a pass over the maze again, adding more cubes for height above existing cubes.

    I agree, it isn't the prettiest maze I have seen

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to create a Maze Generator in C?
    By kknehra in forum C Programming
    Replies: 2
    Last Post: 11-11-2012, 11:55 PM
  2. Random maze generator
    By Bingo The Clown in forum C++ Programming
    Replies: 1
    Last Post: 04-10-2003, 09:15 AM
  3. maze generator
    By datainjector in forum C Programming
    Replies: 2
    Last Post: 11-20-2002, 06:35 PM
  4. IDEA: Maze Generator
    By ygfperson in forum Contests Board
    Replies: 2
    Last Post: 09-09-2002, 08:43 PM
  5. Maze game, complete with maze editor and an example maze!
    By Brian in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 01-20-2002, 03:27 AM