simplify move logic, add cache and solver

1 files changed, 87 insertions, 313 deletions

diff --git a/src/libsok/sok-ctx.c b/src/libsok/sok-ctx.c
index cc6b1ce..d9985d7 100644
--- a/src/libsok/sok-ctx.c
+++ b/src/libsok/sok-ctx.c
@@ -191,116 +191,37 @@ tile_is_floor(
   );
 }
 
-static bool
-tile_is_box(
-  const sok_ctx_t * const ctx,
-  const sok_pos_t pos
+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 < ctx->level.num_boxes; i++) {
-    if (POINTS_EQUAL(ctx->boxes[i], pos)) {
-      return true;
+  for (size_t i = 0; i < len; i++) {
+    if (POINTS_EQUAL(pos, set[i])) {
+      return i;
     }
   }
 
-  return false;
+  return len;
 }
 
 static bool
-tile_is_goal(
+tile_is_box(
   const sok_ctx_t * const ctx,
   const sok_pos_t pos
 ) {
-  for (size_t i = 0; i < ctx->level.num_goals; i++) {
-    if (POINTS_EQUAL(pos, ctx->level.goals[i])) {
-      return true;
-    }
-  }
-
-  return false;
+  const size_t num_boxes = ctx->level.num_boxes;
+  return pos_find(pos, ctx->boxes, num_boxes) < num_boxes;
 }
 
 static bool
-sok_can_move(
-  sok_ctx_t * const ctx,
-  const sok_dir_t dir
+tile_is_goal(
+  const sok_ctx_t * const ctx,
+  const sok_pos_t pos
 ) {
-  if (ctx->num_moves >= SOK_CTX_MAX_MOVES - 1) {
-    // no more move slots available
-    return false;
-  }
-
-  if (dir == SOK_DIR_UP) {
-    const sok_pos_t ps[2] = {
-      { .x = ctx->home.x, .y = ctx->home.y - 1 },
-      { .x = ctx->home.x, .y = ctx->home.y - 2 },
-    };
-
-    return ((
-      (ctx->home.y > 0) &&
-      tile_is_floor(ctx, ps[0]) &&
-      !tile_is_box(ctx, ps[0])
-    ) || (
-      (ctx->home.y > 1) &&
-      tile_is_floor(ctx, ps[0]) &&
-      tile_is_box(ctx, ps[0]) &&
-      tile_is_floor(ctx, ps[1]) &&
-      !tile_is_box(ctx, ps[1])
-    ));
-  } else if (dir == SOK_DIR_DOWN) {
-    const sok_pos_t ps[2] = {
-      { .x = ctx->home.x, .y = ctx->home.y + 1 },
-      { .x = ctx->home.x, .y = ctx->home.y + 2 },
-    };
-
-    return ((
-      (ctx->home.y < SOK_LEVEL_MAX_HEIGHT - 1) &&
-      tile_is_floor(ctx, ps[0]) &&
-      !tile_is_box(ctx, ps[0])
-    ) || (
-      (ctx->home.y < SOK_LEVEL_MAX_HEIGHT - 2) &&
-      tile_is_floor(ctx, ps[0]) &&
-      tile_is_box(ctx, ps[0]) &&
-      tile_is_floor(ctx, ps[1]) &&
-      !tile_is_box(ctx, ps[1])
-    ));
-  } else if (dir == SOK_DIR_LEFT) {
-    const sok_pos_t ps[2] = {
-      { .x = ctx->home.x - 1, .y = ctx->home.y },
-      { .x = ctx->home.x - 2, .y = ctx->home.y },
-    };
-
-    return ((
-      (ctx->home.x > 0) &&
-      tile_is_floor(ctx, ps[0]) &&
-      !tile_is_box(ctx, ps[0])
-    ) || (
-      (ctx->home.x > 1) &&
-      tile_is_floor(ctx, ps[0]) &&
-      tile_is_box(ctx, ps[0]) &&
-      tile_is_floor(ctx, ps[1]) &&
-      !tile_is_box(ctx, ps[1])
-    ));
-  } else if (dir == SOK_DIR_RIGHT) {
-    const sok_pos_t ps[2] = {
-      { .x = ctx->home.x + 1, .y = ctx->home.y },
-      { .x = ctx->home.x + 2, .y = ctx->home.y },
-    };
-
-    return ((
-      (ctx->home.x < SOK_LEVEL_MAX_WIDTH - 1) &&
-      tile_is_floor(ctx, ps[0]) &&
-      !tile_is_box(ctx, ps[0])
-    ) || (
-      (ctx->home.x < SOK_LEVEL_MAX_WIDTH - 2) &&
-      tile_is_floor(ctx, ps[0]) &&
-      tile_is_box(ctx, ps[0]) &&
-      tile_is_floor(ctx, ps[1]) &&
-      !tile_is_box(ctx, ps[1])
-    ));
-  }
-
-  // return failure
-  return false;
+  const size_t num_goals = ctx->level.num_goals;
+  return pos_find(pos, ctx->level.goals, num_goals) < num_goals;
 }
 
 static bool
@@ -349,11 +270,12 @@ sok_ctx_move_box(
   const sok_pos_t old_pos,
   const sok_pos_t new_pos
 ) {
-  for (size_t i = 0; i < ctx->level.num_boxes; i++) {
-    if (POINTS_EQUAL(ctx->boxes[i], old_pos)) {
-      ctx->boxes[i] = new_pos;
-      return true;
-    }
+  const size_t num_boxes = ctx->level.num_boxes,
+               box_ofs = pos_find(old_pos, ctx->boxes, num_boxes);
+
+  if (box_ofs < num_boxes) {
+    ctx->boxes[box_ofs] = new_pos;
+    return true;
   }
 
   return false;
@@ -364,17 +286,7 @@ sok_ctx_is_done(
   sok_ctx_t * const ctx
 ) {
   for (size_t i = 0; i < ctx->level.num_goals; i++) {
-    bool on_goal = false;
-
-    for (size_t j = 0; !on_goal && j < ctx->level.num_boxes; j++) {
-      if (POINTS_EQUAL(ctx->level.goals[i], ctx->boxes[j])) {
-        // found box on this goal
-        on_goal = true;
-      }
-    }
-
-    if (!on_goal) {
-      // no box on this goal, return false
+    if (!tile_is_box(ctx, ctx->level.goals[i])) {
       return false;
     }
   }
@@ -388,186 +300,75 @@ sok_ctx_move(
   sok_ctx_t * const ctx,
   const sok_dir_t dir
 ) {
-  if (!sok_can_move(ctx, dir)) {
+  if (ctx->num_moves >= SOK_CTX_MAX_MOVES - 1) {
+    // no more move slots available
     return false;
   }
 
-  if (dir == SOK_DIR_UP) {
-    const sok_pos_t ps[2] = {
-      { .x = ctx->home.x, .y = ctx->home.y - 1 },
-      { .x = ctx->home.x, .y = ctx->home.y - 2 },
-    };
-
-    if (
-      (ctx->home.y > 0) &&
-      tile_is_floor(ctx, ps[0]) &&
-      !tile_is_box(ctx, ps[0])
-    ) { 
-      // push move
-      if (!sok_ctx_push_move(ctx, dir, false)) {
-        return false;
-      }
-
-      // update position
-      ctx->home.y--;
-
-      // return success
-      return true;
-    } else if (
-      (ctx->home.y > 1) &&
-      tile_is_floor(ctx, ps[0]) &&
-      tile_is_box(ctx, ps[0]) &&
-      tile_is_floor(ctx, ps[1]) &&
-      !tile_is_box(ctx, ps[1])
-    ) { 
-      // push move
-      if (!sok_ctx_push_move(ctx, dir, true)) {
-        return false;
-      }
-
-      // move box
-      if (!sok_ctx_move_box(ctx, ps[0], ps[1])) {
-        return false;
-      }
-
-      // update position
-      ctx->home.y--;
-
-      // return success
-      return true;
+  const sok_pos_t ps[2] = {{
+    .x = ctx->home.x + ((dir == SOK_DIR_LEFT) ? -1 : ((dir == SOK_DIR_RIGHT) ? 1 : 0)),
+    .y = ctx->home.y + ((dir == SOK_DIR_UP) ? -1 : ((dir == SOK_DIR_DOWN) ? 1 : 0))
+  }, {
+    .x = ctx->home.x + ((dir == SOK_DIR_LEFT) ? -2 : ((dir == SOK_DIR_RIGHT) ? 2 : 0)),
+    .y = ctx->home.y + ((dir == SOK_DIR_UP) ? -2 : ((dir == SOK_DIR_DOWN) ? 2 : 0))
+  }};
+
+  const bool can_move = (
+    (dir == SOK_DIR_UP) ? (ctx->home.y > 0) : 
+    ((dir == SOK_DIR_DOWN) ? (ctx->home.y < SOK_LEVEL_MAX_HEIGHT - 1) :
+    ((dir == SOK_DIR_LEFT) ? (ctx->home.x > 0) : 
+    ((dir == SOK_DIR_RIGHT) ? (ctx->home.x < SOK_LEVEL_MAX_WIDTH - 1) : 
+    false
+  ))));
+
+  const bool can_push = (
+    (dir == SOK_DIR_UP) ? (ctx->home.y > 1) : 
+    ((dir == SOK_DIR_DOWN) ? (ctx->home.y < SOK_LEVEL_MAX_HEIGHT - 2) :
+    ((dir == SOK_DIR_LEFT) ? (ctx->home.x > 1) : 
+    ((dir == SOK_DIR_RIGHT) ? (ctx->home.x < SOK_LEVEL_MAX_WIDTH - 2) : 
+    false
+  ))));
+
+  if (
+    can_move &&
+    tile_is_floor(ctx, ps[0]) &&
+    !tile_is_box(ctx, ps[0])
+  ) { 
+    // push move
+    if (!sok_ctx_push_move(ctx, dir, false)) {
+      return false;
     }
-  } else if (dir == SOK_DIR_DOWN) {
-    const sok_pos_t ps[2] = {
-      { .x = ctx->home.x, .y = ctx->home.y + 1 },
-      { .x = ctx->home.x, .y = ctx->home.y + 2 },
-    };
 
-    if (
-      (ctx->home.y < SOK_LEVEL_MAX_HEIGHT - 1) &&
-      tile_is_floor(ctx, ps[0]) &&
-      !tile_is_box(ctx, ps[0])
-    ) {
-      // push move
-      if (!sok_ctx_push_move(ctx, dir, false)) {
-        return false;
-      }
-
-      // update position
-      ctx->home.y++;
-
-      // return success
-      return true;
-    } else if (
-      (ctx->home.y < SOK_LEVEL_MAX_HEIGHT - 2) &&
-      tile_is_floor(ctx, ps[0]) &&
-      tile_is_box(ctx, ps[0]) &&
-      tile_is_floor(ctx, ps[1]) &&
-      !tile_is_box(ctx, ps[1])
-    ) {
-      // push move
-      if (!sok_ctx_push_move(ctx, dir, true)) {
-        return false;
-      }
-
-      // move box
-      if (!sok_ctx_move_box(ctx, ps[0], ps[1])) {
-        return false;
-      }
-
-      // update position
-      ctx->home.y++;
-
-      // return success
-      return true;
+    // update position
+    ctx->home.x += (dir == SOK_DIR_LEFT) ? -1 : ((dir == SOK_DIR_RIGHT) ? 1 : 0);
+    ctx->home.y += (dir == SOK_DIR_UP) ? -1 : ((dir == SOK_DIR_DOWN) ? 1 : 0);
+
+    // return success
+    return true;
+  } else if (
+    can_push &&
+    tile_is_floor(ctx, ps[0]) &&
+    tile_is_box(ctx, ps[0]) &&
+    tile_is_floor(ctx, ps[1]) &&
+    !tile_is_box(ctx, ps[1])
+  ) { 
+    // push move
+    if (!sok_ctx_push_move(ctx, dir, true)) {
+      return false;
     }
-  } else if (dir == SOK_DIR_LEFT) {
-    const sok_pos_t ps[2] = {
-      { .x = ctx->home.x - 1, .y = ctx->home.y },
-      { .x = ctx->home.x - 2, .y = ctx->home.y },
-    };
-
-    if (
-      (ctx->home.x > 1) &&
-      tile_is_floor(ctx, ps[0]) &&
-      !tile_is_box(ctx, ps[0])
-    ) { 
-      // push move
-      if (!sok_ctx_push_move(ctx, dir, false)) {
-        return false;
-      }
-
-      // update position
-      ctx->home.x--;
-
-      // return success
-      return true;
-    } else if (
-      (ctx->home.x > 1) &&
-      tile_is_floor(ctx, ps[0]) &&
-      tile_is_box(ctx, ps[0]) &&
-      tile_is_floor(ctx, ps[1]) &&
-      !tile_is_box(ctx, ps[1])
-    ) {
-      // push move
-      if (!sok_ctx_push_move(ctx, dir, true)) {
-        return false;
-      }
 
-      // move box
-      if (!sok_ctx_move_box(ctx, ps[0], ps[1])) {
-        return false;
-      }
-
-      // update position
-      ctx->home.x--;
-
-      // return success
-      return true;
+    // move box
+    if (!sok_ctx_move_box(ctx, ps[0], ps[1])) {
+      return false;
     }
-  } else if (dir == SOK_DIR_RIGHT) {
-    const sok_pos_t ps[2] = {
-      { .x = ctx->home.x + 1, .y = ctx->home.y },
-      { .x = ctx->home.x + 2, .y = ctx->home.y },
-    };
-
-    if (
-      (ctx->home.x < SOK_LEVEL_MAX_WIDTH - 1) &&
-      tile_is_floor(ctx, ps[0]) &&
-      !tile_is_box(ctx, ps[0])
-    ) {
-      // push move
-      if (!sok_ctx_push_move(ctx, dir, false)) {
-        return false;
-      }
-
-      // update position
-      ctx->home.x++;
-
-      // return success
-      return true;
-    } else if (
-      (ctx->home.x < SOK_LEVEL_MAX_WIDTH - 2) &&
-      tile_is_floor(ctx, ps[0]) &&
-      tile_is_box(ctx, ps[0]) && 
-      tile_is_floor(ctx, ps[1]) &&
-      !tile_is_box(ctx, ps[1])
-    ) {
-      // push move
-      if (!sok_ctx_push_move(ctx, dir, true)) {
-        return false;
-      }
 
-      // move box
-      if (!sok_ctx_move_box(ctx, ps[0], ps[1])) {
-        return false;
-      }
+    // update position
+    ctx->home.x += (dir == SOK_DIR_LEFT) ? -1 : ((dir == SOK_DIR_RIGHT) ? 1 : 0);
+    ctx->home.y += (dir == SOK_DIR_UP) ? -1 : ((dir == SOK_DIR_DOWN) ? 1 : 0);
 
-      // update position
-      ctx->home.x++;
 
-      // return success
-      return true;
-    }
+    // return success
+    return true;
   }
 
   // return failure
@@ -585,39 +386,12 @@ sok_ctx_undo(
   }
 
   if (move.is_push) {
-    switch (move.dir) {
-    case SOK_DIR_UP:
-      {
-        const sok_pos_t box_pos = { move.pos.x, move.pos.y - 2 };
-        sok_ctx_move_box(ctx, box_pos, ctx->home);
-      }
-
-      break;
-    case SOK_DIR_DOWN:
-      {
-        const sok_pos_t box_pos = { move.pos.x, move.pos.y + 2 };
-        sok_ctx_move_box(ctx, box_pos, ctx->home);
-      }
-
-      break;
-    case SOK_DIR_LEFT:
-      {
-        const sok_pos_t box_pos = { move.pos.x - 2, move.pos.y };
-        sok_ctx_move_box(ctx, box_pos, ctx->home);
-      }
-
-      break;
-    case SOK_DIR_RIGHT:
-      {
-        const sok_pos_t box_pos = { move.pos.x + 2, move.pos.y };
-        sok_ctx_move_box(ctx, box_pos, ctx->home);
-      }
+    const sok_pos_t box_pos = {
+      .x = move.pos.x + ((move.dir == SOK_DIR_LEFT) ? -2 : ((move.dir == SOK_DIR_RIGHT) ? 2 : 0)),
+      .y = move.pos.y + ((move.dir == SOK_DIR_UP) ? -2 : ((move.dir == SOK_DIR_DOWN) ? 2 : 0)),
+    };
 
-      break;
-    default:
-      // never reached
-      return false;
-    }
+    sok_ctx_move_box(ctx, box_pos, ctx->home);
   }
 
   // update position