diff options
Diffstat (limited to 'src/maze_solver.c')
| -rw-r--r-- | src/maze_solver.c | 78 |
1 files changed, 78 insertions, 0 deletions
diff --git a/src/maze_solver.c b/src/maze_solver.c new file mode 100644 index 0000000..6286d24 --- /dev/null +++ b/src/maze_solver.c @@ -0,0 +1,78 @@ +#include "maze_solver.h" +#include <string.h> +#include "utilities.h" + +struct solver_data +{ + struct maze *maze; + struct point *first_point; + struct point *last_point; + int count; + //int temp[51][51]; + int **temp; +}; + +static void get_neighbours(struct point point, struct point *neighbours) +{ + neighbours[0].x = point.x + 1; + neighbours[0].y = point.y; + neighbours[1].x = point.x - 1; + neighbours[1].y = point.y; + neighbours[2].x = point.x; + neighbours[2].y = point.y + 1; + neighbours[3].x = point.x; + neighbours[3].y = point.y - 1; +} + +static int solve_maze_rec(struct solver_data *data, struct point point) +{ + if (data->first_point == NULL) + data->count++; + else + *(data->last_point++) = point; + + data->temp[point.x][point.y] = 1; + if (data->maze->end_point.x == point.x && data->maze->end_point.y == point.y) + { + if (data->first_point == NULL) + return data->count; + else + return (data->last_point - data->first_point); + } + struct point neighbours[4]; + get_neighbours(point, neighbours); + for (int i = 0; i < 4; i++) + { + if (neighbours[i].x >= 0 && + neighbours[i].y >= 0 && + neighbours[i].x < data->maze->width && + neighbours[i].y < data->maze->height && + data->maze->map[neighbours[i].x][neighbours[i].y] != 1 && + data->temp[neighbours[i].x][neighbours[i].y] != 1) + { + int value = solve_maze_rec(data, neighbours[i]); + if (value >= 0) + return value; + } + } + if (data->first_point == NULL) + data->count--; + else + data->last_point--; + return -1; +} + +int solve_maze(struct maze *maze, struct point point, struct point *path) +{ + struct solver_data solver_data; + solver_data.maze = maze; + solver_data.first_point = path; + solver_data.last_point = path; + solver_data.count = 0; + int length = sizeof_2d(maze->width, maze->height, sizeof(int)); + char mem[length]; + memset(mem, 0, length); + init2d((void **)mem, maze->width, maze->height, sizeof(int)); + solver_data.temp = (int **)mem; + return solve_maze_rec(&solver_data, point) - 1; +}
\ No newline at end of file |