A* search: refactor, add tests

1 files changed, 95 insertions, 19 deletions

diff --git a/source/tests/astar.test.c b/source/tests/astar.test.c
index eeb1100..6be9418 100644
--- a/source/tests/astar.test.c
+++ b/source/tests/astar.test.c
@@ -10,15 +10,7 @@ enum {
   HEIGHT = 5,
 };
 
-i8 grid[WIDTH * HEIGHT] = {
-  0, 0, 0, 0, 0, 0, 0, 0, //
-  1, 1, 0, 1, 1, 0, 1, 0, //
-  1, 1, 0, 0, 1, 0, 1, 0, //
-  0, 0, 0, 1, 1, 1, 1, 0, //
-  1, 1, 0, 0, 0, 0, 0, 0, //
-};
-
-static astar_link_t neighbor(i64 a, i64 n) {
+static astar_link_t neighbor(i8 *grid, i64 a, i64 n) {
   i64 x = a % WIDTH;
   i64 y = a / WIDTH;
 
@@ -67,15 +59,15 @@ static i64 heuristic(i64 a, i64 b) {
 
 #define ASTAR_TEMPLATE
 #define ASTAR_SUFFIX _test
-#define ASTAR_NEIGHBOR(a, n) neighbor(a, n)
-#define ASTAR_HEURISTIC(a, b) heuristic(a, b)
+#define ASTAR_NEIGHBOR(data, a, n) neighbor((i8 *) data, a, n)
+#define ASTAR_HEURISTIC(data, a, b) heuristic(a, b)
 #include "../kit/astar.h"
 
 static i64 xy(i64 x, i64 y) {
   return y * WIDTH + x;
 }
 
-TEST("astar") {
+TEST("astar path exists") {
   astar_node_t buf[200];
 
   astar_set_t sets[2] = {
@@ -83,17 +75,28 @@ TEST("astar") {
     { .capacity = 100, .size = 0, .values = buf + 100 },
   };
 
+  i8 grid[WIDTH * HEIGHT] = {
+    0, 0, 0, 0, 0, 0, 0, 0, //
+    1, 1, 0, 1, 1, 0, 1, 0, //
+    1, 1, 0, 0, 1, 0, 1, 0, //
+    0, 0, 0, 1, 1, 1, 1, 0, //
+    1, 1, 0, 0, 0, 0, 0, 0, //
+  };
+
   astar_state_t state;
-  REQUIRE_EQ(astar_init(&state, sets[0], sets[1], xy(0, 0), xy(5, 2)),
-             KIT_OK);
+  REQUIRE_EQ(
+      astar_init(&state, sets[0], sets[1], grid, xy(0, 0), xy(5, 2)),
+      KIT_OK);
 
-  s32 status = KIT_OK;
+  s32 status;
 
-  while (state.status == ASTAR_PROGRESS)
-    status |= astar_iteration_test(&state);
+  for (;;) {
+    status = astar_iteration_test(&state);
+    if (status != ASTAR_PROGRESS)
+      break;
+  }
 
-  REQUIRE_EQ(status, KIT_OK);
-  REQUIRE_EQ(state.status, ASTAR_SUCCESS);
+  REQUIRE_EQ(status, ASTAR_SUCCESS);
 
   i64 path_size = 10;
   i64 path[10];
@@ -113,4 +116,77 @@ TEST("astar") {
   }
 }
 
+TEST("astar no path") {
+  astar_node_t buf[200];
+
+  astar_set_t sets[2] = {
+    { .capacity = 100, .size = 0, .values = buf },
+    { .capacity = 100, .size = 0, .values = buf + 100 },
+  };
+
+  i8 grid[WIDTH * HEIGHT] = {
+    0, 0, 0, 0, 1, 0, 0, 0, //
+    1, 1, 0, 1, 1, 0, 1, 1, //
+    1, 1, 0, 0, 1, 0, 1, 0, //
+    0, 0, 0, 1, 1, 1, 1, 0, //
+    1, 1, 0, 0, 0, 0, 0, 0, //
+  };
+
+  astar_state_t state;
+  REQUIRE_EQ(
+      astar_init(&state, sets[0], sets[1], grid, xy(0, 0), xy(5, 2)),
+      KIT_OK);
+
+  s32 status;
+
+  for (;;) {
+    status = astar_iteration_test(&state);
+    if (status != ASTAR_PROGRESS)
+      break;
+  }
+
+  REQUIRE_EQ(status, ASTAR_FAIL);
+}
+
+TEST("astar empty path") {
+  astar_node_t buf[200];
+
+  astar_set_t sets[2] = {
+    { .capacity = 100, .size = 0, .values = buf },
+    { .capacity = 100, .size = 0, .values = buf + 100 },
+  };
+
+  i8 grid[WIDTH * HEIGHT] = {
+    0, 0, 0, 0, 1, 0, 0, 0, //
+    1, 1, 0, 1, 1, 0, 1, 1, //
+    1, 1, 0, 0, 1, 0, 1, 0, //
+    0, 0, 0, 1, 1, 1, 1, 0, //
+    1, 1, 0, 0, 0, 0, 0, 0, //
+  };
+
+  astar_state_t state;
+  REQUIRE_EQ(
+      astar_init(&state, sets[0], sets[1], grid, xy(4, 3), xy(4, 3)),
+      KIT_OK);
+
+  s32 status;
+
+  for (;;) {
+    status = astar_iteration_test(&state);
+    if (status != ASTAR_PROGRESS)
+      break;
+  }
+
+  REQUIRE_EQ(status, ASTAR_SUCCESS);
+
+  i64 path_size = 10;
+  i64 path[10];
+
+  REQUIRE_EQ(astar_path(&state, &path_size, path), KIT_OK);
+  REQUIRE_EQ(path_size, 1);
+
+  if (path_size == 1)
+    REQUIRE_EQ(path[0], xy(4, 3));
+}
+
 #undef KIT_TEST_FILE