Maze Traversal

A common problem in AI(Artificial Intelligent) is solving a Maze. There are number of algorithms to solve different type of mazes and number of Algorithms to create a random maze of a particular type.

there are number of types of mazes. They are classified according to Dimension, Hyper dimension, Topology, Tessellation, Routing, Texture, and Focus. Each have its own properties.

For more Details on Algorithms to Solve Maze go Here
for types of Mazes and maze generation and solution algorithms click here

Below I generate a random maze with Recursive backtracking and Solve it almost same algorithm call wall follower.
The basic idea of the solution is You just place your Right hand on the right side wall and just go until find the exit point. This will eventually guide you to the exit point. this method will suitable for any type of 2D Mazes but it is a little bit slow compared to other methods.

#################################################


#include <stdio.h>
#include <stdlib.h>
#include   <time.h>

#define WALL 1
#define BORDER 2
#define PATH 3

#define TEMPSOL 4
#define SOL 5

#define START 0
#define END 6

#define SIZE 30

void printMaze(int floor[][SIZE]);
void generateMaze(int floor[][SIZE],int start[]);
void solveMaze(int floor[][SIZE],int start[]);

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

    int floor[SIZE][SIZE];

    int start[2]={1,1};
    generateMaze(floor,start);
    printMaze(floor);
   
    solveMaze(floor,start);
    printMaze(floor);

    return (EXIT_SUCCESS);
}


void printMaze(int floor[][SIZE]){
    printf("\n");
    int i;
    int j;
    for(j=SIZE-1;j>=0;j--){
        for(i=0;i<SIZE;i++){
            switch(floor[i][j]){
                case BORDER:
                    printf("##");
                    break;
                case WALL:
                    printf("WW");
                    break;
                case PATH:
                    printf("  ");
                    break;
                case START:
                case TEMPSOL:
                    printf("ST");
                    break;
                case END:
                    printf("EX");
                    break;
                case SOL:
                    printf("* ");
                    break;
            }
        }
        printf("\n");
    }
}

void solveMaze(int floor[][SIZE], int start[]){
    int recursiveSolve(int floor[][SIZE],int position[]);
    recursiveSolve(floor,start);
    floor[start[0]][start[1]]=START;

}

void generateMaze(int floor[][SIZE],int startPosition[]){
    void recursiveBackTrack(int floor[][SIZE],int position[]);

    //initialize Maze Arena
    int i;
    int j;
    for(i=0;i<SIZE;i++){
        for(j=0;j<SIZE;j++){
            floor[i][j]=BORDER;
        }
    }
    for(i=1;i<SIZE-1;i++){
        for(j=1;j<SIZE-1;j++){
            floor[i][j]=WALL;
        }
    }

    //set the StartPosition
    srand(time(NULL));
    recursiveBackTrack(floor,startPosition);
    floor[startPosition[0]][startPosition[1]]=START;
    //set the EndPosition
    int endPosition[2]={SIZE-2,SIZE-2};
    floor[endPosition[0]][endPosition[1]]=END;
}

int  recursiveSolve(int floor[][SIZE],int currentPosition[]){
    int neighbour[4][3]={{floor[currentPosition[0]+1][currentPosition[1]],currentPosition[0]+1,currentPosition[1]},       //right
                             {floor[currentPosition[0]][currentPosition[1]+1],currentPosition[0],currentPosition[1]+1},       //up
                             {floor[currentPosition[0]-1][currentPosition[1]],currentPosition[0]-1,currentPosition[1]},       //left
                             {floor[currentPosition[0]][currentPosition[1]-1],currentPosition[0],currentPosition[1]-1}};      //down
   
    int i;
    if(floor[currentPosition[0]][currentPosition[1]]==END){
        return 1;
    }else{
        for(i=0;i<4;i++){
            if(neighbour[i][0]==PATH||neighbour[i][0]==END){
                 int t[2]={neighbour[i][1],neighbour[i][2]};
                floor[currentPosition[0]][currentPosition[1]]=TEMPSOL;
                if(recursiveSolve(floor,t)==1){
                    floor[currentPosition[0]][currentPosition[1]]=SOL;
                    return 1;
                }
            }
        }
        floor[currentPosition[0]][currentPosition[1]]=PATH;
        return 0;
    }

}

void recursiveBackTrack(int floor[][SIZE],int currentPosition[]){
    int checkPositions(int floor[][SIZE],int position[],int comingFrom);
    floor[currentPosition[0]][currentPosition[1]]=PATH;

   
    int eachDirection[4][2]={{currentPosition[0]+1,currentPosition[1]},       //right
                             {currentPosition[0],currentPosition[1]+1},       //up
                             {currentPosition[0],currentPosition[1]-1},      //down
                             {currentPosition[0]-1,currentPosition[1]}};       //left
                            

   
    int directions[4]={0,1,2,3};
    int i;
   
    for(i=4;i>0;i--){
        int randomDirection=rand()%i;
        int tempDirection=directions[randomDirection];
        directions[randomDirection]=directions[i-1];
        if(checkPositions(floor,eachDirection[tempDirection],(3-tempDirection))==1){
            recursiveBackTrack(floor,eachDirection[tempDirection]);
        }
    }

}

int checkPositions(int floor[][SIZE],int position[],int comingFrom){
    int eachDirection[4][2]={{position[0]+1,position[1]},       //right
                             {position[0],position[1]+1},       //up
                             {position[0],position[1]-1},      //down
                             {position[0]-1,position[1]}};       //left
   
    if(floor[position[0]][position[1]]==WALL){                     //check weather the cell is unused
        int i;
        for(i=0;i<4;i++){
            if(i!=comingFrom && floor[eachDirection[i][0]][eachDirection[i][1]]==PATH){      //skip the previous cell &&
                    return 0;
            }
        }     
        return 1;
    }else{
        return 0;
    }
}