add mazerator

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);
+		}
+	}
+}