/*
##########################################################################################################################
# #
# MAZE GENERATOR PROGRAM IN C PROGRAMMING LANGUAGE USING CONCEPT OF DATA STRUCTURE AND ALGORITHM #
# #
##########################################################################################################################
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <conio.h>
typedef struct{
int x, y; //Node position - little waste of memory, but it allows faster generation
void *parent; //Pointer to parent node
char c; //Character to be displayed
char dirs; //Directions that still haven't been explored
}Node;
Node *nodes; //Nodes array or pointer that works similar to the array
int width, height; //Maze dimensions should be in odd integer number
int init(){
int i, j;
Node *n;
nodes = calloc( width * height, sizeof( Node ) ); //Allocate memory for maze
// printf("nodes = %d\n\n",nodes);
if ( nodes == NULL ){ //Exception handling
return 1;
}
// to create boundaries
for ( i = 0; i < width; i++ ){ //Setup crucial nodes
for ( j = 0; j < height; j++ ){
n = nodes + i + j * width;
if ( i * j % 2 ){ //for creating cell of maze
n->x = i;
n->y = j;
n->dirs = 15; //00001111 //Assume that all directions can be explored (4 youngest bits set)
n->c = ' ';
}else{ //Add walls between nodes
n->c = '#';
}
} //ending of inner for
}
//ending of outer for
return 0; // returning zero to say task successfully completed
}
Node *link( Node *n ){
//Connects node to random neighbor (if possible) and returns
//address of next node that should be visited
int x, y;
char dir;
Node *dest;
//Nothing can be done if null pointer is given - return
if ( n == NULL ){ //Exception handling
return NULL;
}
//While there are directions still unexplored
while ( n->dirs ){
/* rand function gives random value among 0,1,2,3.
depending upon the random value shifted 00000001 to left
for rand = 0, dir = 00000001 == 1
for rand = 1, dir = 00000010 == 2
for rand = 2, dir = 00000100 == 4
for rand = 3, dir = 00001000 == 8
00000001
*/
dir = ( 1 << ( rand() % 4 ) ); //Randomly pick one direction
/*
if dir = 00000001
~00001111 == 11110000 bitwise 00000001
ie 11110000 & 00000001 == 000000000
*/
//If it has already been explored - try again(exception handling)
if ( ~ n->dirs & dir ){
continue;
}
/*
if dir = 00000001 then ~dir == 11111110 == 254
a += b
== a = a + b
similarly
n->dirs &= ~dir;
==
n->dirs = n->dirs & ~dir;
14 == 00001110 = 00001111 & 11111110
*/
n->dirs &= ~dir; //Mark direction as explored
//Depending on chosen direction
switch ( dir ){
//Check if it's possible to go right
case 1:
/*
#####
#####
#####
*/
if ( n->x + 2 < width ){
x = n->x + 2;
y = n->y;
}else{
continue;
}
break;
//Check if it's possible to go down
case 2:
if ( n->y + 2 < height){
x = n->x;
y = n->y + 2;
}else{
continue;
}
break;
//Check if it is possible to go left
case 4:
if ( n->x - 2 >= 0 ){
x = n->x - 2;
y = n->y;
}else{
continue;
}
break;
//Check if it's possible to go up
case 8:
if ( n->y - 2 >= 0 ){
x = n->x;
y = n->y - 2;
}else{
continue;
}
break;
}
/*
nodes = 6500728
let x = 1 and y = 1
then x= 3, y =1
so dest = 6500728 + 3 + 1 * 21
= 6500752
*/
dest = nodes + x + y * width; //Get destination node into pointer (makes things a tiny bit faster)
if ( dest->c == ' ' ){ //Make sure that destination node is not a wall
//If destination is a linked node already - abort(terminated)
if ( dest->parent != NULL ){
continue;
}
dest->parent = n; //Otherwise, adopt node
/*
n->x + ( x - n->x ) / 2 + ( n->y + ( y - n->y ) / 2 ) * width
1+(3 - 1)/2 + (1 +(1 - 1)/2)*21 == 23
here address of nodes[0] = 6500728
address of nodes[23] = 6500728 + 23 = 6500751
*/
//Remove wall between nodes
nodes[ n->x + ( x - n->x ) / 2 + ( n->y + ( y - n->y ) / 2 ) * width ].c = ' ';
//Return address of the child node
return dest;
}
}
//If nothing more can be done here - return parent's address
return n->parent;
}
void draw(){
int i, j;
//Outputs maze to terminal - nothing special
for ( i = 0; i < height; i++ ){
for ( j = 0; j < width; j++ ){
printf( "%c", nodes[j + i * width].c );
}
printf( "\n" );
}
}
/* method to move the player for future plan
void player(Node *basant){
char select;
Node *currentBasant;
if(basant == NULL){
printf("Error in player !!!");
}else{
basant->c = '#';
printf(" A for Left\n");
printf(" W for Up\n");
printf(" D for Right\n");
printf(" S for Down\n");
while(1){
select = getch();
switch(select){
case 'a':
if(basant[0-1].c =='#'){
}else{
basant[0].c == ' ';
basant[0-1].c = '#';
currentBasant = & basant[0-1];
}
//left arrow
###
###
###
break;
case 'w':
//up arrow
if(basant[0-width].c == '#'){
}else{
basant[0].c == ' ';
basant[0-width].c = '#';
currentBasant = & basant[0-width];
}
break;
case 'd':
//right arrow
if(basant[0+1].c == '#'){
}else{
basant[0].c == ' ';
basant[0+1].c = '#';
currentBasant = &basant[0+1];
}
break;
case 's':
//down arrow
if(basant[0+width].c == '#'){
}else{
basant[0].c == ' ';
basant[0+width].c = '#';
currentBasant = &basant[0+width];
}
break;
default:
continue;
}
//to draw a maze
system("CLS");
draw();
basant = currentBasant;
}
}
}
*/
int main(){
Node *start, *last, *playerPosition;
int ch;
while(1){
printf("\nWE HAVE FOLLOWING SERVICES.");
printf("\n1.draw Maze");
printf("\n2.Exit");
printf("\nEnter tour choice : ");
scanf("%d",&ch);
switch(ch){
case 1 :
//taking user input
printf("Enter dimension of maze( add number only ):>\n");
printf("Width = ");
scanf("%d",&width);
printf("Height = ");
scanf("%d",&height);
printf("\n\n Generated maze is :\n\n\n\n");
//checking for dimension validity
if ( width < 3 || height < 3 ){
printf("invalid maze size value!\n");
exit( 1 );
}
//Allow only odd dimensions
if ( !( width % 2 ) || !( height % 2 ) ){
printf("dimensions must be odd!\n");
exit( 1 );
}
//Do not allow negative dimensions
if ( width <= 0 || height <= 0 ){
printf("dimensions must be greater than 0!\n");
exit( 1 );
}
//Seed random generator
srand( time( NULL ) );
//checking memory leak
if ( init() ){
printf("out of memory!\n");
exit( 1 );
}
//Setup start node
/*
start = nodes + 1 + width;
= 6500728 +1 + 21
= 6500750
#######################################
#start
*/
start = nodes + 1 + width;
playerPosition = start;
start->parent = start;
last = start;
//Connect nodes until start node is reached and can't be left
while( ( last = link(last) ) != start );
draw();
//code for player
//function call to move the player for future plan
//player(playerPosition);
break;
case 2:
exit(0);
break;
default:
printf("\nEnter correct choice !!!");
}
}
}