Maze Runner

Overview

In this project we will revisit the logic of maze solving from earlier in the course, this time providing an actual C implementation to solve the problem. In the course of this project, you will get more practice with all of the fundamental programmatic structures of C as well as experience using external library code. Finally, you will need to create your first real `.h' file so that your code can be interfaced with externally.

Submission Instructions

Submit only the .c and .h files that you created along with your Makefile, but do not zip them! Additionally, be sure your makefile produces an executable called maze runner so that my test script can run it.

Technical Description and Instructions

In this project, you will not write a full program. I have already written most of a program to solve randomly generated mazes. The parts that I have written generate the maze and provide functions through which the maze can be interacted with. Additionally, the parts that I have written rely on calling some functions that will solve the maze. Implementing those functions is your job!

Your Two Files

You must create two files for this project: runner.c and runner.h. Runner .h should expose two functions to the rest of the program called runner_solve () and runner_init(). The first function will utilize the maze library functions I've provided to solve a maze¹ . The second function simply performs any setup necessary for the runner_solve() function to run. These two functions should be implemented in the runner.c file.

You may create as many helper functions as necessary to support your runner_solve() function² . Likewise, you may use any reasonable algorithm to actually solve the maze. Your runner must leave behind a trail of `breadcrumbs' as it moves through the maze (see ?? for details).

Program Output

Program output is actually handled for you on this one! The maze_runner.c file I've provided for you will call print_maze() for you to show both the unsolved maze and the maze after your runner has finished. However, you must accurately show the path that was taken by your algorithm to solve the maze. This is done by using the maze_set_char() function as your `runner' moves through the maze. When the runner crosses an empty square, it should leave a '.' behind. When it crosses a '.', it should leave an 'o' behind.

¹Descriptions of these maze library functions are in the comments of the mazelib.h file provided. ²My implementation has around five. 1

When an 'o' is crossed, an 'O'³ should result. Finally, when an 'O' is crossed, a '@' should be left in its place.

Things to Remember and Helpful Hints:

Make sure you read all of the comments in the mazelib.h header file! These comments will tell you all you need to know about interacting with the maze.

Grading Specification

