diff options
| author | Tyge Løvset <[email protected]> | 2021-09-12 23:04:33 +0200 |
|---|---|---|
| committer | Tyge Løvset <[email protected]> | 2021-09-12 23:04:33 +0200 |
| commit | fa2871406affad4d96a54554f80c7418a716b98c (patch) | |
| tree | 8062af12ca689538ee8d6882c6f06bdb05e29a1f /examples/astar.c | |
| parent | 1a9020f895754f564e480ba9ed564c637f26060e (diff) | |
| download | STC-modified-fa2871406affad4d96a54554f80c7418a716b98c.tar.gz STC-modified-fa2871406affad4d96a54554f80c7418a716b98c.zip | |
Renamed input macro i_module to i_prefix. Replaced astar.c example.
Now supports that user defines i_prefix.
Diffstat (limited to 'examples/astar.c')
| -rw-r--r-- | examples/astar.c | 167 |
1 files changed, 167 insertions, 0 deletions
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 <stc/cstr.h>
+#include <stdio.h>
+
+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 <stc/cpque.h>
+
+#define i_val point
+#define i_cmp c_no_compare
+#include <stc/cdeq.h>
+
+#define i_tag pcost
+#define i_key point
+#define i_val int
+#define i_cmp point_key_compare
+#include <stc/csmap.h>
+
+#define i_tag pstep
+#define i_key point
+#define i_val point
+#define i_cmp point_key_compare
+#include <stc/csmap.h>
+
+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);
+ }
+ }
+}
|