Maze Solving
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Maze Solving

  1. #1
    Join Date
    Oct 2009
    Posts
    56

    Maze Solving

    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.

  2. #2
    Join Date
    Apr 1999
    Posts
    27,446

    Re: Maze Solving

    Quote Originally Posted by SterlingM View Post
    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

  3. #3
    Join Date
    Oct 2009
    Posts
    56

    Re: Maze Solving

    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.

  4. #4
    Join Date
    Apr 1999
    Posts
    27,446

    Re: Maze Solving

    Quote Originally Posted by SterlingM View Post
    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?
    Code:
    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
    Last edited by Paul McKenzie; June 15th, 2011 at 04:06 PM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center