For your submission to receive a grade of `pass', it must fulfill the following criteria:

It must be submitted correctly.

I must be able to compile your program simply by invoking make in a directory containing your code and Makefile.

The program must compile with no warnings or errors.

The program should run with no errors and output a legally solved version of the generated maze.

HERE IS THE INITIAL CODE

Maze_runner.c 

#include  

#include  

#include "mazelib.h" 

#include "runner.h" 

void usage(void); 

int main(int argc, char* argv[]) { 

 if (argc < 3) { 

 usage(); 

 return 1; 

 } else { 

 int width = (int) strtol(argv[1], NULL, 10); 

 int height = (int) strtol(argv[2], NULL, 10); 

 if(!maze_init(width, height)) { 

 usage(); 

 return 1; 

 } 

 } 

 maze_print(); 

 printf(" "); 

 runner_init(); 

 runner_solve(); 

 maze_print(); 

 return 0; 

} 

// This function displays the usage message if the parameters are missing or incorrect. 

void usage(void) { 

 printf("Usage: mazerunner width height "); 

 printf("\t width must be an odd integer between 9 and 79 inclusive "); 

 printf("\t height must be an odd integer between 9 and 25 inclusive "); 

} 

Mazelib.c file

#include  

#include  

#include  

#include  

#include "mazelib.h" 

static void set_offsets_for_dir(int*, int*, direction); 

static void shuffle_dirs(direction*); 

static int xy_to_index(int, int); 

static void reset(void); 

static bool are_valid_maze_dimensions(int, int); 

static void set_offsets_for_dir(int*, int*, direction); 

static void maze_visit(int, int); 

static int width; 

static int height; 

static char *maze; 

static bool initializing = false; 

// maze_init allocates the memory for the maze array based on width and height 

bool maze_init(int w, int h) { 

 if(!are_valid_maze_dimensions(w, h)) { 

 return false; 

 } 

 width = w; 

 height = h; 

 srand(time(NULL)); 

 maze = malloc(sizeof(*maze) * width * height); 

 reset(); 

 initializing = true; 

 maze_visit(1, 1); 

 maze_set_char(1, 1, 'S'); 

 maze_set_char(width-2, height-2, 'E'); 

 initializing = false; 

 return true; 

} 

int maze_get_width(void) { 

 return width; 

} 

int maze_get_height(void) { 

 return height; 

} 

// returns "true" if x and y are both in-bounds defined by: 

// 0 <= x < width and 0 <= y <= height 

bool maze_is_coord_in_bounds( int x, int y ) { 

 return 0 <= x && x < width && 0 <= y && y < height; 

} 

/* 

 maze_get_char returns the character in maze at the passed index 

*/ 

char maze_get_char(int x, int y) { 

 return maze[xy_to_index(x, y)]; 

} 

/* 

 maze_set_char sets the character in maze at the passed index to the 

 passed character. 

*/ 

bool maze_set_char(int x, int y, char replacement) { 

 char c = maze_get_char(x, y); 

 if((c == '#' || c == 'S' || c == 'E') && !initializing) { 

 return false; 

 } 

 maze[xy_to_index(x, y)] = replacement; 

 return true; 

} 

/* 

 maze_print displays the maze to the screen. 

*/ 

void maze_print(void) { 

 for(int y = 0; y < height; y++) { 

 for(int x = 0; x < width; x++) { 

 printf("%c", maze_get_char(x,y)); 

 } 

 printf(" "); 

 } 

 printf(" "); 

} 

/* 

 maze_visit starts at a given index and recursively maze_visits every direction in a 

 randomized order. Recursion ends at a particular location when all the 

 directions have been maze_visited. 

*/ 

static void maze_visit(int x, int y) { 

 maze_set_char(x, y, ' '); 

 direction dirs[4] = {NORTH, EAST, SOUTH, WEST}; 

 shuffle_dirs(dirs); 

 for (int i=0; i < 4; i++) { 

 // dx and dy will be offsets from the current location based on the direction at i 

 int dx = 0; 

 int dy = 0; 

 set_offsets_for_dir(&dx, &dy, dirs[i]); 

 // get the (x, y) coordinates for the maze cell 2 spots away in the given direction 

 int x2 = x + 2*dx; 

 int y2 = y + 2*dy; 

 // If the location at (x2, y2) is in bounds and it hasn't been visited yet, visit it 

 if(maze_is_coord_in_bounds(x2, y2) && maze_get_char(x2, y2) == '#') { 

 maze_set_char(x2-dx, y2-dy, ' '); 

 maze_visit(x2, y2); 

 } 

 } 

} 

static bool are_valid_maze_dimensions(int w, int h) { 

 return w % 2 == 1 && 

 h % 2 == 1 && 

 w > 8 && 

 h > 8 && 

 w < 80 && 

 h < 26; 

} 

// reset fills the maze with blocks ('#' characters). 

static void reset(void) { 

 for(int i = 0; i < width*height; i++) 

 { 

 maze[i] = '#'; 

 } 

} 

static int xy_to_index(int x, int y) { 

 return y*width + x; 

} 

static void shuffle_dirs(direction *dirs) { 

 for(int i = 0; i < 4; i++) { 

 int r = rand() & 3; // Random number between 0 and 3 

 // swap directions at r and i 

 int temp = dirs[r]; 

 dirs[r] = dirs[i]; 

 dirs[i] = temp; 

 } 

} 

static void set_offsets_for_dir(int *dx, int *dy, direction dir) { 

 switch (dir) { 

 case NORTH: 

 *dy = -1; 

 break; 

 case SOUTH: 

 *dy = 1; 

 break; 

 case EAST: 

 *dx = 1; 

 break; 

 case WEST: 

 *dx = -1; 

 break; 

 } 

} 

Mazelib.h file

#ifndef _maze_h

#define _maze_h

#include

//---- Directional Constants ------------------------------------------------//

typedef enum { NORTH = 0, EAST, SOUTH, WEST } direction;

//---- Function Prototypes

// Initializes the maze according to the width and height passed in. The width and height should both be

// greater than 8. The width should also be less than 80 and the height should be less than 26.

//

// The start of the maze is always in the upper left of the maze at coordinates (1, 1) and is marked with

// an 'S'. Likewise the exit or end of the maze is always in the lower right corner and marked with an

// 'E'. The coordinates of the exit vary since mazes of different sizes may be used

bool maze_init(int width, int height);

// Gets the width of the maze. This and the following function both return -1 in case of an error. This

// could be caused by calling either of these functions before calling maze_init().

int maze_get_width(void);

// Gets the width of the maze. This and the following function both return -1 in case of an error. This

// could be caused by calling either of these functions before calling maze_init().

int maze_get_height(void);

// returns true if the coordinate supplied is within the bounds of the maze and false otherwise.

bool maze_is_coord_in_bounds(int x, int y);

// Returns the character in the maze at a given coordinate. A return value of '#' represents a wall, 'S'

// represents the starting place of the robot, 'E' represents the exit and ' ' represents an open space.

char maze_get_char(int x, int y);

// This function can be used to set a character in the maze to something new. It will not set a square

// that's filled with a wall ('#'), the start of the maze marker ('S'), or the end of the maze marker

// ('E').

bool maze_set_char(int x, int y, char new_val);

// This function prints the maze as it currently is

void maze_print(void);

#endif