1 files changed, 131 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