diff options
Diffstat (limited to 'src/maze.c')
| -rw-r--r-- | src/maze.c | 145 |
1 files changed, 53 insertions, 92 deletions
@@ -1,124 +1,89 @@ #include "maze.h" +#include "grid.h" +#include "position.h" #include <stdio.h> #include <stdlib.h> #include <string.h> -/** - * Returns a filled grid. - * - * @param width The width of the new grid - * @param height The height of the new grid - * @param fill A string to fill the new grid with - */ -char ***create_grid(int width, int height, char *fill) +int is_pos_empty(Grid grid, Position pos) { - char ***grid; - - // Fill the grid - grid = malloc(height * sizeof(char **)); - for (int y = 0; y < height; y++) - { - grid[y] = malloc(width * sizeof(char *)); - - for (int x = 0; x < width; x++) - { - grid[y][x] = fill; - } - } - - return grid; + return strcmp(grid_get(grid, pos), " ") != 0; } -Maze maze_create(Dimensions dimens, char *wall) +void add_neighbour(Position neighbours[], uint8_t *neighbour_cnt, Position neighbour_pos) { - Maze maze; - - maze.dimens = dimens; - - Dimensions full_dimens = {.width = dimens.width * 2 + 1, - .height = dimens.height * 2 + 1}; + neighbours[*neighbour_cnt] = neighbour_pos; + (*neighbour_cnt)++; - maze.full_dimens = full_dimens; - - maze.grid = create_grid(full_dimens.width, full_dimens.height, wall); - - return maze; } -void maze_destroy(Maze *maze) +void get_neighbours(Grid grid, Position pos, Position neighbours[], uint8_t *neighbour_cnt) { - // Deallocate the memory of the maze's grid - for (int y = 0; y < maze->full_dimens.height; y++) + if (pos.y != 1) { - free(maze->grid[y]); - } - free(maze->grid); -} + Position pos_down = position_create(pos.x, pos.y - 2); -void get_neighbours(Maze *maze, Position pos, Position neighbours[3], int *neighbour_cnt) -{ - if (pos.y != 0 && strcmp(maze->grid[pos.y * 2 - 1][pos.x * 2 + 1], " ") != 0) - { - Position down_neighbour_pos = {.x = pos.x, .y = pos.y - 1}; - neighbours[*neighbour_cnt] = down_neighbour_pos; - (*neighbour_cnt)++; + if (is_pos_empty(grid, pos_down)) + add_neighbour(neighbours, neighbour_cnt, pos_down); } - if (pos.y != maze->dimens.height - 1 && - strcmp(maze->grid[(pos.y + 1) * 2 + 1][pos.x * 2 + 1], " ") != 0) + + if (pos.y != grid.dimens.height - 2) { - Position up_neighbour_pos = {.x = pos.x, .y = pos.y + 1}; - neighbours[*neighbour_cnt] = up_neighbour_pos; - (*neighbour_cnt)++; + Position pos_up = position_create(pos.x, pos.y + 2); + + if (is_pos_empty(grid, pos_up)) + add_neighbour(neighbours, neighbour_cnt, pos_up); } - if (pos.x != 0 && strcmp(maze->grid[pos.y * 2 + 1][pos.x * 2 - 1], " ") != 0) + + if (pos.x != 1) { - Position left_neighbour_pos = {.x = pos.x - 1, .y = pos.y}; - neighbours[*neighbour_cnt] = left_neighbour_pos; - (*neighbour_cnt)++; + Position pos_left = position_create(pos.x - 2, pos.y); + + if (is_pos_empty(grid, pos_left)) + add_neighbour(neighbours, neighbour_cnt, pos_left); } - if (pos.x != maze->dimens.width - 1 && - strcmp(maze->grid[pos.y * 2 + 1][(pos.x + 1) * 2 + 1], " ") != 0) + + if (pos.x != grid.dimens.width - 2) { - Position right_neighbour_pos = {.x = pos.x + 1, .y = pos.y}; - neighbours[*neighbour_cnt] = right_neighbour_pos; - (*neighbour_cnt)++; + Position pos_right = position_create(pos.x + 2, pos.y); + + if (is_pos_empty(grid, pos_right)) + add_neighbour(neighbours, neighbour_cnt, pos_right); } } -int is_whole_maze_visited(Maze *maze, int visited_pos_cnt) +unsigned int get_maze_size(Grid grid) { - if (visited_pos_cnt == (maze->dimens.height * maze->dimens.width) - 1) - { - return 1; - } + return ((grid.dimens.width - 1) / 2) * ((grid.dimens.height - 1) / 2); +} - return 0; +int is_whole_maze_visited(Grid grid, unsigned int visited_pos_cnt) +{ + return visited_pos_cnt == get_maze_size(grid) - 1; } -void maze_excavate(Maze *maze, Position start_pos) +void grid_to_maze(Grid grid, Position start_pos) { - PositionStack *path = pos_stack_create(maze->dimens.width * maze->dimens.height); + PositionStack *path = pos_stack_create(get_maze_size(grid)); pos_stack_push(path, start_pos); - int visited_pos_cnt = 0; + unsigned int visited_pos_cnt = 0; while (1) { Position pos = pos_stack_peek(path); - maze->grid[pos.y * 2 + 1][pos.x * 2 + 1] = " "; + grid_set(grid, pos, " "); - Position neighbours[3] = {}; - int neighbour_cnt = 0; + Position neighbours[3]; + uint8_t neighbour_cnt = 0; - get_neighbours(maze, pos, neighbours, &neighbour_cnt); + get_neighbours(grid, pos, neighbours, &neighbour_cnt); if (neighbour_cnt == 0) { - if (is_whole_maze_visited(maze, visited_pos_cnt)) - { + if (is_whole_maze_visited(grid, visited_pos_cnt)) break; - } // Go back a step pos_stack_pop(path); @@ -129,8 +94,15 @@ void maze_excavate(Maze *maze, Position start_pos) 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] = " "; + Position between_pos = position_create(pos.x, pos.y); + + if (next_pos.y != pos.y) + between_pos.y += next_pos.y > pos.y ? 1 : -1; + + if (next_pos.x != pos.x) + between_pos.x += next_pos.x > pos.x ? 1 : -1; + + grid_set(grid, between_pos, " "); pos_stack_push(path, next_pos); } @@ -138,14 +110,3 @@ void maze_excavate(Maze *maze, Position start_pos) pos_stack_destroy(path); } -void maze_print(Maze maze) -{ - for (int y = 0; y < maze.full_dimens.height; y++) - { - for (int x = 0; x < maze.full_dimens.width; x++) - { - printf("%s", maze.grid[y][x]); - } - printf("\n"); - } -} |