Maze generator

[kironia]

I saw a static level generated with jaldhar/Maze. How can I generate another?

[Stagyrite]

Maze generator

I wrote a maze generator in C that is inspired by jaldhar/Maze.

Example

Here's an example maze where '@' is a player and '#' is a wall.

# # # # # # # ### # # # ### # # ##### # ### # # ### # # # # # # ### # # # # ####
#         # #   # #   #   # #     #         #   #   # # # # # #     # #   #
######### # # # # ### # # # ##### # ####### # # # ### # # # # ##### # ### # # ##
  #         # # #     # #       #       # # # # #   # # #   # #   # # #     #
# # ######### # ##### # ############### # # # # # # # # # # # # # # # ##### # ##
# #       #   # #     #               # # # # # # # # # # # #   # #       # # ##
# # ##### # ##### ##### # ########### # # # # # ### # # # # ##### # ##### # # ##
# # #   # #     #       #         #   #   # # # #     # # #     # # #   # # #
# # ### # # ### ####### ######### # ####### # # # ### # ### ##### # # ### # ####
# #     #   # #           #       #         # #   #   # #     #   #   #   #
# ##### ##### ### # ##### ################# # # ####### # ### # ### ### ##### ##
        #   #     # #   #   #     # #     #   #       # #   # #   #   # #
######### # ####### # # # # ### # # # ### ########### # ##### # # ### # # ######
        # #   #   # # # # #     # # #   #           # #       # #   # #       ##
### # # ### # # # # # # # # ##### # ### ########### # ####### ##### # ### ### ##
    # # #   # # # # # # # # #   #           #       #               #   # ###
##### # # # ### # # # # # # # ############# ####### ################### # ### ##
      # # # #   #   # #   # #    @#           #                         # ###
# ### # # # # # ### # ####### ### # ######### # ### ### ### ### ##### ### ######
  #   #   #   # #   #           # # #         #   # #   #   #       #   # ######
# # # # ### # # # # # # # # # # # # # # # # ##### # # ### # # # ### ### # ######
         #    #         #       # #     #    # ##      #        ##   #     #####

Implementation

/*
 * a maze generator inspired by jaldhar/Maze
 * https://github.com/jaldhar/Maze/
 */

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

#define NORTH	0
#define SOUTH	1
#define WEST	2
#define EAST 	3

#define DIRECTIONS	4

#define MAP_HEIGHT	80
#define MAP_WIDTH	22

#define TILE(x, y)	maze[y][x]
#define SET_TILE(x, y)	maze[y][x] = 1

int maze[MAP_HEIGHT][MAP_WIDTH];
int directions[] = { NORTH, SOUTH, WEST, EAST };
int row, col;

int random_odd(int max) {
	int number = arc4random_uniform(max / 2 - 1);
	number *= 2;
	return 1 + number;
}

int valid_position(int position, int max) {
	return position >= 1 && position < max - 1;
}

int dig_maze(int direction_row, int direction_col) {
	int new_row = row + direction_row * 2;
	int new_col = col + direction_col * 2;
	int can_dig = valid_position(row, MAP_WIDTH)
			&& valid_position(col, MAP_HEIGHT)
			&& !TILE(new_row, new_col);

	if (can_dig) {
		SET_TILE(new_row, new_col);
		SET_TILE(row + direction_row, col + direction_col);
		row = new_row;
		col = new_col;
	}

	return can_dig;
}


void shuffle_directions() {
	int i;

	for (i = DIRECTIONS - 1; i > 0; i--) {
		int j = arc4random_uniform(i);
		int tmp = directions[i];

		directions[i] = directions[j];
		directions[j] = tmp;
	}

}


int dig_maze_in_direction(int direction) {
	int can_dig;

	switch (direction) {
		case NORTH:
			can_dig = dig_maze(-1, 0);
			break;
		case SOUTH:
			can_dig = dig_maze(1, 0);
			break;
		case WEST:
			can_dig = dig_maze(0, -1);
			break;
		case EAST:
			can_dig = dig_maze(0, 1);
			break;
		default:
			exit(1);
			break;
	}

	return can_dig;
}

void generate_maze() {
	int i;
	int blocked;

	shuffle_directions();

	do {
		blocked = 1;

		if (arc4random_uniform(DIRECTIONS - 1) == 0) {
			/* new direction */
			shuffle_directions();
		}
		
		for (i = 0; i < DIRECTIONS; i++) {
			
			if (dig_maze_in_direction(directions[i])) {
				blocked = 0;
				break;
			}

		}

	} while (!blocked);

}

void print_maze(int start_x, int start_y) {

	for (int i = 0; i < MAP_WIDTH; i++) {

		for (int j = 0; j < MAP_HEIGHT; j++) {
			
			if (start_y == j && start_x == i) {

				if (TILE(i, j)) {
					putchar('@');
				}

			} else if (TILE(i, j)) {
				putchar(' ');
			} else {
				putchar('#');
			}

		}

		putchar('\n');
	}

}

int main(int argc, char *argv[]) {
	int done = 0;
	int start_x, start_y;

	srand(time(NULL));
	memset(maze, 0, sizeof(maze));

	do {
		row = random_odd(MAP_WIDTH);
		col = random_odd(MAP_HEIGHT);

		if (done == 0) {
			SET_TILE(row, col);
			start_x = row;
			start_y = col;
		}

		if (TILE(row, col)) {
			generate_maze(row, col);
			done++;
		}

	} while (done < MAP_HEIGHT * MAP_WIDTH / 4);

	print_maze(start_x, start_y);
	return 0;
}