From db5320aa188d773c8edc32eee844127457ef280c Mon Sep 17 00:00:00 2001 From: Kirill Petrashin Date: Tue, 14 Apr 2026 21:41:33 +0300 Subject: Improve the Path type --- bmp.c | 2 +- main.c | 3 +++ map.c | 4 ++-- path.c | 53 ++++++++++++++++++++++++----------------------------- path.h | 1 + structs.h | 10 ++++------ 6 files changed, 35 insertions(+), 38 deletions(-) diff --git a/bmp.c b/bmp.c index 739c2ad..b44ea39 100644 --- a/bmp.c +++ b/bmp.c @@ -77,7 +77,7 @@ void map_to_bmp(Map map, size_t map_width, size_t map_height, Position start, Po buf[(height - cur.y - 1) * width_in_bytes + cur.x * 3 + 0] = 0; /* b */ buf[(height - cur.y - 1) * width_in_bytes + cur.x * 3 + 1] = 0; /* g */ buf[(height - cur.y - 1) * width_in_bytes + cur.x * 3 + 2] = 255; /* r */ - cur = path[cur.y][cur.x].parent; + cur = path[cur.y][cur.x]; } } diff --git a/main.c b/main.c index 937db12..c909633 100644 --- a/main.c +++ b/main.c @@ -22,6 +22,9 @@ - less magical values - MORE MAPS FOR THE MAP PEOPLE - Clean up unused `#include`s + - keybinding help screen + - live updating in map_editor() + - 'clean' rendering mode, without all the ugly shit - Comments */ void sigint_handler(int sig) { diff --git a/map.c b/map.c index f6cb840..dc0a605 100644 --- a/map.c +++ b/map.c @@ -364,13 +364,13 @@ void draw_map(Map map, size_t width, size_t height, Position start, Position goa mvaddch(cur.y + map_offset_y, cur.x*2 + 1 + map_offset_x, c2); } - if (cur.x - path[cur.y][cur.x].parent.x == 0 || cur.y - path[cur.y][cur.x].parent.y == 0) { + if (cur.x - path[cur.y][cur.x].x == 0 || cur.y - path[cur.y][cur.x].y == 0) { length += COST_ORTHOGONAL; } else { length += COST_DIAGONAL; } prev = cur; - cur = path[cur.y][cur.x].parent; + cur = path[cur.y][cur.x]; } attroff(COLOR_PAIR(PATH_COLOR)); attron(COLOR_PAIR(WALL_TEXT_COLOR)); diff --git a/path.c b/path.c index 442ca14..fbd599c 100644 --- a/path.c +++ b/path.c @@ -71,14 +71,8 @@ Path breadth_first_search_path(int dirs, Map map, size_t width, size_t height, P default: error("Tried to call breadth_first_search_path with wrong direction amount\n"); } - 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)); - } + Path path = path_new(width, height); + if (path == NULL) error("Path was NULL\n"); PositionPQ *frontier = ppq_new(start, 0); @@ -104,7 +98,7 @@ Path breadth_first_search_path(int dirs, Map map, size_t width, size_t height, P if (map[na[i].y][na[i].x] == WALL) continue; if (ppq_insert(&frontier, na[i], 0) != PPQ_INSERT_ALREADY) { - path[na[i].y][na[i].x].parent = cur; + path[na[i].y][na[i].x] = cur; } } @@ -137,14 +131,8 @@ Path dijkstra_path(int dirs, Map map, size_t width, size_t height, Position star default: error("Tried to call dijkstra_path with wrong direction amount\n"); } - 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)); - } + Path path = path_new(width, height); + if (path == NULL) error("Path was NULL\n"); PositionPQ *frontier = ppq_new(start, 0); @@ -173,7 +161,7 @@ Path dijkstra_path(int dirs, Map map, size_t width, size_t height, Position star size_t new_cost = cost_so_far[cur.y][cur.x] + costs[i]; if (new_cost < cost_so_far[na[i].y][na[i].x]) { cost_so_far[na[i].y][na[i].x] = new_cost; - path[na[i].y][na[i].x].parent = cur; + path[na[i].y][na[i].x] = cur; ppq_insert(&frontier, na[i], new_cost); } } @@ -210,14 +198,8 @@ Path astar_path(int dirs, Map map, size_t width, size_t height, Position start, default: error("Tried to call astar_path with wrong direction amount\n"); } - 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)); - } + Path path = path_new(width, height); + if (path == NULL) error("Path was NULL\n"); PositionPQ *frontier = ppq_new(start, 0); @@ -246,7 +228,7 @@ Path astar_path(int dirs, Map map, size_t width, size_t height, Position start, size_t new_cost = cost_so_far[cur.y][cur.x] + costs[i]; if (new_cost < cost_so_far[na[i].y][na[i].x]) { cost_so_far[na[i].y][na[i].x] = new_cost; - path[na[i].y][na[i].x].parent = cur; + path[na[i].y][na[i].x] = cur; size_t priority = new_cost + heuristic(na[i], end); ppq_insert(&frontier, na[i], priority); } @@ -308,17 +290,30 @@ size_t path_length(Path path, Position start, Position goal) { if (path != NULL) { Position cur = goal; while (cur.x != start.x || cur.y != start.y) { - if (cur.x - path[cur.y][cur.x].parent.x == 0 || cur.y - path[cur.y][cur.x].parent.y == 0) { + if (cur.x - path[cur.y][cur.x].x == 0 || cur.y - path[cur.y][cur.x].y == 0) { length += COST_ORTHOGONAL; } else { length += COST_DIAGONAL; } - cur = path[cur.y][cur.x].parent; + cur = path[cur.y][cur.x]; } } return length; } +Path path_new(size_t width, size_t height) { + Path path = malloc(sizeof(Position*)*height); + if (path == NULL) return NULL; + + for (size_t row = 0; row < height; row++) { + path[row] = malloc(sizeof(Position) * width); + if (path[row] == NULL) return NULL; + memset(path[row], 0, width * sizeof(Position)); + } + + return path; +} + void path_free(Path path, size_t height) { if (path == NULL) return; for (size_t i = 0; i < height; i++) { diff --git a/path.h b/path.h index 10f79e9..9f3f38f 100644 --- a/path.h +++ b/path.h @@ -12,6 +12,7 @@ Path astar_path(int dirs, Map map, size_t width, size_t height, Position start, size_t manhattan_distance(Position a, Position b); size_t diagonal_distance(Position a, Position b); +Path path_new(size_t width, size_t height); void path_free(Path path, size_t height); size_t path_length(Path path, Position start, Position goal); diff --git a/structs.h b/structs.h index bc63408..5798b9e 100644 --- a/structs.h +++ b/structs.h @@ -32,11 +32,9 @@ enum Colors_e { * Use as map[row][column] */ typedef MapTile** Map; -/* Yeah I'm not sure either */ -struct PathNode_s { - Position parent; -}; -typedef struct PathNode_s PathNode; -typedef PathNode** Path; +/* A path is a 2D array, in which for every tile we store the Position of a + * tile we came from. To get the full path you have to follow it from end + * to start */ +typedef Position** Path; #endif /* STRUCTS_H_ */ -- cgit v1.2.3