Introduction
In this first project you will develop a maze solver based around a recursive search function.
There are several files provided for you for this project, and they contain varying amounts of pre-written code. You will be required to code the missing parts, and create several functions from scratch.
One of the objectives of this project is to test your ability to program within constraints imposed by other developers, specifically you will be provided with structure definitions and function prototypes and you must ensure that your solution works with and within the constrains they impose.
Be sure to study both this question, and the provided files and links carefully. Various pieces of information you will need to successfully complete this project can be found in the provided files and links as well as in this question.
Provided files
For this project, several files are provided. You may download a zip file containing them from here: Project1.zip. You may view the Doxygen output for the supplied files here
Requirements
The requirements for this project are:
You must write the code required to implement the following functions in the map.c file: create_map(), free_map(), file_widthheight() and load_map(). You may not change the return types or argument lists for these functions. See below for a description of these functions.
You must write the following functions in maze.c: find_start() and solve_maze(). See below for a description of these functions.
You should create a <yourname>_project1.c file which should contain your main() function. The main() function should: load a map, the name of which should be entered as a command line argument to your program. That is, you should be able to invoke your program with 'project1.exe testmap2.txt' and the testmap2.txt maze should be loaded. Do not request the filename from the user within your program as you did in the exercises!
locate the start square - marked with an 'S' - in the map.
if you find the 'S', solve the maze starting there, otherwise print an error and exit.
if the end is found, print a success message.
if the end is not found, print an error.
free the map.
Test your program using the provided mazes, and try writing some of your own.
Submit the following files: <yourname>_project1.c, map.c, map.h, maze.c, maze.h via the submission box below (I would actually prefer if you zipped them
into one file called <yourname>_project1.zip and submitted that, but individual files are fine).
Functions in map.c map.c contains a mix of provided functions, and empty function declarations that you must fill in. The file is documented here, the functions you must fill in are:
Map *create_map(int width, int height)
This should allocate a new Map structure, and enough memory to store a map of width*height squares in size. Each square is a char, and the memory for the map should be pointed to by the squares pointer in the Map structure. Ensure that you fill in the width and height fields in the structure.
void free_map(Map *release)
This should free the memory allocated by a call to create_map() - it should release the memory pointed to by the squares field, and then the Map itself.
void file_widthheight(FILE *infile, int *width, int *height)
This should work out how many lines there are in the file provided, and use that as the height of the map, and it should find the longest line in the file, and use the number of characters in that line as the width of the map. Note that you should be careful not to count newlines here, and you can not assume that the map will be square, and thus use the first line as the width - you will need to check all the lines in the file and record the length of the longest one. To make life easier, you may assume that lines will never exceed 128 characters. Once you have determined the width and height, return to the start of the file, and update the memory pointed to by the function arguments to return the maximum width and height of the map.
Map *load_map(char *filename)
This should open the specified file, determine the width and height of the map it contains, allocate a Map structure large enough to hold it, and read the contents of the file into the Map structure. Note that you should not directly access the memory pointed to by the squares field inside the Map structure, you should use set_square() to set the contents of each square as you read it from the file. Once the file has been loaded, return the new Map.
IMPORTANT: you will lose marks if you attempt to directly access the values in the memory pointed to by the squares pointer in a Map structure. All access to the squares data must be done via the set_square() and get_square() functions.
Functions in maze.c
This file should contain the actual solver, and you must write it from scratch - however, you must implement the functions specified here. You may not change the return types or argument lists in any way. You may create additional 'static' functions to perform tasks as part of implementing these functions, but you will lose marks if you deviate from the following specifications: int find_start(Map *mapdata, int *start_x, int *start_y);
This function should search the specified Map for a square containing 'S' (the search should be case sensitive - a square containing 's' is not the square you are looking for). If a square containing 'S' is located, the memory pointed to by start_x and start_y should be updated to contain the x and y coordinates of the square in the map. For example, if the map in memory is:
Then value pointed to by start_x should be set to 5 and the value pointed to by start_y should be set to 8.
int solve_maze(Map *mapdata, int x, int y)
This is the recursive map solver itself. This function should implement the following algorithm:
If x and y are out of bounds (less than 0, greater than or equal to width or height) return false.
If the square at (x,y) contains 'E' then return true (the end has been located).
If the square at (x,y) is filled (it does not contain ' ' or 'S') then return false.
otherwise
mark the square at (x,y) and print out the map to show progress
if the result of calling solve_maze() on the square above this (y-1) is true, return true
if the result of calling solve_maze() on the square right of this (x+1) is true, return true
if the result of calling solve_maze() on the square below this (y+1) is true, return true
if the result of calling solve_maze() on the square left of this (x-1) is true, return true
otherwise unmark the square at (x,y)
return false
This is a basic recursive algorithm to solve a maze. You may wish, and are strongly advised, to add diagnostic printfs() during development so that you can
understand how it accomplishes its task, however the version of this function you submit should not print anything other than the map.
