aboutsummaryrefslogtreecommitdiff
path: root/mazerator.c
diff options
context:
space:
mode:
Diffstat (limited to 'mazerator.c')
-rw-r--r--mazerator.c275
1 files changed, 275 insertions, 0 deletions
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);
+ }
+ }
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-21 20:19:04 +0000