Maze generation and solving algorithm services

Maze Generation and Solving Algorithms

1 Objective

There are three key objectives for this project:

Design and implement a number of algorithms to generate 2D mazes. Design and implement a number of algorithms to solve these mazes.

2 Backgrounds

Mazes have a long history and many of us would remember seeing our first mazes in a puzzle book and trying to trace a path from entrance to exit.

Maze solving seeks to find a path to the exit(s), either from a set of entrance(s), or from somewhere inside the maze. Maze generation, conversely, seeks to use algorithms to construct mazes.

In this assignment, you will explore and implement algorithm(s) to generate and solve mazes.

We first provide some background about maze types, maze generation and maze solving algorithms.

2.1 Mazes

There are multiple types of mazes. In this assignment, we are interested in 2D, rectangular and hexagon, perfect mazes. Mazes are made up of a number of cells and walls (see Figure 2 for an example cell with four walls). 2D mazes are layout on a 2d plane. Rectangular mazes have rectangular cells with 4 sides, where each side can have a wall, see Figure 1a for an illustration. Hexagon mazes have hexagon cells with 6 sides, that can have 6 walls which are at 120 degree angle to their adjacent walls, see Figure 1b for an illustration. Perfect mazes are ones where every cell in the maze can be potentially visited and have no loops, see Figure 1 for examples. In this assignment, we additionally introduce tunnelled mazes. These mazes have a number of tunnels, which link non-adjacent cells, see Figure 1c. If we enter one end of the tunnel, we will exit at the other end of the tunnel.

2.2 Maze Generation Algorithms

There are many maze generation algorithms, each generating mazes of different characteristics. We focus on the following three algorithms.

2.2.1 Recursive Backtracker This generator uses the DFS principle to generate mazes. Starting with a maze where all walls are present, i.e., between every cell is a wall, it uses the following procedure to generate a maze:

Randomly pick a starting cell.

Pick a random unvisited neighboring cell and move to that neighbor. In the process, carve a path (i.e, remove the wall) between the cells.

Continue this process until we reach a cell that has no unvisited neighbors. In that case, backtrack one cell at a time, until we backtracked to a cell that has unvisited neighbors. Repeat step 2.

When there are no more unvisited neighbors for all cells, then every cell would have been visited and we have generated a perfect maze.

2.2.2 Prim's This generator is based on Prim's algorithm for computing minimum spanning tree. We used the modified version of it. Starting with a maze where all walls are present, i.e., between every cell is a wall, it uses the following procedure to generate a maze:

Pick a random starting cell and add it to set Z (initially Z is empty, after addition it contains just the starting cell). Put all neighboring cells of starting cell into the frontier set F.

Randomly select a cell c from the frontier set and remove it from F. Randomly select a cell b that is in Z and adjacent to the cell c. Carve a path between c and b.

Add cell c to the set Z. Add the neighbors of cell c to the frontier set F.

Repeat step 2 until Z includes every cell in the maze. At the end of the process, we would have generated a perfect maze.

2.2.3 Growing Tree This generator is interesting, as it can mimic the behavior of both the recursive backtracker and Prim's algorithm. Starting with a maze where all walls are present, i.e., between every cell is a wall, it uses the following procedure to generate a maze:

Pick a random starting cell and add it to set Z (initially Z is empty, after addition it contains just the starting cell).

Using a particular strategy (see below) select a cell b from Z. If cell b has unvisited neighboring cells, randomly select a neighbor, carve a path to it, and add the selected neighbor to set Z. If b has no unvisited neighbors, remove it from Z.

Repeat step 2 until Z is empty.

Depending on what strategy is used to select a cell from V, we obtain different behavior. If we select the newest cell added to V, then this is the same as recursive backtracker. If we randomly select a cell in V, then this is similar to Prim's generation approach. Other strategies can be a mixture of both.

2.3 Maze Solving Algorithm Similar to generation algorithms, there have been many solvers proposed. In this assignment, we focus on the following two.

2.3.1 Wall Follower This is a simple but generally effective solver. It follows passages in the maze, and when it comes to an intersection, it always turns left (or right, either is okay, but as long as consistent). 2.3.2 Bidirectional Recursive Backtracker This solver performs DFS (Depth First Search) searches starting at both the entrance and exit. When starting at the entrance of the maze, the solver will initially randomly choose an adjacent unvisited cell. It moves to that cell (which is the current front for DFS starting at the entrance), update its visit status, then selects another random unvisited neighbor. It continues this process until it hits a dead-end (no unvisited neighbors), then it backtracks to a previous cell that has an unvisited neighbor. Randomly select one of the unvisited neighbor and repeat process until we reached the exit (this is always possible for a perfect maze). The path from entrance to exit is the solution. When the two DFS fronts first meet, the path from the entrance to the point they meet, and the path from the exit to the meeting point forms the two halves of a shortest path (in terms of cell visited) from entrance to exit. Combine these paths to get the final path solution.

3 Tasks

The project is broken up into a number of tasks.

