Fix stack + implement rbt_maze_map()

6 files changed, 77 insertions, 18 deletions

diff --git a/Makefile b/Makefile
index a8d80e2..c1a92ea 100644
--- a/Makefile
+++ b/Makefile
@@ -1,11 +1,11 @@
 CC=gcc
 EXECUTABLE=astar
 
-astar: main.c map.c
-	$(CC) -Wall -Wpedantic -Wextra -Werror -O3 -o $(EXECUTABLE) map.c main.c -lncurses
+astar: main.c map.c stack.c config.h
+	$(CC) -Wall -Wpedantic -Wextra -Werror -O3 -o $(EXECUTABLE) map.c stack.c main.c -lncurses
 
-debug: main.c map.c 
-	$(CC) -Wall -g -o $(EXECUTABLE) map.c main.c -lncurses
+debug: main.c map.c stack.c config.h
+	$(CC) -Wall -g -o $(EXECUTABLE) map.c stack.c main.c -lncurses
 
 clean: 
 	rm ./$(EXECUTABLE)
diff --git a/main.c b/main.c
index 111c898..71e3b45 100644
--- a/main.c
+++ b/main.c
@@ -2,11 +2,11 @@
 #include <signal.h>
 #include <stdlib.h>
 #include <stdio.h>
+#include <time.h>
 #include "map.h"
 #include "structs.h"
 
 // So, TODO for now:
-// - Implement a stack
 // - Implement a maze algorithm to test my A* algorithm with
 // - Implement the A* algorithm
 
@@ -35,8 +35,8 @@ int main(void) {
     noecho();      // Don't echo characters
     initialize_colors();
 
-    Map map = rbt_maze_map(20, 10);
-    Position fake_player_position_to_pass_into_draw_map = {0, 0};
+    Map map = rbt_maze_map(20, 10, (unsigned int) time(NULL));
+    Position fake_player_position_to_pass_into_draw_map = {11, 21};
     draw_map(map, 20*2-1, 10*2-1, fake_player_position_to_pass_into_draw_map);
     getch();
 
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;
 }
diff --git a/map.h b/map.h
index aa40652..9c4a4fa 100644
--- a/map.h
+++ b/map.h
@@ -26,10 +26,14 @@ typedef MapTile** Map;
 // Returns an empty map of given size
 Map empty_map(size_t width, size_t height);
 
+// Stores all the existing neighbours of pos in neighbour_array and returns their amount
+unsigned int neighbours(Position neighbour_array[], Position pos, size_t width, size_t height, \
+        char visited[height][width]);
+
 // https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_depth-first_search
 // WARNING: width and height are not the width and height of the returned map!
 // TODO: formula for actual size
-Map rbt_maze_map(size_t width, size_t height);
+Map rbt_maze_map(size_t width, size_t height, unsigned int seed);
 
 // Draw the map. Bet you didn't expect that. 
 void draw_map(Map map, int width, int height, Position player_pos);
diff --git a/stack.c b/stack.c
index bcdfbd3..cf169c5 100644
--- a/stack.c
+++ b/stack.c
@@ -7,14 +7,16 @@ PositionStack ps_new(void) {
     return ps;
 }
 
-int ps_push(PositionStack ps, Position pos) {
-    ps.arr[ps.top] = pos;
-    ps.top += 1;
+int ps_push(PositionStack *ps, Position pos) {
+    //TODO: check for stack overflow
+    ps->arr[ps->top] = pos;
+    ps->top += 1;
+    return 0;
 }
 
-Position ps_pop(PositionStack ps) {
-    ps.top -= 1;
-    return ps.arr[ps.top];
+Position ps_pop(PositionStack *ps) {
+    ps->top -= 1;
+    return ps->arr[ps->top];
 }
 
 Position ps_peek(PositionStack ps) {
diff --git a/stack.h b/stack.h
index a83a135..68fdb78 100644
--- a/stack.h
+++ b/stack.h
@@ -1,6 +1,7 @@
 #ifndef STACK_H_
 #define STACK_H_
 
+#include <stddef.h>
 #include "structs.h"
 
 /* So, the implementation of the stack is array-based, for hyperspeed.
@@ -15,8 +16,8 @@ struct PositionStack_s {
 typedef struct PositionStack_s PositionStack;
 
 PositionStack ps_new(void); /* Returns an empty position stack */
-int ps_push(PositionStack ps, Position pos); /* Returns -1 if overflow */
-Position ps_pop(PositionStack ps);
+int ps_push(PositionStack *ps, Position pos); /* Returns -1 if overflow */
+Position ps_pop(PositionStack *ps);
 Position ps_peek(PositionStack ps);
 
 #endif /* STACK_H_ */