Description
Homework 2: An A-MAZE-ING Assignment! Wait, my bad, I meant to say an “amazing” assignment.
For those of you working on this early, this gives you only some direction, I encourage you to do additional research feel free to google and/or ask questions
Intro: Y’know that thing when you come back from data structures class, and you’re just lounging around the apartment/dorm, and you realize that you’ve completed all those Sudokus in that puzzle book. So you bust out that book of Mazes. And then you’re trying to solve one of them, and 30 minutes into it you suddenly say to yourself
“Wait, why am I doing this?! I HATE mazes!” Well now your prayers are answered. In this assignment we will use recursion and dynamic allocation of memory to create a program that can solve any maze of any dimension as long as it’s in the following form.
Figure 1 is the ascii maze that’s included with your assignment.zip. At the top of Figure 1 is two numbers that tell you the dimensions of the maze (yDim=8, xDim=24).
The “x” ascii characters represent the walls of the maze. The “-“ ascii characters represent places you can walk. the “*” character represents the starting point. The “$” character represents the goal you want to reach in our capitalistic
society. Finally the “E” character is the end of the maze (not really necessary since we have the dimensions). The goal of this assignment is to create a path of “*” leading
from the starting point to the goal. One (not the only) solution looks as follows (spoiler alert):
Your homework file includes the maze.txt file.
Your tasks
• Creates an ifStream myIns and opens “maze.txt”. You have to #include that allows you to read in text files
http://www.cplusplus.com/doc/tutorial/files/
• You can hardcode the maze dimensions if you’d like
• Puts all the maze chars into this new 2D array (i.e. some sort of nested loop maybe?)
After you read in the maze you want to have a function that solves the very next step of the maze. It will return a boolean. Recursion is the act of calling a function within a functions own body, we will use recursion to solve the maze Here are some recursion
explanations if you are working on this ahead of the class:
http://www.cplusplus.com/articles/D2N36Up4/
http://pages.cs.wisc.edu/~calvin/cs110/
RECURSION.html
You will have a function called bool mazeSolver that will return true or false if the following step is on the right path to the solution this is done as follows.
o First temporarily change the character at the current index of the maze array to “v” to denote that we have visited this spot (so it doesn’t get visited again) in our
mazeArray.
Check up, down, left, and right for the goal: “$”. (note up will be your index-xDim, down will be your index +xDim, left will be your index-1, and right will be your index+1). Remember when checking up and down to make sure you haven’t gone off the end of your array! If you are at the goal change the character at this index of
the maze array to “*” and return true.
o If you’re not at the goal, check the up location for a ”-” character (which means we can move there). If that exists, call the solve function passing in the up index, and if that returns true, change the character at this index of the maze array to “*” and return true (it means that the up gives us a valid path to the goal!)
o else if do the same with down (i.e. we only do this if up is not a valid path to the goal)
o else if left, else if right.
o If none of these return true we change our current character back to “-“ and return false.
