diff options
Diffstat (limited to 'maze.c')
| -rw-r--r-- | maze.c | 131 |
1 files changed, 131 insertions, 0 deletions
@@ -0,0 +1,131 @@ +#include "maze.h" +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +/** + * Returns a filled maze grid. + * + * Arguments: + * - width: The width of the new maze + * - height: The height of the new maze + * - wall: The wall to fill the new maze with + */ +char ***create_maze_grid(int width, int height, 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; +} + +struct Maze maze_create(struct MazeSize size, char *wall) +{ + struct Maze new_maze; + new_maze.grid = create_maze_grid(size.width * 2 + 1, size.height * 2 + 1, wall); + new_maze.size = size; + + return new_maze; +} + +void get_neighbours(struct Maze maze, struct Position pos, struct Position neighbours[3], int *neighbour_cnt) +{ + if (pos.y != 0 && strcmp(maze.grid[pos.y * 2 - 1][pos.x * 2 + 1], " ") != 0) + { + struct Position down_neighbour_pos = {.x = pos.x, .y = pos.y - 1}; + neighbours[*neighbour_cnt] = down_neighbour_pos; + (*neighbour_cnt)++; + } + if (pos.y != maze.size.height - 1 && strcmp(maze.grid[(pos.y + 1) * 2 + 1][pos.x * 2 + 1], " ") != 0) + { + struct Position up_neighbour_pos = {.x = pos.x, .y = pos.y + 1}; + neighbours[*neighbour_cnt] = up_neighbour_pos; + (*neighbour_cnt)++; + } + if (pos.x != 0 && strcmp(maze.grid[pos.y * 2 + 1][pos.x * 2 - 1], " ") != 0) + { + struct Position left_neighbour_pos = {.x = pos.x - 1, .y = pos.y}; + neighbours[*neighbour_cnt] = left_neighbour_pos; + (*neighbour_cnt)++; + } + if (pos.x != maze.size.width - 1 && strcmp(maze.grid[pos.y * 2 + 1][(pos.x + 1) * 2 + 1], " ") != 0) + { + struct Position right_neighbour_pos = {.x = pos.x + 1, .y = pos.y}; + neighbours[*neighbour_cnt] = right_neighbour_pos; + (*neighbour_cnt)++; + } +} + +/** + * Excavates a maze. + * + * This is what creates the actual maze. + * + * Arguments: + * - maze: The maze to excavate + * - start_pos: Start position + */ +void maze_excavate(struct Maze maze, struct Position start_pos) +{ + struct PositionStack *path = create_pos_stack(maze.size.width * maze.size.height); + + pos_stack_push(path, start_pos); + + int visited_pos_cnt = 0; + while (1) + { + struct Position pos = pos_stack_peek(path); + + maze.grid[pos.y * 2 + 1][pos.x * 2 + 1] = " "; + + struct Position neighbours[3] = {}; + int neighbour_cnt = 0; + + get_neighbours(maze, pos, neighbours, &neighbour_cnt); + + if (neighbour_cnt == 0) + { + if (visited_pos_cnt == (maze.size.height * maze.size.width) - 1) + { + // The whole maze have been visited + break; + } + + // Go back a step + pos_stack_pop(path); + continue; + } + + visited_pos_cnt++; + + struct 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] = " "; + + pos_stack_push(path, next_pos); + } +} + +void maze_print(char ***maze, int width, int height) +{ + for (int y = 0; y < height; y++) + { + for (int x = 0; x < width; x++) + { + printf("%s", maze[y][x]); + } + printf("\n"); + } +}
\ No newline at end of file |