diff options
| -rw-r--r-- | config.h | 2 | ||||
| -rw-r--r-- | main.c | 11 | ||||
| -rw-r--r-- | map.c | 75 | ||||
| -rw-r--r-- | map.h | 9 | ||||
| -rw-r--r-- | maps/diagonal | 22 | ||||
| -rw-r--r-- | path.c | 59 | ||||
| -rw-r--r-- | path.h | 3 | ||||
| -rw-r--r-- | priority_queue.c | 17 | ||||
| -rw-r--r-- | priority_queue.h | 2 | ||||
| -rw-r--r-- | structs.h | 2 |
10 files changed, 185 insertions, 17 deletions
@@ -10,6 +10,8 @@ #define WALL_CHAR '#' #define START_CHAR_1 'S' #define START_CHAR_2 'T' +#define CURSOR_CHAR_1 '<' +#define CURSOR_CHAR_2 '>' #define DRAW_MAP_OFFSET_X 2 #define DRAW_MAP_OFFSET_Y 1 @@ -37,6 +37,8 @@ void initialize_colors(void) { 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); + init_pair(CURSOR_COLOR, -1, COLOR_RED); } void init_ncurses(void) { @@ -78,13 +80,14 @@ int main(int argc, char **argv) { int offset_x = 0, offset_y = 0; - draw_map(map, width, height, offset_x, offset_y, start_pos, end_pos, NULL, NULL); + 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]; - Path path = breadth_first_search_path_4dir(map, width, height, start_pos, end_pos, visited); + Path path = breadth_first_search_path_8dir(map, width, height, start_pos, end_pos, visited, 1); while (1) { - draw_map(map, width, height, offset_x, offset_y, start_pos, end_pos, path, visited); + 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; @@ -95,7 +98,7 @@ int main(int argc, char **argv) { 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); + path = breadth_first_search_path_8dir(map, width, height, start_pos, end_pos, visited, 1); } break; case 'q': endwin(); return 0; @@ -8,6 +8,7 @@ #include "stack.h" #include "error.h" #include "path.h" +#include "priority_queue.h" Map empty_map(size_t width, size_t height) { Map map = malloc(sizeof(MapTile*) * height); @@ -22,6 +23,7 @@ Map empty_map(size_t width, size_t height) { return map; } +/* Honestly, what a shitty fucking way to implement this */ unsigned int neighbours_4dir(Position neighbour_array[], Position pos, size_t width, size_t height, \ char visited[height][width]) { size_t cur = 0; @@ -49,6 +51,54 @@ unsigned int neighbours_4dir(Position neighbour_array[], Position pos, size_t wi return cur; } +unsigned int neighbours_8dir(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]) { + neighbour_array[cur].x = pos.x - 1; + neighbour_array[cur].y = pos.y; + cur += 1; + } + if (pos.x + 1 < width && !visited[pos.y][pos.x + 1]) { + neighbour_array[cur].x = pos.x + 1; + neighbour_array[cur].y = pos.y; + cur += 1; + } + if (pos.y > 0 && !visited[pos.y - 1][pos.x]) { + neighbour_array[cur].x = pos.x; + neighbour_array[cur].y = pos.y - 1; + cur += 1; + } + if (pos.y + 1 < height && !visited[pos.y + 1][pos.x]) { + neighbour_array[cur].x = pos.x; + neighbour_array[cur].y = pos.y + 1; + cur += 1; + } + + if (pos.x > 0 && pos.y > 0 && !visited[pos.y - 1][pos.x - 1]) { + neighbour_array[cur].x = pos.x - 1; + neighbour_array[cur].y = pos.y - 1; + cur += 1; + } + if (pos.x + 1 < width && pos.y > 0 && !visited[pos.y - 1][pos.x + 1]) { + neighbour_array[cur].x = pos.x + 1; + neighbour_array[cur].y = pos.y - 1; + cur += 1; + } + if (pos.x + 1 < width && pos.y + 1 < height && !visited[pos.y + 1][pos.x + 1]) { + neighbour_array[cur].x = pos.x + 1; + neighbour_array[cur].y = pos.y + 1; + cur += 1; + } + if (pos.x > 0 && pos.y + 1 < height && !visited[pos.y + 1][pos.x - 1]) { + neighbour_array[cur].x = pos.x - 1; + neighbour_array[cur].y = pos.y + 1; + cur += 1; + } + + return cur; +} + Map rbt_maze_map(size_t width, size_t height, unsigned int seed) { size_t map_width = width * 2 - 1, map_height = height * 2 - 1; @@ -145,7 +195,8 @@ Map file_plaintext_map(char *filename, size_t *width, size_t *height, Position * /* FIXME: I don't think we need DRAW_MAP_OFFSET_{X,Y} anymore * Although, at the same time, it does make less magic values, so I guess it's fine */ /* TODO: Maybe add an option to render with ▄? that doubles the resolution, but requires us to use ncursesw, probably. */ -void draw_map(Map map, size_t width, size_t height, int offset_x, int offset_y, Position start, Position goal, Path path, char visited[height][width]) { +/* TODO: so many fucking arguments lmao. Break it down into several functions? */ +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)path; /* I think it flickers less when we do that */ wnoutrefresh(stdscr); @@ -203,6 +254,20 @@ void draw_map(Map map, size_t width, size_t height, int offset_x, int offset_y, attroff(color_pair); } } + + /* Render the frontier */ + if (frontier != NULL) { + attron(COLOR_PAIR(FRONTIER_COLOR)); + while (frontier->next != NULL) { + mvaddch(frontier->pos.y + DRAW_MAP_OFFSET_Y + offset_y, frontier->pos.x*2 + DRAW_MAP_OFFSET_X + offset_x, ' '); + mvaddch(frontier->pos.y + DRAW_MAP_OFFSET_Y + offset_y, frontier->pos.x*2 + DRAW_MAP_OFFSET_X + 1 + offset_x, ' '); + frontier = frontier->next; + } + mvaddch(frontier->pos.y + DRAW_MAP_OFFSET_Y + offset_y, frontier->pos.x*2 + DRAW_MAP_OFFSET_X + offset_x, ' '); + mvaddch(frontier->pos.y + DRAW_MAP_OFFSET_Y + offset_y, frontier->pos.x*2 + DRAW_MAP_OFFSET_X + 1 + offset_x, ' '); + + attroff(COLOR_PAIR(FRONTIER_COLOR)); + } /* Draw path */ if (path != NULL) { @@ -227,6 +292,14 @@ void draw_map(Map map, size_t width, size_t height, int offset_x, int offset_y, mvaddch(goal.y + DRAW_MAP_OFFSET_Y + offset_y, goal.x*2 + DRAW_MAP_OFFSET_X + offset_x, GOAL_CHAR_1); mvaddch(goal.y + DRAW_MAP_OFFSET_Y + offset_y, goal.x*2 + DRAW_MAP_OFFSET_X + 1 + offset_x, GOAL_CHAR_2); attroff(COLOR_PAIR(GOAL_COLOR)); + + /* Draw the cursor */ + if (cursor != NULL) { + attron(COLOR_PAIR(CURSOR_COLOR)); + mvaddch(cursor->y + DRAW_MAP_OFFSET_Y + offset_y, cursor->x*2 + DRAW_MAP_OFFSET_X + offset_x, CURSOR_CHAR_1); + mvaddch(cursor->y + DRAW_MAP_OFFSET_Y + offset_y, cursor->x*2 + DRAW_MAP_OFFSET_X + 1 + offset_x, CURSOR_CHAR_2); + attroff(COLOR_PAIR(CURSOR_COLOR)); + } attroff(A_BOLD); doupdate(); @@ -4,7 +4,7 @@ #include <stddef.h> #include "structs.h" #include "path.h" - +#include "priority_queue.h" /* Returns an empty map of given size */ Map empty_map(size_t width, size_t height); @@ -12,6 +12,9 @@ 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[], Position pos, size_t width, size_t height, \ char visited[height][width]); +/* Stores all the existing 8dir neighbours of pos in neighbour_array and returns their amount */ +unsigned int neighbours_8dir(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 * WARNING: width and height are not the width and height of the returned map! @@ -35,8 +38,8 @@ Map rbt_maze_map(size_t width, size_t height, unsigned int seed); Map file_plaintext_map(char *filename, size_t *width, size_t *height, Position *start_pos, Position *end_pos); /* Draw the map. Bet you didn't expect that. - * path could be NULL to draw a map with no path */ -void draw_map(Map map, size_t width, size_t height, int offset_x, int offset_y, Position start, Position goal, Path path, char visited[height][width]); + * 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 print_map_out(Map map, size_t width, size_t height); diff --git a/maps/diagonal b/maps/diagonal new file mode 100644 index 0000000..de08a51 --- /dev/null +++ b/maps/diagonal @@ -0,0 +1,22 @@ +20x20 +.#@x +#................... +.#.................. +..#................. +...#................ +....#..........x.... +.....#.............. +......#............. +.......#............ +........#........... +.........#.......... +..........#......... +...........#........ +............#....... +.............#...... +..............#..... +...............#.... +................#... +.....@...........#.. +..................#. +...................# @@ -1,14 +1,25 @@ #include <stdlib.h> #include <stdio.h> #include <string.h> +#include <curses.h> #include "path.h" #include "map.h" #include "structs.h" #include "priority_queue.h" +int anim(Map map, size_t width, size_t height, Position start, Position end, Position *cur, char visited[height][width], PositionPQ *frontier) { + draw_map(map, width, height, 0, 0, start, end, cur, NULL, visited, frontier); + mvprintw(height+2, 0, "cur: %zu %zu", cur->x, cur->y); + /* TODO: input, automatic mode */ + switch (getch()) { + case 'q': + return -1; + } + return 0; +} /* BLOODY FUCK IT WORKS */ -Path breadth_first_search_path_4dir(Map map, size_t width, size_t height, Position start, Position end, char visited[height][width]) { +Path breadth_first_search_path_4dir(Map map, size_t width, size_t height, Position start, Position end, char visited[height][width], char should_anim) { Path path = malloc(sizeof(PathNode)*height); if (path == NULL) return NULL; @@ -40,6 +51,52 @@ Path breadth_first_search_path_4dir(Map map, size_t width, size_t height, Positi ppq_insert(&frontier, na[i], 0); path[na[i].y][na[i].x].parent = cur; } + + if (should_anim) { + if (anim(map, width, height, start, end, &cur, visited, frontier) == -1) return NULL; + } + } + + return NULL; +} + +Path breadth_first_search_path_8dir(Map map, size_t width, size_t height, Position start, Position end, char visited[height][width], char should_anim) { + Path path = malloc(sizeof(PathNode)*height); + if (path == NULL) return NULL; + + for (size_t row = 0; row < height; row++) { + path[row] = malloc(sizeof(PathNode) * width); + if (path[row] == NULL) return NULL; + memset(path[row], 0, width * sizeof(PathNode)); + } + + PositionPQ *frontier = ppq_new(start, 0); + + memset(visited, 0, height * width * sizeof(char)); + + while (frontier != NULL) { + Position cur = ppq_pop(&frontier); + visited[cur.y][cur.x] = 1; + + if (cur.x == end.x && cur.y == end.y) { + return path; /* Found path */ + } + + Position na[8]; + unsigned int nc = neighbours_8dir(na, cur, width, height, visited); + + for (unsigned int i = 0; i < nc; i++) { + /* The Russian constitution doesn't allow walking on walls */ + if (map[na[i].y][na[i].x] == WALL) continue; + + if (ppq_insert(&frontier, na[i], 0) != 3) { + path[na[i].y][na[i].x].parent = cur; + } + } + + if (should_anim) { + if (anim(map, width, height, start, end, &cur, visited, frontier) == -1) return NULL; + } } return NULL; @@ -4,7 +4,8 @@ #include "structs.h" #include "map.h" -Path breadth_first_search_path_4dir(Map map, size_t width, size_t height, Position start, Position end, char visited[height][width]); +Path breadth_first_search_path_4dir(Map map, size_t width, size_t height, Position start, Position end, char visited[height][width], char should_anim); +Path breadth_first_search_path_8dir(Map map, size_t width, size_t height, Position start, Position end, char visited[height][width], char should_anim); Path astar_path_4dir(Map map, size_t width, size_t height, Position start, Position end); size_t manhattan_distance(Position a, Position b); diff --git a/priority_queue.c b/priority_queue.c index 472f5c3..d2517a6 100644 --- a/priority_queue.c +++ b/priority_queue.c @@ -12,35 +12,40 @@ PositionPQ *ppq_new(Position pos, size_t priority) { return ppq; } -/* FIXME: this is shitty */ -void ppq_insert(PositionPQ **ppq, Position pos, size_t priority) { +/* FIXME: insted of `return n` introduce some defines with error codes, + * or an enum I don't care */ +int ppq_insert(PositionPQ **ppq, Position pos, size_t priority) { + //printf("Inserting %zu %zu\n", pos.x, pos.y); PositionPQ *start = *ppq; if ((*ppq) == NULL) { (*ppq) = ppq_new(pos, priority); - return; + return 1; } PositionPQ *n = ppq_new(pos, priority); if (start->priority > priority) { n->next = start; start = n; - return; + return 2; } PositionPQ *temp = *ppq; 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 */ + return 3; /* pos is already in ppq with a fine priority */ } temp = temp->next; } + if (temp->pos.x == pos.x && temp->pos.y == pos.y && temp->priority <= priority) { + return 3; /* pos is already in ppq with a fine priority */ + } n->next = temp->next; temp->next = n; - return; + return 4; } Position ppq_pop(PositionPQ **ppq) { diff --git a/priority_queue.h b/priority_queue.h index 1f933e7..2ac580e 100644 --- a/priority_queue.h +++ b/priority_queue.h @@ -19,7 +19,7 @@ typedef struct PositionPQNode_s PositionPQ; PositionPQ *ppq_new(Position pos, size_t priority); /* Insert a pos with priority into a given PositionPQ */ -void ppq_insert(PositionPQ **ppq, Position pos, size_t priority); +int ppq_insert(PositionPQ **ppq, Position pos, size_t priority); /* Remove and return the position with the lowest priority */ Position ppq_pop(PositionPQ **ppq); @@ -23,6 +23,8 @@ enum Colors_e { WALL_COLOR = 4, START_COLOR = 5, PATH_COLOR = 6, + FRONTIER_COLOR = 7, + CURSOR_COLOR = 8, }; /* A map is a 2D array of MapTiles. |