From 74ea6dc86646cee9915292d73d8c7afef01ef3e0 Mon Sep 17 00:00:00 2001
From: Sopár Adrián <adrian.sopar@protonmail.com>
Date: Thu, 20 Jun 2024 09:28:14 +0200
Subject: First commit. This is mostly the state of the project as I left it
 around the end of 2019.

---
 src/maze_generator.c | 113 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 113 insertions(+)
 create mode 100644 src/maze_generator.c

(limited to 'src/maze_generator.c')

diff --git a/src/maze_generator.c b/src/maze_generator.c
new file mode 100644
index 0000000..3a2e3b2
--- /dev/null
+++ b/src/maze_generator.c
@@ -0,0 +1,113 @@
+#include <stdlib.h>
+#include "maze_generator.h"
+#include "utilities.h"
+#include "maze.h"
+
+static void remove_wall(int **graph, struct point a, struct point b)
+{
+    int diff_x = a.x - b.x;
+    int diff_y = a.y - b.y;
+    if (diff_y == 0)
+    {
+        if (diff_x == 1)
+            graph[b.x][b.y] &= 3;
+        else if (diff_x == -1)
+            graph[a.x][a.y] &= 3;
+    }
+    else if (diff_x == 0)
+    {
+        if (diff_y == 1)
+            graph[b.x][b.y] &= 5;
+        else if (diff_y == -1)
+            graph[a.x][a.y] &= 5;
+    }
+}
+
+static void generate_maze_graph(int **graph, int width, int height, struct point point)
+{
+    //I've been here.
+    graph[point.x][point.y] &= 6;
+    struct point points[4];
+    int index = 0;
+    //Possibilities:
+    if (point.x > 0)
+        points[index++] = relative_point(point, -1, 0);
+    if (point.x < width - 1)
+        points[index++] = relative_point(point, 1, 0);
+    if (point.y > 0)
+        points[index++] = relative_point(point, 0, -1);
+    if (point.y < height - 1)
+        points[index++] = relative_point(point, 0, 1);
+    //Shuffle:
+    shuffle(points, index, sizeof(struct point));
+    //Examine possibilities:
+    index--;
+    struct point new_point;
+    while (index >= 0)
+    {
+        new_point = points[index];
+        if ((graph[new_point.x][new_point.y] & 1) == 1)
+        {
+            //Remove wall:
+            remove_wall(graph, point, new_point);
+            //Go on:
+            generate_maze_graph(graph, width, height, new_point);
+        }
+        index--;
+    }
+}
+
+int generate_maze(struct maze *maze)
+{
+    if (!is_valid_maze_size(maze->width) || !is_valid_maze_size(maze->height))
+        return -1;
+    //Init graph:
+    int graph_width = ((maze->width - 2) + 1) / 2;
+    int graph_height = ((maze->height - 2) + 1) / 2;
+    char mem[sizeof_2d(graph_width, graph_height, sizeof(int))];
+    init2d((void **)mem, graph_width, graph_height, sizeof(int));
+    int **graph = (int **)mem;
+    for (int x = 0; x < graph_width; x++)
+        for (int y = 0; y < graph_height; y++)
+            graph[x][y] = 7;
+    //Generate graph:
+    struct point starting_point;
+    starting_point.x = 0;
+    starting_point.y = 0;
+    generate_maze_graph(graph, graph_width, graph_height, starting_point);
+    //Convert:
+    for (int x = 0; x < graph_width; x++)
+    {
+        for (int y = 0; y < graph_height; y++)
+        {
+            int real_x = (2 * x) + 1;
+            int real_y = (2 * y) + 1;
+            int is_last_x = x == maze->width - 2;
+            int is_last_y = y == maze->height - 2;
+            maze->map[real_x][real_y] = 0;
+            if (!is_last_x)
+                maze->map[real_x + 1][real_y] = (graph[x][y] & 4) == 4;
+            if (!is_last_y)
+                maze->map[real_x][real_y + 1] = (graph[x][y] & 2) == 2;
+            if (!(is_last_x || is_last_y))
+                maze->map[real_x + 1][real_y + 1] = 1;
+        }
+    }
+    //Set sides:
+    for (int x = 0; x < maze->width; x++)
+    {
+        maze->map[x][0] = 1;
+        maze->map[x][maze->height - 1] = 1;
+    }
+    for (int y = 0; y < maze->height; y++)
+    {
+        maze->map[0][y] = 1;
+        maze->map[maze->width - 1][y] = 1;
+    }
+    //Set start and end:
+    maze->starting_point.x = 1;
+    maze->starting_point.y = 1;
+    maze->end_point.x = maze->width - 2;
+    maze->end_point.y = maze->height - 2;
+    return 0;
+}
\ No newline at end of file
-- 
cgit v1.2.3