Note: This website is archived. For up-to-date information about D projects and development, please visit wiki.dlang.org.

Recursive Maze Solver

Part of TutorialIntermediate

Description

This program uses recursion to solve a maze. The maze is parsed from a text file into an array of char[][]. The input file (MazeInput.txt here) is formated where the first line is the size of the maze, second line is starting location, and third is the ending location. The rest of the file is the maze 'X' denoting a wall.

After the program has run it will print out the path 'P' and where it has been 'V'. The start 'S' and finish 'F' will also be marked. (No output file is written)

Disclaimer

Though this is done using a class it is likely that it would have been better done without one. There aren't many tutorials yet that use classes and this will hopefully be accurate for setting one up.

See File Parsing Article by Brad Anderson - Jan 2004 for more on the parsing of files.

Example

MazeInput.txt

10 10
4 4
9 9
 XXXXX XXX
 X  X  X X
          
XXXXXXX XX
X       X
XXXX XXXX
     X
 XXXX XX
      X
XXXXX     |

'X' = walls and spaces are traversable paths.

Note:: I used '|' to show that there are spaces before it, though leaving it there won't break the program not having the spaces will.

MazeDriver.d

//Used for writef()
import std.stdio;
//Used for read()
import std.file;
//Used for splitlines(), split(), atoi(), format()
import std.string;

int main() {
  Maze myMaze = new Maze();

  writefln("%s", myMaze);

  if(myMaze.solveMaze()) {
    writefln("The maze has been solved.");
    myMaze.markStart();
  }else
    writefln("The maze could not be solved.");

  writefln("%s", myMaze);
  
  return 0;
}

class Maze {

  public:
    // Defines two constants X = 0, Y = 1;
    enum {X, Y};

    /// Constructer, that creats my array of strings (char[][])
    this() {
      // std.string.splitlines() and std.file.read()
      // read(file) will take a file and load everything into a char[].
      // splitlines(char[]) will creat a 2D array where where char[i] holds a line
      try {
        fileIn = splitlines(cast(char[])read("MazeInput.txt"));

        // I assume the size will always be on the first line
        size = getXbyY(0);
        // I assume the start coordenants will be on the second line
        start = getXbyY(1);
        // I assume the end coordenants will be on the third line
        end = getXbyY(2);
        maze = buildMaze();
      }catch(FileException fe) {
        writefln("Caught a file Exception");
        // I don't know what I can do with fe, is it like Java?
      }
    }

    /// Prints the maze to the screen.
    /// I will look for a Java's toString() equivalent
    override string toString() 
    // Using Contracts (in{}out{}body{})
    in {
      // Must evaluate to true or throws an AssertException, wich could be caught
      // Also assert() is left out when $dmd -release is used according to
      // http://www.prowiki.org/wiki4d/wiki.cgi?JavaToD
      // And tested to be true.
      assert(maze);
    }body {
      string result = format("Maze Size: %dx%d\n", size[X], size[Y]);
      // change the array length to about 200 because I know it will be large
      result ~= format("Starting Postion: (%d,%d)\n",start[X],start[Y]);
      result ~= format("Starting Postion: (%d,%d)\n",end[X],end[Y]);

      // for each char[] in maze = (line = char[i++])
      foreach(char[] line; maze)
        result ~= line ~ "\n";

      return result;
    }

    bool solveMaze()
    in {
      assert(maze);
    }body {
      return traverseMaze(start[X], start[Y]);
    }

    void markStart() {
      maze[start[Y]][start[X]] = 'S';
    }

  private:
    char[][] maze;
    int[] start, end, size;
    char[][] fileIn;

    /// Parses a line in the file (now an array) into ints
    int[] getXbyY(int line) {
      int[] result = new int[2];
      // std.string.split() splits a string by whitespace into a char[][]
      char[][] charSize =  split(fileIn[line]);

      version(D_Version2) {
         result[X] = std.conv.to!int(charSize[X]);
         result[Y] = std.conv.to!int(charSize[Y]);
      } else {
         // std.string.atoi() converts strings to int
         result[X] = atoi(charSize[X]);
         result[Y] = atoi(charSize[Y]);
      }

      return result;
    }

    /// @returns A char[][] of the maze from a section of fileIn[][]
    ///   fileIn was the string array created by std.file.read()
    char[][] buildMaze() {
      return fileIn[3..$][0..$];
    }

    /// Makes an attempt to move into x,y and continue to the exit
    bool traverseMaze(int x, int y) {
      if(validMove(x, y))
        if(atEnd(x, y)) {
          // Mark the exit
          maze[y][x] = 'F';
          return true;
        }else {
          // Mark that we moved here
          maze[y][x] = 'V';

          if(  traverseMaze(x+1, y) ||  //Move right
              traverseMaze(x, y+1) || //Move down
              traverseMaze(x-1, y) ||  //Move left
              traverseMaze(x, y-1)) {  //Move up
                // The exit was found and so this location is a part of the path
                maze[y][x] = 'P';
                return true;
          }
        }
        return false;
    }

    /// Checks to see if we are at the ending location
    bool atEnd(int curX, int curY) {
      return (curX == end[X] && curY == end[Y]);
    }

    /// Checks to see if we are in a wall, out of bounds, or somewhere we have been
    bool validMove(int x, int y) {
      // Within the maze bounds?
      if(y < 0 || x < 0 || y >= maze.length || x >= maze[y].length)
        return false;
      // In a wall or where we have been?
      if(maze[y][x] is 'X' || maze[y][x] is 'V')
        return false;

      return true;
    }
}

output

Maze Size: 10x10
Starting Postion: (4,4)
Starting Postion: (9,9)
 XXXXX XXX
 X  X  X X
          
XXXXXXX XX
X       X
XXXX XXXX
     X
 XXXX XX
      X
XXXXX     

The maze has been solved.
Maze Size: 10x10
Starting Postion: (4,4)
Starting Postion: (9,9)
VXXXXXVXXX
VXVVXVVXVX
VVVVVVVVVV
XXXXXXXVXX
X   SVVVX
XXXXPXXXX
PPPPPX
PXXXX XX
PPPPPPX
XXXXXPPPPF