aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/core/sok-ctx.c367
-rw-r--r--src/core/sok.h6
-rw-r--r--src/sdl/main.c13
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
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-22 04:53:10 +0000