Reference no: EM132924355

Overview - Maze generator and solver

In this assignment, you are going to implement a simple maze generator and solver. Your program has two usages:

Generate maze usage: ./hw2 <maze file> <width> <height> [threshold = 0.5] [seed = 0] Solve maze usage: ./hw2 <maze file>

The first one will generate a maze with size <width> x <height> saved as a text file in <maze file> . [threshold] and [seed] are optional parameters for maze generation, which will be described in the program specification section. The second usage will solve the maze provided by <maze file> . Here are some sample runs to illustrate the idea.

Program Specification

Starter codes and Makefile
The main goal of this assignment is for you to practice breaking a program down into functions and modularizing your code. In the starter code, you will find the following files:

1. hw2.c is the main driver function; it checks and parses the command line arguments, and calls functions to complete the main logic.
2. print_functions.[c|h] is a module for all print-related functions.
3. maze.[c|h] is the maze module which provides all maze-related functionalities.

We also provide you with some maze files for testing your program. To start the project, you must provide the Makefile that compiles each source file into an object file and then links them together into a target called hw2 . [Note, your output program must be called hw2 . Otherwise, it may fail all the testing.]

Read the comments in the codes carefully to get a sense of what each function is supposed to do. Details are provided in the *.h files, but not the *.c files. Your task is to implement all the functions. You are free to create your own helper functions if necessary.

Maze generator

Generate maze usage: ./hw2 <maze file> <width> <height> [threshold = 0.5] [seed = 0]

To generate a maze, your program accepts at least 3 arguments: the output maze filename <maze file> , the maze width <width> , and the maze height <height> . It can accept two more optional arguments [threshold] and [seed] . When they are not provided, [threshold] and [seed] should have default values of 0.5 and 0 respectively. Your program should check that
<width> and <height> are positive integers. If they are invalid input, your program should terminate and return an error code -3 . You don't need to perform any input validation for [threshold] and [seed] . Finish the command line argument parsing logic in hw2.c for that.

Maze generation - genMaze

Your program should generate a maze of size <width> x <height> as follows [Note: you must follow this order to generate the expected results]:

1. Initialize a random seed with the argument [seed] . You can do this by calling
srand(seed) .
2. Use rand() to generate a start position (first generate at which column, then generate at which row) inside the interior of the maze. (i.e. the start position should not be at the
boundary walls.)
3. Do the same to generate a target ending position (first generate at which column, then generate at which row) inside the interior of the maze. (You don't need to check if start and target are the same.)
4. For each row of the maze

For each column of the maze
If it is on the boundary, set it to # Else if it is the start position, set it to @ Else if it is the end position, set it to <
Else generate a random number between 0 and 1, and check if it is greater than or equal to [threshold] . If so, set it to # ; otherwise, set it to (a space)

Your program is looking for a solution path connecting the start position @ to the target position
< without hitting or going through any wall # . In this homework, a path can only move in four directions: left, right, up, and down (not diagonally). Our functions are organized with a second maze representation ( char* sol ) to keep track of the solution path. This array mirrors the original maze array in many ways. The solution path can be found and established in the sol array using the below recursive search algorithm:

1. For each position in the solution maze ( sol ), mark them all as unvisited.

2. Given a position and a current path ( sol ), do the following:
If the position is the end target (in maze ), the current path is a solution path. Return true.
Else if it is a wall (in maze ), or it is already visited (in sol ), the current path is not a solution path. Return false.
Mark the current position as visited in sol .

Try to extend the path in each direction (in the order of left, right, up, down) and for each one, recursively perform Step 2 to check if a solution path can be found by moving to the neighbor in that direction. If a solution path is found from one of the neighbors, mark the position as a part of the solution path (in sol ), and immediately return true.
Otherwise, no solution path can be found. Return false.

Attachment:- Coding Homework.rar