Program To Create a Maze Solver Using Stacks in Java

Instructions

Objective

Write a java homework to create a maze solver using stacks implementation in java language.

Requirements and Specifications

Maze Solver

Create a program to solve a maze using a Stack (also known as Depth First Search).

Allow the user to choose from 3 different mazes that are read in from a text file, and then allow them to choose how to solve the maze. At the top of the text file are two numbers, they are the height and width of the maze. The possible characters in the maze are: ‘*’ – a wall, ‘ ‘ – a movable space, ‘s’ – the starting location, ‘f’ – the finish.

Stack – Use the Stack from Java Collections classes. The Stack is generic, like ArrayLists, so it can store objects of type Point. Point – Your Stack will store Points as the locations in the maze that it will visit. Point is a class in the java.awt library that stores an x and y value. Example of using Point: Point p = new Point( 5, 10 );

System.out.println( “(” + p.x + “,” + p.y + “)” ); //(5,10)

Main – create the following methods:

1. readMaze – pass in the maze number, open the file and read in the first two numbers, construct the 2D array of chars using the rows and columns, then read in the rest of the maze and populate the array with the contents and then return it.
2. displayMaze – pass in the 2D array and print out the maze.
3. findStart – pass in the maze, iterate through the maze to locate the start (‘s’), then return the location of the starting position as a Point.
4. mazeSolver – pass in the 2D array for the maze. Construct a new empty Stack, then call findStart and place the starting location in the Stack. Then repeat the following until the finish is found:

• Remove the top-most Point from the Stack.
• Check to see if this point is the finish (‘f’).
• If it is, end the loop.
• If it’s not, mark the spot in the maze as evaluated (add a ‘.’ in the array). Then check the spots in the maze that are neighboring the current location (up, down, left, right). If it is not a wall, and hasn’t already been evaluated, then add the Point(s) to the Stack.

Source Code

import java.awt.*; import java.io.File; import java.io.IOException; import java.util.Scanner; import java.util.Stack; public class Main { private static final char WALL = '*'; private static final char EMPTY = ' '; private static final char VISITED = '.'; private static final char START = 's'; private static final char FINISH = 'f'; /** * Reads maze as 2D char array from file named "maze{n}.txt" * @param n number of file to read from * @return 2D char array, representing maze */ private static char[][] readMaze(int n) { String filename = "maze" + Integer.toString(n) + ".txt"; try(Scanner scanner = new Scanner(new File(filename))) { String[] parts = scanner.nextLine().split("\\s+"); int height = Integer.parseInt(parts[0]); int width = Integer.parseInt(parts[1]); char[][] result = new char[height][width]; for (int i = 0; i String line = scanner.nextLine(); for (int j = 0 ; j result[i][j] = line.charAt(j); } } return result; } catch (IOException e) { return null; } } /** * Shows maze state in the console * @param maze to show */ public static void displayMaze(char[][] maze) { for (char[] chars : maze) { for (char aChar : chars) { System.out.print(aChar); } System.out.println(); } } /** * Returns position of start cell in maze as a Point object * @param maze to find start in * @return position of start cell */ public static Point findStart(char[][] maze) { for (int i = 0; i for (int j = 0; j if (maze[i][j] == START) { return new Point(j, i); } } } return null; } /** * Builds paths from start to finish in given maze instance * @param maze to find path in */ public static void mazeSolver(char[][] maze) { Stack stack = new Stack<>(); int height = maze.length; int width = maze[0].length; Point start = findStart(maze); stack.push(start); while(!stack.empty()) { Point top = stack.pop(); if (maze[top.y][top.x] == FINISH) { return; } maze[top.y][top.x] = VISITED; if (top.y > 0 && (maze[top.y-1][top.x] == EMPTY || maze[top.y-1][top.x] == FINISH)) { stack.push(new Point(top.x, top.y-1)); } if (top.y < height - 1 && (maze[top.y+1][top.x] == EMPTY || maze[top.y+1][top.x] == FINISH)) { stack.push(new Point(top.x, top.y+1)); } if (top.x < width - 1 && (maze[top.y][top.x+1] == EMPTY || maze[top.y][top.x+1] == FINISH)) { stack.push(new Point(top.x+1, top.y)); } if (top.x > 0 && (maze[top.y][top.x-1] == EMPTY || maze[top.y][top.x-1] == FINISH)) { stack.push(new Point(top.x-1, top.y)); } } } public static void main(String[] args) { try(Scanner scanner = new Scanner(System.in)) { System.out.print("Enter maze # "); int n = Integer.parseInt(scanner.nextLine()); char[][] maze = readMaze(n); displayMaze(maze); System.out.println(); mazeSolver(maze); displayMaze(maze); } } }