diff options
| -rw-r--r-- | Makefile | 11 | ||||
| -rw-r--r-- | mazerator.c | 275 |
2 files changed, 286 insertions, 0 deletions
diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..4b9bb98 --- /dev/null +++ b/Makefile @@ -0,0 +1,11 @@ +TARGET=mazerator +CC=gcc +CFLAGS=-Wall + +all: $(TARGET) + +$(TARGET): $(TARGET).c + $(CC) $(CFLAGS) $(TARGET).c -o $(TARGET) + +clean: + $(RM) $(TARGET) diff --git a/mazerator.c b/mazerator.c new file mode 100644 index 0000000..25a7f7d --- /dev/null +++ b/mazerator.c @@ -0,0 +1,275 @@ +#include <stdio.h> +#include <stdlib.h> +#include <getopt.h> +#include <unistd.h> +#include <ctype.h> +#include <string.h> + +// The fundementals for the maze-generation algoritm +// A stack data-structure +struct stack +{ + int max_size; + int top; + int *items; +}; + +// Create a new stack +struct stack* new_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; +} + +// Check if a stack is empty +int stack_is_empty(struct stack *pt) +{ + return pt->top == -1; +} + +// Check if a stack is full +int stack_is_full(struct stack *pt) +{ + return pt->top == pt->max_size - 1; +} + +// Add 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 (stack_is_full(pt)) + { + printf("Overflow error\nProgram terminated\n"); + exit(EXIT_FAILURE); + } + + // Add an element and increase the top index + pt->items[++pt->top] = x; +} + +// Get the topmost item of a stack +int stack_peek(struct stack *pt) +{ + // Check if the stack is empty + if (!stack_is_empty(pt)) + return pt->items[pt->top]; + else + exit(EXIT_FAILURE); +} + +// Remove the topmost item of a stack +int stack_pop(struct stack *pt) +{ + // Check for a stack underflow + if (stack_is_empty(pt)) + { + printf("Underflow error\nProgram terminated\n"); + exit(EXIT_FAILURE); + } + + // Decrease the stack size by 1 and (optionally) return the popped element + return pt->items[pt->top--]; +} + +// 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 +int get_maze_coords(int pos, int *y, int *x) +{ + *y = pos >> 8; + *x = pos & 255; + return 1; +} + +// Find out if a string is a number by running it through +// isdigit() char-by-char +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; +} + +// Where the magic happends +int main(int argc, char *argv[]) +{ + int maze_width = 40; + int maze_heigth = 20; + char *wall = "█"; + int seed; + + 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 c; + while((c = getopt_long(argc, argv, "w:h:W:s:", options, NULL)) != -1) { + switch(c){ + case 'w': + // Set Width + if(is_number(optarg) && atoi(optarg) >= 1 && atoi(optarg) <= 255) + maze_width = atoi(optarg); + else{ + printf("Invalid option argument for -w/--width!\n"); + exit(1); + } + break; + case 'h': + // Set heigth + if(is_number(optarg) && atoi(optarg) >= 1 && atoi(optarg) <= 255) + maze_heigth = atoi(optarg); + else{ + printf("Invalid option argument for -h/--heigth!\n"); + exit(1); + } + break; + case 'W': + // Set the wall + wall = optarg; + break; + case 's': + // Set the seed + if(is_number(optarg)){ + seed = atoi(optarg); + break; + } + else{ + printf("Invalid option argument for -s/--seed!\n"); + exit(1); + } + 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\ +"); + exit(0); + case '?': + printf("\nTry 'mazerator --help' for more information\n"); + 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){ + 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; + } + } + + // 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); + + // 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] = " "; + + // 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++; + } + + 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); + } + } +} |