Creating a maze solution algorithm in Java

Question

I was entrusted with the task of creating a maze in Java. Here's the task:

Write an application that finds a path through a maze. The maze should be read from a file. A sample maze is shown below. OOOOOXO XXOXOOX OXOOXXX XXXOOXO XXXXOOX OOOOOOO XXOXXXO 

The “X” represents a wall or a blocked position, and the “O” represents an open position. You can assume that the entrance to the maze is always in the lower right hand and the exit is always in the upper left corner. Your program should send the output to a file. If a path is found, the output file must contain the path. If the path is not found, the message should be sent to the file. Note that a maze can have more than one solution path, but in this exercise you will be asked to find one solution, not all solutions.

Your program should use the stack to write the path that it is exploring, and back off when it reaches a locked position.

Be sure to write a complete algorithm before writing code. Feel free to create any additional classes that will help you complete the task.

 Here my Algorithm: 1)Initialize array list to hold maze 2)Read text file holding maze in format oxxxxo ooxoxx ooooox xxxxoo 3)Create variables to hold numbers of columns and rows 3)While text file has next line A. Read next line B. Tokenize line C. Create a temporary ArrayList D. While there are tokens i. Get token ii. create a Point iii. add point to temp ArrayList iv. increment maximum number of columns E. Add temp to maze arraylist, increment max rows F. initialize a hold of points as max rows - 1 G. Create a start point with x values as maximum number of rows - 1, and y values as maximum number of columns - 1 H. Create stack of points and push starting location I. While finished searching is not done i. Look at top of stack and check for finish ii. check neighbors iii. is there an open neighbor? - if yes, update flags and push - if no, pop from stack J. Print solution 4. Done is true 

Anyway, what I created is the Points class, which has set / get methods for moving in all the main directions that return boolean values, as shown:

 public class Points<E> { private int xCoord; private int yCoord; private char val; private boolean N; private boolean S; private boolean E; private boolean W; public Points() { xCoord =0; yCoord =0; val =' '; N = true; S = true; E = true; W = true; } public Points (int X, int Y) { xCoord = X; yCoord = Y; } public void setX(int x) { xCoord = x; } public void setY(int y) { yCoordinate = y; } public void setNorth(boolean n) { N = n; } public void setSouth(boolean s) { S= s; } public void setEast(boolean e) { E = e; } public void setWest(boolean w) { W = w; } public int getX() { return xCoord; } public int getY() { return yCoord; } public char getVal() { return val; } public boolean getNorth() { return N; } public boolean getSouth() { return S; } public boolean getEast() { return E; } public boolean getWest() { return W; } public String toString1() { String result = "(" + xCoord + ", " +yCoord + ")"; return result; } 

}

