Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Algorithms and Analysis
COSC 1285/2123
Assignment 2: Exploring Maze Generation and Solving Algorithms
Assessment Type Individual assignment. Submit online via Canvas → Assign-
ments → Assignment 2. Marks awarded for meeting require-
ments as closely as possible. Clarifications/updates may be
made via announcements/assignment FAQ/relevant discus-
sion forums.
Marks 30
Please read all the following information before attempting your assign-
ment. This is an individual assignment. You may not collude with any other people and
plagiarise their work. Everyone is expected to present the results of their own thinking
and writing. Never copy other student’s work (even if they “explain it to you first”) and
never give your written work to others. Keep any conversation high-level and never show
your solution to others. Never copy from the Web or any other resource or use Genera-
tive AI like ChatGPT to generate solutions or the report. Remember you are meant to
develop the solution by yourself - assessment is designed to encourage everyone to learn,
and you are not doing yourself any favours by taking short cuts. Suspected collusion or
plagiarism will be dealt with according to RMIT policy.
In the submission (your PDF file for the report of Task B) you will be required to
certify that the submitted solution represents your own work only by agreeing to the
following statement:
I certify that this is all my own original work. If I took any parts from
elsewhere, then they were non-essential parts of the assignment, and they
are clearly attributed in my submission. I will show I agree to this honor
code by typing “Yes”:
1 Overview
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.
2 Learning Outcomes
This assessment relates to two learning outcomes of the course which are:
• CLO 1: Compare, contrast, and apply the key algorithmic design paradigms: brute
force, divide and conquer, decrease and conquer, transform and conquer, greedy,
dynamic programming and iterative improvement;
• CLO 5: Implement, empirically compare, and apply fundamental algorithms and
data structures to real-world problems.
3 Background
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
2
(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.
4 Assessment details
The assignment is broken up into a number of tasks, to help you progressively complete
the project.
Task A: Different Generation Approaches (6 marks)
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 can’t 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:
• Recursive backtracking (generation) algorithm - this is the same as in Assignment
1.
We ask you to study, understand and implement two more advanced and different
algorithms.
• Prim’s algorithm.
• Wilson’s Algorithm.
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.