Design and implement an algorithm for solving a maze. Produce ASCII output indicating path. The starter code
Question:
Design and implement an algorithm for solving a maze. Produce ASCII output indicating path.
The starter code can be downloaded from :
https://github.com/ajahanba/ass3-maze-starter
(Links to an external site.)
The problem description is taken from Carrano Chapter 5 Problem 9 (Carrano Chapter 5, Problem 4 in 6th edition) which is linked to this assignment.
The maze is provided by a text file in the following format:
20 7
0 18
xxxxxxxxxxxxxxxxxx x
xxxxxx x
x xxxxxxxxxxxx x
x xxxxx xxxxxxx xx x
x xxx xx x
x xxxxxxxxxx xxx
xxxxxxxxxxxxxxxxxxxx
The first 2 numbers are: width-of-maze, height-of-maze
The next 2 numbers are: row-exit column-exit
x represents wall
space represents movable space
Unlike the textbook version, the entrance to the Maze is not specified as part of the maze.txt file but will be provided by Creature's location
When maze is printed, you should also add
* part of the path to exit
+ visited square not part of the path to exit
When the solved maze is printed, you should get (without color)
Path: EEENNNEEEEEESEESSSEEENNNNN
xxxxxxxxxxxxxxxxxx*x
xx*******xxxx*x
x xxxxx*xxxxx***xx*x
x xxxxx*xxxxxxx*xx*x
x x+****+++++xx*xx*x
x xxxxxxxxxx+xx****x
xxxxxxxxxxxxxxxxxxxx
Above maze has "red *" to indicate path, "green star" to indicate starting location and "+" to indicate explored areas that are not part of the final path to exit.
The ASCII representation of the maze is important for debugging, but does not have to be exactly as above. The Path string has to exactly match the solution.
You can assume that mazes will have less than 100 rows and 100 columns.
You need to submit ass3.zip with the following files in it. Put all the files below into a folder called "ass3", make a zip file of the folder and submit it. Do not submit executables or other files from IDE. See https://github.com/pisanorg/w/wiki
(Links to an external site.)
> "Creating a zip file" if you need to.
maze.h, maze.cpp - modify as/if needed
creature.h, creature.cpp - implement functions and modify as needed
main.cpp - add your own tests
maze.txt - original sample maze file (do not modify)
maze1.txt, maze2.txt maze3.txt - 3 different mazes that your main.cpp uses to test your program
output.txt - Shows the output from compiling and running your program on CSS Linux Labs. Can be generated using simplecompile.sh
README.md - No need to make changes to the readme file
simplecompile.sh - easy way to compile, test and run your program (you do not need to modify it)
.clang-tidy - this style file is provided, you do not need to modify it but you can if you want to enable or disable additional checks.
CMakeListsts.txt - used by CLion projects
Important: All the file names are in lowercase which may not be the default for your IDE.
Configure your IDE to create lowercase files for classes.
Implement the following class functions in Creature class:
1.Creature(int Row, int Col);
2.// returns a string in the form of NNEEN
// (where N means North, E means East, etc)
string solve(Maze &Maze);
3.bool atExit(const Maze &Maze) const;
4.Go in a specific direction -- these 4 functions will be similar
string goNorth(Maze &Maze);
string goSouth(Maze &Maze);
string goEast(Maze &Maze);
string goWest(Maze &Maze);
5.// prints current location of creature, for example C(7,3)
ostream &operator<<(ostream &out, const Creature &creature);
You may choose to have additional public or private functions as needed.
All functions in the .h file and in the .cpp files MUST have at least one line of documentation.
Your code should not go over 80 columns. Should not have to scroll left-right to read it.
Additional Requirements
1.Add and change the tests as needed to fully test your code - use assert statements for testing, not just visual check of the output
2.Your program should not require any keyboard input when running.
3.Generate a new output.txt file using (you can modify simplecompile.sh if needed)
$./simplecompile.sh > output.txt 2>&1
4.Program compiles without warnings or errors with the following flags
-Wall -Wextra -Wno-sign-compare
5.You should not get any warnings from clang-tidy. You can modify .clang-options as needed, but have to explain each check you disabled in your README.md file. You cannot disable groups of tests (such as -google-* to disable all google style checks
Discrete Mathematics and Its Applications
ISBN: 978-0073383095
7th edition
Authors: Kenneth H. Rosen