From 528841328da0114981ee6e8c6dbdde72b64fb284 Mon Sep 17 00:00:00 2001
From: Kirill Petrashin <kirill8201@yandex.ru>
Date: Sat, 14 Mar 2026 14:42:14 +0300
Subject: Fix stack + implement rbt_maze_map()

---
 map.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 54 insertions(+), 2 deletions(-)

(limited to 'map.c')

diff --git a/map.c b/map.c
index 21023f0..3a8ef8f 100644
--- a/map.c
+++ b/map.c
@@ -19,7 +19,35 @@ Map empty_map(size_t width, size_t height) {
     return map;
 }
 
-Map rbt_maze_map(size_t width, size_t height) {
+unsigned int neighbours(Position neighbour_array[], Position pos, size_t width, size_t height, \
+        char visited[height][width]) {
+    //TODO: add thing for when visited is NULL
+    size_t cur = 0;
+    if (pos.x > 0 && !visited[pos.y][pos.x - 1]) {
+        neighbour_array[cur].x = pos.x - 1;
+        neighbour_array[cur].y = pos.y;
+        cur += 1;
+    }
+    if (pos.x + 1 < width && !visited[pos.y][pos.x + 1]) {
+        neighbour_array[cur].x = pos.x + 1;
+        neighbour_array[cur].y = pos.y;
+        cur += 1;
+    }
+    if (pos.y > 0 && !visited[pos.y - 1][pos.x]) {
+        neighbour_array[cur].x = pos.x;
+        neighbour_array[cur].y = pos.y - 1;
+        cur += 1;
+    }
+    if (pos.y + 1 < height && !visited[pos.y + 1][pos.x]) {
+        neighbour_array[cur].x = pos.x;
+        neighbour_array[cur].y = pos.y + 1;
+        cur += 1;
+    }
+
+    return cur;
+}
+
+Map rbt_maze_map(size_t width, size_t height, unsigned int seed) {
     size_t map_width  = width * 2 - 1,
            map_height = height * 2 - 1;
     Map map = empty_map(map_width, map_height);
@@ -37,7 +65,31 @@ Map rbt_maze_map(size_t width, size_t height) {
         }
     }
 
-    //TODO: Draw the rest of the owl
+    Position beginning_cell = {width - 1, height - 1};
+
+    char visited[height][width]; // 1 if visited, 0 if not
+    memset(visited, 0, sizeof(char) * width * height);
+
+    PositionStack ps = ps_new();
+    ps_push(&ps, beginning_cell);
+    visited[beginning_cell.y][beginning_cell.x] = 1;
+
+    Position na[4];
+
+    srand(seed);
+
+    do {
+        int nc = neighbours(na, ps_peek(ps), width, height, visited);
+        if (nc > 0) {
+            Position next = na[rand() % nc];
+            Position prev = ps_peek(ps);
+            ps_push(&ps, next);
+            visited[next.y][next.x] = 1;
+            map[(next.y * 2 + prev.y * 2) / 2][(next.x * 2 + prev.x * 2) / 2] = EMPTY;
+        } else {
+            (void)ps_pop(&ps);
+        }
+    } while (ps_peek(ps).x != beginning_cell.x || ps_peek(ps).y != beginning_cell.y) ;
 
     return map;
 }
-- 
cgit v1.2.3