I'm trying to solve a maze that originally chooses moves randomly, keeping track of its last move...left and forward, right and foward, and forward, and by chance will choose to 'undoMove' if a 'moveBlocked', but not guaranteed. I am attempting to use a stack to solve. according to instructions the loop is guaranteed not to have loops, so to get back to a previous location, you must undo moves made.
The function to solve is below, followed by the header file for the maze. I'm supposed to ONLY rewrite the solveMaze function to implement the stack. Anything I have done to the function so far has been commented out, so you know what the original function looks like. Anything below the comment 'probably leave intact' need not be modified.
I'm having problems getting the function to 'pop' the moves until an new route opening occurs. I can only get it to 'pop' the stack once, but I don't want it to pop the entire stack, so I've been stuck on this...any suggestions?
99% of this code was already given, I just have to modify the solveMaze function which shouldnt be more than 2 or 3 lines longer than the original code according to the instructions given.
void solveMaze(Maze & maze, int timeout) {
// Uncomment to get a stack
// Stack stack(2048);
int move = 0, lastMove = -1;
int numSteps = 0;
bool failed;
while (!maze.atGoal()) {
failed = true;
for (int i=0; i<20; i++) {
move = rand() % NUM_MOVES;
if (!maze.moveBlocked(move)) {
maze.doMove(move);
lastMove = move;
//stack.push(lastMove); push moves to stack
failed = false;
break;
}
}
if (failed && lastMove >= 0) {
maze.undoMove(lastMove);
lastMove = -1;
/*while(maze.moveBlocked(lastMove++) && lastMove <= 2)
{
maze.undoMove(lastMove);
stack.pop();
lastMove++;
}*/
}
// probably leave the stuff after here intact
// print out the maze
cout << maze;
// keep track of steps so we eventually terminate
numSteps++;
if (timeout >= 0 && numSteps > timeout)
break;
}
if (maze.atGoal()) {
cout << maze;
cout << "Found path";
}
else
cout << "Search failed";
cout << " after " << numSteps << " steps." << endl;
}maze header file
using namespace std;
const int FORWARD = 0;
const int LEFT = 1;
const int RIGHT = 2;
const int NUM_MOVES = 3;
enum Direction {NORTH, EAST, SOUTH, WEST};
struct Position {
int x;
int y;
};
struct Pose {
Position cell;
int orientation;
};
class Maze {
public:
// makes an empty maze
Maze();
// make an Maze with given dimensions,
// filling in the walls (somewhat) randomly
Maze(int xDim, int yDim, bool verbose = true, bool eraseBeforeDraw = true);
Maze(const Maze & other);
~Maze();
Maze & operator=(const Maze & other);
// Set the amount of time to pause after redrawing
// (to help with debugging)
void setRedrawPause(double milliseconds) {pauseMilliseconds = milliseconds;};
// Set the verbose flag. If true, prints current position
// and actions as they are executed and un-executed.
// If false, prints only the maze
void setVerbose(bool newVerbose) {verbose = newVerbose;};
// atGoal: Returns true if the current pose is
// at the goal location, and false otherwise
bool atGoal();
// returns the number of potentially open cells
// (for figuring out how long to search)
int numCells() {return (xDim-1)*(yDim-1);};
// moveBlocked: Returns true if a move is not
// possible from the current location (and false
// otherwise)
bool moveBlocked(int move);
bool undoMoveBlocked(int move);
// doMove: executes the move from the current location
// if it is not blocked. If the move is blocked, the
// current location is unchanged.
void doMove(int move);
// undoMove: does the inverse of the move from the
// current location if the target location is not
// blocked. If the target location is blocked, the
// current location is unchanged.
void undoMove(int move);
// some functions to help with debugging
void markCurrentLocation(); // will print a . in a location
void unmarkCurrentLocation(); // removes the . from the location
// function for printing an action as an intelligable string
string moveToStr(int move);
// function for printing the current location
string currentPoseToStr();
// input/output
void display(ostream & out);
// reads the stream from a file stream (not from the user)
void read(ifstream & in);
private:
// internal functions for memory (de)allocation
void allocateCells();
void deallocateCells();
// For random maze generation. Clears cells along a
// random path, so long as loops are not generated.
Pose clearRandomWalk(int numSteps);
// return a randomly chosen non-blocked cell
Pose randomOpenCell();
// Returns new pose after executing move from current pose
Pose getNewPose(Pose pose, int move, bool invert = false);
// For going forward/backward
Pose translate(Pose pose, int dir);
// For turning
Pose turn(Pose pose, int move, int dir);
// Returns true iff pose is blocked
bool blocked(Pose pose);
// Returns the number of neighboring cells that are
// blocked (does not include diagonal)
int neighborsBlocked(Pose pose);
// Returns string for any pose
string poseToStr(Pose pose);
// dimensions of grid
int xDim;
int yDim;
// poses
Pose currPose;
Pose startPose;
Pose goalPose;
// actual grid
// first bit indicates blocked/clear
// second bit indicates marked/unmarked (for printing only)
int ** cells;
bool eraseBeforeDraw;
double pauseMilliseconds;
bool verbose;
};
// input/output operators
ostream & operator<<(ostream & out, Maze & m);
istream & operator>>(istream & in, Maze & m);
// utility function because C++ mod function doesn't work
// with negative numbers
int fixMod(int n, int mod);
// UGLINESS!
// On windows, puts the cursor back at the top of the console window
// so that maze is drawn on top of old maze (instead of drawing a
// bazillion mazes)
// This is much harder to do on the Mac (and doesn't work with the
// xCode terminal anyway), so on a Mac you're just stuck with
// drawing a bazillion mazes.
//#if defined (_WIN32)
void putCursor(int x, int y);
//#endif
void initScr();
//void putCursor(int x, int y);
void closeScr();
#endif