source: code/trunk/src/modules/hover/MazeGenerator.cc @ 12080

/*
 *   ORXONOX - the hottest 3D action shooter ever to exist
 *                    > www.orxonox.net <
 *
 *
 *   License notice:
 *
 *   This program is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU General Public License
 *   as published by the Free Software Foundation; either version 2
 *   of the License, or (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 *
 *   Author:
 *      Manuel Meier
 *   Co-authors:
 *      Cyrill Burgener
 *
 *   Based on random-maze-generator by Sergey Kosarevsky, 2014
 *   https://github.com/corporateshark/random-maze-generator
 *
 */

/**
    @file MazeGenerator.cc
    @brief Implementation of the MazeGenerator class. Generates the maze.
*/

#include "MazeGenerator.h"

#include <vector>

#include "util/Output.h"
#include "util/Math.h"

namespace orxonox
{
    MazeGenerator::MazeGenerator(int numCells)
    {
        this->numCells_ = numCells;

        //levelcode_ represents the pitch: It's a 10x10 field.
        // 1 represents a Wall on the right side of this square
        // 2 represents a Wall on the top of this square
        // 3 represents 2 and 1 at the same time
        // Note: the levelcode_ is generated from the Maze-Generator functions at the beginning of the game
        this->levelcode_ = new int[ numCells_*numCells_ ];;
        std::fill( levelcode_, levelcode_ + numCells_*numCells_, 0 );

        this->maze_ = new unsigned char[ numCells_*numCells_ ];
        std::fill( maze_, maze_ + numCells_*numCells_, 0 );

        // current traversing position
        this->ptX_ = 0;
        this->ptY_ = 0;

        //                  0  1  2  3  4  5  6  7  8
        //                     U  R     D           L
        int headingX[9] = { 0, 0,+1, 0, 0, 0, 0, 0,-1 };
        int headingY[9] = { 0,-1, 0, 0,+1, 0, 0, 0, 0 };
        int mask[9]     = {
                              0,
                              eDirection_Down | eDirection_Down << 4,
                              eDirection_Left | eDirection_Left << 4,
                              0,
                              eDirection_Up | eDirection_Up << 4,
                              0,
                              0,
                              0,
                              eDirection_Right | eDirection_Right << 4
                          };

        std::copy(headingX, headingX + 9, this->headingX_);
        std::copy(headingY, headingY + 9, this->headingY_);
        std::copy(mask,     mask + 9,     this->mask_);
    }

    MazeGenerator::~MazeGenerator()
    {
        delete[] this->levelcode_;
        delete[] this->maze_;
    }

    /**
    @brief
        Checks if Direction is valid (for Maze-Generator)
    */
    bool MazeGenerator::isDirValid( eDirection Dir )
    {
        int NewX = ptX_ + headingX_[ Dir ];
        int NewY = ptY_ + headingY_[ Dir ];

        if ( !Dir || NewX < 0 || NewY < 0 || NewX >= numCells_ || NewY >= numCells_ ) return false;

        return !maze_[ NewX + numCells_ * NewY ];
    }

    /**
    @brief
        Generates new Direction (for Maze-Generator)
    */
    eDirection MazeGenerator::getDirection()
    {
        eDirection Dir = eDirection( 1 << randomInt4() );

        while ( true )
        {
            for ( int x = 0; x < 4; x++ )
            {
                if ( isDirValid( Dir ) ) { return eDirection( Dir ); }

                Dir = eDirection( Dir << 1 );

                if ( Dir > eDirection_Left ) { Dir = eDirection_Up; }
            }

            Dir = eDirection( ( maze_[ cellIdx() ] & 0xf0 ) >> 4 );

            // nowhere to go
            if ( !Dir ) return eDirection_Invalid;

            ptX_ += headingX_[ Dir ];
            ptY_ += headingY_[ Dir ];

            Dir = eDirection( 1 << randomInt4() );
        }
    }

    /**
    @brief
        Generates a Maze (for Maze-Generator)
    */
    void MazeGenerator::generateMaze()
    {

        for ( eDirection Dir = getDirection(); Dir != eDirection_Invalid; Dir = getDirection() )
        {
            maze_[ cellIdx() ] |= Dir;

            ptX_ += headingX_[ Dir ];
            ptY_ += headingY_[ Dir ];

            maze_[ cellIdx() ] = mask_[ Dir ];
        }
    }  
    
    /**
    @brief
        Print Maze (for Debugging only)
    */
    void MazeGenerator::mazeOut(){
        for ( int y = 0; y < numCells_; y++ )
        {
            for ( int x = 0; x < numCells_; x++ )
            {
                char v = maze_[ y * numCells_ + x ];
                orxout()<<"[";
                if ( ( v & eDirection_Up    ) ) orxout()<<"U";
                else orxout()<<" ";
                if ( ( v & eDirection_Right ) ) orxout()<<"R";
                else orxout()<<" ";
                if ( ( v & eDirection_Down  ) ) orxout()<<" ";
                else orxout()<<" ";
                if ( ( v & eDirection_Left  ) ) orxout()<<" ";
                else orxout()<<" ";
                orxout()<<"]";
            }
            orxout()<<endl;
        }

    }

    /**
    @brief
        Print levelcode_ (for Debugging only)
    */
    void MazeGenerator::levelOut(){
        for ( int y = 0; y < numCells_; y++ )
        {
            for ( int x = 0; x < numCells_; x++ )
            {
                orxout()<<"[";
                if ( levelcode_[ y * numCells_ + x ] < 2) orxout()<<"U";
                else orxout()<<" ";
                if ( levelcode_[ y * numCells_ + x ] % 2 == 0) orxout()<<"R";
                else orxout()<<" ";

                orxout()<<" ";
                orxout()<<" ";
                orxout()<<"]";
            }
            orxout()<<endl;
        }
    }

    /**
    @brief
        Generate levelcode_ from Maze
    */
    void MazeGenerator::renderMaze()
    {
        for ( int y = 0; y < numCells_; y++ )
        {
            for ( int x = 0; x < numCells_; x++ )
            {
                char v = maze_[ y * numCells_ + x ];

                if ( !( v & eDirection_Up    ) && y >0) levelcode_[ y * numCells_ + x ] |= 2;
                if ( !( v & eDirection_Right ) && x <(numCells_-1)) levelcode_[ y * numCells_ + x ] |= 1;
            }
        }

        // leave an empty space in the middle of the maze
        int lowerBound = numCells_ / 2 - 2;
        int upperBound = numCells_ / 2 + 2;
        for ( int y = lowerBound; y < upperBound; y++ )
        {
            for ( int x = lowerBound; x < upperBound; x++ )
            {

                if(y == lowerBound && x != upperBound)
                    levelcode_[ y * numCells_ + x ] &= 2;
                else if (x == upperBound && y != lowerBound)
                    levelcode_[ y * numCells_ + x ] &= 1;
                else if(x != upperBound)
                    levelcode_[ y * numCells_ + x ] = 0;
            }
        }

    }

    // return the current index in maze_
    int MazeGenerator::cellIdx()
    {
        return ptX_ + numCells_ * ptY_;
    }

    int MazeGenerator::randomInt()
    {
        return (rand() % numCells_);
    }

    int MazeGenerator::randomInt4()
    {
        return (rand() % 4);
    }
}