Source

3dmaze / mazeengine.cpp

/* Copyright (C) 2010 by Eric Waller 
  
   Build and display a maze in either 2-D or 3-D

   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 3 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, see <http://www.gnu.org/licenses/>.

   ewwaller@gmail.com

   Revision History

   Date        Author      Description
   ---------   ----------  -----------
   2010.7.20   E Waller    Initial Release
*/

#include "mazeengine.h"

MazeEngine::MazeEngine()
{
}

MazeEngine::~MazeEngine()
{
}


bool MazeEngine::IsMoveLegal (int x, int y)
{
  if (x < 1) return FALSE;			// Check for out of bounds on left
  if (y < 1) return FALSE;			// on top
  if (x > xSize - 1 ) return FALSE;		// on right
  if (y > ySize -1) return FALSE;			// and on the bottom
  return (!theMap[x + y * xSize]); 		// We are in bounds, if it is a Wall (0) it is legal
}

void MazeEngine::CreateMaze(int newXSize,int newYSize)
{
  xSize=newXSize;
  ySize=newYSize;
  // initialize the stack, when it is empty, we are done
  QVector<Coordinate> theStack;
  
  // The map starts out as all walls. Size the map and fill it with walls
  
  theMap.fill(WALL,xSize * ySize);
  
  // Let's start in the upper left corner for now
  
  Coordinate theLocation;
  theLocation.x = 1;
  theLocation.y = 1;

  // This is main loop.  It repeats until we have been
  // to all coordinates where x and y are both odd
  
  do
    {
      // We are here, turn here into a path,  define storage for valid directions
      
      theMap[theLocation.x + xSize * theLocation.y] = PATH;
      QVector<int> validDirections;
      
      // Check for valid directions, and store them in validDirection
      for (int dir = NORTH  ; dir <= WEST  ; dir=dir+1)
        if (IsMoveLegal (theLocation.x + 2 * dx[dir],
                         theLocation.y + 2 * dy[dir]))
          // A move is valid if the location two steps away has not been visted yet
          // and if it is inbounds
          validDirections.push_back(dir);

      // If there are valid directions, then we are good to go forward

      if (! validDirections.empty())
        {
          // If we have more than 1 choice,
          // remember this locale so we can come back here later
          
          if (validDirections.size() > 1)
            theStack.push_back(theLocation);
          
          // Pick a valid direction, Move one square in the chosen direction.
          // stored in validDirections.  The offsets are the calculated from
          //  dx[] and dy[].
          
          int dirindex = rand() % validDirections.size();
          
          // dirindex selects one of the known good directions which are
          
          theLocation.x +=dx[validDirections[dirindex]];
          theLocation.y +=dy[validDirections[dirindex]];
          
          //Now, one of the coordinates is odd and the other
          // is even.  Turn this intermediate spot into a path.
          
          theMap[theLocation.x + xSize * theLocation.y] = PATH;
          
          // Move another space in the chosen direction.  both coordinates will be again odd.
          
          theLocation.x +=dx[validDirections[dirindex]];
          theLocation.y +=dy[validDirections[dirindex]];
          
        }

      else
        // no valid directions, we are stuck, so back up to the last place we had a choice.
        {
          // get the most recent location we have been where there was a choice.
          // go there, and pop that location off the stack.
          
          theLocation = theStack.back();
          theStack.pop_back();			
        }
    }while ( ! theStack.empty() );
  
  // If we have reached this point, the return coordinate stack is empty, We have been everywhere once.
  // Stick a fork in us, we are done. (almost).  We still need an exit and an enterance
  
  // Allocate storage for the exit point. Exit is in the right side
  // pick an odd location along the right edge. Knock a hole for the exit
  
  Coordinate endPoint;
  endPoint.x = xSize-1;
  endPoint.y = (rand() % (ySize - 2)) | 1	;
  theMap[endPoint.x + xSize * endPoint.y]= PATH;
  
  // The entrance is on the left Pick an odd location along the left edge.
  // Turn the entrance into a path.
  
  theLocation.x=0;
  theLocation.y=(rand() % (ySize - 2)) | 1;		//
  theMap[theLocation.x + xSize * theLocation.y] = PATH;
  
  // Now find the solution.  To do this, we will find the right hand solution
  
  // We know the entrance is on the left, so we must start at the enterance going east
  
  int dir = EAST;
  Coordinate oldLocation;
  
  // Wander around until we find the exit
  
  while ((theLocation.x != endPoint.x ) || (theLocation.y != endPoint.y ))
    {
      // Turn the path into the solution. (drop a bread crumb)
      
      theMap[theLocation.x + xSize * theLocation.y] = SOLUTION ;
      
      // Remember where we were, then move in our current direction.
      
      oldLocation = theLocation;
      theLocation.x += dx[dir];
      theLocation.y += dy[dir];
      
      // See if we have been here already.  If so, from whence we came is not part of the
      //  solution (Pick up the bread crumb)
      if (theMap[theLocation.x + xSize * theLocation.y] == SOLUTION)
        theMap[oldLocation.x + xSize * oldLocation.y] = PATH ;
      
      //  Turn right.
      
      if (++dir > WEST)
        dir = NORTH;
      
      // If there is a wall in front of us, turn left until we have a clear path
      // there are only four directions.  One of them has to work since we are here
      while (theMap[theLocation.x+dx[dir] +
                    xSize * (theLocation.y + dy[dir])] == WALL)
        if (--dir  < NORTH)
          dir = WEST; 					//
        }

  // We are at the exit.  It too is part of the solution
  
  theMap[theLocation.x + xSize * theLocation.y] = SOLUTION ;
}