Maze Game Recursions

The Problem

You are in a field of sugar cane, represented as a grid array. You will represent a maze of paths through the field using a 2 dimensional array (details provided later). At some location in the field, there is a Dog. At another place in the field, there is at least one bone. The problem is for you to explore the paths recursively to find a path from the Dog to a Bone.

The following strategies are to be followed:

• The dog will prefer to turn right if the opportunity exists to turn right;
• If it is not possible to turn right, the dog will choose another direction;
• The dog will move one step location at a time to crawl along the paths;
• The dog will only move left, right, up or down (not diagonally);
• If the dog reaches a dead end, he will backtrack to a point where he can take an alternative path and explore that path;
• The dog will stop when he reaches a bone, the program will end, printing the successful path as a series of (x,y) coordinates. The path will print in reverse order from most recent position to starting position.
• As the dog moves through the field, he will leave a trail (of #’s ) showing where he has been;

Using the power of recursion, you will implement a method: gridSearch() to explore possible paths through the maze of paths. As you explore the field, you will print (to screen or output file) helpful messages to explain what you are doing (sample output below). When you have found a path, you will print the successful path (in reverse order).

Data Structures:

The field grid will be a 2 dimensional character array with at most 12 rows and 12 columns, char **table = new char*[12];

for(int i = 0; i < n; i++){ table[i] = new char[12]; }

You are provided with the following test grid arrays that you will use (at least) to test your algorithm. The first test case is shown here: See image.

Legend:

• The ‘-’ symbols represent cane and the Dog cannot move into that position.
• The ‘0’ represents an open path.
• The ‘D’ represents a Dog (starting point for a search).
• The ‘B’ represents a Bone (ending point for the search).
• In the second test case, remove the ‘B’ bone at position 7,3 and replace it with a ‘0’.
• In the third test case, remove the ‘B’ bone at position 3,9 with ‘0’ also, having only one bone at 4,10.
• You should also test your solution with different test cases with different configurations of paths.

The algorithm for your main() function:

• Create a grid object
• Copy the given grid array into your object to create the paths and insert dog/s and bone/s
• Look for a dog, starting from the bottom right hand corner of the grid
• Start your search from the dog position, set the initial direction the dog is facing e.g. West (this is so that you know what ‘look right’ means)
• Search for bones using a recursive function

The recursive algorithm is to try to move one position, then from the new position recursively search for a valid path from that position, if fail, backtrack out of the recursion and try a different position. More details are below. When you find a bone, stop, print the location of the found bone, print the path and exit.

The algorithm for your recursive gridSearch function:

• If you are in position with a bone, stop
• If you are in position with sugar cane, ‘-‘, backtrack as it is a failed move
• If you are in position with a ‘0’, this is a valid move, replace ‘0’ with ‘#’ to leave a trail
• If it is possible to move right, move right and continue your search (note that a right turn is relative to the current direction the dog is facing)
• If it is not possible to move right, choose another adjacent position to move in
• If the search was successful, print the path by printing the current position and as you backtrack through the recursive calls, each position in turn will be printed.

Parameters for your gridSearch function:

• You may need to send parameters for the x,y position to start the search and the current direction the dog is facing (e.g. one of “NORTH”,”SOUTH”,”EAST”,”WEST” or “UP”, “DOWN”, “RIGHT”, “LEFT”).
• Your function definition will look like:

int Grid::gridSearch (int startx, int starty, char *direction)

Other functions:

When designing your solution, please consider good design principles. You will need to write some functions and methods to help organize your code and enable code reuse. You are expected to (at least) include the following functions:

• int getxSize(); // method to get the dimension of the grid array in x direction
• int getySize(); //method to get the dimension of the grid array in y direction
• void createGrid(char** newgrid, int sizex, int sizey); //method to create the grid
• int findDog(); // method to find the dog
• char * lookRight(char* directn, int* x, int* y, char * newdirectn); //from current position, find the new x,y position looking right
• char** getGrid(); //return the address of the start of the grid array
• void printGrid(); //print the grid array to output file

Your Output:

Here is Sample output for a very small 4 rows x 4 columns test grid: See image.

You should complete your project in stages as follows. After completing each stage, you are encouraged to discuss your answer with your tutor for feedback, before continuing to the next stage.

Stage One:

Given the algorithm above, draw on paper a simple maze grid and work through how the algorithm works using recursion. What is stored at each step? Why do you need to ‘leave a trail of #s’? Elaborate detailed algorithms for your solution, for each method you think you need. Think about the objects you will need. For each objects, what methods are needed for input/output? What methods will you need to search through the field? How do you calculate what ‘look right’ will mean? Write up your design in a text/word document.

Stage Two:

Data structures – think about the details, elaborate on your design. How will you represent your grid? Devise your Program, include comments to ‘tell the story’ of how your code works. Write a main function that creates a grid object, sets values into the grid (‘-’, ‘0’, ‘B’ ,’D’), prints the grid as per the sample output provided to an output file. Write methods for your grid object to create grid, print the grid, get the grid size. Write your recursive method to search the field grid.

Stage Three:

Devise appropriate test cases to verify your solution is correct. Test for a larger grid up to 12x12 cells Review your original algorithm, update it if necessary.