Assignment Task

Overview

In this assignment, you will implement a number of basic 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 analysis 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).

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 the generation of mazes.

Figure 1: Sample 5 by 5 maze. 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 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 specified as (0,-1) and (-1,1) and exits as (5,4) and (3,5).

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.

Task A: Implement Mazes using Different Data Structures

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 a number of data structures, namely graphs. Existing implementations using 2D arrays is provided as an example. Your implementation should complete the implementation of a number of operations in the provided Python skeleton code.

Data Structure

Details Mazes can be implemented using a number of data structures. We provide an implementation and you are to implement two others. We provide the implementations using the following data structures:

• 2D Array. Each element in the 2D array represents a cell or a wall in a 2D (square, 4 sided, cell) maze. You are asked to implement the maze abstract data type using the following data structures:
• Graph (adjacency list). Adjacency list representation of a graph representing a 2D (square cell) maze.
• Graph (adjacency matrix). Adjacency matrix representation of a graph representing a 2D (square cell) maze.

Code Framework

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. You need to 4 complete the implementation of adjListGraph.py and adjMatGraph.py. We have provided the code to construct and provide functionaliy of a maze in the graphMaze file. It is mostly generic, but does assume a certain way of implementing the maze using the two graph data strucutres. If that doesn’t align with your approach, please feel free to modify it, but please ensure the same functionality is still maintained and that you are able to generate mazes. Note the first time you run this, please see the two provided configuration files, which will use the provided array data structure as the maze representation. If you modify and use one of the graph ones, there likely be errors returned when running, as the implementation for the graphs are empty. Please do not be alarmed by this - once the implementation is complete, we hopefully be able to output the correct graphs.

Note that for Task A, part of the assessment will be based on automated testing, which will feed a number of configuration files into your (completed) implementation of the provided Python skeleton. We will then check if the generated mazes are correct, e.g., whether they are perfect, have correct entrances and exits, didn’t go into infinite loops etc. We would like you to do some testing about this - if you look at the code, there is a method to test if the generated maze is perfect, but no implementation. This implementation will not be part of your assessment, but it might be useful to consider how to implement this and do checking yourself, as part of practising evaluating your own code. Remember a perfect maze is one where any cell in the maze can reach any other cell, or another way to put it, there exists a path between any pair of cells in the maze

B: Evaluate your Data Structures

In this second task, you will evaluate your implemented structures both theoretically and empirically in terms of their time complexities for the different use case scenarios and different operations, e.g., removeWall(). Scenarios arise from different parameter settings for generating a maze.

Write a report on your analysis and evaluation of the different implementations. Consider and recommend in which scenarios each type of implementation would be most appropriate.

Use Case Scenarios

Typically, you may use real usage data to evaluate your data structures. However, for this assignment, you will write configuration file generators to enable testing over different scenarios of interest. There are many possibilities, hence to help you we suggest you consider the following factors.

• The dimensions of the maze.
• Data structure implementations.

Theoretical Analysis

At first, you are to conduct a theoretical analysis of the performance. Given the height h and width w (in terms of number of rows and columns) of the generated maze, report the best case and worse case running time estimate in terms of the exact asymptotic complexity (Θ) of each of your graph implementations when executing updateWall() and neighbours(). You will also need to provide an example scenario and explanation on the each of the best case and worse case running time estimate. This will help you when explaining your empirical analysis results.

Empirical Analysis

Typically, you use real usage data to evaluate your data structures. However, for this assignment, you will write data generators to enable testing over different scenarios of interest.

Data Generation

When generating different maze dimensions, you may want to write some configuration file generators (or generator directly within a copy of mazeTester.py). Due to the randomness of the data, you may wish to generate several datasets with the same parameters settings and take the average across a number of runs.

C. Video Interview

After the report and code is 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. You’ll have a set time to consider the questions, make a recording then upload that recording.

Report Structure

As a guide, the report could contain the following sections:

Theoretical analysis on running time and complexities of the different data structure implementation as outlined in Section 4.

• Explain your data and experimental setup. Things to include are (brief) explanations of the parameter configurations in your experiments, e.g., the range of maze dimensions sizes (add some brief explanation of why this range selection), describe how the evaluation parameters and data are generated (a paragraph and perhaps a figure or high level pseudo code suffice) and which approach(es) you decide to use for measuring the timing results.
• Evaluation of the data structures using the generated data. Analyse, compare and discuss your results. Provide your explanation on why you think the results are as you observed. You may consider using the known theoretical time complexities of the operations of each data structure to help in your explanation.
• Summarise your analysis as recommendations, e.g., for this range of maze dimensions, I recommend to use this data structure because We suggest you refer to your previous analysis to help.