diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | maze.c | 131 | ||||
| -rw-r--r-- | maze.h | 24 | ||||
| -rw-r--r-- | mazerator.c | 191 | ||||
| -rw-r--r-- | position_stack.c | 69 | ||||
| -rw-r--r-- | position_stack.h | 28 | ||||
| -rw-r--r-- | stack.c | 57 | ||||
| -rw-r--r-- | stack.h | 19 | ||||
| -rw-r--r-- | utils.c | 17 | ||||
| -rw-r--r-- | utils.h | 6 |
10 files changed, 294 insertions, 250 deletions
@@ -1,5 +1,5 @@ TARGET=mazerator -SRCS=$(TARGET).c stack.c +SRCS=$(TARGET).c maze.c position_stack.c utils.c CC=gcc CFLAGS=-Wall CFLAGS_DEBUG=-fdiagnostics-color=always -g @@ -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 @@ -0,0 +1,24 @@ +#ifndef MAZE_H +#define MAZE_H + +#include "position_stack.h" + +struct MazeSize +{ + int width; + int height; +}; + +struct Maze +{ + char ***grid; + struct MazeSize size; +}; + +struct Maze maze_create(struct MazeSize size, char *wall); + +void maze_excavate(struct Maze maze, struct Position start_pos); + +void maze_print(char ***maze, int width, int height); + +#endif
\ No newline at end of file diff --git a/mazerator.c b/mazerator.c index 46ac9fc..33c47ce 100644 --- a/mazerator.c +++ b/mazerator.c @@ -1,176 +1,12 @@ -#include "stack.h" -#include <ctype.h> +#include "maze.h" +#include "utils.h" #include <getopt.h> #include <stdio.h> #include <stdlib.h> -#include <string.h> -#include <unistd.h> - -/** - * Returns a position in the maze from coordinates y and x. - * - * This is achieved by concatenating the binary values of the two variables. - * - * For example: - * - * Y: 8 (0b00001000) - * X: 15 (0b00001111) - * - * Will become: - * 0b0000100000001111 - */ -int get_maze_pos(int posY, int posX) -{ - return ((posY) << 8) | posX; -} - -/** - * Returns y and x coordinates from a position in the maze. - */ -int get_maze_coords(int pos, int *y, int *x) -{ - *y = pos >> 8; - *x = pos & 255; - return 1; -} - -/** - * Returns whether or not a string is a number. - */ -int is_number(char *str) -{ - size_t len = strlen(str); - for (int c = 0; c < len; c++) - { - if (!isdigit(str[c])) - return 0; - } - return 1; -} - -/** - * Returns a maze filled with walls. - * - * Arguments: - * - height: The height of the new maze - * - width: The width of the new maze - * - wall: The wall to fill the new maze with - */ -char ***create_maze(int height, int width, 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; -} - -/** - * Excavates a maze. - * - * This is what creates the actual maze. - * - * Arguments: - * - maze: The maze to excavate - * - maze_height: The height of the maze - * - maze_width: The width of the maze - * - start_x: X coordinate to start on - * - start_y Y coordinate to start on - */ -void excavate_maze(char ***maze, int maze_height, int maze_width, int start_x, int start_y) -{ - struct stack *path = create_stack(maze_width * maze_height); - - stack_push(path, get_maze_pos(start_y, start_x)); - - int visited_pos_cnt = 0; - while (1) - { - int pos = stack_peek(path); - int posY, posX; - get_maze_coords(pos, &posY, &posX); - - // Set the currently visited grid square to 1 indicating that it has been - // visited and excavate the visual maze - maze[posY * 2 + 1][posX * 2 + 1] = " "; - - // Find out available next positions to go to - int neighbours[3]; - int neighbour_cnt = 0; - - if (posY != 0 && strcmp(maze[posY * 2 - 1][posX * 2 + 1], " ") != 0) - { - neighbours[neighbour_cnt] = get_maze_pos(posY - 1, posX); - neighbour_cnt++; - } - if (posY != maze_height - 1 && strcmp(maze[(posY + 1) * 2 + 1][posX * 2 + 1], " ") != 0) - { - neighbours[neighbour_cnt] = get_maze_pos(posY + 1, posX); - neighbour_cnt++; - } - if (posX != 0 && strcmp(maze[posY * 2 + 1][posX * 2 - 1], " ") != 0) - { - neighbours[neighbour_cnt] = get_maze_pos(posY, posX - 1); - neighbour_cnt++; - } - if (posX != maze_width - 1 && strcmp(maze[posY * 2 + 1][(posX + 1) * 2 + 1], " ") != 0) - { - neighbours[neighbour_cnt] = get_maze_pos(posY, posX + 1); - neighbour_cnt++; - } - - if (neighbour_cnt == 0) - { - if (visited_pos_cnt == (maze_height * maze_width) - 1) - { - // The whole maze have been visited - break; - } - - // Go back a step - stack_pop(path); - continue; - } - - visited_pos_cnt++; - - int next_pos = neighbours[rand() % neighbour_cnt]; - - int next_pos_y, next_pos_x; - get_maze_coords(next_pos, &next_pos_y, &next_pos_x); - - maze[posY * 2 - (posY - next_pos_y) + 1] - [posX * 2 - (posX - next_pos_x) + 1] = " "; - - stack_push(path, next_pos); - } -} - -void print_maze(char ***maze, int height, int width) -{ - for (int y = 0; y < height; y++) - { - for (int x = 0; x < width; x++) - { - printf("%s", maze[y][x]); - } - printf("\n"); - } -} void validate_number_optarg(char *optarg, int c) { - char *base_error = malloc(39 * sizeof(char)); + char *base_error = malloc((38 + 1) * sizeof(char)); sprintf(base_error, "Error: Invalid option argument for -%c.", c); if (!is_number(optarg)) @@ -203,6 +39,13 @@ void validate_start_coords(int start_x, int start_y, int width, int height) } } +void get_seed(int *seed_dst) +{ + FILE *urandom = fopen("/dev/urandom", "r"); + fread(seed_dst, sizeof(*seed_dst), 1, urandom); + fclose(urandom); +} + const struct option options[] = { {"width", required_argument, NULL, 'w'}, {"heigth", required_argument, NULL, 'h'}, @@ -273,9 +116,7 @@ int main(int argc, char *argv[]) if (seed == -1) { - FILE *f = fopen("/dev/urandom", "r"); - fread(&seed, sizeof(seed), 1, f); - fclose(f); + get_seed(&seed); } srand(seed); @@ -283,9 +124,13 @@ int main(int argc, char *argv[]) int full_maze_height = maze_height * 2 + 1; int full_maze_width = maze_width * 2 + 1; - char ***maze = create_maze(full_maze_height, full_maze_width, wall); + struct MazeSize maze_size = {.width = maze_width, .height = maze_height}; + + struct Maze maze = maze_create(maze_size, wall); + + struct Position start_pos = {.x = start_x, .y = start_y}; - excavate_maze(maze, maze_height, maze_width, start_x, start_y); + maze_excavate(maze, start_pos); - print_maze(maze, full_maze_height, full_maze_width); + maze_print(maze.grid, full_maze_width, full_maze_height); } diff --git a/position_stack.c b/position_stack.c new file mode 100644 index 0000000..3d546b8 --- /dev/null +++ b/position_stack.c @@ -0,0 +1,69 @@ +#include "position_stack.h" +#include <stdio.h> +#include <stdlib.h> + +// Error handler for stack errors +void stack_error(int err) +{ + switch (err) + { + case STACK_ERR_OVERFLOW: + printf("Error: Stack overflow\nBe kind and report this problem."); + break; + case STACK_ERR_UNDERFLOW: + printf("Error: Stack underflow\nBe kind and report this problem."); + break; + } + + exit(1); +} + +// Creates a new stack +struct PositionStack *create_pos_stack(int capacity) +{ + struct PositionStack *stack_pt = malloc(sizeof(struct PositionStack)); + + stack_pt->max_size = capacity; + stack_pt->top = -1; + stack_pt->items = malloc(sizeof(struct Position) * capacity); + + return stack_pt; +} + +// Adds a new item to a stack +void pos_stack_push(struct PositionStack *stack_pt, struct Position pos) +{ + // Avoid a overflow by checking if the stack is full + if (stack_pt->top == stack_pt->max_size - 1) + { + stack_error(STACK_ERR_OVERFLOW); + } + + // Add an element and increase the top index + stack_pt->items[++stack_pt->top] = pos; +} + +// Returns the topmost item of a stack +struct Position pos_stack_peek(struct PositionStack *stack_pt) +{ + // Avoid a underflow by checking if the stack is empty + if (stack_pt->top == -1) + { + stack_error(STACK_ERR_UNDERFLOW); + } + + return stack_pt->items[stack_pt->top]; +} + +// Deletes the topmost item of a stack +struct Position pos_stack_pop(struct PositionStack *stack_pt) +{ + // Avoid a underflow by checking if the stack is empty + if (stack_pt->top == -1) + { + stack_error(STACK_ERR_UNDERFLOW); + } + + // Decrease the stack size by 1 and return the popped element + return stack_pt->items[stack_pt->top--]; +}
\ No newline at end of file diff --git a/position_stack.h b/position_stack.h new file mode 100644 index 0000000..fe93e8c --- /dev/null +++ b/position_stack.h @@ -0,0 +1,28 @@ +#ifndef POSITION_STACK_H +#define POSITION_STACK_H + +#define STACK_ERR_OVERFLOW 0xFFF01 +#define STACK_ERR_UNDERFLOW 0xFFF02 + +struct Position +{ + int x; + int y; +}; + +struct PositionStack +{ + int max_size; + int top; + struct Position *items; +}; + +struct PositionStack *create_pos_stack(int capacity); + +void pos_stack_push(struct PositionStack *stack_pt, struct Position pos); + +struct Position pos_stack_peek(struct PositionStack *stack_pt); + +struct Position pos_stack_pop(struct PositionStack *stack_pt); + +#endif
\ No newline at end of file diff --git a/stack.c b/stack.c deleted file mode 100644 index de5807c..0000000 --- a/stack.c +++ /dev/null @@ -1,57 +0,0 @@ -#include "stack.h" -#include <stdio.h> -#include <stdlib.h> - -// Error handler for stack errors -void stack_error(int id) -{ - switch (id) - { - case 0: - printf("Error: Stack overflow\nBe kind and report this problem."); - break; - case 1: - printf("Error: Stack underflow\nBe kind and report this problem."); - break; - } - exit(1); -} - -// Creates a new stack -struct stack *create_stack(int capacity) -{ - struct stack *pt = (struct stack *)malloc(sizeof(struct stack)); - pt->max_size = capacity; - pt->top = -1; - pt->items = (int *)malloc(sizeof(int) * capacity); - return pt; -} - -// Adds a new item to a stack -void stack_push(struct stack *pt, int x) -{ - // Avoid a overflow by checking if the stack is full - if (pt->top == pt->max_size - 1) - stack_error(0); - // Add an element and increase the top index - pt->items[++pt->top] = x; -} - -// Returns the topmost item of a stack -int stack_peek(struct stack *pt) -{ - // Check if the stack is empty - if (pt->top == -1) - stack_error(1); - return pt->items[pt->top]; -} - -// Deletes the topmost item of a stack -int stack_pop(struct stack *pt) -{ - // Check for a stack underflow - if (pt->top == -1) - stack_error(0); - // Decrease the stack size by 1 and (optionally) return the popped element - return pt->items[pt->top--]; -}
\ No newline at end of file diff --git a/stack.h b/stack.h deleted file mode 100644 index 7f259fe..0000000 --- a/stack.h +++ /dev/null @@ -1,19 +0,0 @@ -#ifndef STACK_H -#define STACK_H - -struct stack -{ - int max_size; - int top; - int *items; -}; - -struct stack *create_stack(int capacity); - -void stack_push(struct stack *pt, int x); - -int stack_peek(struct stack *pt); - -int stack_pop(struct stack *pt); - -#endif
\ No newline at end of file @@ -0,0 +1,17 @@ +#include "utils.h" +#include <ctype.h> +#include <string.h> + +/** + * Returns whether or not a string is a number. + */ +int is_number(char *str) +{ + size_t len = strlen(str); + for (int c = 0; c < len; c++) + { + if (!isdigit(str[c])) + return 0; + } + return 1; +}
\ No newline at end of file @@ -0,0 +1,6 @@ +#ifndef UTILS_H +#define UTILS_H + +int is_number(char *str); + +#endif
\ No newline at end of file |