Maze Alogrithm (No recursion or backtracking)

maze.cpp

// (The MIT License)
// 
// Copyright (c) 2011 Ledsworth Consulting LLC
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
// documentation files (the "Software"), to deal in the Software without restriction, including without limitation the 
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit 
// persons to whom the Software is furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in all copies or substantial portions of the 
// Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE 
// WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR 
// COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 
// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
// File format rules:
// 1) '#' denotes a wall, ' ' (space) is a path
// 2) Entrance must be on left, and the exit on right
// 3) Maze cannot be larger than 100x100
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
using namespace std;

class MazePathFinder {

    private: 

    char matrix[100][100];
    int rows, cols;
    int entrance_row, entrance_col;
    int exit_row, exit_col;
    bool exitFound;

    // Square with x,y coordinates and a pointer to its parent.
    struct square {
      pair<int,int> cord;
      square * parent;
    };

    queue<square *> q;

    public: 

    // Loads a 2d array from a file and setups up the maze
    // ---------------------------------------------------
    void loadMaze(char * const mazeFile) {
      // Open maze file for reading
      ifstream inFile;
      inFile.open(mazeFile);
      if( !inFile ) {
        perror(mazeFile);
      }

      // Load maze into two dimentional array of chars
      int row = 0;
      string line;
      while(!inFile.eof()) {
        getline(inFile,line);
        for(int x=0; x<line.size(); x++) {
          matrix[row][x] = line[x];
        }    
        row++;
        if(line.size()>0)
          cols = line.size();
      }
      rows = row-1;

      findEntryAndExit();
      exitFound = false;
    }

    // Print maze to stdout
    // --------------------
    void printMaze() {
      for(int x=0; x<rows; x++) {
        for(int y=0; y<cols; y++)
          cout << matrix[x][y];
        cout << endl;
      }
    }

    // Solve the maze
    // --------------
    void solveMaze() {
      // Start at entrance
      square * s = new square;
      s->cord = make_pair(entrance_row,entrance_col);
      s->parent = NULL;
      q.push(s);

      // Crawl pathways until the exit is found
      int x,y;
      while(!exitFound && !q.empty()) {
        s = q.front();
        q.pop();
        x = s->cord.first; y = s->cord.second;
        if(x==exit_row && y==exit_col) {
          matrix[x][y] = '>';
          exitFound = true;
        }
        else {
          walkPath(x-1,y,s);
          walkPath(x+1,y,s);
          walkPath(x,y-1,s);
          walkPath(x,y+1,s);
          }
      }

      // Remove makers from unfished/non solution paths
      clearMaze();

      // Mark solution pathway, starting at exit and working backwards
      while(s->parent != NULL) {
        matrix[s->cord.first][s->cord.second] = '-';
        s = s->parent;
      }
    }

    private:

    // Take a square, see if it's the exit. If not, 
    // push it onto the queue so its (possible) pathways
    // are checked.
    void walkPath(int x, int y, square * parent) {
      if(!exitFound) {
        if(x==exit_row && y==exit_col) {
          exitFound = true;
          matrix[x][y] = '>';
        }
        else
        {
          if(freeSquare(x,y)) {
            // Tag as visited
            matrix[x][y]='-';
            // Add to queue
            square * s = new square;
            s->cord = make_pair(x,y);
            s->parent = parent;
            q.push(s);
          }
        }
      }
    }

    // Find and mark entrance and exit points
    // --------------------------------------
    void findEntryAndExit() {
      for(int x=0; x<rows; x++) {
        if( matrix[x][cols-1] == ' ') {
          exit_row = x;
          exit_col = cols-1;     
        }
        if( matrix[x][0] == ' ') {
          entrance_row = x;
          entrance_col = 0;
        }
      }
    }

    // Clear maze pathways
    // -------------------
    void clearMaze() {
      for(int x=1; x<rows-1; x++) {
        for(int y=1; y<cols-1; y++) {
          if( matrix[x][y] != '#') {
            matrix[x][y] = ' ';
          }
        }
      }
    }

    // Checks to ensure the coordinates are within the maze
    // ----------------------------------------------------
    bool overEdge(int x, int y) {
      if( x<0 || x>rows || y<0 || y>cols) 
        return true;
      else
        return false;
    }

    // Checks to see if a square is open and has not been visited
    // ----------------------------------------------------------
    bool freeSquare(int x, int y) {
      return (!overEdge(x,y) && matrix[x][y] == ' ');
    }

};

void wrong_args() {
  cout << "Usage: maze MAZE" << endl;
  cout << endl << "MAZE is the name of a maze file." << endl;
}

int main(int argc, char * const argv[]) {

  if( argc != 2 ) {
    wrong_args();
    return -1;
  }

  MazePathFinder maze;
  maze.loadMaze(argv[1]);
  maze.printMaze();
 
  maze.solveMaze();

  maze.printMaze();

  return 0;
}