Solving mazes with 2d arrays. Java. Recursion

Question

need some help with a maze solving program in java.

The program has to read a maze from a file, store it into an array, solve it, and display the solution in a drawing panel. I'm struggling storing it into an array, and I'm really unsure of how to move into solving it and displaying it. But if i could get some help on the array part to get into a groove, I'd really appreciate it.

Here is an example of an input file. I want it to work for any maze of this structure, (with +, -, S, E, and |). The first two numbers, (8, 10) represent the height and width, the # of rows and # of columns.

8 10
+-+-+-+-+-+-+-+-+-+  
|                 |  
+ +-+-+-+ +-+-+-+ +  
| |             | |  
+ + +-+-+-+-+-+ + +  
| | |         | | |  
+ + + +-+-+-+ + + +-+
| | | |     | | |  S|
+ + + + +-+ + + + +-+
| |   |   |E| | | |  
+ + + +-+ +-+ + + +  
| | |         | | |  
+ + +-+-+-+-+-+ + +  
| |             | |  
+ +-+-+-+-+-+-+-+ +  
|                 |  
+-+-+-+-+-+-+-+-+-+

Here is my code so far:

import java.util.Arrays;
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;

public class MazeSolver {

   // The name of the file describing the maze
   static String mazefile;
   static int width;
   static int height;
   public static void main(String[] args) throws FileNotFoundException {
      if (handleArguments(args)) {

         readMazeFile(mazefile);
         DrawMaze.draw();

         if (solveMaze())
            System.out.println("Solved!");
         else
            System.out.println("Maze has no solution.");
      }
      else {
      System.out.println("The arguments are invalid.");
      }
   }

   // Handle the input arguments
   static boolean handleArguments(String[] args) {
      if (args.length > 4 || args.length < 1) {
         System.out.println("There are too many or too few command line arguments");
         return false;
      }
      if (args.length == 1) {
         String mazefile = args[0];
         File file = new File(mazefile);
         if (!file.canRead()) {
            return false;
         }
         return true;
      }
      if (args.length == 2) {
         String mazefile = args[0];
         File file = new File(mazefile);
         if (!file.canRead()) {
            return false;
         }
         int cellsize = Integer.parseInt(args[1]);
         if (cellsize < 10) {
            return false;
         }
         return true;
      }
      if (args.length == 3) {
         String mazefile = args[0];
         File file = new File(mazefile);
         if (!file.canRead()) {
            return false;
         }
         int cellsize = Integer.parseInt(args[1]);
         int borderwidth = Integer.parseInt(args[2]);
         if (borderwidth < 5) {
            return false;
         }
         return true;
      }
      if (args.length == 4) {
         String mazefile = args[0];
         File file = new File(mazefile);
         if (!file.canRead()) {
            return false;
         }
         int cellsize = Integer.parseInt(args[1]);
         int borderwidth = Integer.parseInt(args[2]);
         int sleeptime = Integer.parseInt(args[3]);
         if (sleeptime < 0 || sleeptime > 10000) {
            return false;
         }
         return true;
      }   
      return false;
   }

   // Read the file describing the maze.
   static char[][] readMazeFile(String mazefile) throws FileNotFoundException {

      Scanner scanner = new Scanner(new File(mazefile));
      height = scanner.nextInt();
      width = scanner.nextInt();
      int arrayHeight = 2  * height + 1;
      int arrayWidth = 2 * width + 1;
      char[][] mazeArrays = new char[arrayHeight][arrayWidth];
      while (scanner.hasNextLine()) {
         String line = scanner.nextLine();
         System.out.println(line);
         for (int row = 0; row < arrayHeight; row++) {
            for (int col = 0; col < arrayWidth; col++) {
               mazeArrays[row][col] = line.charAt(col);
            }
         }

      }
      return mazeArrays;
   }

   // Solve the maze.      
   static boolean solveMaze() {
      return true;
   }
}

I think I have the handling of command line arguments down. The readMazeFile method is where I'm currently struggling. I just can't wrap my head around storing the maze in an array and solving it.

Thanks!

Answer 1

The first thing to do is to work out a data structure for you to store the maze in. I suggest using a structure that makes the solving as easy as possible, even if printing is more complicated. Here is a simple example:

class Node {
    private final int row;
    private final int col;
    private final List<Node> paths;
}

class Maze {
    private final int rowCount;
    private final int colCount;
    private final List<Node> nodes;
    private Node start;
    private Node end;
}

This, in my view, is going to be more useful than something like an array. An array would make it easy to print the maze but that's not the most difficult part of the operation. A path finding algorithm needs to be able to easily get the paths from any position which this data structure allows.

You asked for some help on reading the maze. I suggest making the reading method a static 'builder' method inside Maze. In general the structure will be something like:

class Maze {
    public static Maze buildMaze(String mazeFile) {
        // read row & col size from file
        Maze maze = new Maze(rows, cols);
        // skip first line (invariant)
        for (int row = 0; row < rows; row++) {
            // get next 2 lines (for horizontal & vertical paths)
            for (int col = 0; col < cols; col++) {
                // get corresponding horizontal wall or space
                if (isHorizontalPath) {
                    maze.getNode(row,col).addHorizontalPath();
                }
                if (hasVerticalPath) {
                    maze.getNode(row, col).addVerticalPath();
                }
                // check for S and E
                if (isStart) {
                    maze.setStart(row, col);
                } else if (isEnd) {
                    maze.setEnd(row, col);
                }
            }
        }
        return maze;
    }
}