diff options
| -rw-r--r-- | .gitignore | 3 | ||||
| -rw-r--r-- | mazerator.c | 345 | ||||
| -rw-r--r-- | stack.c | 32 | ||||
| -rw-r--r-- | stack.h | 2 |
4 files changed, 207 insertions, 175 deletions
@@ -1 +1,2 @@ -mazerator
\ No newline at end of file +mazerator +.vscode
\ No newline at end of file diff --git a/mazerator.c b/mazerator.c index f15c4ae..8ebc7d3 100644 --- a/mazerator.c +++ b/mazerator.c @@ -6,38 +6,27 @@ #include <string.h> #include <unistd.h> -// Error handling -void err(int id) +/** + * 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) { - 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); + return ((posY) << 8) | posX; } -// Get 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 00001000 -// X: 15 00001111 -// Will become: -// 0000100000001111 -int get_maze_pos(int posY, int posX) { return ((posY) << 8) | posX; } - -// Get y and x coordinates from a position in the maze -// -// This is achived by using bitwise operations -// -// >> is the bitwise right shift operator and will shift bits to the right -// & is the bitwise and operator and is used to get only specific bits +/** + * Returns y and x coordinates from a position in the maze. + */ int get_maze_coords(int pos, int *y, int *x) { *y = pos >> 8; @@ -45,8 +34,9 @@ int get_maze_coords(int pos, int *y, int *x) return 1; } -// Find out if a string is a number by running it through -// isdigit() char-by-char +/** + * Returns whether or not a string is a number. + */ int is_number(char *str) { size_t len = strlen(str); @@ -58,21 +48,138 @@ int is_number(char *str) 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 + */ +void excavate_maze(char ***maze, int maze_height, int maze_width) +{ + struct stack *path = create_stack(maze_width * maze_height); + + stack_push(path, 0); + + 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"); + } +} + +const struct option options[] = { + {"width", required_argument, NULL, 'w'}, + {"heigth", required_argument, NULL, 'h'}, + {"wall", required_argument, NULL, 'W'}, + {"seed", required_argument, NULL, 's'}, + {"help", no_argument, NULL, 0}, + {NULL, 0, NULL, 0}}; + int main(int argc, char *argv[]) { int maze_width = 40; - int maze_heigth = 20; + int maze_height = 20; char *wall = "█"; - int seed = 0; - - static struct option options[] = { - /* NAME ARGUMENT FLAG SHORTNAME */ - {"width", required_argument, NULL, 'w'}, - {"heigth", required_argument, NULL, 'h'}, - {"wall", required_argument, NULL, 'W'}, - {"seed", required_argument, NULL, 's'}, - {"help", no_argument, NULL, 0}, - {NULL, 0, NULL, 0}}; + int seed = -1; int c; while ((c = getopt_long(argc, argv, "w:h:W:s:", options, NULL)) != -1) @@ -80,159 +187,67 @@ int main(int argc, char *argv[]) switch (c) { case 'w': + if (!is_number(optarg) || atoi(optarg) < 1 || atoi(optarg) > 255) + { + printf("Invalid option argument for -%c!\n", c); + exit(1); + } + + maze_width = atoi(optarg); + break; case 'h': - // Set heigth or width - if (is_number(optarg) && atoi(optarg) >= 1 && atoi(optarg) <= 255) - switch (c) - { - case 'h': - maze_heigth = atoi(optarg); - case 'w': - maze_width = atoi(optarg); - } - else + if (!is_number(optarg) || atoi(optarg) < 1 || atoi(optarg) > 255) { printf("Invalid option argument for -%c!\n", c); exit(1); } + + maze_height = atoi(optarg); break; case 'W': - // Set the wall wall = optarg; break; case 's': - // Set the seed - if (is_number(optarg)) - { - seed = atoi(optarg); - break; - } - else + if (!is_number(optarg)) { printf("Invalid option argument for -s/--seed!\n"); exit(1); } + + seed = atoi(optarg); + break; case 0: - // Help printf( - "Usage: mazerator [--help] [-W wall] [-s seed] [-w width] [-h heigth]\n\n\ -OPTIONS\n\ - --width -w The width of the maze. (1-255). Default: 40\n\ - --heigth -h The heigth of the maze. (1-255). Default: 20\n\ - --wall -W Single character used as maze walls. Default: '█'\n\ - --seed -s The randomization seed used for maze generation. (Any number). Default is to read /dev/urandom\n\ - --help Displays usage information\n\ -"); + "Usage: %s [OPTION]...\n\n" + "Options:\n" + " -w, --width WIDTH The width of the maze. (1-255) (Default: 40)\n" + " -h, --heigth HEIGHT The heigth of the maze. (1-255) (Default: 20)\n" + " -w, --wall WALL Single character used as maze walls (Default: '█')\n" + " -s, --seed SEED The randomization seed used for maze generation. (Any number)\n" + " --help Displays usage information\n", + argv[0]); exit(0); case '?': - printf("\nTry 'mazerator --help' for more information\n"); + printf("\nTry '%s --help' for more information\n", argv[0]); exit(1); } } - int maze[maze_heigth][maze_width]; - char *maze_visual[maze_heigth * 2 + 1][maze_width * 2 + 1]; - struct stack *path = new_stack(maze_width * maze_heigth); - - // Prepares seed value for randr() - // Get's a seed from /dev/urandom if not already set - if (seed == 0) + if (seed == -1) { - printf("What"); FILE *f = fopen("/dev/urandom", "r"); fread(&seed, sizeof(seed), 1, f); fclose(f); } - srand(seed); - // Prepares the maze grids - // Fills the maze with zeroes indicating that none of the grid squares have - // been visited - // - // Fills the visual maze with walls - for (int y = 0; y < sizeof(maze) / sizeof(maze[0]); y++) - { - for (int x = 0; x < sizeof(maze[0]) / sizeof(maze[0][0]); x++) - { - maze[y][x] = 0; - } - } - for (int y = 0; y < sizeof(maze_visual) / sizeof(maze_visual[0]); y++) - { - for (int x = 0; x < sizeof(maze_visual[0]) / sizeof(maze_visual[0][0]); - x++) - { - maze_visual[y][x] = wall; - } - } + srand(seed); - // Set the start value (0, 0) and begin the algoritm loop - stack_push(path, 0); - int cnt = 0; - while (1) - { - int pos = stack_peek(path); - int posY, posX; - get_maze_coords(pos, &posY, &posX); + int full_maze_height = maze_height * 2 + 1; + int full_maze_width = maze_width * 2 + 1; - // Set the currently visited grid square to 1 indicating that it has been - // visited and excavate the visual maze - maze[posY][posX] = 1; - maze_visual[posY * 2 + 1][posX * 2 + 1] = " "; + char ***maze = create_maze(full_maze_height, full_maze_width, wall); - // Find out available next positions to go to - int neighbours[3]; - int i = 0; - if (posY != 0 && maze[posY - 1][posX] == 0) - { - neighbours[i] = get_maze_pos(posY - 1, posX); - i++; - } - if (posY != maze_heigth - 1 && maze[posY + 1][posX] == 0) - { - neighbours[i] = get_maze_pos(posY + 1, posX); - i++; - } - if (posX != 0 && maze[posY][posX - 1] == 0) - { - neighbours[i] = get_maze_pos(posY, posX - 1); - i++; - } - if (posX != maze_width - 1 && maze[posY][posX + 1] == 0) - { - neighbours[i] = get_maze_pos(posY, posX + 1); - i++; - } + excavate_maze(maze, maze_height, maze_width); - switch (i) - { - case 0: - // No available next positions - if (cnt == (maze_heigth * maze_width) - 1) - { - for (int y = 0; y < sizeof(maze_visual) / sizeof(maze_visual[0]); y++) - { - for (int x = 0; - x < sizeof(maze_visual[0]) / sizeof(maze_visual[0][0]); x++) - { - printf("%s", maze_visual[y][x]); - } - printf("\n"); - } - exit(0); - } - stack_pop(path); - break; - default: - // Available next positions - // Choose a random one and go there - cnt++; - int next = neighbours[rand() % i]; - int next_y, next_x; - get_maze_coords(next, &next_y, &next_x); - maze_visual[posY * 2 - (posY - next_y) + 1] - [posX * 2 - (posX - next_x) + 1] = " "; - stack_push(path, next); - } - } + print_maze(maze, full_maze_height, full_maze_width); } @@ -1,8 +1,24 @@ #include "stack.h" +#include <stdio.h> #include <stdlib.h> -// Create a new stack -struct stack *new_stack(int capacity) +// 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; @@ -11,31 +27,31 @@ struct stack *new_stack(int capacity) return pt; } -// Add a new item to a stack +// 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) - err(0); + stack_error(0); // Add an element and increase the top index pt->items[++pt->top] = x; } -// Get the topmost item of a stack +// Returns the topmost item of a stack int stack_peek(struct stack *pt) { // Check if the stack is empty if (pt->top == -1) - err(1); + stack_error(1); return pt->items[pt->top]; } -// Remove the topmost item of a stack +// Deletes the topmost item of a stack int stack_pop(struct stack *pt) { // Check for a stack underflow if (pt->top == -1) - err(0); + 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 @@ -8,7 +8,7 @@ struct stack int *items; }; -struct stack *new_stack(int capacity); +struct stack *create_stack(int capacity); void stack_push(struct stack *pt, int x); |