# Maze Generation Assignment solution

1. Write a program that generates a random maze of a requested size.
2. Write a program that implements the DFS technique for solving a maze.

Maze Definition

Your aim is to create a simple maze that will have exactly one path from any point in the maze to any other point (as an example, see Figure 1). Therefore, your maze will not have inaccessible areas (cells without any missing walls around them), open areas (cells without walls), and no circular paths (loops). We can represent our maze as a 2D array (matrix) of Cells. Each Cell knows which of the four possible walls are adjacent to it. Each cell also knows if it is a starting or finishing cell. For example, in the maze shown in Figure 1, the top left-hand corner cell (start) has walls to the top, left, and right, but no wall below it, so we would be able to move from this cell to the cell below in a valid move. This cell would also have a flag to indicate that it is the starting cell. The maze in Figure 1 is a 4x4 maze with 16 cells.

We can simplify the above cell representation somewhat, such that, instead of a cell needing to know about the four directions around it each cell only needs to know if you can move to the cell to the right or to the cell down from it. This requires only 2 bits of information: Both closed (0) Right only open (1) Down only open (2) Both open (3). So our top left-hand corner cell can be represented by the value 2 since we can only move down, and not to the right.

When we need to know about connectivity to cells above or to the left of us, we just need to look at their information. For instance, if I want to know about paths out of the cell in position 6 of the above maze (marked with an X) I know directly how it can move to the right or below. The data for this cell is 0 indicating it can’t move to the right or down. To find if it can move to the top, I look at the data for cell 2 (the cell above it), which has value 3 indicating I can move both rights and down from this cell. This also tells me that I can move up from cell 6. Similarly, I look to the value of the cell to the left to know if I can move left from the current cell.

1. Generating a Random Maze

Although there are many techniques for generating mazes, we will focus on only one technique in this assignment. We will use a Depth First Search (DFS) technique to generate a random maze. The technique is as follows. To generate an n×m maze we create a grid graph of size n×m (for example, see Figure 2 for a 5x5 grid). To generate the maze, we mark a random vertex (vertex 1 in the top left corner in this example) as the start node and then perform a DFS on the graph. When selecting which vertex to visit from the current node, we randomly select an unvisited node from the neighboring vertices. For each edge that appears in our DFS tree, we consider this as a way to move from one cell to another in our resulting maze. Formulated another way, when two nodes are not connected by an edge in the DFS tree, then there is a wall between these two cells in the resulting maze. See Figure 3 for a sample DFS tree and resulting maze.

Here the vertex labels indicate the order in which the nodes were visited in the DFS. The node that is the last one ‘visited’ in our DFS is marked as the finish node (e.g., vertex 25, cell 3 in Figure 3). Your MazeGenerator program should ask the user for the size of the maze, based on the number of columns and rows and a file name for output. It should randomly generate a maze of this size. It will set the randomly visited first node as the start node, and the last node visited in the DFS as the finish node. Once the maze is generated, your program should save the maze to a file in the following format.

n,m:start_node:end_node:cell_openness_list

where

• start_node and end_node are not equal and are between 1 and n×m
• cell_openness values are decided by the following codes. 0: Both closed

1: Right only open 2: Down only open 3: both open

Example file format for the sample maze shown in Figure 3 would be:

5,5:1:3:1223030112231122230210110

2. 2. Solving a Maze with DFS

Your second program MazeSolverDFS will input a maze from a file given as a command-line argument in the format discussed above and solve it using a DFS. When solving a maze your program needs to keep track of the order in which it visits the cells, and

the number of steps taken to ‘walk’ from start to finish. It will also keep track of the time taken to solve the maze.

The program should output:

• The solution to the maze (path from start to finish). For example, looking at the path in Figure 4, the cell ordering is (1,2,7,6,11,16,21,22,17,12,13,14,15,10,9,4,5,4,9,8,3)
• The number of steps in this path. (For example, the number of steps is 20 for the path given above). A step is a move from one cell to the next. Note that the sample solution contains a loop which is when a wrong path was taken, and we need to backtrack to then find the endpoint.
• The time is taken to solve the maze, in milliseconds. Solution:

1.

