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 | |
| 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')
| -rw-r--r-- | examples/astar.c | 167 | ||||
| -rw-r--r-- | examples/stc_astar.c | 184 |
2 files changed, 167 insertions, 184 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);
+ }
+ }
+}
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 <stc/cstr.h>
-#include <stdio.h>
-
-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 <stc/cdeq.h>
-
-#define i_tag pnt
-#define i_val MazePoint
-#define i_cmp mpnt_compare_priority
-#include <stc/cpque.h>
-
-#define i_tag step
-#define i_key MazePoint
-#define i_val MazePoint
-#define i_cmp mpnt_key_compare
-#include <stc/csmap.h>
-
-#define i_tag cost
-#define i_key MazePoint
-#define i_val int
-#define i_cmp mpnt_key_compare
-#include <stc/csmap.h>
-
-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 |