diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | src/grid.c | 55 | ||||
| -rw-r--r-- | src/grid.h | 59 | ||||
| -rw-r--r-- | src/maze.c | 145 | ||||
| -rw-r--r-- | src/maze.h | 28 | ||||
| -rw-r--r-- | src/mazerator.c | 118 | ||||
| -rw-r--r-- | src/position.c | 9 | ||||
| -rw-r--r-- | src/position.h | 13 | ||||
| -rw-r--r-- | src/position_stack.c | 7 | ||||
| -rw-r--r-- | src/position_stack.h | 12 | ||||
| -rw-r--r-- | src/utils.c | 54 | ||||
| -rw-r--r-- | src/utils.h | 22 |
12 files changed, 331 insertions, 192 deletions
@@ -1,2 +1,3 @@ build .vscode +.cache diff --git a/src/grid.c b/src/grid.c new file mode 100644 index 0000000..7248087 --- /dev/null +++ b/src/grid.c @@ -0,0 +1,55 @@ +#include "grid.h" +#include "utils.h" +#include <stdlib.h> + +Grid grid_create(unsigned int width, unsigned int height, char *fill) +{ + unsigned int mem_height = height * sizeof(char **); + unsigned int mem_width = width * sizeof(char *); + + Dimensions dimens = {.width = width, .height = height}; + + Grid grid = {.grid = malloc_s(mem_height), .dimens = dimens}; + + // Fill the grid + for (unsigned int y = 0; y < height; y++) + { + grid.grid[y] = malloc_s(mem_width); + + for (unsigned int x = 0; x < width; x++) + grid.grid[y][x] = fill; + } + + return grid; +} + +char *grid_get(Grid grid, Position pos) +{ + return grid.grid[pos.y][pos.x]; +} + +void grid_set(Grid grid, Position pos, char *value) +{ + grid.grid[pos.y][pos.x] = value; +} + +void grid_print(Grid grid) +{ + for (unsigned int y = 0; y < grid.dimens.height; y++) + { + for (unsigned int x = 0; x < grid.dimens.width; x++) + printf("%s", grid.grid[y][x]); + + printf("\n"); + } +} + +void grid_destroy(Grid grid) +{ + // Deallocate the memory of the grid + for (unsigned int y = 0; y < grid.dimens.height; y++) + free(grid.grid[y]); + + free(grid.grid); +} + diff --git a/src/grid.h b/src/grid.h new file mode 100644 index 0000000..65fa01a --- /dev/null +++ b/src/grid.h @@ -0,0 +1,59 @@ +#ifndef GRID_H +#define GRID_H + +#include "position.h" + +typedef struct Dimensions +{ + unsigned int width; + unsigned int height; +} Dimensions; + +typedef struct Grid +{ + char ***grid; + Dimensions dimens; +} Grid; + +/** + * Returns a grid. + * + * @param width The grid width + * @param height The grid height + * @param fill A string to fill the new grid with + */ +Grid grid_create(unsigned int width, unsigned int height, char *fill); + +/* + * Returns a value from a position in a grid. + * + * @param grid A grid + * @param pos A grid position + */ +char *grid_get(Grid grid, Position pos); + +/* + * Sets the value of a position in a grid. + * + * @param grid A grid + * @param pos A grid position + * @param value A new value + */ +void grid_set(Grid grid, Position pos, char *value); + +/** + * Prints a grid. + * + * @param grid A grid + */ +void grid_print(Grid grid); + +/** + * Destroys a grid. + * + * @param grid A grid + */ +void grid_destroy(Grid grid); + +#endif + @@ -1,124 +1,89 @@ #include "maze.h" +#include "grid.h" +#include "position.h" #include <stdio.h> #include <stdlib.h> #include <string.h> -/** - * Returns a filled grid. - * - * @param width The width of the new grid - * @param height The height of the new grid - * @param fill A string to fill the new grid with - */ -char ***create_grid(int width, int height, char *fill) +int is_pos_empty(Grid grid, Position pos) { - char ***grid; - - // Fill the grid - grid = malloc(height * sizeof(char **)); - for (int y = 0; y < height; y++) - { - grid[y] = malloc(width * sizeof(char *)); - - for (int x = 0; x < width; x++) - { - grid[y][x] = fill; - } - } - - return grid; + return strcmp(grid_get(grid, pos), " ") != 0; } -Maze maze_create(Dimensions dimens, char *wall) +void add_neighbour(Position neighbours[], uint8_t *neighbour_cnt, Position neighbour_pos) { - Maze maze; - - maze.dimens = dimens; - - Dimensions full_dimens = {.width = dimens.width * 2 + 1, - .height = dimens.height * 2 + 1}; + neighbours[*neighbour_cnt] = neighbour_pos; + (*neighbour_cnt)++; - maze.full_dimens = full_dimens; - - maze.grid = create_grid(full_dimens.width, full_dimens.height, wall); - - return maze; } -void maze_destroy(Maze *maze) +void get_neighbours(Grid grid, Position pos, Position neighbours[], uint8_t *neighbour_cnt) { - // Deallocate the memory of the maze's grid - for (int y = 0; y < maze->full_dimens.height; y++) + if (pos.y != 1) { - free(maze->grid[y]); - } - free(maze->grid); -} + Position pos_down = position_create(pos.x, pos.y - 2); -void get_neighbours(Maze *maze, Position pos, Position neighbours[3], int *neighbour_cnt) -{ - if (pos.y != 0 && strcmp(maze->grid[pos.y * 2 - 1][pos.x * 2 + 1], " ") != 0) - { - Position down_neighbour_pos = {.x = pos.x, .y = pos.y - 1}; - neighbours[*neighbour_cnt] = down_neighbour_pos; - (*neighbour_cnt)++; + if (is_pos_empty(grid, pos_down)) + add_neighbour(neighbours, neighbour_cnt, pos_down); } - if (pos.y != maze->dimens.height - 1 && - strcmp(maze->grid[(pos.y + 1) * 2 + 1][pos.x * 2 + 1], " ") != 0) + + if (pos.y != grid.dimens.height - 2) { - Position up_neighbour_pos = {.x = pos.x, .y = pos.y + 1}; - neighbours[*neighbour_cnt] = up_neighbour_pos; - (*neighbour_cnt)++; + Position pos_up = position_create(pos.x, pos.y + 2); + + if (is_pos_empty(grid, pos_up)) + add_neighbour(neighbours, neighbour_cnt, pos_up); } - if (pos.x != 0 && strcmp(maze->grid[pos.y * 2 + 1][pos.x * 2 - 1], " ") != 0) + + if (pos.x != 1) { - Position left_neighbour_pos = {.x = pos.x - 1, .y = pos.y}; - neighbours[*neighbour_cnt] = left_neighbour_pos; - (*neighbour_cnt)++; + Position pos_left = position_create(pos.x - 2, pos.y); + + if (is_pos_empty(grid, pos_left)) + add_neighbour(neighbours, neighbour_cnt, pos_left); } - if (pos.x != maze->dimens.width - 1 && - strcmp(maze->grid[pos.y * 2 + 1][(pos.x + 1) * 2 + 1], " ") != 0) + + if (pos.x != grid.dimens.width - 2) { - Position right_neighbour_pos = {.x = pos.x + 1, .y = pos.y}; - neighbours[*neighbour_cnt] = right_neighbour_pos; - (*neighbour_cnt)++; + Position pos_right = position_create(pos.x + 2, pos.y); + + if (is_pos_empty(grid, pos_right)) + add_neighbour(neighbours, neighbour_cnt, pos_right); } } -int is_whole_maze_visited(Maze *maze, int visited_pos_cnt) +unsigned int get_maze_size(Grid grid) { - if (visited_pos_cnt == (maze->dimens.height * maze->dimens.width) - 1) - { - return 1; - } + return ((grid.dimens.width - 1) / 2) * ((grid.dimens.height - 1) / 2); +} - return 0; +int is_whole_maze_visited(Grid grid, unsigned int visited_pos_cnt) +{ + return visited_pos_cnt == get_maze_size(grid) - 1; } -void maze_excavate(Maze *maze, Position start_pos) +void grid_to_maze(Grid grid, Position start_pos) { - PositionStack *path = pos_stack_create(maze->dimens.width * maze->dimens.height); + PositionStack *path = pos_stack_create(get_maze_size(grid)); pos_stack_push(path, start_pos); - int visited_pos_cnt = 0; + unsigned int visited_pos_cnt = 0; while (1) { Position pos = pos_stack_peek(path); - maze->grid[pos.y * 2 + 1][pos.x * 2 + 1] = " "; + grid_set(grid, pos, " "); - Position neighbours[3] = {}; - int neighbour_cnt = 0; + Position neighbours[3]; + uint8_t neighbour_cnt = 0; - get_neighbours(maze, pos, neighbours, &neighbour_cnt); + get_neighbours(grid, pos, neighbours, &neighbour_cnt); if (neighbour_cnt == 0) { - if (is_whole_maze_visited(maze, visited_pos_cnt)) - { + if (is_whole_maze_visited(grid, visited_pos_cnt)) break; - } // Go back a step pos_stack_pop(path); @@ -129,8 +94,15 @@ void maze_excavate(Maze *maze, Position start_pos) 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] = " "; + Position between_pos = position_create(pos.x, pos.y); + + if (next_pos.y != pos.y) + between_pos.y += next_pos.y > pos.y ? 1 : -1; + + if (next_pos.x != pos.x) + between_pos.x += next_pos.x > pos.x ? 1 : -1; + + grid_set(grid, between_pos, " "); pos_stack_push(path, next_pos); } @@ -138,14 +110,3 @@ void maze_excavate(Maze *maze, Position start_pos) pos_stack_destroy(path); } -void maze_print(Maze maze) -{ - for (int y = 0; y < maze.full_dimens.height; y++) - { - for (int x = 0; x < maze.full_dimens.width; x++) - { - printf("%s", maze.grid[y][x]); - } - printf("\n"); - } -} @@ -2,34 +2,14 @@ #define MAZE_H #include "position_stack.h" - -typedef struct Dimensions -{ - int width; - int height; -} Dimensions; - -typedef struct Maze -{ - char ***grid; - Dimensions dimens; - Dimensions full_dimens; -} Maze; - -Maze maze_create(Dimensions dimens, char *wall); - -void maze_destroy(Maze *maze); +#include "grid.h" /** - * Excavates a maze. - * - * This is what creates the actual maze. + * Creates a maze from a grid * - * @param maze The maze to excavate + * @param grid A grid * @param start_pos Start position */ -void maze_excavate(Maze *maze, Position start_pos); - -void maze_print(Maze maze); +void grid_to_maze(Grid grid, Position start_pos); #endif diff --git a/src/mazerator.c b/src/mazerator.c index d231173..95c6fb6 100644 --- a/src/mazerator.c +++ b/src/mazerator.c @@ -1,38 +1,19 @@ #include "maze.h" +#include "grid.h" +#include "position.h" #include "utils.h" #include <getopt.h> #include <stdio.h> #include <stdlib.h> -void validate_number_optarg(char *optarg, int c) +void optarg_error(char arg, char *error) { - unsigned int is_invalid = 0; - - size_t error_length = 40; - char *error = malloc(error_length + 1); - - if (!is_number(optarg)) - { - is_invalid = 1; - snprintf(error, error_length, "It must be a number"); - } - else if (atoi(optarg) < 1) - { - is_invalid = 1; - snprintf(error, error_length, "It must be greater than 0"); - } - - if (is_invalid == 1) - { - printf("Error: Invalid option argument for -%c. %s\n", c, error); - free(error); - exit(1); - } - - free(error); + printf("Error: Invalid option argument for -%c. %s\n", arg, error); + exit(EXIT_FAILURE); } -void validate_start_coords(int start_x, int start_y, int width, int height) +void validate_start_coords(unsigned int start_x, unsigned int start_y, unsigned int width, + unsigned int height) { char *error_format = "Error: The %s start coordinate is not allowed to be higher than the maze's %s\n"; @@ -40,17 +21,17 @@ void validate_start_coords(int start_x, int start_y, int width, int height) if (start_x > width) { printf(error_format, "x", "width"); - exit(1); + exit(EXIT_FAILURE); } if (start_y > height) { printf(error_format, "y", "height"); - exit(1); + exit(EXIT_FAILURE); } } -void get_seed(int *seed_dst) +void get_seed(unsigned int *seed_dst) { FILE *urandom = fopen("/dev/urandom", "r"); fread(seed_dst, sizeof(*seed_dst), 1, urandom); @@ -68,40 +49,60 @@ const struct option options[] = {{"width", required_argument, NULL, 'w'}, int main(int argc, char *argv[]) { - int maze_width = 40; - int maze_height = 20; - int start_x = 0; - int start_y = 0; + unsigned int maze_width = 40U; + unsigned int maze_height = 20U; + unsigned int start_x = 1U; + unsigned int start_y = 1U; + unsigned int *seed = NULL; + char *wall = "█"; - int seed = -1; - int c; - while ((c = getopt_long(argc, argv, "w:h:W:s:x:y:", options, NULL)) != -1) + int arg; + while ((arg = getopt_long(argc, argv, "w:h:W:s:x:y:", options, NULL)) != -1) { - switch (c) + char *err = NULL; + + switch (arg) { case 'w': - validate_number_optarg(optarg, c); - maze_width = atoi(optarg); + maze_width = str_to_uint(optarg, &err); + + if (err != NULL) + optarg_error(arg, err); + break; case 'h': - validate_number_optarg(optarg, c); - maze_height = atoi(optarg); + maze_height = str_to_uint(optarg, &err); + + if (err != NULL) + optarg_error(arg, err); + break; case 'x': - validate_number_optarg(optarg, c); - start_x = atoi(optarg); + start_x = str_to_uint(optarg, &err); + + if (err != NULL) + optarg_error(arg, err); + break; case 'y': - validate_number_optarg(optarg, c); - start_y = atoi(optarg); + start_y = str_to_uint(optarg, &err); + + if (err != NULL) + optarg_error(arg, err); + break; case 'W': wall = optarg; break; case 's': - validate_number_optarg(optarg, c); - seed = atoi(optarg); + seed = malloc_s(sizeof(unsigned int *)); + + *seed = str_to_uint(optarg, &err); + + if (err != NULL) + optarg_error(arg, err); + break; case 0: printf("Usage: %s [OPTION]...\n\n" @@ -109,9 +110,9 @@ int main(int argc, char *argv[]) " -w, --width WIDTH The width of the maze (Default: 40)\n" " -h, --heigth HEIGHT The heigth of the maze (Default: 20)\n" " -x, --start-x X The x coordinate for the start position " - "(Default: 0)\n" + "(Default: 1)\n" " -y, --start-y Y The y coordinate for the start position " - "(Default: 0)\n" + "(Default: 1)\n" " -W, --wall WALL Single character used as maze walls " "(Default: '█')\n" " -s, --seed SEED The randomization seed used for maze " @@ -127,22 +128,23 @@ int main(int argc, char *argv[]) validate_start_coords(start_x, start_y, maze_width, maze_height); - if (seed == -1) + if (seed == NULL) { - get_seed(&seed); + seed = malloc_s(sizeof(unsigned int *)); + get_seed(seed); } - srand(seed); + srand(*seed); - Dimensions dimens = {.width = maze_width, .height = maze_height}; + free(seed); - Maze maze = maze_create(dimens, wall); + Position start_pos = position_create(start_x, start_y); - Position start_pos = {.x = start_x, .y = start_y}; + Grid grid = grid_create(maze_width * 2 + 1, maze_width * 2 + 1, wall); - maze_excavate(&maze, start_pos); + grid_to_maze(grid, start_pos); - maze_print(maze); + grid_print(grid); - maze_destroy(&maze); + grid_destroy(grid); } diff --git a/src/position.c b/src/position.c new file mode 100644 index 0000000..937edd5 --- /dev/null +++ b/src/position.c @@ -0,0 +1,9 @@ +#include "position.h" + +Position position_create(unsigned int x, unsigned int y) +{ + Position pos = {.x = x, .y = y}; + + return pos; +} + diff --git a/src/position.h b/src/position.h new file mode 100644 index 0000000..d1bc9eb --- /dev/null +++ b/src/position.h @@ -0,0 +1,13 @@ +#ifndef POSITION_H +#define POSITION_H + +typedef struct Position +{ + unsigned int x; + unsigned int y; +} Position; + +Position position_create(unsigned int x, unsigned int y); + +#endif + diff --git a/src/position_stack.c b/src/position_stack.c index 846d933..597ed5a 100644 --- a/src/position_stack.c +++ b/src/position_stack.c @@ -1,4 +1,5 @@ #include "position_stack.h" +#include "utils.h" #include <stdio.h> #include <stdlib.h> @@ -19,13 +20,13 @@ void stack_error(int err) } // Creates a new stack -PositionStack *pos_stack_create(int capacity) +PositionStack *pos_stack_create(unsigned int capacity) { - PositionStack *pos_stack = malloc(sizeof(PositionStack)); + PositionStack *pos_stack = malloc_s(sizeof(PositionStack)); pos_stack->capacity = capacity; pos_stack->top = -1; - pos_stack->items = malloc(sizeof(Position) * capacity); + pos_stack->items = malloc_s(sizeof(Position) * capacity); return pos_stack; } diff --git a/src/position_stack.h b/src/position_stack.h index 83fb98c..674da23 100644 --- a/src/position_stack.h +++ b/src/position_stack.h @@ -1,23 +1,19 @@ #ifndef POSITION_STACK_H #define POSITION_STACK_H +#include "position.h" + #define STACK_ERR_OVERFLOW 0xFFF01 #define STACK_ERR_UNDERFLOW 0xFFF02 -typedef struct Position -{ - int x; - int y; -} Position; - typedef struct PositionStack { - int capacity; + unsigned int capacity; int top; Position *items; } PositionStack; -PositionStack *pos_stack_create(int capacity); +PositionStack *pos_stack_create(unsigned int capacity); void pos_stack_destroy(PositionStack *pos_stack); diff --git a/src/utils.c b/src/utils.c index 93f7c53..69ce55d 100644 --- a/src/utils.c +++ b/src/utils.c @@ -1,17 +1,57 @@ #include "utils.h" #include <ctype.h> #include <string.h> +#include <stdlib.h> +#include <limits.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++) - { + unsigned int length = strlen(str); + + for (unsigned int c = 0; c < length; c++) if (!isdigit(str[c])) return 0; - } + return 1; } + + +void *malloc_s(unsigned long amount) +{ + void *memory = malloc(amount); + + if (memory == NULL) + { + printf("Error: Memory allocation failed"); + exit(EXIT_FAILURE); + } + + return memory; +} + +unsigned int str_to_uint(char *str, char **err) +{ + if (*str == '-') + { + *err = "Not greater than 0"; + return 0; + } + + char *str_waste; + unsigned long num = strtoul(str, &str_waste, 10); + + if (strlen(str_waste) != 0) + { + *err = "Not a number"; + return 0; + } + + if (num > (unsigned long)UINT_MAX) + { + *err = "Too large"; + return 0; + } + + return (unsigned int)num; +} + diff --git a/src/utils.h b/src/utils.h index a1b69e1..049e583 100644 --- a/src/utils.h +++ b/src/utils.h @@ -1,6 +1,28 @@ #ifndef UTILS_H #define UTILS_H +/** + * Returns whether or not a string is a number. + * + * @param str A string + */ int is_number(char *str); +/** + * Safely allocates memory to the heap. + * + * @param amount The amount of memory to allocate + * @returns The allocated memory. + */ +void *malloc_s(unsigned long amount); + +/** + * Converts a string to a unsigned integer. + * + * @param str A string + * @param err A error destination + * @returns A unsigned integer. + */ +unsigned int str_to_uint(char *str, char **err); + #endif |