Maze Goals : Understanding recursion Design and implement an algorithm for solving a maze. Produce ASCII output indicating path. The starter code can be downloaded from :...

1 answer below »

Maze

Goals: Understanding recursion

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
x x xxxx x
x xxxxx xxxxx xx x
x xxxxx xxxxxxx xx x
x x xx xx x
x xxxxxxxxxx xx x
xxxxxxxxxxxxxxxxxxxx
  • The first 2 numbers are:width-of-maze,height-of-maze
  • The next 2 numbers are:row-exitcolumn-exit
  • xrepresents wall
  • spacerepresents 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
x x*******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 (replace with your UW NetID) with the following files in it. Put all the files below into a folder called "-ass3", create a zip file of the folder and submit it. Do not submit executables or other files from IDE. Seehttps://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

You may choose to have additional public or private functions as needed.

All functions in the .h file and in the .cpp filesMUST haveat least one line of documentation. See Appendix I of the Carrano book for documentation information.

Your code should not go over 80 columns.Should not have to scroll left-right to read it.

Answered 4 days AfterMay 03, 2021

Solution

Kamal Barman answered on May 08 2021
27 Votes

Submit New Assignment

Copy and Paste Your Assignment Here