From fa2871406affad4d96a54554f80c7418a716b98c Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 12 Sep 2021 23:04:33 +0200 Subject: Renamed input macro i_module to i_prefix. Replaced astar.c example. Now supports that user defines i_prefix. --- examples/astar.c | 167 ++++++++++++++++++++++++++++++++++++++++++++++ examples/stc_astar.c | 184 --------------------------------------------------- 2 files changed, 167 insertions(+), 184 deletions(-) create mode 100644 examples/astar.c delete mode 100644 examples/stc_astar.c (limited to 'examples') diff --git a/examples/astar.c b/examples/astar.c new file mode 100644 index 00000000..5571c306 --- /dev/null +++ b/examples/astar.c @@ -0,0 +1,167 @@ +// +// -- An A* pathfinder inspired by the excellent tutorial at Red Blob Games -- +// +// This is a reimplementation of the CTL example to STC: +// https://github.com/glouw/ctl/blob/master/examples/astar.c +// https://www.redblobgames.com/pathfinding/a-star/introduction.html + +#include +#include + +typedef struct +{ + int x; + int y; + int priorty; + int width; +} +point; + +point +point_init(int x, int y, int width) +{ + return (point) { x, y, 0, width }; +} + +int +point_compare_priority(const point* a, const point* b) +{ + return a->priorty < b->priorty; +} + +int +point_equal(const point* a, const point* b) +{ + return a->x == b->x && a->y == b->y; +} + +point +point_from(const cstr* maze, const char* c, int width) +{ + int index = cstr_find(*maze, c); + return point_init(index % width, index / width, width); +} + +int +point_index(const point* p) +{ + return p->x + p->width * p->y; +} + +int +point_key_compare(const point* a, const point* b) +{ + int i = point_index(a); + int j = point_index(b); + return (i == j) ? 0 : (i < j) ? -1 : 1; +} + +#define i_val point +#define i_cmp point_compare_priority +#include + +#define i_val point +#define i_cmp c_no_compare +#include + +#define i_tag pcost +#define i_key point +#define i_val int +#define i_cmp point_key_compare +#include + +#define i_tag pstep +#define i_key point +#define i_val point +#define i_cmp point_key_compare +#include + +cdeq_point +astar(cstr* maze, int width) +{ + cdeq_point path = cdeq_point_init(); + + c_forauto (cpque_point, front) + c_forauto (csmap_pstep, from) + c_forauto (csmap_pcost, costs) + { + point start = point_from(maze, "@", width); + point goal = point_from(maze, "!", width); + csmap_pcost_insert(&costs, start, 0); + cpque_point_push(&front, start); + while (!cpque_point_empty(front)) + { + point current = *cpque_point_top(&front); + cpque_point_pop(&front); + if (point_equal(¤t, &goal)) + break; + point deltas[] = { + { -1, +1, 0, width }, { 0, +1, 0, width }, { 1, +1, 0, width }, + { -1, 0, 0, width }, /* ~ ~ ~ ~ ~ ~ ~ */ { 1, 0, 0, width }, + { -1, -1, 0, width }, { 0, -1, 0, width }, { 1, -1, 0, width }, + }; + for (size_t i = 0; i < c_arraylen(deltas); i++) + { + point delta = deltas[i]; + point next = point_init(current.x + delta.x, current.y + delta.y, width); + int new_cost = *csmap_pcost_at(&costs, current); + if (maze->str[point_index(&next)] != '#') + { + csmap_pcost_value_t *cost = csmap_pcost_get(&costs, next); + if (cost == NULL || new_cost < cost->second) + { + csmap_pcost_insert(&costs, next, new_cost); + next.priorty = new_cost + abs(goal.x - next.x) + abs(goal.y - next.y); + cpque_point_push(&front, next); + csmap_pstep_insert(&from, next, current); + } + } + } + } + point current = goal; + while (!point_equal(¤t, &start)) + { + cdeq_point_push_front(&path, current); + current = *csmap_pstep_at(&from, current); + } + cdeq_point_push_front(&path, start); + } + return path; +} + +int +main(void) +{ + c_forvar (cstr maze = cstr_lit( + "#########################################################################\n" + "# # # # # # #\n" + "# # ######### # ##### ######### ##### ##### ##### # ! #\n" + "# # # # # # # # # #\n" + "######### # ######### ######### ##### # # # ######### #\n" + "# # # # # # # # # # #\n" + "# # ############# # # ######### ##### # ######### # #\n" + "# # # # # # # # # #\n" + "# ############# ##### ##### # ##### ######### # ##### #\n" + "# # # # # # # # # #\n" + "# ##### ##### # ##### # ######### # # # #############\n" + "# # # # # # # # # # # #\n" + "############# # # # ######### # ##### # ##### ##### #\n" + "# # # # # # # # # #\n" + "# ##### # ######### ##### # ##### ##### ############# #\n" + "# # # # # # # # # #\n" + "# # ######### # ##### ######### # # ############# # #\n" + "# # # # # # # # # # #\n" + "# ######### # # # ##### ######### ######### # #########\n" + "# # # # # # # # # #\n" + "# @ # ##### ##### ##### ######### ##### # ######### # #\n" + "# # # # # # #\n" + "#########################################################################\n"), cstr_del(&maze)) + { + int width = cstr_find(maze, "\n") + 1; + c_forvar (cdeq_point path = astar(&maze, width), cdeq_point_del(&path)) + { + c_foreach (it, cdeq_point, path) maze.str[point_index(it.ref)] = 'x'; + printf("%s", maze.str); + } + } +} diff --git a/examples/stc_astar.c b/examples/stc_astar.c deleted file mode 100644 index 4f5075a1..00000000 --- a/examples/stc_astar.c +++ /dev/null @@ -1,184 +0,0 @@ -// -// -- An A* pathfinder inspired by the excellent tutorial at Red Blob Games -- -// -// See: -// https://www.redblobgames.com/pathfinding/a-star/introduction.html - -#include -#include - -typedef struct { - int x, y; - int priorty, width; -} MazePoint; - -MazePoint -mpnt_init(int x, int y, int width) -{ - return c_make(MazePoint){ x, y, 0, width }; -} - -int -mpnt_compare_priority(const MazePoint* a, const MazePoint* b) -{ - //return 0; // NB! gives 14 steps shorter path!? hmm.. - return c_default_compare(&b->priorty, &a->priorty); // note: high priority is low cost -} - -int -mpnt_equal(MazePoint* a, MazePoint* b) -{ - return a->x == b->x && a->y == b->y; -} - -MazePoint -mpnt_from(cstr maze, const char* c, int width) -{ - int index = cstr_find(maze, c); - return mpnt_init(index % width, index / width, width); -} - -int -mpnt_index(const MazePoint* p) -{ - return p->x + p->width * p->y; -} - -int -mpnt_key_compare(const MazePoint* a, const MazePoint* b) -{ - int i = mpnt_index(a); - int j = mpnt_index(b); - return (i > j) - (i < j); -} - -typedef struct { - MazePoint point; - int value; -} MazeCost; - -typedef struct { - MazePoint a; - MazePoint b; -} MazeStep; - -#define i_tag pnt -#define i_val MazePoint -#define i_cmp c_no_compare -#include - -#define i_tag pnt -#define i_val MazePoint -#define i_cmp mpnt_compare_priority -#include - -#define i_tag step -#define i_key MazePoint -#define i_val MazePoint -#define i_cmp mpnt_key_compare -#include - -#define i_tag cost -#define i_key MazePoint -#define i_val int -#define i_cmp mpnt_key_compare -#include - -cdeq_pnt -astar(cstr maze, int width) -{ - MazePoint start = mpnt_from(maze, "@", width); - MazePoint goal = mpnt_from(maze, "!", width); - - cdeq_pnt path = cdeq_pnt_init(); // returned - - cpque_pnt frontier = cpque_pnt_init(); - csmap_step came_from = csmap_step_init(); - csmap_cost cost_so_far = csmap_cost_init(); - c_fordefer (cpque_pnt_del(&frontier), - csmap_step_del(&came_from), - csmap_cost_del(&cost_so_far)) - { - cpque_pnt_push(&frontier, start); - csmap_cost_insert(&cost_so_far, start, 0); - - while (!cpque_pnt_empty(frontier)) - { - MazePoint current = *cpque_pnt_top(&frontier); - cpque_pnt_pop(&frontier); - if (mpnt_equal(¤t, &goal)) - break; - MazePoint deltas[] = { - { -1, +1, 0, width }, { 0, +1, 0, width }, { 1, +1, 0, width }, - { -1, 0, 0, width }, /* ~ ~ ~ ~ ~ ~ ~ */ { 1, 0, 0, width }, - { -1, -1, 0, width }, { 0, -1, 0, width }, { 1, -1, 0, width }, - }; - - c_forrange (i, c_arraylen(deltas)) - { - MazePoint delta = deltas[i]; - MazePoint next = mpnt_init(current.x + delta.x, current.y + delta.y, width); - int new_cost = *csmap_cost_at(&cost_so_far, current); - if (maze.str[mpnt_index(&next)] != '#') - { - csmap_cost_value_t* cost = csmap_cost_find(&cost_so_far, next).ref; - if (!cost || new_cost < cost->second) - { - csmap_cost_put(&cost_so_far, next, new_cost); // update - next.priorty = new_cost + abs(goal.x - next.x) + abs(goal.y - next.y); - cpque_pnt_push(&frontier, next); - csmap_step_put(&came_from, next, current); - } - } - } - } - MazePoint current = goal; - while(!mpnt_equal(¤t, &start)) - { - cdeq_pnt_push_front(&path, current); - current = *csmap_step_at(&came_from, current); - } - cdeq_pnt_push_front(&path, start); - } - return path; -} - -int -main(void) -{ - cstr maze = cstr_from( - "#########################################################################\n" - "# # # # # # #\n" - "# # ######### # ##### ######### ##### ##### ##### # ! #\n" - "# # # # # # # # # #\n" - "######### # ######### ######### ##### # # # ######### #\n" - "# # # # # # # # # # #\n" - "# # ############# # # ######### ##### # ######### # #\n" - "# # # # # # # # # #\n" - "# ############# ##### ##### # ##### ######### # ##### #\n" - "# # # # # # # # # #\n" - "# ##### ##### # ##### # ######### # # # #############\n" - "# # # # # # # # # # # #\n" - "############# # # # ######### # ##### # ##### ##### #\n" - "# # # # # # # # # #\n" - "# ##### # ######### ##### # ##### ##### ############# #\n" - "# # # # # # # # # #\n" - "# # ######### # ##### ######### # # ############# # #\n" - "# # # # # # # # # # #\n" - "# ######### # # # ##### ######### ######### # #########\n" - "# # # # # # # # # #\n" - "# @ # ##### ##### ##### ######### ##### # ######### # #\n" - "# # # # # # #\n" - "#########################################################################\n"); - int width = cstr_find(maze, "\n") + 1; - cdeq_pnt path = astar(maze, width); - - printf("length: %zu\n", cdeq_pnt_size(path)); - - c_foreach (it, cdeq_pnt, path) - maze.str[mpnt_index(it.ref)] = 'x'; - - printf("%s", maze.str); - cstr_del(&maze); - cdeq_pnt_del(&path); -} \ No newline at end of file -- cgit v1.2.3