Maze Solving

[SterlingM]

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 -

#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

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

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.

[Paul McKenzie]

I have not been able to figure out why and where the previous member for the Positions change.

That is what a debugger is for.

Have you used the debugger that comes with your compiler? If not, please learn to use it as it is a mandatory tool that every programmer must use to debug programs.

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?

To remove all doubt, use the debugger.

Last, C++ already has a std::stack class. Why did you need to create your own when one already exists?

Regards,

Paul McKenzie

[SterlingM]

I was not aware a std::stack existed. I made my template to 1) better learn how it works and 2) always have one that I knew exactly what was going on. I have used debuggers in the IDE GUIs (setting breakpoints and looking at data in the ide's window) I used before in the past, but not gdb in the terminal. I have been having trouble working my way around gdb so far.

I found another way around the problem though. I did not find where the segmentation fault was occurring, but I realized having a Position* member in the class was just really unnecessary. I can just pop off the stack and get the path...

Thanks for the reply.

[Paul McKenzie]

I was not aware a std::stack existed. I made my template to 1) better learn how it works and 2) always have one that I knew exactly what was going on. I have used debuggers in the IDE GUIs (setting breakpoints and looking at data in the ide's window) I used before in the past, but not gdb in the terminal. I have been having trouble working my way around gdb so far.

Well, without the debugger, it is very difficult to solve programming problems.

I found another way around the problem though. I did not find where the segmentation fault was occurring, but I realized having a Position* member in the class was just really unnecessary. I can just pop off the stack and get the path...

Which brings this up -- what does this do?

if( positionValid(*(new Position(pos.getRow(), pos.getCol()+1))) )

What is "positionValid", and why are you creating a Position dynamically like this in cascading if() statement? This is more than likely a memory leak. Unless the Position() class somehow stores its instances in some global container of Position pointers, that is a memory leak.

So the reason why your fix works is that you removed the usage of pointers and instead used value-based semantics. This is how you reduce or eliminate pointer bugs that I endorse. However, you really do need to brush up more on how to handle dynamically allocated memory properly, since at some point you will have to call "new" and use pointers for legitimate and necessary reasons.

Regards,

Paul McKenzie