From 4b5af8da20f2e35e6cd81a4e7418767e6964e8bc Mon Sep 17 00:00:00 2001 From: Paul Duncan Date: Sun, 20 Jan 2019 10:27:10 -0500 Subject: solve: check for corners --- src/core/sok-ctx.c | 163 ++++++++++++++++++++++++--------------------------- src/core/sok-solve.c | 13 ++-- src/core/sok.h | 4 +- 3 files changed, 85 insertions(+), 95 deletions(-) (limited to 'src') diff --git a/src/core/sok-ctx.c b/src/core/sok-ctx.c index e278af1..036bf66 100644 --- a/src/core/sok-ctx.c +++ b/src/core/sok-ctx.c @@ -183,6 +183,52 @@ pos_find( 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; +} + +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, + }); + + // left + const bool l = ctx_is_wall(ctx, (sok_pos_t) { + .x = pos.x - 1, + .y = pos.y, + }); + + // bottom + const bool b = ctx_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 @@ -201,73 +247,29 @@ sok_ctx_count_goals_left( return r; } -/* - * static bool - * sok_ctx_has_corner_boxes( - * const sok_ctx_t * const ctx - * ) { - * for (size_t i = 0; i < ctx->level.num_boxes; i++) { - * // right - * const bool r = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x + 1, - * .y = ctx->boxes[i].y, - * }); - * - * // top-right - * const bool tr = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x + 1, - * .y = ctx->boxes[i].y - 1, - * }); - * - * // top - * const bool t = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x, - * .y = ctx->boxes[i].y - 1, - * }); - * - * // top-left - * const bool tl = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x - 1, - * .y = ctx->boxes[i].y - 1, - * }); - * - * // left - * const bool l = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x - 1, - * .y = ctx->boxes[i].y, - * }); - * - * // bottom-left - * const bool bl = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x - 1, - * .y = ctx->boxes[i].y + 1, - * }); - * - * // bottom - * const bool b = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x, - * .y = ctx->boxes[i].y + 1, - * }); - * - * const bool br = ctx_is_wall(ctx, (sok_pos_t) { - * .x = ctx->boxes[i].x + 1, - * .y = ctx->boxes[i].y + 1, - * }); - * - * if ( - * (r && tr && t) || // top-right - * (t && tl && l) || // top-left - * (l && bl && b) || // bottom-left - * (b && br && r) // bottom-right - * ) { - * // return - * return true; - * } - * } - * - * return false; - * } - */ +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]) + ); +} + +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; +} void sok_ctx_init(sok_ctx_t * const ctx, void *user_data) { @@ -301,7 +303,7 @@ sok_ctx_set_level( // count number of goals left and check whether there are ctx->num_goals_left = sok_ctx_count_goals_left(ctx); - // ctx->is_lost = sok_ctx_is_lost(ctx); + ctx->is_lost = sok_ctx_has_stuck_boxes(ctx); // return success return true; @@ -328,15 +330,6 @@ tile_is_box( return pos_find(pos, ctx->boxes, num_boxes) < num_boxes; } -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; -} - static bool sok_ctx_push_move( sok_ctx_t * const ctx, @@ -390,7 +383,7 @@ sok_ctx_move_box( // update box and goal count ctx->boxes[box_ofs] = new_pos; ctx->num_goals_left = sok_ctx_count_goals_left(ctx); - // ctx->is_lost = sok_ctx_has_corner_boxes(ctx); + ctx->is_lost = sok_ctx_has_stuck_boxes(ctx); // return success return true; @@ -407,14 +400,12 @@ sok_ctx_is_done( return ctx->num_goals_left == 0; } -/* - * bool - * sok_ctx_is_lost( - * const sok_ctx_t * const ctx - * ) { - * return ctx->is_lost; - * } - */ +bool +sok_ctx_is_lost( + const sok_ctx_t * const ctx +) { + return ctx->is_lost; +} bool sok_ctx_move( diff --git a/src/core/sok-solve.c b/src/core/sok-solve.c index 45d227c..0d4e500 100644 --- a/src/core/sok-solve.c +++ b/src/core/sok-solve.c @@ -36,13 +36,12 @@ sok_solve_step( // return failure return false; } -/* - * // make sure level is solvable - * if (sok_ctx_is_lost(ctx)) { - * // return failure - * return false; - * } - */ + + // make sure level is solvable + if (sok_ctx_is_lost(ctx)) { + // return failure + return false; + } for (size_t dir = 0; dir < SOK_DIR_LAST; dir++) { if (!sok_ctx_move(ctx, dir)) { diff --git a/src/core/sok.h b/src/core/sok.h index 92fb4e7..d24d22b 100644 --- a/src/core/sok.h +++ b/src/core/sok.h @@ -132,7 +132,7 @@ typedef struct { size_t num_goals_left; // are there boxes in corners? - // _Bool is_lost; + _Bool is_lost; // player position sok_pos_t home; @@ -149,7 +149,7 @@ void sok_ctx_init(sok_ctx_t * const ctx, void *user_data); _Bool sok_ctx_set_level(sok_ctx_t * const ctx, const char * const level); _Bool sok_ctx_is_done(const sok_ctx_t * const); -// _Bool sok_ctx_is_lost(const sok_ctx_t * const); +_Bool sok_ctx_is_lost(const sok_ctx_t * const); _Bool sok_ctx_move(sok_ctx_t * const, const sok_dir_t); _Bool sok_ctx_undo(sok_ctx_t * const); -- cgit v1.2.3