diff options
| -rw-r--r-- | main.c | 51 | ||||
| -rw-r--r-- | map.c | 13 | ||||
| -rw-r--r-- | map.h | 6 | ||||
| -rw-r--r-- | path.c | 42 | ||||
| -rw-r--r-- | path.h | 9 | ||||
| -rw-r--r-- | stack.c | 2 |
6 files changed, 94 insertions, 29 deletions
@@ -14,14 +14,14 @@ #include "path.h" /* So, TODO for now: - - Keybinds to increase map size + - Generate an image?? - Allow maps to have costs - Implement greedy-best-first algorithm (4 and 8 dir) - Implement Dijkstra algorithm (4 and 8 dir) - Implement the A* algorithm (4 and 8 dir) - MORE MAPS FOR THE MAP PEOPLE - Implement controls (to change maps, move start/goal, etc.) - - Clean up unused `#include`s + - Clean up unused `#include`s - mouse controls to edit map, drag start and end around */ void sigint_handler(int sig) { @@ -37,7 +37,7 @@ void initialize_colors(void) { init_pair(EMPTY_COLOR, COLOR_BLACK, -1); init_pair(VISITED_COLOR, COLOR_GREEN, COLOR_GREEN); init_pair(GOAL_COLOR, -1, COLOR_RED); - init_pair(WALL_COLOR, COLOR_WHITE, COLOR_WHITE); + init_pair(WALL_COLOR, COLOR_WHITE, COLOR_WHITE); init_pair(START_COLOR, -1, COLOR_RED); init_pair(PATH_COLOR, COLOR_RED, COLOR_RED); init_pair(FRONTIER_COLOR, COLOR_BLUE, COLOR_BLUE); @@ -65,7 +65,7 @@ int main(int argc, char **argv) { int dirs = 8; srand(time(NULL)); - + /* Handle args. * Currently supported: * -a to animate the pathfinding (get input after each step) @@ -74,6 +74,7 @@ int main(int argc, char **argv) { * -4 for four directions * -8 for eight directions */ /* TODO: Argument to choose the algorithm */ + /* TODO: Argument to set seed */ int opt; while ((opt = getopt(argc, argv, ":am:f:48")) != -1) { switch (opt) { @@ -81,7 +82,7 @@ int main(int argc, char **argv) { case 'm': if (sscanf(optarg, "%zux%zu", &mwidth, &mheight) != 2) error("Wrong maze size string in argument\n"); is_maze = 1; - map = rbt_maze_map(mwidth, mheight, (unsigned int) time(NULL)); + map = rbt_maze_map(mwidth, mheight, rand()); start_pos.x = 0; start_pos.y = 0; height = mheight * 2 - 1; @@ -122,7 +123,7 @@ int main(int argc, char **argv) { draw_map(map, width, height, offset_x, offset_y, start_pos, end_pos, NULL, NULL, NULL, NULL); //print_map_out(map, width, height); - char visited[height][width]; + char **visited = visited_new(width, height); Path path = NULL; path = breadth_first_search_path(dirs, map, width, height, start_pos, end_pos, visited, anim); @@ -130,13 +131,39 @@ int main(int argc, char **argv) { draw_map(map, width, height, offset_x, offset_y, start_pos, end_pos, NULL, path, visited, NULL); char c = getch(); switch (c) { - case 'h': offset_x -= 2; break; - case 'l': offset_x += 2; break; - case 'j': offset_y += 1; break; - case 'k': offset_y -= 1; break; + /* FIXME: scroll the view not the content or whatever */ + case 'h': offset_x += 2; break; + case 'l': offset_x -= 2; break; + case 'j': offset_y -= 1; break; + case 'k': offset_y += 1; break; case 'a': anim = !anim; break; - case 'n': - if (is_maze) { + case 'y': + case 'o': + case 'u': + case 'i': + if(is_maze) { + switch (c) { + case 'y': mwidth -= 1; break; + case 'o': mwidth += 1; break; + case 'u': mheight += 1; break; + case 'i': mheight -= 1; break; + } + map_free(map, height); + visited_free(visited, height); + path_free(path, height); + + height = mheight * 2 - 1; + width = mwidth * 2 - 1; + end_pos.x = width - 1; + end_pos.y = height - 1; + + map = rbt_maze_map(mwidth, mheight, rand()); + visited = visited_new(width, height); + path = breadth_first_search_path(dirs, map, width, height, start_pos, end_pos, visited, anim); + } + break; + case 'n': + if (is_maze) { map_free(map, height); map = rbt_maze_map(mwidth, mheight, rand()); path_free(path, height); @@ -27,7 +27,7 @@ Map empty_map(size_t width, size_t height) { /* When we allow maps to have costs, these two neighbours functions will have to use the instead of COST_* defines */ /* TODO: maybe merge them, add `dirs` parameter, like we do in path.c? */ unsigned int neighbours_4dir(Position neighbour_array[4], size_t cost_array[4], Position pos, size_t width, size_t height, \ - char visited[height][width]) { + char **visited) { size_t cur = 0; if (pos.x > 0 && !visited[pos.y][pos.x - 1]) { neighbour_array[cur].x = pos.x - 1; @@ -58,7 +58,7 @@ unsigned int neighbours_4dir(Position neighbour_array[4], size_t cost_array[4], } unsigned int neighbours_8dir(Position neighbour_array[8], size_t cost_array[8], Position pos, size_t width, size_t height, \ - char visited[height][width]) { + char **visited) { size_t cur = 0; if (pos.x > 0 && !visited[pos.y][pos.x - 1]) { neighbour_array[cur].x = pos.x - 1; @@ -133,8 +133,8 @@ Map rbt_maze_map(size_t width, size_t height, unsigned int seed) { Position beginning_cell = {width - 1, height - 1}; - char visited[height][width]; /* 1 if visited, 0 if not */ - memset(visited, 0, sizeof(char) * width * height); + char **visited = visited_new(width, height); + visited_clear(visited, width, height); PositionStack ps = ps_new(); if (ps_push(&ps, beginning_cell) == -1) error("Is the STACK_SIZE zero?"); @@ -157,6 +157,7 @@ Map rbt_maze_map(size_t width, size_t height, unsigned int seed) { } } while (ps_peek(ps).x != beginning_cell.x || ps_peek(ps).y != beginning_cell.y) ; + visited_free(visited, height); return map; } @@ -208,7 +209,7 @@ Map file_plaintext_map(char *filename, size_t *width, size_t *height, Position * /* TODO: so many fucking arguments lmao. Break it down into several functions? */ /* TODO: draw the start and goal with no background, allowing us to see the frontier/path/whatever's underneath. I think attr_get() will be useful */ -void draw_map(Map map, size_t width, size_t height, int offset_x, int offset_y, Position start, Position goal, Position *cursor, Path path, char visited[height][width], PositionPQ *frontier) { +void draw_map(Map map, size_t width, size_t height, int offset_x, int offset_y, Position start, Position goal, Position *cursor, Path path, char **visited, PositionPQ *frontier) { /* I think it flickers less when we do that */ wnoutrefresh(stdscr); @@ -223,6 +224,8 @@ void draw_map(Map map, size_t width, size_t height, int offset_x, int offset_y, mvaddch(i + offset_y, DRAW_MAP_OFFSET_X - 1 + offset_x - 2, ' '); mvaddch(i + offset_y, DRAW_MAP_OFFSET_X + width * 2 + offset_x + 2, ' '); mvaddch(i + offset_y, DRAW_MAP_OFFSET_X + width * 2 + 1 + offset_x + 2, ' '); + mvaddch(i + offset_y, DRAW_MAP_OFFSET_X + width * 2 + 2 + offset_x + 2, ' '); + mvaddch(i + offset_y, DRAW_MAP_OFFSET_X + width * 2 + 3 + offset_x + 2, ' '); } /* Draw the borders */ @@ -11,12 +11,12 @@ Map empty_map(size_t width, size_t height); /* Stores all the existing 4dir neighbours of pos in neighbour_array and returns their amount */ unsigned int neighbours_4dir(Position neighbour_array[4], size_t cost_array[4], Position pos, size_t width, size_t height, \ - char visited[height][width]); + char **visited); /* Stores all the existing 8dir neighbours of pos in neighbour_array and returns their amount. * Additionaly stores costs into cost_array if it's not NULL. * The cost of goint orthogonally is 10, diagonaly is 14 (sqrt(2) * 10) */ unsigned int neighbours_8dir(Position neighbour_array[8], size_t cost_array[8], Position pos, size_t width, size_t height, \ - char visited[height][width]); + char **visited); /* https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_depth-first_search * WARNING: width and height are not the width and height of the returned map! @@ -41,7 +41,7 @@ Map file_plaintext_map(char *filename, size_t *width, size_t *height, Position * /* Draw the map. Bet you didn't expect that. * path could be NULL to draw a map with no path. So can cursor, frontier and visited */ -void draw_map(Map map, size_t width, size_t height, int offset_x, int offset_y, Position start, Position goal, Position *cursor, Path path, char visited[height][width], PositionPQ *frontier); +void draw_map(Map map, size_t width, size_t height, int offset_x, int offset_y, Position start, Position goal, Position *cursor, Path path, char **visited, PositionPQ *frontier); /* Frees all the memory reserved for the map */ void map_free(Map map, size_t height); @@ -10,7 +10,7 @@ #include "error.h" /* TODO: somehow get offsets back to main */ -int anim(Map map, size_t width, size_t height, Position start, Position end, Position *cur, char visited[height][width], PositionPQ *frontier) { +int anim(Map map, size_t width, size_t height, Position start, Position end, Position *cur, char **visited, PositionPQ *frontier) { static int offset_y = 0, offset_x = 0; while (1) { draw_map(map, width, height, offset_x, offset_y, start, end, cur, NULL, visited, frontier); @@ -27,9 +27,9 @@ int anim(Map map, size_t width, size_t height, Position start, Position end, Pos return 0; } /* BLOODY FUCK IT WORKS */ -Path breadth_first_search_path(int dirs, Map map, size_t width, size_t height, Position start, Position end, char visited[height][width], char should_anim) { +Path breadth_first_search_path(int dirs, Map map, size_t width, size_t height, Position start, Position end, char **visited, char should_anim) { /* The function to use to find neighbours */ - unsigned int (*neighbours)(Position[], size_t[], Position, size_t, size_t, char[height][width]) = NULL; + unsigned int (*neighbours)(Position[], size_t[], Position, size_t, size_t, char**) = NULL; switch (dirs) { case 4: neighbours = &neighbours_4dir; break; case 8: neighbours = &neighbours_8dir; break; @@ -47,7 +47,7 @@ Path breadth_first_search_path(int dirs, Map map, size_t width, size_t height, P PositionPQ *frontier = ppq_new(start, 0); - memset(visited, 0, height * width * sizeof(char)); + visited_clear(visited, width, height); while (frontier != NULL) { Position cur = ppq_pop(&frontier); @@ -91,10 +91,10 @@ Path breadth_first_search_path(int dirs, Map map, size_t width, size_t height, P } /* FIXME: THIS IS NOT YET DIJKSTRA!!! don't use for now (WIP) */ -Path dijkstra_path(int dirs, Map map, size_t width, size_t height, Position start, Position end, char visited[height][width], char should_anim) { +Path dijkstra_path(int dirs, Map map, size_t width, size_t height, Position start, Position end, char **visited, char should_anim) { return NULL; /* The function to use to find neighbours */ - unsigned int (*neighbours)(Position[], size_t[], Position, size_t, size_t, char[height][width]) = NULL; + unsigned int (*neighbours)(Position[], size_t[], Position, size_t, size_t, char**) = NULL; switch (dirs) { case 4: neighbours = &neighbours_4dir; break; case 8: neighbours = &neighbours_8dir; break; @@ -112,7 +112,7 @@ Path dijkstra_path(int dirs, Map map, size_t width, size_t height, Position star PositionPQ *frontier = ppq_new(start, 0); - memset(visited, 0, height * width * sizeof(char)); + visited_clear(visited, width, height); while (frontier != NULL) { Position cur = ppq_pop(&frontier); @@ -168,3 +168,31 @@ void path_free(Path path, size_t height) { } free(path); } + +char **visited_new(size_t width, size_t height) { + char **visited = malloc(sizeof(char*) * height); + if (visited == NULL) return NULL; + + for (size_t row = 0; row < height; row++) { + visited[row] = malloc(sizeof(char) * width); + if (visited[row] == NULL) return NULL; + memset(visited[row], 0x00, width*sizeof(char)); + } + + return visited; +} + +void visited_clear(char **visited, size_t width, size_t height) { + for (size_t row = 0; row < height; row++) { + memset(visited[row], 0x00, sizeof(char) * width); + } +} + +void visited_free(char **visited, size_t height) { + if (visited == NULL) return; + for (size_t row = 0; row < height; row++) { + free(visited[row]); + } + free(visited); + return; +} @@ -5,11 +5,16 @@ #include "map.h" /* dirs can be 4 or 8 to disallow or allow diagonal movement */ -Path breadth_first_search_path(int dirs, Map map, size_t width, size_t height, Position start, Position end, char visited[height][width], char should_anim); -Path dijkstra_path(int dirs, Map map, size_t width, size_t height, Position start, Position end, char visited[height][width], char should_anim); +Path breadth_first_search_path(int dirs, Map map, size_t width, size_t height, Position start, Position end, char **visited, char should_anim); +Path dijkstra_path(int dirs, Map map, size_t width, size_t height, Position start, Position end, char **visited, char should_anim); size_t manhattan_distance(Position a, Position b); void path_free(Path path, size_t height); +/* Helper funcs for the visited array */ +char **visited_new(size_t width, size_t height); +void visited_clear(char **visited, size_t width, size_t height); +void visited_free(char **visited, size_t height); + #endif /* ASTAR_H_ */ @@ -18,11 +18,13 @@ int ps_push(PositionStack *ps, Position pos) { } Position ps_pop(PositionStack *ps) { + if (ps->top == 0) error("Stack underflow\n"); ps->top -= 1; return ps->arr[ps->top]; } Position ps_peek(PositionStack ps) { + if (ps.top == 0) error("Stack underflow\n"); return ps.arr[ps.top - 1]; } |