Traversing a maze

[pepstein]

I am creating a maze game that is to be traversed and solved by the machine. I have created a maze class that contains the starting and ending positions of the maze as well as the maze itself which is contained in a 2d vector of bools. What I am getting tripped up on is how to actually code moving up and down and across the maze to get to the finish. My starting point is [11][4] in the maze and our professor has told us the best way to move about is to check all 4 locations around the current position and if its true (aka it is a path and not a wall) push it onto the stack. I understand conceptually what this means but I can't visualize how to code it properly, any help would be appreciated. FYI, there is a location struct that simplifies how to express a location.

location class

  struct Location  {
	friend std::ostream &operator <<(std::ostream &os, const Location &location) {
		os << "(" << location.x << ", " << location.y << ")";
		return os;
	}
	bool operator ==(const Location &rhs) const {return x == rhs.x && y == rhs.y;}
	bool operator !=(const Location &rhs) const {return !(*this == rhs);}
	operator bool() const {return x >= 0;}
	Location(int x=-1, int y=-1) : x(x), y(y) {}
	int x, y;
};

maze class

class Maze {
	friend std::ostream &operator <<(std::ostream &os, Maze &maze);
	friend Maze load(std::string filename);
public:
    Maze(std::vector<std::vector<bool> > specifics, const Location &startPos, const Location &endPos);
    bool solve();
    //void run();
private:
	bool contains(const Location &location) const;
	bool isPath(const Location &location) const;
	int height() {return spec.size();}
	int width() {return spec[0].size();}
	std::vector<std::vector<bool> > spec;
	Location start, finish;
	Location current;
};

solve function thus far

bool Maze::solve() {
    stack<Location> location; //vector to hold location objects/paths
    Location current; //will hold current position in maze
    current = start; //set current to start position in beginning
    location.push(current); //push first maze location (start) onto vector
   
    ///need to set current to top of stack; while traversing maze current is top of stack and if current hits (==) finish return true
    while (!location.empty()) //while location still has values inside
    {
        current=location.top();//set current to top of stack
        cout << current << endl;
        cout << spec[11][4];
        if (current==finish) //if current == finish the maze is solved
            return true;
        for loop to start moving around... but how?
      }
}

sorry about sloppiness of solve, been trying to understand it so there are some random comments and print statements.

[Lowest0ne]

The Location has x and y values, which relate to the position in the vector.

Location my_location( 0, 1 );
cout << spec[ my_location.y ][ my_location.x ]; // prints zero if there is not a wall there, one otherwise 

So to get the space in the maze below my_location:
spec[ my_location.y + 1 ][ my_location.x ];

Note that the space in the maze above my_location is not valid ( spec[-1][1] ), so you need to make sure you are in bounds.

It seems like your teacher is trying to get you to implement Astar pathfinding. Its a little more complicated than the directions he/she gave you, so I'm not too sure.

[pepstein]

yes, the spec vector holds bools and the maze is either a * or nothing. anything that is a "*" is a path while everything else is a wall.

[AbstractionAnon]

In traversing the maze, you will probably want a tri-state indicator instead of a bool. The third state is whether you've visited that cell. If you've already been there, you don't want to go there again.

[pepstein]

ok, my start position was already filled when I loaded my maze so when I set current it is being filled with a valid location, the actual location being [11][4]. i feel like the following line to check the for valid paths would be along the lines of: if (spec[i+1][j]==true||spec[i-1][j]==true||spec[i][j+1]==true||spec[i][j+1]==true). is that correct?

where would I go from there? i know I need to convert that true position to a Location and then push it on the stack but I'm new to vectors and can't figure out exactly how to code it. thanks.

[AbstractionAnon]

. i feel like the following line to check the for valid paths would be along the lines of: if (spec[i+1][j]==true||spec[i-1][j]==true||spec[i][j+1]==true||spec[i][j+1]==true).

As LowestOne pointed out, that statement is going to be a problem when you are at the edges of the maze unless you're making the assumption that the maze is closed on all sides. Consider when i = 0, spec[i-1][j] is going to be out of bounds, not just of the maze, but also an invalid vector reference. Same applies when i = size()-1 or j = 0 or j = size() -1.

Also consider what I pointed out before. If you move from [11][4] to [11][5], you're going to consider that moving backward to [11][4] is valid because it's not a wall. It doesn't consider that you've already been there.

I would suggest implementing four functions. One each to move Up, Left, Right, or Down. I would implement these as bool functions that return false if the respective direction is not valid (out of bound, wall, or been there). Then in your logic, you want to try each individual direction. If none of the directions are valid, then you want to pop the location stack (i.e. back up).

[pepstein]

thanks, i should have made mention that there is in fact a border so the first issue you mentioned won't present itself.

[AbstractionAnon]

That's only true if the entrance or exit can't be on the border.

[Lowest0ne]

Are there dead ends in your maze? Or is it a labyrinth? Can you post what the maze looks like?

[pepstein]

+----------------------------------------+
|*                           F           |
|*      ***** *********      *           |
|****   *   * *       *      *           |
|   *   *   * *       ********           |
| ***   *   * *       *  *               |
| *     *   * *       *  *               |
| *******   * *       *                  |
|   *    **** *       *   *         *****|
|   *    *    *       *   *             *|
|   *    ******       ********          *|
|   *                        *          *|
|   S                 *******************|
+----------------------------------------+

[Lowest0ne]

if (spec[i+1][j]==true||spec[i-1][j]==true||spec[i][j+1]==true||spec[i][j+1]==true).

That will tell you if there are any moves you could make. You do have the right idea though, those are the four locations. You may want to beef up you Location a little:

struct Location
{
  int x;
  int y;

  Location( int x, int  y );
  
  Location relative( int x_dir, int y_dir ){ return Location( x + x_dir, y + y_dir ); }
  Location north( void ) { return relative( 0, -1 ); }
  // similar for east, south, and west

  double distance( Location& other ){ /* method to return distance between Locations */ }
};

Now you can do something like:

std::vector< Location > path;
Location current( /* start of maze */ )

while ( current != finish )
{
  // create the four surrounding locations
  Location neighbors[] = { current.north(), current.east(), current.south(), current.west() };
  
  // look through the array for
  // a ) a location that is a valid path
  // b ) a location that is not on the back() of the path vector
  // c ) the closest location to the finish
  // call that location best_location

  // push_back() the current location onto the path vector
  // set the current to the best
}

// current is now the final location, perhaps push_back() that onto the vector 

It would be neat to take that path vector and then use the locations it has to overwrite your map with, say, plus signs, to show the path you came up with.

Edit: This should suffice for the maze that you have, but pathfinding is a complicated thing.

[pepstein]

thanks for the help guys