Reference no: EM131196371

Overview

This assignment will require you to extend the functionality of assignment 1 by exploring different aspects of inheritance/polymorphism as well as some design patterns to produce modular code, with a focus on performance. The main requirements are:

- Generate mazes using different algorithms.
- Solve various mazes using pathfinding algorithms.
- Use polymorphism and design patterns to allow different maze generation/solving algorithms to be added easily.
- A simple class diagram representing what you think your final code will look like - do this at the start as you will be required to discuss how your original and final plan differed.
- A report discussing performance differences of the generating/solving algorithms implemented.

Details

The assignment should be done in C++, and must compile on the jupiter/saturn/titan servers using C++14. A large part of the assignment can be completed in the labs, and the exercises are directly related to the assignments.
You may work in pairs or individually.

You may enable g++ to use c++14 by entering the following command:

source /opt/rh/devtoolset-3/enable

It is probably a good idea to add this to your .bashrc file.

Class Diagram

Before getting started, draw a basic class diagram representing what you think your assignment will look like when finished. This does not have to be complete or exact but keep in mind good design principles when creating it. *Do not* do this after finishing the assignment as you will be asked to compare your original design with your finished application.

Generate maze with the sidewinder algorithm
From Buck, Jamison, "Mazes for Programmers": Consider the grid one row at a time. For each row, link random runs of adjacent cells, and then carve north from a random cell in each run. Treat the northern row specially, linking all cells into a single corridor.

Generate maze using Wilson's Algorithm
From Buck, Jamison, "Mazes for Programmers": The algorithm starts by choosing a point on the grid-any point-and marking it visited. Then it chooses any unvisited cell in the grid and does a loop-erased random walk (see https://en.wikipedia.org/wiki/Loop-erased_random_walk ) until it encounters a visited cell. At that point it adds the path it followed to the maze, marking as visited each of the cells along that path, and then it goes again. The process repeats until all the cells in the grid have been visited.

Pathfinding
The program should be able to generate a path from cell (0,0) to cell (width-1,height-1) using three different algorithms:

- Dijkstra's Algorithm
- Breadth First Search
- A-star using both manhattan and euclidean distance

For full marks polymorphism should be used to reduce code duplication between the algorithms, and a Binary Heap should be implemented to speed up execution of the A* algorithm.

Your solvers should also be able to detect if the maze they are trying to solve is solvable (there is a path from the top left corner to the bottom right corner of the maze). If a maze is not solvable, you should inform the user of this.

Path Saving (SVG)
The program should be able to save the generated path in the SVG file. In addition to saving all the edges of the maze as in assignment 1, all edges belonging to the path should be saved in the colour red instead of the colour white.

Design Patterns
To promote modularity by allowing algorithms to be added/modified without affecting the rest of the program, a combination of the Prototype/Strategy/Factory Design Patterns could be used for maze generators and solvers. Use patterns only where it makes sense to use them - don't go overboard here.

Timing
Your program should be able to output to the terminal the time (in milliseconds) taken to generate the maze and to solve it.

Set Implementation
For some of the functionality used in this this program you will need to use a set. The std::set will not be efficient enough for your program because of its implementation as a binary search tree (a linked structure which doesn't implement efficient memory access because the elements are not contiguous). Instead, you will need to implement a set based on a binary heap. Create a class that inherits from vector or contains an array and does appropriate sorting to ensure the heap is a valid min heap. This class will need to be templated so it can contain different kinds of objects. For help with the implementation of the heap you can have a look at the following web page: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Binary%20Heaps/heaps.html

Report
Note: For all timings you should run your program on the jupiter/saturn/titan servers. To calculate the timings you should use the std::chrono library.

Generate some mazes and save them both as binary and svg files - outline some reasonable tests for the algorithms used. You might consider generation of various sized mazes.

Do this 10 times for each size, and record the mean (average) time for generation and for saving in binary/svg formats, as well as the standard deviation for your timings (You may find it easier to import your timing data into a spreadsheet program to help you with this).

Now record the time taken to solve each maze, using each maze solving algorithm. Again do this 10 times each and record the mean and standard deviations. Also consider here the impact of size on the overall runtime for the solvers.

Are there particular parts of the maze algorithms that take more time (use valgrind's callgrind facility or another profiler to help you figure this out).

Finally write a report in pdf format, highlighting the following:

- Does your final application resemble your original class diagram and why/why not? What changes did you end up making for your design that you did not foresee?
- Discuss the difference in performance of each generation/solving algorithm and potential reasons for these differences.
- Are the results for each solving algorithm what you expected and why/why not?
- Are there any improvements you could make to increase performance?

Compilation
An appropriate makefile should be used and at a minimum you should used the following flags:

-Wall -Wextra -pedantic -std=c++14

Your makefile should build each .cpp file separately and then link them together into a single executable.

Controls
In addition to the controls from assignment 1, the program should now also accept the following arguments:

./exe --gb ... # generate a maze using the binary tree method
./exe --gw ... # generate a maze using Wilsons's algorithm
./exe --gs ... # generate a maze using the sidewinder algorithm.
./exe --pd ... # solve the maze using Dijkstra's algorithm
./exe --pb ... # solve the maze using Breadth First Search
./exe --pm ... # solve the maze using a* search with the manhattan distance heuristic
./exe --pe ... # solve the maze using a* search with the euclidean distance heuristic

Note that command line args can be given in any order, and an appropriate error message should be given if inappropriate args are entered.

Note that the flag --g should no longer be accepted, since it has been replaced with --gb and --gw and --gs. These should accept variable arguments as they did in assignment 1. All other flags from assignment 1 should still work in the same way.

Attachment:- MazeSolution.zip