use dead edges to improve solver speed

3 files changed, 290 insertions, 96 deletions

diff --git a/src/core/sok-ctx.c b/src/core/sok-ctx.c
index 036bf66..fef2c8b 100644
--- a/src/core/sok-ctx.c
+++ b/src/core/sok-ctx.c
@@ -14,14 +14,133 @@
   ((a).y == (b).y) \
 )
 
+static size_t
+pos_find(
+  const sok_pos_t pos,
+  const sok_pos_t * const set,
+  const size_t len
+) {
+  for (size_t i = 0; i < len; i++) {
+    if (POINTS_EQUAL(pos, set[i])) {
+      return i;
+    }
+  }
+
+  return len;
+}
+
 static bool
-ctx_is_wall(
+tile_is_goal(
+  const sok_ctx_t * const ctx,
+  const sok_pos_t pos
+) {
+  const size_t num_goals = ctx->level.num_goals;
+  return pos_find(pos, ctx->level.goals, num_goals) < num_goals;
+}
+
+static bool
+tile_is_wall(
   const sok_ctx_t * const ctx,
   const sok_pos_t pos
 ) {
   return ctx->level.walls[pos.y * ctx->level.size.x + pos.x];
 }
 
+
+static bool
+tile_is_corner(
+  const sok_ctx_t * const ctx,
+  const sok_pos_t pos
+) {
+  // right
+  const bool r = tile_is_wall(ctx, (sok_pos_t) {
+    .x = pos.x + 1,
+    .y = pos.y,
+  });
+
+  // top
+  const bool t = tile_is_wall(ctx, (sok_pos_t) {
+    .x = pos.x,
+    .y = pos.y - 1,
+  });
+
+  // left
+  const bool l = tile_is_wall(ctx, (sok_pos_t) {
+    .x = pos.x - 1,
+    .y = pos.y,
+  });
+
+  // bottom
+  const bool b = tile_is_wall(ctx, (sok_pos_t) {
+    .x = pos.x,
+    .y = pos.y + 1,
+  });
+
+  return (
+    (t && r) || // top-right
+    (t && l) || // top-left
+    (b && l) || // bottom-left
+    (b && r)    // bottom-right
+  );
+}
+
+static size_t
+sok_ctx_count_goals_left(
+  sok_ctx_t * const ctx
+) {
+  const size_t num_boxes = ctx->level.num_boxes;
+  size_t r = 0;
+
+  for (size_t i = 0; i < ctx->level.num_goals; i++) {
+    r += pos_find(
+      ctx->level.goals[i],
+      ctx->boxes,
+      num_boxes
+    ) < num_boxes ? 0 : 1;
+  }
+
+  return r;
+}
+
+static bool
+sok_ctx_box_is_stuck(
+  const sok_ctx_t * const ctx,
+  const size_t i
+) {
+  const sok_pos_t box_pos = ctx->boxes[i];
+
+  for (size_t i = 0; i < ctx->num_dead_edges; i++) {
+    if ((
+      box_pos.x == ctx->dead_edges[i].src.x &&
+      box_pos.y >= ctx->dead_edges[i].src.y &&
+      box_pos.y <= ctx->dead_edges[i].dst.y
+    ) || (
+      box_pos.y == ctx->dead_edges[i].src.y &&
+      box_pos.x >= ctx->dead_edges[i].src.x &&
+      box_pos.x <= ctx->dead_edges[i].dst.x
+    )) {
+      // return true (box is in dead corner/edge)
+      return true;
+    }
+  }
+
+  // return false (not in dead corner/edge)
+  return false;
+}
+
+static bool
+sok_ctx_has_stuck_boxes(
+  const sok_ctx_t * const ctx
+) {
+  for (size_t i = 0; i < ctx->level.num_boxes; i++) {
+    if (sok_ctx_box_is_stuck(ctx, i)) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
 static void
 ctx_set_wall(
   sok_ctx_t * const ctx,
@@ -168,113 +287,162 @@ LEVEL_PARSER_CBS = {
   .on_junk = on_junk,
 };
 
-static size_t
-pos_find(
-  const sok_pos_t pos,
-  const sok_pos_t * const set,
-  const size_t len
-) {
-  for (size_t i = 0; i < len; i++) {
-    if (POINTS_EQUAL(pos, set[i])) {
-      return i;
-    }
-  }
-
-  return len;
-}
-
-static bool
-tile_is_goal(
-  const sok_ctx_t * const ctx,
-  const sok_pos_t pos
-) {
-  const size_t num_goals = ctx->level.num_goals;
-  return pos_find(pos, ctx->level.goals, num_goals) < num_goals;
+void
+sok_ctx_init(sok_ctx_t * const ctx, void *user_data) {
+  memset(ctx, 0, sizeof(sok_ctx_t));
+  ctx->user_data = user_data;
 }
 
-static bool
-tile_is_corner(
-  const sok_ctx_t * const ctx,
-  const sok_pos_t pos
-) {
-  // right
-  const bool r = ctx_is_wall(ctx, (sok_pos_t) {
-    .x = pos.x + 1,
-    .y = pos.y,
-  });
-
-  // top
-  const bool t = ctx_is_wall(ctx, (sok_pos_t) {
-    .x = pos.x,
-    .y = pos.y - 1,
-  });
+#define MIN_POS(a, b) ((sok_pos_t) { \
+  .x = (a).x < (b).x ? (a).x : (b).x, \
+  .y = (a).y < (b).y ? (a).y : (b).y, \
+})
 
-  // left
-  const bool l = ctx_is_wall(ctx, (sok_pos_t) {
-    .x = pos.x - 1,
-    .y = pos.y,
-  });
+#define MAX_POS(a, b) ((sok_pos_t) { \
+  .x = (a).x > (b).x ? (a).x : (b).x, \
+  .y = (a).y > (b).y ? (a).y : (b).y, \
+})
 
-  // bottom
-  const bool b = ctx_is_wall(ctx, (sok_pos_t) {
-    .x = pos.x,
-    .y = pos.y + 1,
-  });
+static void
+sok_ctx_add_dead_edge(
+  sok_ctx_t * const ctx,
+  const sok_pos_t src,
+  const sok_pos_t dst
+) {
+  for (size_t i = 0; i < ctx->num_dead_edges; i++) {
+    if (
+      src.x >= ctx->dead_edges[i].src.x &&
+      src.y >= ctx->dead_edges[i].src.y &&
+      dst.x <= ctx->dead_edges[i].dst.x &&
+      dst.y <= ctx->dead_edges[i].dst.y
+    ) {
+      // inside existing edge, skip
+      return;
+    } else if (
+      ctx->dead_edges[i].src.x >= src.x &&
+      ctx->dead_edges[i].src.y >= src.y &&
+      ctx->dead_edges[i].dst.x <= dst.x &&
+      ctx->dead_edges[i].dst.y <= dst.y
+    ) {
+      // existing edge inside new edge, expand edge
+      ctx->dead_edges[i].src = MIN_POS(ctx->dead_edges[i].src, src);
+      ctx->dead_edges[i].dst = MAX_POS(ctx->dead_edges[i].dst, dst);
+      return;
+    }
+  }
 
-  return (
-    (t && r) || // top-right
-    (t && l) || // top-left
-    (b && l) || // bottom-left
-    (b && r)    // bottom-right
-  );
+  // not found, add to list of edges
+  ctx->dead_edges[ctx->num_dead_edges].src = src;
+  ctx->dead_edges[ctx->num_dead_edges].dst = dst;
+  ctx->num_dead_edges++;
 }
 
-static size_t
-sok_ctx_count_goals_left(
+static void
+sok_ctx_find_dead_edges(
   sok_ctx_t * const ctx
 ) {
-  const size_t num_boxes = ctx->level.num_boxes;
-  size_t r = 0;
-
-  for (size_t i = 0; i < ctx->level.num_goals; i++) {
-    r += pos_find(
-      ctx->level.goals[i],
-      ctx->boxes,
-      num_boxes
-    ) < num_boxes ? 0 : 1;
+  size_t num_corners = 0;
+  sok_pos_t corners[SOK_CTX_MAX_DEAD_EDGES];
+  bool used[SOK_CTX_MAX_DEAD_EDGES];
+
+  // clear used
+  memset(used, 0, sizeof(used));
+
+  // scan corners
+  for (size_t y = 1; y < ctx->level.size.y - 1; y++) {
+    for (size_t x = 1; x < ctx->level.size.x - 1; x++) {
+      const sok_pos_t pos = { x, y };
+
+      if (
+        !tile_is_wall(ctx, pos) &&
+        !tile_is_goal(ctx, pos) &&
+        tile_is_corner(ctx, pos)
+      ) {
+        // tile is not a wall, not a goal, and is a corner, so
+        // add to the list of corners
+        corners[num_corners] = pos;
+        num_corners++;
+      }
+    }
   }
 
-  return r;
-}
+  // look for dead edges
+  for (size_t i = 0; i < num_corners; i++) {
+    for (size_t j = i + 1; j < num_corners; j++) {
+      if (
+        corners[j].x == corners[i].x &&
+        corners[j].y > corners[i].y
+      ) {
+        bool has_goal = false,
+             has_wall = false,
+             l_wall = true,
+             r_wall = true;
+
+        for (size_t k = corners[i].y; k < corners[j].y; k++) {
+          // is there a goal or wall on this tile?
+          const sok_pos_t pos = { corners[i].x, k };
+          has_goal = has_goal || tile_is_goal(ctx, pos);
+          has_wall = has_wall || tile_is_wall(ctx, pos);
+
+          // is there a wall to the left of this tile?
+          const sok_pos_t l_pos = { corners[i].x - 1, k };
+          l_wall = l_wall && tile_is_wall(ctx, l_pos);
+
+          // is there a wall to the right of this tile?
+          const sok_pos_t r_pos = { corners[i].x + 1, k };
+          r_wall = r_wall && tile_is_wall(ctx, r_pos);
+        }
 
-static bool
-sok_ctx_box_is_stuck(
-  const sok_ctx_t * const ctx,
-  const size_t i
-) {
-  return (
-    !tile_is_goal(ctx, ctx->boxes[i]) &&
-    tile_is_corner(ctx, ctx->boxes[i])
-  );
-}
+        if (!has_goal && !has_wall && (l_wall || r_wall)) {
+          // emit dead edge (vertical)
+          sok_ctx_add_dead_edge(ctx, corners[i], corners[j]);
 
-static bool
-sok_ctx_has_stuck_boxes(
-  const sok_ctx_t * const ctx
-) {
-  for (size_t i = 0; i < ctx->level.num_boxes; i++) {
-    if (sok_ctx_box_is_stuck(ctx, i)) {
-      return true;
+          // flag corners as used
+          used[i] = true;
+          used[j] = true;
+        }
+      } else if (
+        corners[j].x > corners[i].x &&
+        corners[j].y == corners[i].y
+      ) {
+        bool has_goal = false,
+             has_wall = false,
+             t_wall = true,
+             b_wall = true;
+
+        for (size_t k = corners[i].x; k < corners[j].x; k++) {
+          // is there a goal or wall on this tile?
+          const sok_pos_t pos = { k, corners[i].y };
+          has_goal = has_goal || tile_is_goal(ctx, pos);
+          has_wall = has_wall || tile_is_wall(ctx, pos);
+
+          // is there a wall above this tile?
+          const sok_pos_t t_pos = { k, corners[i].y - 1 };
+          t_wall = t_wall && tile_is_wall(ctx, t_pos);
+
+          // is there a wall below this tile?
+          const sok_pos_t b_pos = { k, corners[i].y + 1 };
+          b_wall = b_wall && tile_is_wall(ctx, b_pos);
+        }
+
+        if (!has_goal && !has_wall && (t_wall || b_wall)) {
+          // emit dead edge (horizontal)
+          sok_ctx_add_dead_edge(ctx, corners[i], corners[j]);
+
+          // flag corners as used
+          used[i] = true;
+          used[j] = true;
+        }
+      }
     }
   }
 
-  return false;
-}
-
-void
-sok_ctx_init(sok_ctx_t * const ctx, void *user_data) {
-  memset(ctx, 0, sizeof(sok_ctx_t));
-  ctx->user_data = user_data;
+  for (size_t i = 0; i < num_corners; i++) {
+    if (!used[i]) {
+      // emit dead edge (single tile)
+      sok_ctx_add_dead_edge(ctx, corners[i], corners[i]);
+    }
+  }
 }
 
 bool
@@ -301,8 +469,15 @@ sok_ctx_set_level(
   ctx->home = ctx->level.home;
   memcpy(ctx->boxes, ctx->level.boxes, ctx->level.num_boxes * sizeof(sok_pos_t));
 
-  // count number of goals left and check whether there are
+  // count number of goals left
   ctx->num_goals_left = sok_ctx_count_goals_left(ctx);
+
+  // find dead edges in level
+  // (used by solver to reject invalid moves quickly)
+  ctx->num_dead_edges = 0;
+  sok_ctx_find_dead_edges(ctx);
+
+  // check whether there are stuck boxes
   ctx->is_lost = sok_ctx_has_stuck_boxes(ctx);
 
   // return success
@@ -317,7 +492,7 @@ tile_is_floor(
   return (
     (pos.x < SOK_LEVEL_MAX_WIDTH - 1) &&
     (pos.y < SOK_LEVEL_MAX_HEIGHT - 1) &&
-    !ctx_is_wall(ctx, pos)
+    !tile_is_wall(ctx, pos)
   );
 }
 
@@ -380,7 +555,7 @@ sok_ctx_move_box(
                box_ofs = pos_find(old_pos, ctx->boxes, num_boxes);
 
   if (box_ofs < num_boxes) {
-    // update box and goal count
+    // update box count, goal count, and stuck box bool
     ctx->boxes[box_ofs] = new_pos;
     ctx->num_goals_left = sok_ctx_count_goals_left(ctx);
     ctx->is_lost = sok_ctx_has_stuck_boxes(ctx);
@@ -541,7 +716,7 @@ bool sok_ctx_walk(
         .x = i % ctx->level.size.x,
       };
 
-      if (ctx_is_wall(ctx, pos)) {
+      if (tile_is_wall(ctx, pos)) {
         // emit wall
         if (!cbs->on_wall(ctx, pos, data)) {
           return false;
diff --git a/src/core/sok.h b/src/core/sok.h
index d24d22b..0acb1ff 100644
--- a/src/core/sok.h
+++ b/src/core/sok.h
@@ -120,6 +120,7 @@ typedef struct {
 /***********/
 
 #define SOK_CTX_MAX_MOVES 1024
+#define SOK_CTX_MAX_DEAD_EDGES 1024
 
 typedef struct {
   sok_level_t level;
@@ -140,6 +141,11 @@ typedef struct {
   // box positions
   sok_pos_t boxes[SOK_LEVEL_MAX_BOXES];
 
+  struct {
+    sok_pos_t src, dst;
+  } dead_edges[SOK_CTX_MAX_DEAD_EDGES];
+  size_t num_dead_edges;
+
   // user data
   void *user_data;
 } sok_ctx_t;
diff --git a/src/sdl/main.c b/src/sdl/main.c
index 83ea51e..852a5ae 100644
--- a/src/sdl/main.c
+++ b/src/sdl/main.c
@@ -131,6 +131,19 @@ set_level(
     draw_ctx->level->name,
     (int) level_num
   );
+
+  if (false) {
+    // log dead edges (disabled)
+    for (size_t i = 0; i < ctx->num_dead_edges; i++) {
+      SDL_Log(
+        "dead edge: [%u, %u] => [%u, %u]",
+        ctx->dead_edges[i].src.x,
+        ctx->dead_edges[i].src.y,
+        ctx->dead_edges[i].dst.x,
+        ctx->dead_edges[i].dst.y
+      );
+    }
+  }
 }
 
 static void