From 528841328da0114981ee6e8c6dbdde72b64fb284 Mon Sep 17 00:00:00 2001 From: Kirill Petrashin Date: Sat, 14 Mar 2026 14:42:14 +0300 Subject: Fix stack + implement rbt_maze_map() --- Makefile | 8 ++++---- main.c | 6 +++--- map.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-- map.h | 6 +++++- stack.c | 14 ++++++++------ stack.h | 5 +++-- 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 #include #include +#include #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 #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_ */ -- cgit v1.2.3