Project 4 Maze Runner Overview In this project you will implement the logic of a

Question

Project 4

Maze Runner

Overview

In this project you will implement the logic of a maze solver in C. 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 ‘.h’ file to provide an interface to your code.

Submission Instructions

Submit only the .c and .h files that you created, but do not zip them! 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 for interaction with the maze. 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 maze1 . 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() function2 . 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 Program Output 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. When an ’o’ is crossed, an ’O’3 should result. Finally, when an ’O’ is crossed, an ’@’ should be left in its place. 1Descriptions of these maze library functions are in the comments of the mazelib.h file provided. 2My implementation has around five. 3Capital ’o’, not a zero!

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. To run the program, type “./maze_runner ” at the command prompt. A good way to start this project would simply be to create your .h and .c files and fill in a skeleton for the necessary functions. They can just do nothing and return, but this will let you compile the project. After that, you can run the program to make sure everything is working and then begin to implement your solver logic.

--start of mazelib.c--

// PAY NO MIND TO ANYTHING FROM HERE
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#include "mazelib.h"

static int xy_to_index(int, int);

static int width;
static int height;
static char *maze;
static bool initializing = false;
// TO HERE

////////////////////////////////////////////////////////////////////////////////
// BEGIN: THINGS YOU SHOULD LOOK AT //
////////////////////////////////////////////////////////////////////////////////
/*
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;
}

// returns "true" if x and y are both in-bounds defined by:
// 0 <= x < width and 0 <= y <= height
// This function is not strictly necessary to complete the project
bool maze_is_coord_in_bounds( int x, int y ) {
return 0 <= x && x < width && 0 <= y && y < height;
}

////////////////////////////////////////////////////////////////////////////////
// BEGIN: STUFF YOU DON'T NEED TO LOOK AT OR UNDERSTAND FOR THE PROJECT //
////////////////////////////////////////////////////////////////////////////////

static void shuffle_dirs(enum direction*);
static void reset(void);
static bool are_valid_maze_dimensions(int, int);
static void set_offsets_for_dir(int*, int*, enum direction);
static void maze_visit(int, int);

// 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;
}

/*
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, ' ');

enum 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(enum 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, enum direction dir) {
switch (dir) {
case NORTH:
*dy = -1;
break;
case SOUTH:
*dy = 1;
break;
case EAST:  
*dx = 1;
break;
case WEST:  
*dx = -1;
break;
}
}

--start of mazelib.h--

#ifndef _maze_h
#define _maze_h
#include <stdbool.h>

//---- Directional Constants ------------------------------------------------//
// You can use this to track the direction your solver is facing
enum direction { NORTH, EAST, SOUTH, WEST };

//---- 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.
// IMPORTANT: The start of the maze is always in the upper left of the maze at (1, 1)
bool maze_init(int width, int height);

// 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 to something new though.
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

--start of maze_runner.c--

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#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(); // These are the two functions you must implement in runner.c
runner_solve(); // and declare in runner.h
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(" width must be an odd integer between 9 and 79 inclusive ");
printf(" height must be an odd integer between 9 and 25 inclusive ");
}

Thank you!!

Explanation / Answer

As per your requirements, I am attaching Runner.h and Runner.c file in order to resolve the problem of your project.  

Here Runner.h file as follows:

//CREATING RUNNER_H FILE
#ifndef _runner_h
#define _runner_h
#include "mazelib.h"

void runner_init();

void runner_solve();

#endif // _runner_h

Here Runner.C file as follows:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include "runner.h"
#include<string.h>

//runnner_init declaration here. Here you can use mazelib function according to your wish.
void runner_init(){
printf("%c%d%d ",maze_get_char(10,10),10,10);
}

//runner_Solve declaration here. Here you can use mazelib or other inbuilt library by including #include in file as per
//your wish
void runner_solve(){
printf("%c%d%d ",maze_get_char(10,10),10,10);
}

Here I am using mazelib function for just printing value of char at some particular position. As per your description, you had already mentioned that you just need a direction to apply for your own project. I am sure, It will help you to understand how you can mix library to solve a big complex problem.

Thanks

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.