7 files changed, 411 insertions, 0 deletions
diff --git a/src/maze.c b/src/maze.c
new file mode 100644
index 0000000..9830098
--- /dev/null
+++ b/src/maze.c
@@ -0,0 +1,131 @@
+#include "maze.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/**
+ * Returns a filled maze grid.
+ *
+ * Arguments:
+ * - width: The width of the new maze
+ * - height: The height of the new maze
+ * - wall: The wall to fill the new maze with
+ */
+char ***create_maze_grid(int width, int height, 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;
+}
+
+struct Maze maze_create(struct MazeSize size, char *wall)
+{
+	struct Maze new_maze;
+	new_maze.grid = create_maze_grid(size.width * 2 + 1, size.height * 2 + 1, wall);
+	new_maze.size = size;
+
+	return new_maze;
+}
+
+void get_neighbours(struct Maze maze, struct Position pos, struct Position neighbours[3], int *neighbour_cnt)
+{
+	if (pos.y != 0 && strcmp(maze.grid[pos.y * 2 - 1][pos.x * 2 + 1], " ") != 0)
+	{
+		struct Position down_neighbour_pos = {.x = pos.x, .y = pos.y - 1};
+		neighbours[*neighbour_cnt] = down_neighbour_pos;
+		(*neighbour_cnt)++;
+	}
+	if (pos.y != maze.size.height - 1 && strcmp(maze.grid[(pos.y + 1) * 2 + 1][pos.x * 2 + 1], " ") != 0)
+	{
+		struct Position up_neighbour_pos = {.x = pos.x, .y = pos.y + 1};
+		neighbours[*neighbour_cnt] = up_neighbour_pos;
+		(*neighbour_cnt)++;
+	}
+	if (pos.x != 0 && strcmp(maze.grid[pos.y * 2 + 1][pos.x * 2 - 1], " ") != 0)
+	{
+		struct Position left_neighbour_pos = {.x = pos.x - 1, .y = pos.y};
+		neighbours[*neighbour_cnt] = left_neighbour_pos;
+		(*neighbour_cnt)++;
+	}
+	if (pos.x != maze.size.width - 1 && strcmp(maze.grid[pos.y * 2 + 1][(pos.x + 1) * 2 + 1], " ") != 0)
+	{
+		struct Position right_neighbour_pos = {.x = pos.x + 1, .y = pos.y};
+		neighbours[*neighbour_cnt] = right_neighbour_pos;
+		(*neighbour_cnt)++;
+	}
+}
+
+/**
+ * Excavates a maze.
+ *
+ * This is what creates the actual maze.
+ *
+ * Arguments:
+ * - maze: The maze to excavate
+ * - start_pos: Start position
+ */
+void maze_excavate(struct Maze maze, struct Position start_pos)
+{
+	struct PositionStack *path = create_pos_stack(maze.size.width * maze.size.height);
+
+	pos_stack_push(path, start_pos);
+
+	int visited_pos_cnt = 0;
+	while (1)
+	{
+		struct Position pos = pos_stack_peek(path);
+
+		maze.grid[pos.y * 2 + 1][pos.x * 2 + 1] = " ";
+
+		struct Position neighbours[3] = {};
+		int neighbour_cnt = 0;
+
+		get_neighbours(maze, pos, neighbours, &neighbour_cnt);
+
+		if (neighbour_cnt == 0)
+		{
+			if (visited_pos_cnt == (maze.size.height * maze.size.width) - 1)
+			{
+				// The whole maze have been visited
+				break;
+			}
+
+			// Go back a step
+			pos_stack_pop(path);
+			continue;
+		}
+
+		visited_pos_cnt++;
+
+		struct Position next_pos = neighbours[rand() % neighbour_cnt];
+
+		maze.grid[pos.y * 2 - (pos.y - next_pos.y) + 1]
+				 [pos.x * 2 - (pos.x - next_pos.x) + 1] = " ";
+
+		pos_stack_push(path, next_pos);
+	}
+}
+
+void maze_print(char ***maze, int width, int height)
+{
+	for (int y = 0; y < height; y++)
+	{
+		for (int x = 0; x < width; x++)
+		{
+			printf("%s", maze[y][x]);
+		}
+		printf("\n");
+	}
+}
+\ No newline at end of file
diff --git a/src/maze.h b/src/maze.h
new file mode 100644
index 0000000..fc0e489
--- /dev/null
+++ b/src/maze.h
@@ -0,0 +1,24 @@
+#ifndef MAZE_H
+#define MAZE_H
+
+#include "position_stack.h"
+
+struct MazeSize
+{
+	int width;
+	int height;
+};
+
+struct Maze
+{
+	char ***grid;
+	struct MazeSize size;
+};
+
+struct Maze maze_create(struct MazeSize size, char *wall);
+
+void maze_excavate(struct Maze maze, struct Position start_pos);
+
+void maze_print(char ***maze, int width, int height);
+
+#endif
+\ No newline at end of file
diff --git a/src/mazerator.c b/src/mazerator.c
new file mode 100644
index 0000000..33c47ce
--- /dev/null
+++ b/src/mazerator.c
@@ -0,0 +1,136 @@
+#include "maze.h"
+#include "utils.h"
+#include <getopt.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+void validate_number_optarg(char *optarg, int c)
+{
+	char *base_error = malloc((38 + 1) * 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);
+	}
+}
+
+void get_seed(int *seed_dst)
+{
+	FILE *urandom = fopen("/dev/urandom", "r");
+	fread(seed_dst, sizeof(*seed_dst), 1, urandom);
+	fclose(urandom);
+}
+
+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)
+	{
+		get_seed(&seed);
+	}
+
+	srand(seed);
+
+	int full_maze_height = maze_height * 2 + 1;
+	int full_maze_width = maze_width * 2 + 1;
+
+	struct MazeSize maze_size = {.width = maze_width, .height = maze_height};
+
+	struct Maze maze = maze_create(maze_size, wall);
+
+	struct Position start_pos = {.x = start_x, .y = start_y};
+
+	maze_excavate(maze, start_pos);
+
+	maze_print(maze.grid, full_maze_width, full_maze_height);
+}
diff --git a/src/position_stack.c b/src/position_stack.c
new file mode 100644
index 0000000..3d546b8
--- /dev/null
+++ b/src/position_stack.c
@@ -0,0 +1,69 @@
+#include "position_stack.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+// Error handler for stack errors
+void stack_error(int err)
+{
+	switch (err)
+	{
+	case STACK_ERR_OVERFLOW:
+		printf("Error: Stack overflow\nBe kind and report this problem.");
+		break;
+	case STACK_ERR_UNDERFLOW:
+		printf("Error: Stack underflow\nBe kind and report this problem.");
+		break;
+	}
+
+	exit(1);
+}
+
+// Creates a new stack
+struct PositionStack *create_pos_stack(int capacity)
+{
+	struct PositionStack *stack_pt = malloc(sizeof(struct PositionStack));
+
+	stack_pt->max_size = capacity;
+	stack_pt->top = -1;
+	stack_pt->items = malloc(sizeof(struct Position) * capacity);
+
+	return stack_pt;
+}
+
+// Adds a new item to a stack
+void pos_stack_push(struct PositionStack *stack_pt, struct Position pos)
+{
+	// Avoid a overflow by checking if the stack is full
+	if (stack_pt->top == stack_pt->max_size - 1)
+	{
+		stack_error(STACK_ERR_OVERFLOW);
+	}
+
+	// Add an element and increase the top index
+	stack_pt->items[++stack_pt->top] = pos;
+}
+
+// Returns the topmost item of a stack
+struct Position pos_stack_peek(struct PositionStack *stack_pt)
+{
+	// Avoid a underflow by checking if the stack is empty
+	if (stack_pt->top == -1)
+	{
+		stack_error(STACK_ERR_UNDERFLOW);
+	}
+
+	return stack_pt->items[stack_pt->top];
+}
+
+// Deletes the topmost item of a stack
+struct Position pos_stack_pop(struct PositionStack *stack_pt)
+{
+	// Avoid a underflow by checking if the stack is empty
+	if (stack_pt->top == -1)
+	{
+		stack_error(STACK_ERR_UNDERFLOW);
+	}
+
+	// Decrease the stack size by 1 and return the popped element
+	return stack_pt->items[stack_pt->top--];
+}
+\ No newline at end of file
diff --git a/src/position_stack.h b/src/position_stack.h
new file mode 100644
index 0000000..fe93e8c
--- /dev/null
+++ b/src/position_stack.h
@@ -0,0 +1,28 @@
+#ifndef POSITION_STACK_H
+#define POSITION_STACK_H
+
+#define STACK_ERR_OVERFLOW 0xFFF01
+#define STACK_ERR_UNDERFLOW 0xFFF02
+
+struct Position
+{
+	int x;
+	int y;
+};
+
+struct PositionStack
+{
+	int max_size;
+	int top;
+	struct Position *items;
+};
+
+struct PositionStack *create_pos_stack(int capacity);
+
+void pos_stack_push(struct PositionStack *stack_pt, struct Position pos);
+
+struct Position pos_stack_peek(struct PositionStack *stack_pt);
+
+struct Position pos_stack_pop(struct PositionStack *stack_pt);
+
+#endif
+\ No newline at end of file
diff --git a/src/utils.c b/src/utils.c
new file mode 100644
index 0000000..ce3dcd4
--- /dev/null
+++ b/src/utils.c
@@ -0,0 +1,17 @@
+#include "utils.h"
+#include <ctype.h>
+#include <string.h>
+
+/**
+ * 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;
+}
+\ No newline at end of file
diff --git a/src/utils.h b/src/utils.h
new file mode 100644
index 0000000..357f0d2
--- /dev/null
+++ b/src/utils.h
@@ -0,0 +1,6 @@
+#ifndef UTILS_H
+#define UTILS_H
+
+int is_number(char *str);
+
+#endif
+\ No newline at end of file