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
 * - start_x: X coordinate to start on
 * - start_y Y coordinate to start on
 */
void excavate_maze(char ***maze, int maze_height, int maze_width, int start_x, int start_y)
{
	struct stack *path = create_stack(maze_width * maze_height);

	stack_push(path, get_maze_pos(start_y, start_x));

	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");
	}
}

void validate_number_optarg(char *optarg, int c)
{
	char *base_error = malloc(39 * sizeof(char));
	sprintf(base_error, "Error: Invalid option argument for -%c.", c);

	if (!is_number(optarg))
	{
		printf("%s It must be a number\n", base_error);
		exit(1);
	}

	if (atoi(optarg) < 1)
	{
		printf("%s It must be greater than 0\n", base_error);
		exit(1);
	}
}

void validate_start_coords(int start_x, int start_y, int width, int height)
{
	char *error_format = "Error: The %s start coordinate is not allowed to be higher than the maze's %s\n";

	if (start_x > width)
	{
		printf(error_format, "x", "width");
		exit(1);
	}

	if (start_y > height)
	{
		printf(error_format, "y", "height");
		exit(1);
	}
}

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

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

	int c;
	while ((c = getopt_long(argc, argv, "w:h:W:s:x:y:", options, NULL)) != -1)
	{
		switch (c)
		{
		case 'w':
			validate_number_optarg(optarg, c);
			maze_width = atoi(optarg);
			break;
		case 'h':
			validate_number_optarg(optarg, c);
			maze_height = atoi(optarg);
			break;
		case 'x':
			validate_number_optarg(optarg, c);
			start_x = atoi(optarg);
			break;
		case 'y':
			validate_number_optarg(optarg, c);
			start_y = atoi(optarg);
			break;
		case 'W':
			wall = optarg;
			break;
		case 's':
			validate_number_optarg(optarg, c);
			seed = atoi(optarg);
			break;
		case 0:
			printf(
				"Usage: %s [OPTION]...\n\n"
				"Options:\n"
				"  -w, --width WIDTH       The width of the maze (Default: 40)\n"
				"  -h, --heigth HEIGHT     The heigth of the maze (Default: 20)\n"
				"  -x, --start-x X         The x coordinate for the start position (Default: 0)\n"
				"  -y, --start-y Y         The y coordinate for the start position (Default: 0)\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);
		}
	}

	validate_start_coords(start_x, start_y, maze_width, maze_height);

	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, start_x, start_y);

	print_maze(maze, full_maze_height, full_maze_width);
}