diff options
| -rw-r--r-- | main.c | 50 | ||||
| -rw-r--r-- | map.c | 4 | ||||
| -rw-r--r-- | map.h | 4 | ||||
| -rw-r--r-- | path.c | 6 | ||||
| -rw-r--r-- | priority_queue.c | 7 |
5 files changed, 46 insertions, 25 deletions
@@ -1,6 +1,7 @@ #include <curses.h> #include <signal.h> #include <stdlib.h> +#include <string.h> #include <stdio.h> #include <time.h> @@ -46,26 +47,39 @@ void init_ncurses(void) { initialize_colors(); } -int main(void) { +int main(int argc, char **argv) { + Position start_pos, end_pos; + size_t width, height; + Map map; + + size_t mwidth = 20; /* Maze width */ + size_t mheight = 10; /* Maze height */ + + char is_maze = 0; + if (argc == 1 || !strcmp(argv[1], "-m")) { + is_maze = 1; + if (argc == 4) { /* maze size as argv[2] and [3] */ + mwidth = atoi(argv[2]); + mheight = atoi(argv[3]); + } + map = rbt_maze_map(mwidth, mheight, (unsigned int) time(NULL)); + start_pos.x = 0; + start_pos.y = 0; + height = mheight * 2 - 1; + width = mwidth * 2 - 1; + end_pos.x = width - 1; + end_pos.y = height - 1; + } else { + map = file_plaintext_map(argv[1], &width, &height, &start_pos, &end_pos); + } signal(SIGINT, sigint_handler); init_ncurses(); - size_t mwidth = 20; /* Maze width */ - size_t mheight = 10; /* Maze height */ - Map map = rbt_maze_map(mwidth, mheight, (unsigned int) time(NULL)); - Position start_pos = {0, 0}; - Position end_pos = {mwidth*2-2, mheight*2-2}; - size_t height = mheight * 2 - 1; - size_t width = mwidth * 2 - 1; int offset_x = 0, offset_y = 0; - //size_t width, height; - //Position start_pos, end_pos; - //Map map = file_plaintext_map("maps/test", &width, &height, &start_pos, &end_pos); - //print_map_out(map, width, height); - //draw_map(map, width, height, offset_x, offset_y, start_pos, end_pos, NULL); - + draw_map(map, width, height, offset_x, offset_y, start_pos, end_pos, NULL, NULL); + char visited[height][width]; Path path = breadth_first_search_path_4dir(map, width, height, start_pos, end_pos, visited); @@ -78,9 +92,11 @@ int main(void) { case 'j': offset_y += 1; break; case 'k': offset_y -= 1; break; case 'n': - //FIXME: free it all before generating a new one - map = rbt_maze_map(mwidth, mheight, (unsigned int) time(NULL)); - path = breadth_first_search_path_4dir(map, width, height, start_pos, end_pos, visited); + if (is_maze) { + //FIXME: free it all before generating a new one + map = rbt_maze_map(mwidth, mheight, (unsigned int) time(NULL)); + path = breadth_first_search_path_4dir(map, width, height, start_pos, end_pos, visited); + } break; case 'q': endwin(); return 0; } @@ -22,7 +22,7 @@ Map empty_map(size_t width, size_t height) { return map; } -unsigned int neighbours(Position neighbour_array[], Position pos, size_t width, size_t height, \ +unsigned int neighbours_4dir(Position neighbour_array[], Position pos, size_t width, size_t height, \ char visited[height][width]) { size_t cur = 0; if (pos.x > 0 && !visited[pos.y][pos.x - 1]) { @@ -81,7 +81,7 @@ Map rbt_maze_map(size_t width, size_t height, unsigned int seed) { srand(seed); do { - int nc = neighbours(na, ps_peek(ps), width, height, visited); + int nc = neighbours_4dir(na, ps_peek(ps), width, height, visited); if (nc > 0) { Position next = na[rand() % nc]; Position prev = ps_peek(ps); @@ -9,8 +9,8 @@ /* Returns an empty map of given size */ Map empty_map(size_t width, size_t height); -/* Stores all the existing neighbours of pos in neighbour_array and returns their amount */ -unsigned int neighbours(Position neighbour_array[], Position pos, 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[], Position pos, size_t width, size_t height, \ char visited[height][width]); /* https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_depth-first_search @@ -27,11 +27,11 @@ Path breadth_first_search_path_4dir(Map map, size_t width, size_t height, Positi visited[cur.y][cur.x] = 1; if (cur.x == end.x && cur.y == end.y) { - break; + return path; /* Found path */ } Position na[4]; - unsigned int nc = neighbours(na, cur, width, height, visited); + unsigned int nc = neighbours_4dir(na, cur, width, height, visited); for (unsigned int i = 0; i < nc; i++) { /* The Russian constitution doesn't allow walking on walls */ @@ -42,7 +42,7 @@ Path breadth_first_search_path_4dir(Map map, size_t width, size_t height, Positi } } - return path; + return NULL; } /* FIXME: Rewrite this shit */ diff --git a/priority_queue.c b/priority_queue.c index c8bd8b0..472f5c3 100644 --- a/priority_queue.c +++ b/priority_queue.c @@ -12,6 +12,7 @@ PositionPQ *ppq_new(Position pos, size_t priority) { return ppq; } +/* FIXME: this is shitty */ void ppq_insert(PositionPQ **ppq, Position pos, size_t priority) { PositionPQ *start = *ppq; @@ -29,8 +30,12 @@ void ppq_insert(PositionPQ **ppq, Position pos, size_t priority) { PositionPQ *temp = *ppq; - while(temp->next != NULL && temp->next->priority <= priority) + while(temp->next != NULL && temp->next->priority <= priority) { + if (temp->pos.x == pos.x && temp->pos.y == pos.y && temp->priority <= priority) { + return; /* pos is already at the start of ppq with a fine priority */ + } temp = temp->next; + } n->next = temp->next; temp->next = n; |