MAIN.C
======
Main function for
maze solver
*/
#include <stdio.h>
#include <stdlib.h>
#include "maze.h"
#include "solve.h"
int main(int argc, char *argv[]) {
struct maze maze;
if ( argc < 2 )
{
puts("You
must specify the filename of your maze");
return
EXIT_FAILURE;
}
else if ( argc
> 2 ) {
puts("Too
many command line arguments");
return
EXIT_FAILURE;
}
GetMazeFromFile(argv[1], &maze);
if (
solve(&maze) == MAZE_FOUNDEXIT )
puts("Found exit!");
else
puts("Can't reach exit!");
PrintMaze(&maze);
FreeMaze(&maze);
return
EXIT_SUCCESS;
}
--------------------------------------------------------------------------------
maze.h
/*
MAZE.H
======
Interface to maze
functions
*/
#ifndef PG_MAZE_H
#define PG_MAZE_H
/* Structure
definitions */
struct maze {
char ** map;
int startx,
starty;
int numrows;
int initdir;
};
struct pos {
int x, y, dir;
};
/* Macros */
#define BUFFERSIZE (1000)
#define MAZE_ENTRANCE 'I'
#define MAZE_EXIT
'O'
#define MAZE_WALL
'X'
#define MAZE_PATH
' '
#define MAZE_TRAIL
'@'
#define MOVE_LEFT (0)
#define MOVE_UP (1)
#define MOVE_RIGHT (2)
#define MOVE_DOWN (3)
#define MAZE_NOWAY
(0)
#define MAZE_FOUNDEXIT
(1)
#define MAZE_NOEXIT
(-1)
/* Function
declarations */
void GetMazeFromFile(char * filename, struct maze * maze);
void FreeMaze(struct maze * maze);
void PrintMaze(struct maze * maze);
#endif /* PG_MAZE_H
*/
--------------------------------------------------------------------------------
maze.c
/*
MAZE.C
======
Implementation of
maze functions
*/
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include "maze.h"
/* Creates a maze
from a file */
void GetMazeFromFile(char * filename, struct maze * maze) {
char
buffer[BUFFERSIZE];
FILE * fp;
char ** map;
int n = 0,
foundentrance = 0, foundexit = 0;
/* Open file
*/
if ( !(fp =
fopen(filename, "r")) ) {
sprintf(buffer, "Couldn't open file %s", filename);
perror(buffer);
exit(EXIT_FAILURE);
}
/* Determine number of rows in maze */
while (
fgets(buffer, BUFFERSIZE, fp) )
++n;
/* Allocate correct number of rows */
if ( !(map =
malloc(n * sizeof *map)) ) {
fputs("Couldn't allocate memory for map\n", stderr);
exit(EXIT_FAILURE);
}
/* Reset file
*/
rewind(fp);
n = 0;
/* Store each row */
while (
fgets(buffer, BUFFERSIZE, fp) ) {
int i;
if ( !(map[n]
= malloc((strlen(buffer)+1) * sizeof map[n])) ) {
fputs("Couldn't allocate memory for map\n", stderr);
for ( i =
0; i < n; ++i )
free(map[i]);
free(map);
exit(EXIT_FAILURE);
}
strcpy(map[n],
buffer);
/* Remove trailing whitespace */
for ( i =
strlen(map[n]) - 1; isspace(map[n][i]); --i )
map[n][i]
= 0;
/* Check for entrance and store position if
found */
if (
!foundentrance ) {
i = 0;
while (
map[n][i] != 'I' && map[n][i++] );
if (
map[n][i] == MAZE_ENTRANCE ) {
maze->startx = i;
maze->starty = n;
foundentrance = 1;
}
}
/* Check for exit */
if (
!foundexit ) {
if (
strchr(map[n], MAZE_EXIT) )
foundexit = 1;
}
++n;
}
/* Fill in maze structure */
maze->map =
map;
maze->numrows =
n;
/* Exit if there is no entrance or no exit */
if ( !foundentrance
) {
fputs("Maze has no entrance!\n", stderr);
FreeMaze(maze);
exit(EXIT_FAILURE);
}
if ( !foundexit )
{
fputs("Maze has no exit!\n", stderr);
FreeMaze(maze);
exit(EXIT_FAILURE);
}
/* Check for initial direction into the
maze */
if (
maze->startx < strlen(maze->map[maze->starty]) - 1 &&
maze->map[maze->starty][maze->startx+1] == MAZE_PATH )
maze->initdir = MOVE_RIGHT;
else if (
maze->startx > 0 &&
maze->map[maze->starty][maze->startx-1] == MAZE_PATH )
maze->initdir = MOVE_LEFT;
else if (
maze->starty > 0 &&
maze->map[maze->starty-1][maze->startx] == MAZE_PATH )
maze->initdir = MOVE_UP;
else if (
maze->starty < (maze->numrows-1) &&
maze->map[maze->starty+1][maze->startx] == MAZE_PATH )
maze->initdir = MOVE_DOWN;
/* Close file and return */
if ( fclose(fp) )
{
perror("Couldn't close file");
FreeMaze(maze);
exit(EXIT_FAILURE);
}
}
/* Frees memory used
by a maze */
void FreeMaze(struct maze * maze) {
int n;
for ( n = 0; n
< maze->numrows; ++n )
free(maze->map[n]);
free(maze->map);
}
/* Outputs a
maze */
void PrintMaze(struct maze * maze) {
int n;
for ( n = 0; n
< maze->numrows; ++n )
puts(maze->map[n]);
}
--------------------------------------------------------------------------------
solve.h
/*
SOLVE.H
=======
Interface to maze
solving operation
*/
#ifndef PG_SOLVE_H
#define PG_SOLVE_H
#include "maze.h"
/* Function
declarations */
int solve(struct maze * maze);
#endif /* PG_SOLVE_H
*/
--------------------------------------------------------------------------------
solve.c
/*
SOLVE.C
=======
Implementation of
maze solving operation
*/
#include "solve.h"
/* Recursive function
to find a path through a maze */
int look(struct maze * maze, struct pos pos) {
int i, n;
/* Set new position based on direction */
switch ( pos.dir )
{
case MOVE_UP:
pos.y -= 1;
break;
case MOVE_DOWN:
pos.y += 1;
break;
case MOVE_LEFT:
pos.x -= 1;
break;
case MOVE_RIGHT:
pos.x += 1;
break;
default:
break;
}
/* Check new position */
if ( pos.y < 0
|| pos.y >= maze->numrows )
return
MAZE_NOWAY;
else if ( pos.x
< 0 || pos.x >= strlen(maze->map[pos.y]) )
return
MAZE_NOWAY;
else if (
maze->map[pos.y][pos.x] == MAZE_WALL )
return
MAZE_NOWAY;
else if (
maze->map[pos.y][pos.x] == MAZE_EXIT )
return
MAZE_FOUNDEXIT;
else if (
maze->map[pos.y][pos.x] == MAZE_ENTRANCE )
return
MAZE_NOEXIT;
/* Try all the three directions other than
backwards */
pos.dir -= 1;
if ( pos.dir <
0 )
pos.dir += 4;
for ( i = 0; i
< 3; ++i ) {
maze->map[pos.y][pos.x] = MAZE_TRAIL; /*
Leave trail through maze */
n = look(maze,
pos);
if ( n ) {
if ( n ==
MAZE_NOEXIT )
maze->map[pos.y][pos.x] = MAZE_PATH;
/* No exit, so clear trail */
return n;
}
pos.dir += 1;
if ( pos.dir
> 3 )
pos.dir -=
4;
}
/* Dead end, so clear trail and return */
maze->map[pos.y][pos.x] = MAZE_PATH;
return 0;
}
/* Function to find a
path through a maze */
int solve(struct maze * maze) {
struct pos pos;
pos.x =
maze->startx;
pos.y =
maze->starty;
pos.dir =
maze->initdir;
return look(maze,
pos);
}
--------------------------------------------------------------------------------
maze1.maz
XXXXXXXXXXXXXXXIXXX
X X
X XXXXXXXXXXXXXXXXX
X X X
X XXX XXXXX X X X X
X X X X X X X X
X X X XXX X X X X X
X X X X X X X
XXXXXXXXXXXOXXXXXXX
--------------------------------------------------------------------------------
maze2.maz
XXXXXXXXXXXXXXXXXXXX
X X X X
X X XXXX XXX XXXXXXX
X X X X
X X X XXXXX XXX X XX
X XXX X X X X X XX
I X X X XXXXXX
X XXXXX X X X
X X X X XX O
XXXXXXXXXXXXXXXXXXXX
--------------------------------------------------------------------------------
nowayout.maz
XXXXXXXXXIXXXXXXXXX
X X XX XX X X
X X X X X X
X XXXXX X X XXXXX X
X O X
X XXXXX X X XXXXX X
X X X X X X
X X XX XX X X
XXXXXXXXXXXXXXXXXXX
Contact:
Mr. Roshan P. Helonde
Mobile: +91-7276355704
WhatsApp: +91-7276355704
Email: roshanphelonde@rediffmail.com
.png)
.png)
