[SOLVED] COSC1285/2123 Assignment 2-Exploring Maze Generation and Solving Algorithms Solved

In this assignment, you will implement and explore algorithms for maze generation and solving. This assignment extends upon Assignment 1, and focuses on algorithmic design and understanding.This assessment relates to two learning outcomes of the course which are:In Assignment 1, we studied 2D mazes and two data structures for representing/storing them. In this assignment, we extend this to 3D mazes in addition to rows and columns, we now have a number of levels. The aims is still to find a path from an entrance to an exit, but now we can additionally go up or down a level. See Figure 1 for an example.Figure 1: Sample 3D maze that has 3 levels. Level 0 is 5 by 5, level 1 is 6 by 6 and level 2 is 10 by 5. The entrances are illustrated as arrows pointing towards the maze, and exits are illustrated as arrows pointing away from the maze. The cells of the maze are indexed from 0, and the row and column indices are drawn outside the maze. Note that the bottom left cell on the lowest level (level 0) is (0,0,0), and top right cell is (0,4,4), where the the format is (level, row, column). This follows the convention that matplotlib follows. Note the exits and entrances do not all have to be on level 0, they can be on any level. The indexing of the cells in levels 1 and 2 are aligned with this indexing, e.g., the cell on level 1 that is above cell (0,0,0) on level 0 is (1,0,0). To illustrate passages between cells of different floors, a passage to a cell on the adjacent higher level is illustrated by a red triangle, while a cell on the adjacent lower level is illustrated by a blue triangle.We are focused on perfect mazes, where there is always a path from entrance to exit(by the virtue that in a perfect maze, there is always a path from a cell in the maze to any other cell in the maze).Each cell has 4 sides on a level, and possibly one cell one level above it, and one cell one level below it. There is no standard way to reference the cells, hence we adopted the convention illustrated in Figure 1, with (0,0,0) (level, row, column) denoting the bottom left cell on the lowest level (always referenced from 0, or level 0), and columns increase as we travel to the right of the maze (page), and rows increases as we travel up the maze (page). Similar to Assignment 1, in order to specify the entrances and exits, we have added one row above, and one row below each level of the maze, and one column to the left, and one column to the right of each level. This means the row below the maze is referenced as -1, the row above by 5 (if we have 5 rows in the maze), the additional column to the left of the maze by -1, and the column to the right by 5 (if we have 5 columns in the maze). This allows us to still be able to use the original indexing, i.e., (0,0,0) refers to the bottom left cell of the maze on level 0, but still able to reference the location of entrances and exits. This is the same convention as Assignment 1, apart from addition of levels.There are strategies and algorithms to solve a maze, i.e., find such a solution path given a maze. There are also strategies and algorithms to generate a maze. We will focus on these generation and solving strategies in this assignment.The assignment is broken up into a number of tasks, to help you progressively complete the project.To gain a better understanding of how mazes are generated, you will implement two maze generation algorithms. We also provide an implementation for your study, and to allow you to progress with maze solving even if you cant get some of the maze generators working. Each algorithm can produce different types of mazes, which is something we will explore further in Task D.We provide the following maze generation algorithms:1.We ask you to study, understand and implement two more advanced and different algorithms.See the provide skeleton code also for additional information on how we implemented the Recursive Backtracking maze generation algorithm, particularly how we used the Maze3D data structure. Below is some description of the algorithms, but please attend the lectorials and read the online material, where further descriptions will be provided.The recursive backtracking maze generator is essentially a DFS generator. Starting with a maze with walls between all adjacent pairs of cells, it randomly selects a cell in the maze, and perform a DFS traversal of the whole maze, from that initial cell. During the DFS traversal, we generate all the unvisited neighbours of the current cell, and randomly select one of those to go to. When we go to an unvisited cell, we remove/destroy the wall between the current cell to the selected unvisited neighbouring cell. If there is no unvisited neighbouring cell from our current one, we backtrack to the cell we were at previously. The DFS ends when we have visited all the cells in the maze.Prims algorithm for maze generation is very similar to Prims algorithm, particularly when we also using a graph representation of the maze. We start with a maze with walls between all pairs of adjacent cells. We select a random starting cell and put it into the visited set. We find all the neighbours of this cell, and this forms the frontier set. We select the cell/node with lowest weight in the frontier set (in our maze case, unless there is differences in moving between cells, all the edge weight/costs are the same, which means we randomly pick one). We then add that selected cell/node to the visited set, remove the wall between the selected cell and its neighbour that caused it to be added to the frontier set, remove it from the frontier set, and add all of the selected cells unvisited neighbours to the frontier set. We repeat this until all cells/nodes are in the visited set.Wilsons maze generation algorithm is one algorithm that can generate all mazes of any given size with equal probability i.e., it doesnt favour one type of maze over another.The algorithm, like the previous two, starts with a maze with walls between all pairs of adjacent cells. Also initially every cell in the maze is considered as not finalised. It then starts by randomly selecting a starting cell, that is the first cell to be considered as finalised. Select another cell, at random, that isnt finalised yet. Perform a random walk from this 2nd selected cell, until this random walk visits a cell that is finalised. Once this occurs, return to the initial selected cell, and carve a path from that cell to the last visited cell. Where the random walk looped back to a cell it has visited before (hence that cell can have two neighbouring cells it can go next), we choose the direction/cell that it most recently took by selecting only one, we can avoid loops, which is not something we want generated (for this assignment).In the last task, we studied and implemented a number of maze generation algorithms. In this task, we will focus on maze solving algorithms. Similar to the previous task, we provide a Recursive Backtracking solving algorithm, and ask you to implement two others that are similar to each other, the Wall Following solving algorithm and the Pledge solving algorithm to improve your understanding of how maze solvers work.We provide the following maze solving algorithms:We ask you to study, understand and implement two more advanced and different algorithms.See the code also for additional information on how we implemented the Recursive Backtracking solving algorithm, particularly how we used the Maze3D data structure. Below is some description of the algorithms, but please attend the lectorials and read the online material, where further descriptions will be provided.The recursive backtracking maze solver is the equivalent of the recursive backtracking maze generator. It starts at an entrance, and from the current cell, finds an unvisited neighbouring cell and go there (and mark it visited). Then it continues until either it reaches an exit, or a deadend, by which then it backtracks to a cell where there is at least one unvisited neighbour.This algorithm is a simple heuristic and one that a human might follow. Starting at the entrance, once we step into the maze, imagine we either reach out our right (left) hand and follow the right (left) wall. We maintain contact with our right (left) hand until we reach the exit. When we lose contact with the wall, we rotate then move forward. The rotation is according to a cyclic order. For a 2D maze and right hand rule, it will be a 90 degree turn, e.g., the order {North, East, South, West}. That is, if we were going in a North direction, when rotate, we will head East; when we are heading East, and rotate, we will be heading South, etc. This wont work for a 3D maze, but if we project going up or down a level to a 2D maze by extending the rotations we can do as follows: {North, North-East, East, South, Sourth-West, West}, where North-East is equivalent to heading in the direction of going up one level, and South-West is equivalent to heading in the direction of going down one level. When we turn/rotate, we cycle through the six directions for a 3D maze. With this extension, this algorithm can solve a 3D maze if there isnt loops, which is the case for this assignment.The Pledge algorithm is an extension of the wall following approach. Initially, we start at an entrance and select a direction (one of the six directions in the Wall Following algorithm description above) to travel (at random), and keep moving in that direction until we hit a wall (or find the exit). We then perform wall following with either the left or right hand rule. We also keep count of the angle of turns we have made, e.g., if we consider going up a level is NE, and going down is SW (see Wall-following algorithm), then a left turn is -60, and a right turn is 60. This angle tracking, when done during the wall following step, means once we have done a series of turns where we have rotated enough times to go in the initial selected direction (angle = 0). We then proceed again with going in the initial direction until hit a wall etc. We then repeat the process until we find the exit. The Pledge algorithm is less likely than the Wall following algorithm to be stuck in loops.This is the first of two tasks where you will get opportunities to extend and explore beyond standard implementations. Typically a maze will have an entrance and an exit, and a maze solving algorithm will only need to go from the entrance to the exit, and we only seek to find a path.However, when we have multiple entrances and exits, there are multiple paths from one of the entrances to one of the exits. We then can introduce the concept of closest entrance-exit pair.In this task, youll explore and design algorithms to find these closest pair of entrances and exits and a solution path between them. However, there is a number of conditions we have to find the paths between the entrances and exits, and additionally, we include the cells explored by the path finders/solvers as the cost of finding this path. We wish to find the path of entrances and exits that:min(cells explored() + distance(entrance, exit))where we are only given the set of entrances but not the location of the exits, hence need to locate the exits. We are given the number of exits there are. To help you get started, select one of the solvers, either provided or implemented by you, and solve the problem where we have one entrance and multiple exits. Once you solved this, then extend this to the case where there are multiple entrances (and still multiple exits).Note that:To help us understand your approaches, we ask you to write a report of up to 2 pages as part of this task, in addition to your implementation.This task is likely the most difficult of the Tasks A-D, and is considered as a HD task and suggested to be tackled last.In this task, a town of maze generators and solvers is running a competition. There is a number of solvers with known solving strategies (algorithms), and the town is running a competition where competitors generate different mazes such that the average cells explored over a number of generated mazes is maximised. The identify of the solvers are known each time a competitor is asked to generate a maze.They also have a bonus part, where there is a mystery solver (with unknown strategy) and the idea is to generate a maze that will maximise the cell taken on average, regardless of what strateg(ies) the solver used.Note that:To help us understand your approaches, we ask you to write a report of up to 2 pages as part of this task, in addition to your implementation and comments.After your implementations and report are submitted, you will be asked to record your responses to a number of questions in Canvas. These questions will ask you about aspects of your implementation or report. Youll have a set time to consider the questions, make a recording then upload that recording. More details will be explained closer to submission.We provide Python skeleton code (see Table 1) to help you get started and ensure we have consistent interfacing so we can have consist correctness testing.We also listed the files that you really need to modify/implement. Unlike Assignment 1, there are more files you need to implement, hence see Table 1 to confirm those.As a guide, the report could contain the following sections:Please periodically check the assignment FAQ for further clarifications about specifications. In addition, the lecturer will go through different aspects of the assignment each week, so even if you cannot make it to the lectorials, be sure to check the course material page on Canvas to see if there are additional notes posted.The final submission will consist of three parts:Note: submission of the report and code will be done via Canvas. We will provide details closer to the submission deadline.The project will be marked out of 30.The assessment in this project will be broken down into three parts. The following criteria will be considered when allocating marks.Tasks A and B (13/30):Task C (7/30):Task D (8/30):Video Interview 2/30:This is a pass/fail assessment, and youll be assessed based on your ability to answer some questions about your implement and report.Late Submission Penalty: Late submissions will incur a 10% penalty on the total marks of the corresponding assessment task per day or part of day late, i.e, 3 marks per day. Submissions that are late by 5 days or more are not accepted and will be awarded zero, unless special consideration has been granted. Granted Special Considerations with new due date set after the results have been released (typically 2 weeks after the deadline) will automatically result in an equivalent assessment in the form of a practical test, assessing the same knowledge and skills of the assignment (location and time to be arranged by the coordinator). Please ensure your submission is correct (all files are there, compiles etc), re-submissions after the due date and time will be considered as late submissions. The core teaching servers and Canvas can be slow, so please do double check ensure you have your assignments done and submitted a little before the submission deadline to avoid submitting late. We strongly advice you submit at least one hour before the deadline. Late submissions due to slow processing of Canvas or slow Internet will not be looked upon favourly, even if it is a few minutes late. Slow processing of Canvas or slow Internet will require documentation and evidence submission attempts was made at least one hour before the deadline.Assessment declaration: By submitting this assessment, you agree to the assessment declaration https://www.rmit.edu.au/students/student-essentials/assessment-and-exams/ assessment/assessment-declarationAcademic integrity is about honest presentation of your academic work. It means acknowledging the work of others while developing your own insights, knowledge and ideas. You should take extreme care that you have:RMIT University treats plagiarism as a very serious offence constituting misconduct. Plagiarism covers a variety of inappropriate behaviours, including:For further information on our policies and procedures, please refer to the following:https://www.rmit.edu.au/students/student-essentials/rights-and-responsibilities/ academic-integrity.There are multiple venues to get help. There are weekly consultation hours (see Canvas for time and location details). In addition, you are encouraged to discuss any issues you have with your Tutor. We will also be posting common questions on the Assignment 2 Q&A section on Canvas and we encourage you to check and participate in the EdForum discussion forum. However, please refrain from posting solutions, particularly as this assignment is focused on algorithmic and data structure design.file descriptionmazeTester2.py Code that reads a configuration file and runs theappropriate generator and solver. No need to modify this file.generatorSelector.py Code that determines what generator to use in current run. Used in all tasks, particularly for Task D. Please update file as needed.solverSelector.py Code that determines what solver to use in currentrun. Used in all tasks, particularly for Task C. Please update file as needed.maze/maze3D.py Implementation of 3D maze. No need to modify this file.maze/util.py 3D Coordinates class, and other utlity classes and methods. No need to modify this file.maze/graph.py Abstract class for graphs. All graph implementations should implement the Graph class (same as assignment 1). No need to modify this file.maze/adjListGraph.py Code that implements an adjacent list (for maze) No need to modify this file.generation/mazeGenerator.py Abstract class for maze generators. No need to modify this file.generation/recurBackGenerator.py Implementation of the recursive backtracking maze generator. No need to modify this file.generation/primGenerator.py Implementation of the Prims generator algorithms. Used for Task A. Please complete implementation.generation/wilsonGenerator.py Implementation of the Wilson generator algorithms. Used for Task A. Please complete implementation.generation/taskDGenerator.py Implementation of the generator for Task D. Used for Task D. Please complete implementation.solving/mazeSolver.py Abstract class for maze solvers. No need to modify this file.solving/recurBackSolver.py Implementation of the recursive backtracking maze solver. No need to modify this file.solving/wallFollowingSolver.py Implementation of the Wall following algorithm solvers. Used for Task B. Please complete implementation.solving/pledgeSolver.py Implementation of the Pledge algorithm solvers. Used for Task B. Please complete implementation..solving/taskCSolver.py Implementation of the solver for Task C. Used forTask C. Please complete implementation.README.txt Please read this first, it mentions how to run thecode. No need to modify this file.Table 1: Table of provided Python skeleton files.