Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COSC 1285/2123
Assignment 1: Implementing and Evaluating
Data Structures for Maze Generation
1 Overview
In this assignment, you will implement a number of well-established data structures for developing a maze generation program and evaluate their performance to determine what would be the best data structure in different situations. This assignment aims to help crystallise the analytical parts of the course and familiarise you with certain data structures, how implementation decisions can have an influence on running times, and how to empirically evaluate different possible design choices (in this case, data structures).
3 Background
A maze is typically a 2D grid of cells and walls, an entrance and an exit. The aim is to find a path from the entrance to the exit. See Figure 1 for an example. 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; in this assignment, we will focus on generation of mazes, however, the implementation for maze generation is already provided in the Python skeleton (detailed in Section 4) and you will need to only focus on data structures that represent mazes in our maze generation scenario. 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). In addition, in this assignment, we focus on 2D, square cell mazes, i.e., each cell has 4 sides. There is no standard way to reference the cells, hence we adopted the convention issued in Figure 1, with (0,0) denoting the bottom left cell, and columns increase as we travel to the right of the maze (page), and rows increases as we travel up the maze (page). In order to specify the entrances and exits, we have added one row above, and one row below the maze, and one column to the left, and one column to the right of the maze. 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) refers to the bottom left cell of the maze, but still able to reference the location of entrances and exits.
4 Assessment details
The assignment is broken up into a number of tasks, to help you progressively complete the project.
Figure 1: Sample 5 by 5 maze. The entrances are il-lustrated as arrows pointing towards the maze, and ex-its are illustrated as arrows pointing away from the maze. The cells of the maze are in-dexed from 0, and the row and column indices are drawn outside the maze. Note that the bottom left cell is (0,0), and top right cell is (4,4). This follows the convention that matplotlib follows (we use that for visualisation). Note the entrances are spec-ified as (0,-1) and (-1,1) and exits as (5,4) and (3,5).
Task A: Implement Mazes using Different Data Structures (6 marks)
In order to generate mazes, we need a way to represent them. In the assignment and this task, you will implement a Maze abstract data type using graphs. Your task is to complete the implementation of a number of sections in the provided Python skeleton code. The implementation of the maze using 2D arrays is provided as an example in the skeleton.