I just have problems with the actual solution basically. Here is what I have:

 import java.io.*; import java.util.*; import java.lang.*; import java.text.*; public class MazeSolve1 { public static void main(String[] args) { //Create arrayList of Points ArrayList<ArrayList<Points>> MAZE = new ArrayList<ArrayList<Points>>(); Scanner in = new Scanner(System.in); //Read File in System.out.print("Enter the file name: "); String fileName = in.nextLine(); fileName = fileName.trim(); FileReader reader = new FileReader(fileName+".txt"); Scanner in2 = new Scanner(reader); //Write file out FileWriter writer = new FileWriter("Numbers.out"); PrintWriter out = new PrintWriter(writer); boolean done = false; int maxCol = 0; int maxRow = 0; while(!done) { //creating array lists while (in2.hasNextLine()) { //Read next line String nextLine = in2.nextLine(); //Tokenize Line StringTokenizer st = new StringTokenizer(nextLine, " "); //Create temp ArrayList ArrayList<ArrayList<Points>> temp = new ArrayList<ArrayList<Points>>(); //While there are more tokens while (st.hasNextToken()) { String token = st.nextToken(); Points pt = new Points(); temp.add(pt); maxCol++ } MAZE.add(temp); maxRow++; } //create hold arraylist for max rows of maze -1 //create variables for start x and y coordinates ArrayList<ArrayList<Points>> hold = new ArrayList<ArrayList<Points>>(); hold = MAZE.get(maxRow - 1); int startColumn = hold.get(maxCol - 1); int startRow = hold.get(maxRow - 1); Point start = new Point(); start.setX(startColumn); start.setY(startRow); //initialize stack, and push the start position MyStack<Points> st = new ArrayStack<Points>(); st.push(start.toString1()); //south and east of start are edges of array start.setSouth(false); start.setEast(false); //while your position is not equal to point (0,0) [finish] while (st.peek() != "(0, 0)") { //getting the next coordinate to the North int nextY = start.getY() - 1; int nextX = start.getX(); //if character to the North is an O it open and the North flag is true if (hold.get(nextY) = 'O' && start.getNorth() == true) { //set flags and push coordinate start.setNorth(false); st.push(start.toString1()); } //else pop from stack else { st.pop(); } //look at coordinate to the East nextX = start.getX() + 1; //if character to the East is a O and the East flag is true if (hold.get(nextX) = 'O' && start.getEast() == true) { //set flags and push coordinate start.setEast(false); st.push(start.toString1()); } //else pop from stack else { st.pop(); } //look at coordinate to the South nextY = start.getY() + 1; //if character to the South is a O and the West flag is true if (hold.get(nextY) = 'O' && start.getSouth() == true) { //set flags and push coordinate start.setSouth(false); st.push(start.toString1()); } //else pop from stack else { st.pop() } //keep looping until the top of the stack reads (0, 0) } done = true; } //Print the results System.out.println("---Path taken---"); for (int i = 0; i< st.size(); i++) { System.out.println(st.pop); i++ } 

Besides any syntax errors, could you guys help me out? Many thanks.

Answer 1

I presented a similar answer here. Algorithm for solving the maze in C ++ .

To have a chance in resolving this issue, you must:

• Create a Solve() routine and call yourself recursively:
  • if 1, 2, 3, ... are true Solve managed to find a solution
  • If the 1st, 2nd, 3rd, ... contains a lie, he must retreat and find another way.
• You need to create a buffer in which you had to avoid endless loops
  • when you make moves, he needs to follow him.
  • when we come to a standstill, we need to erase the bad moves.
  • we can implement the above by burning under the assumption and removing it if it is wrong

Here is some pseudo code for the solution.

 boolean solve(int X, int Y) { if (mazeSolved(X, Y)) { return true; } // Test for (X + 1, Y) if (canMove(X + 1, Y)) { placeDude(X + 1, Y); if (solve(X + 1, Y)) return true; eraseDude(X + 1, Y); } // Repeat Test for (X - 1, Y), (X, Y - 1) and (X, Y + 1) // ... // Otherwise force a back track. return false; } 

Answer 2

You should probably have a module in your program - as I can understand, you are reading the maze from the file and trying to solve it at the same time.

The best approach would be to split the program into two separate parts:

• read the input file and create a matrix with all the data
• solve a maze from a given matrix

This will help you build and test each part separately, which is likely to lead to a better, more reliable program.

Maze solution can be done with simple DFS

Answer 3

As Amit said, you must first read the entire maze and save it as a 2-dimensional array. This allows you to see the entire maze without solving it in turn.

Since you need to first find the size of the array, you should read the text file in the list of strings.

 List<String> strs = new ArrayList<String>(); //Pseudocode, choose however you want to read the file while(file_has_next_line) { strs.add(get_next_line); } 

The size of the list gives you the number of rows and assumes that it is always a grid, you can use split (). length, (count spaces + 1) or count characters on any of the lines to get the number of columns.

The easiest way to save map data is a 2D Boolean array. Where truth is wall and false is empty space.

 boolean[][] wallMap = new boolean[rows][cols]; for(int i = 0; i < wallMap.length; i++) { //Separate each symbol in corresponding line String[] rowSymbols = strs.get(i).split(" "); for(int j = 0; j < wallMap[i].length; j++) { //Ternary operator can be used here, I'm just keeping it simple if(rowSymbols[j].equals("X")) { wallMap[i][j] = true; } else { wallMap[i][j] = false; } } } 

Now that you have the map data stored in the array, it’s much easier to move around the map and make your choice, you can either use a ready-made algorithm (see amit answer) or make your own. Since this is homework, you should try and come up with your own.

Good luck.

Answer 4

You need to separate your program in two stages. The first is initialization, where you read the description of the maze and the player’s starting position. After that, you have a data structure to represent the board. The second is a real game where there should be 3 abstractions:

• Player Status In your case, it is quite simple, its actual position on the board.
• The labyrinth itself, which is the medium. It should have functions telling you if you visited a given position to mark the position you visited, where is the target, the closest available cells, etc.
• Logic, which is a search algorithm.

Any of them should be able to change without significant changes to others. For example, you may be asked to improve your search algorithm or problem when you have several goals. The ease of transition from the current problem to a slightly modified one is a real metric of program design.

Answer 5

I tried to implement this using the DFS algorithm using some Java OOP concepts.

See the complete solution on my github repository

 private boolean solveDfs() { Block block = stack.peekFirst(); if (block == null) { // stack empty and not reached the finish yet; no solution return false; } else if (block.equals(maze.getEnd())) { // reached finish, exit the program return true; } else { Block next = maze.getNextAisle(block); // System.out.println("next:" + next); if (next == null) { // Dead end, chose alternate path Block discard = stack.pop(); discard.setInPath(false); // System.out.println("Popped:" + discard); } else { // Traverse next block next.setVisited(true); next.setInPath(true); stack.push(next); } } return solveDfs(); 

}