diff options
Diffstat (limited to 'src/maze_generator.c')
| -rw-r--r-- | src/maze_generator.c | 113 |
1 files changed, 113 insertions, 0 deletions
diff --git a/src/maze_generator.c b/src/maze_generator.c new file mode 100644 index 0000000..3a2e3b2 --- /dev/null +++ b/src/maze_generator.c @@ -0,0 +1,113 @@ +#include <stdlib.h> +#include "maze_generator.h" +#include "utilities.h" +#include "maze.h" + +static void remove_wall(int **graph, struct point a, struct point b) +{ + int diff_x = a.x - b.x; + int diff_y = a.y - b.y; + if (diff_y == 0) + { + if (diff_x == 1) + graph[b.x][b.y] &= 3; + else if (diff_x == -1) + graph[a.x][a.y] &= 3; + } + else if (diff_x == 0) + { + if (diff_y == 1) + graph[b.x][b.y] &= 5; + else if (diff_y == -1) + graph[a.x][a.y] &= 5; + } +} + +static void generate_maze_graph(int **graph, int width, int height, struct point point) +{ + //I've been here. + graph[point.x][point.y] &= 6; + struct point points[4]; + int index = 0; + //Possibilities: + if (point.x > 0) + points[index++] = relative_point(point, -1, 0); + if (point.x < width - 1) + points[index++] = relative_point(point, 1, 0); + if (point.y > 0) + points[index++] = relative_point(point, 0, -1); + if (point.y < height - 1) + points[index++] = relative_point(point, 0, 1); + //Shuffle: + shuffle(points, index, sizeof(struct point)); + //Examine possibilities: + index--; + struct point new_point; + while (index >= 0) + { + new_point = points[index]; + if ((graph[new_point.x][new_point.y] & 1) == 1) + { + //Remove wall: + remove_wall(graph, point, new_point); + //Go on: + generate_maze_graph(graph, width, height, new_point); + } + index--; + } +} + +int generate_maze(struct maze *maze) +{ + if (!is_valid_maze_size(maze->width) || !is_valid_maze_size(maze->height)) + return -1; + //Init graph: + int graph_width = ((maze->width - 2) + 1) / 2; + int graph_height = ((maze->height - 2) + 1) / 2; + char mem[sizeof_2d(graph_width, graph_height, sizeof(int))]; + init2d((void **)mem, graph_width, graph_height, sizeof(int)); + int **graph = (int **)mem; + for (int x = 0; x < graph_width; x++) + for (int y = 0; y < graph_height; y++) + graph[x][y] = 7; + //Generate graph: + struct point starting_point; + starting_point.x = 0; + starting_point.y = 0; + generate_maze_graph(graph, graph_width, graph_height, starting_point); + //Convert: + for (int x = 0; x < graph_width; x++) + { + for (int y = 0; y < graph_height; y++) + { + int real_x = (2 * x) + 1; + int real_y = (2 * y) + 1; + int is_last_x = x == maze->width - 2; + int is_last_y = y == maze->height - 2; + maze->map[real_x][real_y] = 0; + if (!is_last_x) + maze->map[real_x + 1][real_y] = (graph[x][y] & 4) == 4; + if (!is_last_y) + maze->map[real_x][real_y + 1] = (graph[x][y] & 2) == 2; + if (!(is_last_x || is_last_y)) + maze->map[real_x + 1][real_y + 1] = 1; + } + } + //Set sides: + for (int x = 0; x < maze->width; x++) + { + maze->map[x][0] = 1; + maze->map[x][maze->height - 1] = 1; + } + for (int y = 0; y < maze->height; y++) + { + maze->map[0][y] = 1; + maze->map[maze->width - 1][y] = 1; + } + //Set start and end: + maze->starting_point.x = 1; + maze->starting_point.y = 1; + maze->end_point.x = maze->width - 2; + maze->end_point.y = maze->height - 2; + return 0; +}
\ No newline at end of file |