``` import java.util.*; public class Maze { // coordinates shift for each of directions private static final int[][] DIRS = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; // directions constants private static final int LEFT = 0; private static final int UP = 1; private static final int RIGHT = 2; private static final int DOWN = 3; /** * Maze height */ private final int height; /** * Maze width */ private final int width; /** * 2D array of maze cells */ private final Node[][] graph; /** * Start cell of maze */ private final Node startNode; /** * Finish node of maze */ private final Node finishNode; /** * Constructor for parsing maze from string * @param s string to parse maze from */ public Maze(String s) { // separating string into parts with delimiter ' String[] parts = s.split(":"); // there must be 4 parts if (parts.length != 4) { throw new IllegalArgumentException("Invalid number of delimiters ':'"); } // first part contains height and width, separated with ',' String[] parts2 = parts.split(","); // there must be 2 parts after separating if (parts2.length != 2) { throw new IllegalArgumentException("Invalid number of delimiters ','"); } // parsing height height = Integer.parseInt(parts2); // parsing width width = Integer.parseInt(parts2); // creating cells 2D-array graph = new Node[height][width]; for (int i = 0; i= 2, it means, that down door for current cell is open if (code / 2 == 1) { graph[row][column].neighbours[DOWN] = graph[row+1][column]; graph[row+1][column].neighbours[UP] = graph[row][column]; } } } /** * Constructor for creating maze with given height, width and start cell. * If startIndex == 0, start node is selected randomly * @param height of maze to create * @param width of maze to create * @param startIndex index of start cell. If equals 0, start is selected randomly */ public Maze(int height, int width, int startIndex) { // validating sizes if (height < 2 || width < 2) { throw new IllegalArgumentException("Invalid size"); } // validating start index if (startIndex < 0 || startIndex > height * width) { throw new IllegalArgumentException("Invalid start"); } // assigning size parameters this.height = height; this.width = width; // selecting start index if it equals 0 Random random = new Random(); if (startIndex == 0) { startIndex = random.nextInt(height * width) + 1; } // creating cells 2D-array graph = new Node[height][width]; for (int i = 0; i visited = new ArrayList<>(); // adding start cell to visited collection visited.add(startNode); // generating maze, using DFS algorithm buildMaze(startNode, visited); // finish node is last visited node finishNode = visited.get(visited.size()-1); } /** * Constructor for creating maze with given height, width and random start cell. * @param height of maze to create * @param width of maze to create */ public Maze(int height, int width) { this(height, width, 0); } /** * Method for finding path from start cell to finish cell in maze using DFS approach * @return list of cell indices in order of visiting */ public List solve() { // creating collection of visited cells. List visited = new ArrayList<>(); // adding start cell to visited collection visited.add(startNode); // creating list of passed indices List path = new ArrayList<>(); // calling recursive procedure from start node with initialized visited and path variables solve(startNode, visited, path); // returning result path return path; } /** * Helper recursive method * @param node to continue DFS from * @param visited current collection of visited cells * @param path current list of visited cell indices * @return true, if solution is already found, false - otherwise */ private boolean solve(Node node, Collection visited, List path) { // adding current cell index to path path.add(node.index); // if current cell is finish cell, returning true if (node.index == finishNode.index) { return true; } // generating list of dirs, containing all directions List dirsList = new ArrayList<>(); for (int i = 0; i visited) { // generating list of dirs, containing all directions List dirsList = new ArrayList<>(); for (int i = 0; i= 0 && r < height && c >= 0 && c < width) { // getting neighbor cell Node next = graph[r][c]; // checking, that neighbor cell is not visited yet if (!visited.contains(next)) { // adding this not-visited cell to visited collection. visited.add(next); // opening appropriate door of current cell and appropriate door of neighbor cell node.neighbours[dir] = next; next.neighbours[2 * (1 - dir / 2) + dir % 2] = node; // continue build maze from neighbor cell buildMaze(next, visited); } } } } /** * Overridden method for generating code string for maze * @return code string of this maze */ @Override public String toString() { StringBuilder builder = new StringBuilder(); // appending maze size builder.append(height).append(',') .append(width).append(':') // appending start cell index .append(startNode.index).append(':') // appending finish cell index .append(finishNode.index).append(':'); // for each cell of maze appending its neighbor code for (int i = 0; i```

``` import java.io.IOException; import java.io.PrintWriter; public class MazeGenerator { /** * Main driver method of MazeGenerator app * @param args command-line arguments */ public static void main(String[] args) { // validating number of command line arguments if (args.length != 3) { throw new IllegalArgumentException("Illegal number of command line arguments. 3 arguments expected"); } // validating and parsing maze height int height; try { height = Integer.parseInt(args); } catch (NumberFormatException ignored) { throw new IllegalArgumentException("Can not parse maze height. Positive integer expected"); } // validating and parsing maze width int width; try { width = Integer.parseInt(args); } catch (NumberFormatException ignored) { throw new IllegalArgumentException("Can not parse maze width. Positive integer expected"); } // generating maze with given parameters and writing it to file with given filename try (PrintWriter pw = new PrintWriter(args)) { Maze maze = new Maze(height, width); pw.println(maze); } catch (IOException ignored) { throw new IllegalArgumentException("Can not open output file"); } } } ```

2.

``` import java.io.File import java.io.IOException; import java.util.List; import java.util.Scanner; import java.util.stream.Collectors; public class MazeSolverDFS { /** * Main driver method of MazSolverDFS app * @param args command-line arguments */ public static void main(String[] args) { // validating number of arguments if (args.length != 1) { throw new IllegalArgumentException("Illegal number of command line arguments. 1 argument expected"); } // scanning input file try (Scanner scanner = new Scanner(new File(args))) { // creating maze Maze maze = new Maze(scanner.nextLine()); // starting time count long start = System.currentTimeMillis(); // solving maze List result = maze.solve(); // stopping time count long time = System.currentTimeMillis() - start; // outputting result path System.out.println("(" + result.stream().map(i -> Integer.toString(i)).collect(Collectors.joining(",")) + ")"); // showing path length System.out.println(result.size() - 1); // showing time used System.out.println(time); } catch (IOException ignored) { throw new IllegalArgumentException("Can not open input file"); } } } ```