From 119e48bfa0f20686bc7cb0fd43323a7648aa598a Mon Sep 17 00:00:00 2001 From: Paul Duncan Date: Mon, 21 Jan 2019 17:11:37 -0500 Subject: use dead edges to improve solver speed --- src/core/sok-ctx.c | 367 +++++++++++++++++++++++++++++++++++++++-------------- src/core/sok.h | 6 + 2 files changed, 277 insertions(+), 96 deletions(-) (limited to 'src/core') 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; -- cgit v1.2.3