path: root/mazerator.c

#include "stack.h"
#include <ctype.h>
#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

/**
 * Returns a position in the maze from coordinates y and x.
 *
 * This is achieved by concatenating the binary values of the two variables.
 *
 * For example:
 *
 * Y: 8 (0b00001000)
 * X: 15 (0b00001111)
 *
 * Will become:
 * 0b0000100000001111
 */
int get_maze_pos(int posY, int posX)
{
	return ((posY) << 8) | posX;
}

/**
 * Returns y and x coordinates from a position in the maze.
 */
int get_maze_coords(int pos, int *y, int *x)
{
	*y = pos >> 8;
	*x = pos & 255;
	return 1;
}

/**
 * Returns whether or not a string is a number.
 */
int is_number(char *str)
{
	size_t len = strlen(str);
	for (int c = 0; c < len; c++)
	{
		if (!isdigit(str[c]))
			return 0;
	}
	return 1;
}

/**
 * Returns a maze filled with walls.
 *
 * Arguments:
 * - height: The height of the new maze
 * - width: The width of the new maze
 * - wall: The wall to fill the new maze with
 */
char ***create_maze(int height, int width, char *wall)
{
	char ***maze;

	// Fill the maze with walls
	maze = malloc(height * sizeof(char **));
	for (int y = 0; y < height; y++)
	{
		maze[y] = malloc(width * sizeof(char *));

		for (int x = 0; x < width; x++)
		{
			maze[y][x] = wall;
		}
	}

	return maze;
}

/**
 * Excavates a maze.
 *
 * This is what creates the actual maze.
 *
 * Arguments:
 * - maze: The maze to excavate
 * - maze_height: The height of the maze
 * - maze_width: The width of the maze
 */
void excavate_maze(char ***maze, int maze_height, int maze_width)
{
	struct stack *path = create_stack(maze_width * maze_height);

	stack_push(path, 0);

	int visited_pos_cnt = 0;
	while (1)
	{
		int pos = stack_peek(path);
		int posY, posX;
		get_maze_coords(pos, &posY, &posX);

		// Set the currently visited grid square to 1 indicating that it has been
		// visited and excavate the visual maze
		maze[posY * 2 + 1][posX * 2 + 1] = " ";

		// Find out available next positions to go to
		int neighbours[3];
		int neighbour_cnt = 0;

		if (posY != 0 && strcmp(maze[posY * 2 - 1][posX * 2 + 1], " ") != 0)
		{
			neighbours[neighbour_cnt] = get_maze_pos(posY - 1, posX);
			neighbour_cnt++;
		}
		if (posY != maze_height - 1 && strcmp(maze[(posY + 1) * 2 + 1][posX * 2 + 1], " ") != 0)
		{
			neighbours[neighbour_cnt] = get_maze_pos(posY + 1, posX);
			neighbour_cnt++;
		}
		if (posX != 0 && strcmp(maze[posY * 2 + 1][posX * 2 - 1], " ") != 0)
		{
			neighbours[neighbour_cnt] = get_maze_pos(posY, posX - 1);
			neighbour_cnt++;
		}
		if (posX != maze_width - 1 && strcmp(maze[posY * 2 + 1][(posX + 1) * 2 + 1], " ") != 0)
		{
			neighbours[neighbour_cnt] = get_maze_pos(posY, posX + 1);
			neighbour_cnt++;
		}

		if (neighbour_cnt == 0)
		{
			if (visited_pos_cnt == (maze_height * maze_width) - 1)
			{
				// The whole maze have been visited
				break;
			}

			// Go back a step
			stack_pop(path);
			continue;
		}

		visited_pos_cnt++;

		int next_pos = neighbours[rand() % neighbour_cnt];

		int next_pos_y, next_pos_x;
		get_maze_coords(next_pos, &next_pos_y, &next_pos_x);

		maze[posY * 2 - (posY - next_pos_y) + 1]
			[posX * 2 - (posX - next_pos_x) + 1] = " ";

		stack_push(path, next_pos);
	}
}

void print_maze(char ***maze, int height, int width)
{
	for (int y = 0; y < height; y++)
	{
		for (int x = 0; x < width; x++)
		{
			printf("%s", maze[y][x]);
		}
		printf("\n");
	}
}

const struct option options[] = {
	{"width", required_argument, NULL, 'w'},
	{"heigth", required_argument, NULL, 'h'},
	{"wall", required_argument, NULL, 'W'},
	{"seed", required_argument, NULL, 's'},
	{"help", no_argument, NULL, 0},
	{NULL, 0, NULL, 0}};

int main(int argc, char *argv[])
{
	int maze_width = 40;
	int maze_height = 20;
	char *wall = "█";
	int seed = -1;

	int c;
	while ((c = getopt_long(argc, argv, "w:h:W:s:", options, NULL)) != -1)
	{
		switch (c)
		{
		case 'w':
			if (!is_number(optarg) || atoi(optarg) < 1 || atoi(optarg) > 255)
			{
				printf("Invalid option argument for -%c!\n", c);
				exit(1);
			}

			maze_width = atoi(optarg);
			break;
		case 'h':
			if (!is_number(optarg) || atoi(optarg) < 1 || atoi(optarg) > 255)
			{
				printf("Invalid option argument for -%c!\n", c);
				exit(1);
			}

			maze_height = atoi(optarg);
			break;
		case 'W':
			wall = optarg;
			break;
		case 's':
			if (!is_number(optarg))
			{
				printf("Invalid option argument for -s/--seed!\n");
				exit(1);
			}

			seed = atoi(optarg);
			break;
		case 0:
			printf(
				"Usage: %s [OPTION]...\n\n"
				"Options:\n"
				"  -w, --width WIDTH       The width of the maze. (1-255) (Default: 40)\n"
				"  -h, --heigth HEIGHT     The heigth of the maze. (1-255) (Default: 20)\n"
				"  -w, --wall WALL         Single character used as maze walls (Default: '█')\n"
				"  -s, --seed SEED         The randomization seed used for maze generation. (Any number)\n"
				"  --help                  Displays usage information\n",
				argv[0]);
			exit(0);
		case '?':
			printf("\nTry '%s --help' for more information\n", argv[0]);
			exit(1);
		}
	}

	if (seed == -1)
	{
		FILE *f = fopen("/dev/urandom", "r");
		fread(&seed, sizeof(seed), 1, f);
		fclose(f);
	}

	srand(seed);

	int full_maze_height = maze_height * 2 + 1;
	int full_maze_width = maze_width * 2 + 1;

	char ***maze = create_maze(full_maze_height, full_maze_width, wall);

	excavate_maze(maze, maze_height, maze_width);

	print_maze(maze, full_maze_height, full_maze_width);
}