I am trying to make a maze solving program using c++ and a stack. It will get to the end of the maze, but then it cannot trace back its steps. First, here is some code -
Code:
#ifndef POSITION_H
#define POSITION_H
#include <string>
class Position {
friend std::ostream& operator<<(std::ostream&, Position&);
public:
Position();
Position(int,int);
Position(int, int, int, int);
~Position();
int& getRow();
int& getCol();
void setRow(int);
void setCol(int);
Position* getPrevious();
bool visited();
bool operator==(Position&);
const Position& operator=(const Position&);
std::string toString();
private:
int row;
int col;
Position* prev;
};
#endif
Code:#include "position.h"
#include <sstream>
#include <iostream>
//std::ostream& operator<<(std::ostream& output, Position& p) {
// output<<p.toString();
// return output;
//}
Position::Position() {}
Position::Position(int r, int c) : row(r), col(c) {}
Position::Position(int r, int c, int pr, int pc) : row(r), col(c) {
prev = new Position(pr,pc);
std::cout<<"\nposition "<<toString()<<"'s previous: "<<prev->toString();
}
Position::~Position() {}
int& Position::getRow() {return row;}
int& Position::getCol() {return col;}
void Position::setRow(int r) {row = r;}
void Position::setCol(int c) {col = c;}
Position* Position::getPrevious() {return prev;}
//operator== returns true is the row and col and equal
bool Position::operator==(Position& right) {
if((getRow() == right.getRow()) && (getCol() == right.getCol()) )
return true;
return false;
}
//operator= sets the row and col equal to each other
const Position& Position::operator=(const Position& right) {
if(&right != this) {
row = right.row;
col = right.col;
}
return *this;
}
std::string Position::toString() {
std::ostringstream result;
result<<"("<<row<<","<<col<<")";
return result.str();
}
Code:Path Agent::traverse(Position& end) {
Position start = pos;
Path result;
Stack<Position> stack;
bool done = false;
while(!done) {
std::cout<<std::endl<<"pos: "<<pos.toString();
if(pos == end) {
std::cout<<"\npos==end";
done = true;
}
else {
//try and push neighboring positions onto stack
//right
if( positionValid(*(new Position(pos.getRow(), pos.getCol()+1))) ) {
Position temp(pos.getRow(), pos.getCol()+1, pos.getRow(), pos.getCol());
stack.push(temp);
}
//left
if( positionValid(*(new Position(pos.getRow(), pos.getCol()-1))) ) {
Position temp(pos.getRow(), pos.getCol()-1, pos.getRow(), pos.getCol());
stack.push(temp);
}
//down
if( positionValid(*(new Position(pos.getRow()+1, pos.getCol()))) ) {
Position temp(pos.getRow()+1, pos.getCol(), pos.getRow(), pos.getCol());
stack.push(temp);
}
//up
if( positionValid(*(new Position(pos.getRow()-1, pos.getCol()))) ) {
Position temp(pos.getRow()-1, pos.getCol(), pos.getRow(), pos.getCol());
stack.push(temp);
}
if(!stack.isEmpty()) {
pos = stack.pop();
visited.push_back(pos);
}
else
done = true;
} //end else
} //end while
std::cout<<"\nendpos: "<<pos.toString()<<" prev: "<<pos.getPrevious()->toString();
int i=0;
while(!(pos==start) && i < 25) {
result.getPath()[i] = pos;
pos = *pos.getPrevious();
i++;
}
return result;
}
When I am going through, the print statement in the Position constructor says that the correct values for the previous positions are being set. However, the print statement before the second while loop in the traverse function says that the previous position is not correct. Then I am not able to trace back. I have not been able to figure out why and where the previous member for the Positions change. I think it has something to do with having a Position data member for each Position instance. Maybe the pointers are being deleted and changed that way or something? Maybe the local Position temps are being deleted after I push them onto the stack? I don't know, I have tried multiple different approaches that I could think of and am pretty stuck. If anyone can help me out I would greatly appreciate it, thanks.