Task A: Implement Maze Generators To explore the different approaches to maze generation, in this task, you will implement the three different maze generation algorithms for the different maze types. The maze generators to implement are: Recursive backtracker Prim's Growing tree The types of mazes we want to generate with these algorithms are as follows: 2D rectangular perfect maze with no tunnels (type A) 2D hexagon perfect maze with no tunnels (type B) 2D rectangular perfect maze with tunnels (type C) However, not every algorithm can generate all three types of mazes. Hence, you only need to implement the recursive backtracker algorithm to generate all three types of mazes; for prim's and growing tree algorithms, you only need to generate the mazes without tunnels, i.e., the rst two. The following table states which type of maze each of your generator implementation should be able to construct:

Task B: Implement Maze Solver

In this task, you are to implement two solvers to see how different mazes affect the different solvers. The solvers to implement are the Wall Follower and the Bidirectional Recursive Backtracker solvers. They should be able to solve all three type of mazes.

Details for both tasks

As explained above, your task is to implement the three generation and two solving approaches for different types of mazes. Which maze type, generator and solver will be specified in a parameter setting le.

To help you get started, you are provided with skeleton code that implements the data structures for the three types of mazes.

In addition, we provide a main class (MazeTester) which parses parameters, specified in a le, and correctly call the specified generator, optionally visualise the generated maze and optionally call the specified solver on the maze.

Note,

Please do not modify MazeTester class at all, as this contains some of the evaluation code, hence we will be using our copy to do the evaluation and any changes will not be included.

We also strongly suggest not modifying any of the “No need to modify" files.

You may add methods and java les, but it should be within the structure of the skeleton code, i.e., keep the same directory structure. Similar to assignment 1, this is to minimise compiling and running issues.

The onus is on you to ensure correct compilation on the core teaching servers.

As a friendly reminder, remember how packages work and IDE like Eclipse will automatically add the package qualifiers to les created in their environments.

Compiling and Executing

To compile the les, run the following command from the root directory: javac -cp .:mazeSolver/SampleSolver.jar *.java To run the maze visualisation and evaluation algorithm, run the following command: java -cp .:mazeSolver/SampleSolver.jar MazeTester where

parameter file: name of the file that contains the parameter specifications of the run.
visualise maze and solver path: [y/n], to indicate whether to visualise (y) or not (n). (Please read \using Putty for visualisation.pdf" (as attached in this assignment folder in Blackboard) for how to make the visualisation work on teaching server when using Putty on Windows or SSH on Mac.)

The jar le contains bytecode for a solver we have already coded up. This is to help you see a solver in action on your maze (before you have implemented your own solvers). We now describe the contents of the parameter file.

Parameters

The parameter le specifies all the settings for the maze generation, evaluation and visualisation. This le has the following format: mazeType generatorNamesolverName numRownumCol entranceRow e n t r a n c e C o l exitRow e x i t C o l t u n n e l L i s t Where parameters are as follows:

mazeType: The type of maze to generate, where it should be one of fnormal, tunnel, hexg.

generatorName: Name of maze generation algorithm, where it should be one of frecurBack, growingTree, modiPrimg. recurBack is recursive backtracker, growingTree is the growing tree algorithm, and modiPrim is (modied) prim's algorithm.

solverName: Name of the maze generation algorithm, where it should be one of fwallFollower, biDirrecurBack, sample, noneg. biDirrecurBack is bidirectional Recursive Backtracker, wallFol-lower is the wall follower algorithm (solver), sample is a sample solver for you to visualise solving and none is to specify that no solving is wanted.

numRow: Number of rows in the generated maze, it should be a positive integer (1 or greater).

numCol: Number of columns in the generated maze, it should be a positive integer (1 or greater).

entranceRow: the row of the entrance cell, should be in range [0, numRow-1].

entranceCol: the column of the entrance cell, should be in range [0, numCol-1].

exitRow: the row of the exit cell, should be in range [0, numRow-1].

exitCol: the column of the exit cell, should be in range [0, numCol-1].

For tunnel mazes, we have additional parameters (the non-tunnelled mazes will ignore these parameter settings if they are specified):

tunnelList: list of tunnels, one per line. Each line consists of the (row, column) of the cells on each end of the tunnel. For example, \a b c d" means one end of the tunnel is at (a, b) while the other end is (c, d). Each row must be in range [0, numRow-1], each column in range [0, numCol-1].

An example parameter file is as follows: hex modiPrim w a l l F o l l o w e r 30 30 2 0 0 0 This specifies the following parameters:

Generating hexagonal mazes

Using modified Prim's algorithm for generation

Using wallFollower for solving

The maze has 30 rows and 30 columns (30 by 30 maze)

Entrance is located at cell (2,0).

Exit is located at cell (0,0).

An example parameter le for tunnel mazes. t u n n e l recurBack none 50 50 0 5 49 12 5 9 15 9 3 7 14 8 0 0 22 12 This specifies the following parameters:

Generating (rectangular) tunnel mazes

Using recursive backtracker algorithm for generation

No solver, just maze generation

The maze has 50 rows and 50 columns (30 by 30 maze)

Entrance is located at cell (0,5).

Exit is located at cell (49,12).
There are three tunnels.

First tunnel has one end at (5,9) and the other end at (15,9)

Second tunnel has one end at (3,7) and the other end at (14,8)

Third tunnel has one end at (0,0) and the other end at (22,12)

Maze generation and solving algorithms homework help

Maze Generation and Solving Algorithms