How to make Maze in 2d using C programming language using concept of Data structure and Algorithm

MAZE Generator

ALGORITHM

1.  Start
2. Declaration of all the necessary variable.
3. Display initial message to user to perform some task.
4. Depending upon the user input perform task as below:

a)    if userInput == 1 then draw maze.

                                                                             i.          Take length and width of maze from user.

                                                                           ii.          Allocate memory segment for all maze dynamically.

                                                                         iii.          Set boundary  with “#” character.

                                                                         iv.           Link inner node with each other.

                                                                           v.          Check whether destination is wall or not.if not make it blank.

                                                                         vi.          Draw character of each node to generate maze.

b)    else if userInput == 2 then terminate  the program.

c)     else goto step 3.

1.  Handle  all necessary exception.
2.   stop.

      CODE

	/*
	##########################################################################################################################
	# #
	# 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 !!!");
	}
	}
	}

view raw MazeGenerator.html hosted with ❤ by GitHub