From fa56925a5de7384c03f4775822444095d38bf3ac Mon Sep 17 00:00:00 2001 From: Paul Duncan Date: Tue, 8 Jan 2019 11:33:24 -0500 Subject: simplify move logic, add cache and solver --- meson.build | 2 + src/libsok/sok-cache.c | 135 +++++++++++++++++ src/libsok/sok-ctx.c | 400 +++++++++++-------------------------------------- src/libsok/sok-solve.c | 77 ++++++++++ src/libsok/sok.h | 27 ++++ 5 files changed, 328 insertions(+), 313 deletions(-) create mode 100644 src/libsok/sok-cache.c create mode 100644 src/libsok/sok-solve.c diff --git a/meson.build b/meson.build index 9ae6cb6..1a52bbe 100644 --- a/meson.build +++ b/meson.build @@ -3,6 +3,8 @@ project('sok', 'c', default_options: ['c_std=c11']) sources = [ 'src/libsok/sok-level-parser.c', 'src/libsok/sok-ctx.c', + 'src/libsok/sok-cache.c', + 'src/libsok/sok-solve.c', ] # text interface diff --git a/src/libsok/sok-cache.c b/src/libsok/sok-cache.c new file mode 100644 index 0000000..748614e --- /dev/null +++ b/src/libsok/sok-cache.c @@ -0,0 +1,135 @@ +#include // bool +#include // uint64_t +#include // bsearch(), qsort() +#include "sok.h" + +#define UNUSED(a) ((void) (a)) +#define GROW_SIZE (4096 / sizeof(uint64_t)) + +static uint64_t +hash_ctx( + const sok_ctx_t * const ctx +) { + UNUSED(ctx); + // TODO + return 0; +} + +static int +u64_cmp( + const void * const ap, + const void * const bp +) { + const uint64_t a = *((uint64_t*) ap), + b = *((uint64_t*) bp); + + return (a > b) ? -1 : ((a == b) ? 0 : 1); +} + +static bool +sok_cache_grow( + sok_cache_t * const cache +) { + // calculate new capacity + const size_t new_capacity = cache->capacity + GROW_SIZE; + if (new_capacity < cache->capacity) { + return false; + } + + // reallocate memory + uint64_t * const vals = realloc(cache->vals, new_capacity); + if (!vals) { + return false; + } + + // update data + cache->vals = vals; + cache->capacity = new_capacity; + + // return success + return true; +} + +static bool +sok_cache_has_hash( + const sok_cache_t * const cache, + const uint64_t hash +) { + return !!bsearch( + &hash, + cache->vals, + cache->num_vals, + sizeof(uint64_t), + u64_cmp + ); +} + +bool +sok_cache_has( + const sok_cache_t * const cache, + const sok_ctx_t * const ctx +) { + return sok_cache_has_hash(cache, hash_ctx(ctx)); +} + +bool +sok_cache_add( + sok_cache_t * const cache, + const sok_ctx_t * const ctx +) { + // hash context + const uint64_t hash = hash_ctx(ctx); + + // check for duplicates + if (sok_cache_has_hash(cache, hash)) { + return true; + } + + // check capacity + if (cache->num_vals >= cache->capacity) { + // grow cache + if (!sok_cache_grow(cache)) { + // return failure + return false; + } + } + + // append hash, sort values + cache->vals[cache->num_vals++] = hash_ctx(ctx); + qsort(cache->vals, cache->num_vals, sizeof(uint64_t), u64_cmp); + + // return success + return true; +} + +bool +sok_cache_init( + sok_cache_t * const cache, + const size_t capacity +) { + // alloc memory, check for error + uint64_t * const vals = malloc(sizeof(uint64_t) * capacity); + if (!vals) { + // return failure + return false; + } + + // populate cache + cache->vals = vals; + cache->num_vals = 0; + cache->capacity = capacity; + + // return success + return true; +} + +void +sok_cache_fini( + sok_cache_t * const cache +) { + if (cache->vals) { + // free memory + free(cache->vals); + cache->vals = NULL; + } +} 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 diff --git a/src/libsok/sok-solve.c b/src/libsok/sok-solve.c new file mode 100644 index 0000000..6637feb --- /dev/null +++ b/src/libsok/sok-solve.c @@ -0,0 +1,77 @@ +#include +#include "sok.h" + +#define UNUSED(a) ((void) (a)) + +static bool +sok_solve_step( + sok_ctx_t * const ctx, + sok_cache_t * const cache, + void (*on_error)(const char * const) +) { + for (size_t dir = 0; dir < SOK_DIR_LAST; dir++) { + if (!sok_ctx_move(ctx, dir)) { + continue; + } + + if (!sok_cache_has(cache, ctx)) { + // check for success + if (sok_ctx_is_done(ctx)) { + // return success + return true; + } + + // add to cache + if (!sok_cache_add(cache, ctx)) { + if (on_error) { + // log error + on_error("sok_cache_add() failed"); + } + + // return failure + return false; + } + + // recurse, check for success + if (sok_solve_step(ctx, cache, on_error)) { + // return success + return true; + } + } + + if (!sok_ctx_undo(ctx)) { + if (on_error) { + // log error + on_error("sok_ctx_undo() failed"); + } + + // return failure + return false; + } + } + + // return failure + return false; +} + +bool +sok_solve( + sok_ctx_t * const ctx, + void (*on_error)(const char * const) +) { + // init cache + sok_cache_t cache; + if (!sok_cache_init(&cache, SOK_CACHE_DEFAULT_CAPACITY)) { + on_error("sok_cache_init() failed"); + return false; + } + + // solve + const bool r = sok_solve_step(ctx, &cache, on_error); + + // finalize cache + sok_cache_fini(&cache); + + // return result + return r; +} diff --git a/src/libsok/sok.h b/src/libsok/sok.h index 7635ead..074fbf6 100644 --- a/src/libsok/sok.h +++ b/src/libsok/sok.h @@ -6,6 +6,7 @@ extern "C" { #endif /* __cplusplus */ #include // uint16_t +#include // size_t /*********/ /* types */ @@ -174,6 +175,32 @@ _Bool sok_ctx_walk( void * const ); +/*********/ +/* cache */ +/*********/ + +#define SOK_CACHE_DEFAULT_CAPACITY 1024 + +typedef struct { + uint64_t *vals; + size_t num_vals, capacity; +} sok_cache_t; + +_Bool sok_cache_init(sok_cache_t * const, const size_t); +void sok_cache_fini(sok_cache_t * const); + +_Bool sok_cache_has(const sok_cache_t * const, const sok_ctx_t * const); +_Bool sok_cache_add(sok_cache_t * const, const sok_ctx_t * const); + +/*********/ +/* solve */ +/*********/ + +_Bool sok_solve( + sok_ctx_t * const, + void (*on_error)(const char * const) +); + #ifdef __cplusplus }; #endif /* __cplusplus */ -- cgit v1.2.3