3dmaze / mazeengine.cpp

Full commit
/* 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
   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 <>.

   Revision History

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

#include "mazeengine.h"



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)
  // 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
      // 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

      // 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)
          // 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]];

        // 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();
    }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.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 ;