From 3e658ed87b5795b2be8f50d683dc19241aba0111 Mon Sep 17 00:00:00 2001 From: Paul Duncan Date: Tue, 15 Jan 2019 09:16:56 -0500 Subject: s/libsok/core/g --- src/core/sok-cache.c | 168 +++++++++++ src/core/sok-ctx-hash.c | 41 +++ src/core/sok-ctx.c | 636 ++++++++++++++++++++++++++++++++++++++++++ src/core/sok-level-parser.c | 193 +++++++++++++ src/core/sok-solve.c | 89 ++++++ src/core/sok.h | 257 +++++++++++++++++ src/libsok/sok-cache.c | 168 ----------- src/libsok/sok-ctx-hash.c | 41 --- src/libsok/sok-ctx.c | 636 ------------------------------------------ src/libsok/sok-level-parser.c | 193 ------------- src/libsok/sok-solve.c | 89 ------ src/libsok/sok.h | 257 ----------------- src/sdl/action.c | 2 +- src/sdl/draw.h | 2 +- src/sdl/main.c | 2 +- src/sdl/text-style.h | 2 +- src/solve/main.c | 2 +- src/text/action.c | 2 +- src/text/draw.c | 2 +- src/text/draw.h | 2 +- src/text/levels.c | 2 +- src/text/main.c | 2 +- 22 files changed, 1394 insertions(+), 1394 deletions(-) create mode 100644 src/core/sok-cache.c create mode 100644 src/core/sok-ctx-hash.c create mode 100644 src/core/sok-ctx.c create mode 100644 src/core/sok-level-parser.c create mode 100644 src/core/sok-solve.c create mode 100644 src/core/sok.h delete mode 100644 src/libsok/sok-cache.c delete mode 100644 src/libsok/sok-ctx-hash.c delete mode 100644 src/libsok/sok-ctx.c delete mode 100644 src/libsok/sok-level-parser.c delete mode 100644 src/libsok/sok-solve.c delete mode 100644 src/libsok/sok.h diff --git a/src/core/sok-cache.c b/src/core/sok-cache.c new file mode 100644 index 0000000..df3c729 --- /dev/null +++ b/src/core/sok-cache.c @@ -0,0 +1,168 @@ +#include // bool +#include // uint64_t +#include // bsearch(), qsort() +#include // memcpy +#include // debug +#include "sok.h" + +#define UNUSED(a) ((void) (a)) +#define GROW_SIZE (4096 / sizeof(uint64_t)) +#define USE_QSORT 1 + +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 * sizeof(uint64_t)); + 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 +) { +#if 0 + for (size_t i = 0; i < cache->num_vals; i++) { + if (cache->vals[i] == hash) { + return true; + } + } + + // return failure + return false; +#else + return !!bsearch( + &hash, + cache->vals, + cache->num_vals, + sizeof(uint64_t), + u64_cmp + ); +#endif /* 0 */ +} + +bool +sok_cache_has( + const sok_cache_t * const cache, + const sok_ctx_t * const ctx +) { + return sok_cache_has_hash(cache, sok_ctx_hash(ctx)); +} + +bool +sok_cache_add( + sok_cache_t * const cache, + const sok_ctx_t * const ctx +) { +/* + * // hash context + * const uint64_t hash = sok_ctx_hash(ctx); + * + * // check for duplicates + * if (sok_cache_has_hash(cache, hash)) { + * return false; + * } + */ + + // check capacity + if (cache->num_vals >= cache->capacity) { + // grow cache + if (!sok_cache_grow(cache)) { + // return failure + return false; + } + } + + // append hash + const uint64_t hash = sok_ctx_hash(ctx); +#if USE_QSORT + cache->vals[cache->num_vals] = hash; + cache->num_vals++; + + // sort values + qsort(cache->vals, cache->num_vals, sizeof(uint64_t), u64_cmp); +#else + size_t i; + for (i = 0; cache->vals[i] < hash && i < cache->num_vals; i++); + if (i < cache->num_vals) { + if (cache->vals[i] == hash) { + return true; + } + + // move remaining data + const size_t num_bytes = (cache->num_vals - i) * sizeof(uint64_t); + memmove(cache->vals + (i + 1), cache->vals + i, num_bytes); + + // insert value + cache->vals[i] = hash; + cache->num_vals++; + } else { + // append value + cache->vals[cache->num_vals] = hash; + cache->num_vals++; + } +#endif /* USE_QSORT */ + + // 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(capacity * sizeof(uint64_t)); + 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/core/sok-ctx-hash.c b/src/core/sok-ctx-hash.c new file mode 100644 index 0000000..61689ea --- /dev/null +++ b/src/core/sok-ctx-hash.c @@ -0,0 +1,41 @@ +#include // uint16_t +#include "sok.h" + +// fnv64 +// src: https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function +#define FNV_OFFSET 1099511628211 +#define FNV_PRIME 0xcbf29ce484222325 + +static uint64_t +fnv1a( + const uint8_t * const buf, + const size_t len +) { + uint64_t hash = FNV_OFFSET; + + for (size_t i = 0; i < len; i++) { + hash ^= buf[i]; + hash *= FNV_PRIME; + } + + return hash; +} + +uint64_t +sok_ctx_hash( + const sok_ctx_t * const ctx +) { + uint16_t buf[512] = {ctx->home.x, ctx->home.y, 0}; + const size_t BUF_MASK = (sizeof(buf) / sizeof(uint16_t) - 1); + + for (size_t i = 0; i < ctx->level.num_boxes; i++) { + buf[(2 * (i + 1) + 0) & BUF_MASK] = ctx->boxes[i].x; + buf[(2 * (i + 1) + 1) & BUF_MASK] = ctx->boxes[i].y; + } + + // calculate buffer length + const size_t used = 2 * (ctx->level.num_boxes + 1) * sizeof(uint16_t); + const size_t len = (used < sizeof(buf)) ? used : sizeof(buf); + + return fnv1a((uint8_t*) buf, len); +} diff --git a/src/core/sok-ctx.c b/src/core/sok-ctx.c new file mode 100644 index 0000000..e278af1 --- /dev/null +++ b/src/core/sok-ctx.c @@ -0,0 +1,636 @@ +#include +#include // memset() +#include "sok.h" + +#define UNUSED(a) ((void) (a)) + +#define VALID_POS(pos) ( \ + (pos).x < SOK_LEVEL_MAX_WIDTH && \ + (pos).y < SOK_LEVEL_MAX_HEIGHT \ +) + +#define POINTS_EQUAL(a, b) ( \ + ((a).x == (b).x) && \ + ((a).y == (b).y) \ +) + +static bool +ctx_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 void +ctx_set_wall( + sok_ctx_t * const ctx, + const sok_pos_t pos +) { + ctx->level.walls[pos.y * ctx->level.size.x + pos.x] = true; +} + +static void +ctx_clear_walls( + sok_ctx_t * const ctx +) { + memset(ctx->level.walls, 0, SOK_LEVEL_MAX_WIDTH * SOK_LEVEL_MAX_HEIGHT); +} + +static bool +on_size( + const sok_level_parser_t * const parser, + const sok_pos_t pos +) { + sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; + + if (!VALID_POS(pos)) { + // size out of bounds + return false; + } + + // save width and height + ctx->level.size = pos; + + // return success + return true; +} + +static bool +on_home( + const sok_level_parser_t * const parser, + const sok_pos_t pos +) { + sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; + + if (!VALID_POS(pos)) { + // position out of bounds + return false; + } + + // save start position + ctx->level.home = pos; + + // return success + return true; +} + +static bool +on_wall( + const sok_level_parser_t * const parser, + const sok_pos_t pos +) { + sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; + + if (!VALID_POS(pos)) { + // position out of bounds + return false; + } + + // save wall + ctx_set_wall(ctx, pos); + + // return sucess + return true; +} + +static bool +on_goal( + const sok_level_parser_t * const parser, + const sok_pos_t pos +) { + sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; + + if (!VALID_POS(pos)) { + // position out of bounds + return false; + } + + if (ctx->level.num_goals >= SOK_LEVEL_MAX_GOALS - 1) { + // too many goals + return false; + } + + // save goal + ctx->level.goals[ctx->level.num_goals++] = pos; + + // return sucess + return true; +} + +static bool +on_box( + const sok_level_parser_t * const parser, + const sok_pos_t pos +) { + sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; + + if (!VALID_POS(pos)) { + // position out of bounds + return false; + } + + if (ctx->level.num_boxes >= SOK_LEVEL_MAX_BOXES - 1) { + // too many boxes + return false; + } + + // save box + ctx->level.boxes[ctx->level.num_boxes++] = pos; + + // return sucess + return true; +} + +static bool +on_junk( + const sok_level_parser_t * const parser, + const size_t ofs, + const char tile +) { + UNUSED(parser); + UNUSED(ofs); + UNUSED(tile); + + // TODO + + // return sucess + return true; +} + +static const sok_level_parser_cbs_t +LEVEL_PARSER_CBS = { + .on_size = on_size, + .on_home = on_home, + .on_wall = on_wall, + .on_goal = on_goal, + .on_box = on_box, + .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 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_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; + * } + */ + +void +sok_ctx_init(sok_ctx_t * const ctx, void *user_data) { + memset(ctx, 0, sizeof(sok_ctx_t)); + ctx->user_data = user_data; +} + +bool +sok_ctx_set_level( + sok_ctx_t * const ctx, + const char * const str +) { + + // clear level + ctx->level.num_goals = 0; + ctx->level.num_boxes = 0; + ctx_clear_walls(ctx); + + // parse level + sok_level_parser_t parser; + sok_level_parser_init(&parser, &LEVEL_PARSER_CBS, ctx); + if (!sok_level_parser_parse(&parser, str, strlen(str))) { + // return failure + return false; + } + + // init moves, player, and boxes + ctx->num_moves = 0; + 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 + ctx->num_goals_left = sok_ctx_count_goals_left(ctx); + // ctx->is_lost = sok_ctx_is_lost(ctx); + + // return success + return true; +} + +static bool +tile_is_floor( + const sok_ctx_t * const ctx, + const sok_pos_t pos +) { + return ( + (pos.x < SOK_LEVEL_MAX_WIDTH - 1) && + (pos.y < SOK_LEVEL_MAX_HEIGHT - 1) && + !ctx_is_wall(ctx, pos) + ); +} + +static bool +tile_is_box( + const sok_ctx_t * const ctx, + const sok_pos_t pos +) { + const size_t num_boxes = ctx->level.num_boxes; + 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, + const sok_dir_t dir, + const bool is_push +) { + if (ctx->num_moves >= SOK_CTX_MAX_MOVES - 1) { + return false; + } + + ctx->moves[ctx->num_moves].pos = ctx->home; + ctx->moves[ctx->num_moves].dir = dir; + ctx->moves[ctx->num_moves].is_push = is_push; + ctx->num_moves++; + + return true; +} + +static bool +sok_ctx_pop_move( + sok_ctx_t * const ctx, + sok_move_t * const ret +) { + if (!ctx->num_moves) { + // return failure + return false; + } + + // decriment moves + ctx->num_moves--; + + if (ret) { + // save popped move + *ret = ctx->moves[ctx->num_moves]; + } + + // return success + return true; +} + +static bool +sok_ctx_move_box( + sok_ctx_t * const ctx, + const sok_pos_t old_pos, + const sok_pos_t new_pos +) { + const size_t num_boxes = ctx->level.num_boxes, + box_ofs = pos_find(old_pos, ctx->boxes, num_boxes); + + if (box_ofs < num_boxes) { + // 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); + + // return success + return true; + } + + // return failure + return false; +} + +bool +sok_ctx_is_done( + const sok_ctx_t * const ctx +) { + return ctx->num_goals_left == 0; +} + +/* + * bool + * sok_ctx_is_lost( + * const sok_ctx_t * const ctx + * ) { + * return ctx->is_lost; + * } + */ + +bool +sok_ctx_move( + sok_ctx_t * const ctx, + const sok_dir_t dir +) { + if (ctx->num_moves >= SOK_CTX_MAX_MOVES - 1) { + // no more move slots available + return false; + } + + 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; + } + + // 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; + } + + // 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); + + + // return success + return true; + } + + // return failure + return false; +} + +bool +sok_ctx_undo( + sok_ctx_t * const ctx +) { + sok_move_t move; + if (!sok_ctx_pop_move(ctx, &move)) { + // return failure + return false; + } + + if (move.is_push) { + 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)), + }; + + sok_ctx_move_box(ctx, box_pos, ctx->home); + } + + // update position + ctx->home = move.pos; + + // return success + return true; +} + +bool sok_ctx_walk( + const sok_ctx_t * const ctx, + const sok_ctx_walk_cbs_t * const cbs, + void * const data +) { + if (!cbs) { + return false; + } + + if (cbs->on_size) { + // emit size + if (!cbs->on_size(ctx, ctx->level.size, data)) { + return false; + } + } + + if (cbs->on_walls_start && !cbs->on_walls_start(ctx, data)) { + return false; + } + + if (cbs->on_wall) { + // walk walls + for (size_t i = 0; i < (ctx->level.size.x * ctx->level.size.y); i++) { + const sok_pos_t pos = { + .y = i / ctx->level.size.x, + .x = i % ctx->level.size.x, + }; + + if (ctx_is_wall(ctx, pos)) { + // emit wall + if (!cbs->on_wall(ctx, pos, data)) { + return false; + } + } + } + } + + if (cbs->on_walls_end && !cbs->on_walls_end(ctx, data)) { + return false; + } + + if (cbs->on_goals_start && !cbs->on_goals_start(ctx, data)) { + return false; + } + + if (cbs->on_goal) { + // walk goals + for (size_t i = 0; i < ctx->level.num_goals; i++) { + const bool has_player = POINTS_EQUAL(ctx->level.goals[i], ctx->home); + const bool has_box = tile_is_box(ctx, ctx->level.goals[i]); + + // emit goal + if (!cbs->on_goal(ctx, ctx->level.goals[i], has_player, has_box, data)) { + return false; + } + } + } + + if (cbs->on_goals_end && !cbs->on_goals_end(ctx, data)) { + return false; + } + + if (cbs->on_boxes_start && !cbs->on_boxes_start(ctx, data)) { + return false; + } + + if (cbs->on_home) { + const bool has_goal = tile_is_goal(ctx, ctx->home); + + // emit home + if (!cbs->on_home(ctx, ctx->home, has_goal, data)) { + return false; + } + } + + if (cbs->on_box) { + // walk boxes + for (size_t i = 0; i < ctx->level.num_boxes; i++) { + const bool has_goal = tile_is_goal(ctx, ctx->boxes[i]); + + // emit box + if (!cbs->on_box(ctx, ctx->boxes[i], has_goal, data)) { + return false; + } + } + } + + if (cbs->on_boxes_end && !cbs->on_boxes_end(ctx, data)) { + return false; + } + + if (cbs->on_moves_start && !cbs->on_moves_start(ctx, data)) { + return false; + } + + if (cbs->on_move) { + // walk moves + for (size_t i = 0; i < ctx->num_moves; i++) { + // emit move + if (!cbs->on_move(ctx, ctx->moves[i], data)) { + return false; + } + } + } + + if (cbs->on_moves_end && !cbs->on_moves_end(ctx, data)) { + return false; + } + + // return success + return true; +} diff --git a/src/core/sok-level-parser.c b/src/core/sok-level-parser.c new file mode 100644 index 0000000..276ebcb --- /dev/null +++ b/src/core/sok-level-parser.c @@ -0,0 +1,193 @@ +#include +#include // size_t +#include "sok.h" + +#define UNUSED(a) ((void) (a)) + +#define IS_DIGIT(c) ((c) >= '0' && (c) <= '9') +#define CASE_DIGIT \ + case '0': \ + case '1': \ + case '2': \ + case '3': \ + case '4': \ + case '5': \ + case '6': \ + case '7': \ + case '8': \ + case '9': + +void +sok_level_parser_init( + sok_level_parser_t * const parser, + const sok_level_parser_cbs_t * const cbs, + void * const user_data +) { + parser->cbs = cbs; + parser->user_data = user_data; +} + +bool +sok_level_parser_parse( + sok_level_parser_t * const parser, + const char * const buf, + const size_t buf_len +) { + sok_pos_t size = { .x = 0, .y = 0 }; + + for (size_t i = 0, ofs = 0, w = 0; i < buf_len; i++) { + if (buf[i] == '|') { + if (w > size.x) { + size.x = w; + } + + // reset column position, increment row count + w = 0; + size.y++; + } else if (IS_DIGIT(buf[i])) { + ofs = 10 * ofs + (buf[i] - '0'); + } else if (ofs > 0) { + w += ofs; + ofs = 0; + } else { + w++; + } + } + + // increment row count + size.y++; + + // emit level size + if ( + parser->cbs->on_size && + !parser->cbs->on_size(parser, size) + ) { + // return failure + return false; + } + + sok_pos_t pos = { 0, 0 }; + for (size_t i = 0, ofs = 0; i < buf_len; i++) { + switch (buf[i]) { + case '|': + // new line + pos.x = 0; + pos.y++; + + break; + CASE_DIGIT + ofs = 10 * ofs + (buf[i] - '0'); + break; + case '-': + case '_': + case ' ': + // advance + pos.x += (ofs > 0) ? ofs : 1; + ofs = 0; + + break; + case '+': + // emit goal + if (parser->cbs->on_goal && !parser->cbs->on_goal(parser, pos)) { + // return failure + return false; + } + + // emit home + if (parser->cbs->on_home && !parser->cbs->on_home(parser, pos)) { + // return failure + return false; + } + + // advance + pos.x++; + + break; + case '@': + // emit home + if (parser->cbs->on_home && !parser->cbs->on_home(parser, pos)) { + // return failure + return false; + } + + // advance + pos.x++; + + break; + case '#': + for (size_t j = (ofs > 0) ? ofs : 1; j; j--) { + // emit wall + if (parser->cbs->on_wall && !parser->cbs->on_wall(parser, pos)) { + // return failure + return false; + } + + // advance + pos.x++; + } + ofs = 0; + + break; + case '*': + for (size_t j = (ofs > 0) ? ofs : 1; j--;) { + // emit goal + if (parser->cbs->on_goal && !parser->cbs->on_goal(parser, pos)) { + // return failure + return false; + } + + // emit box + if (parser->cbs->on_box && !parser->cbs->on_box(parser, pos)) { + // return failure + return false; + } + + // advance + pos.x++; + } + ofs = 0; + + break; + case '.': + for (size_t j = (ofs > 0) ? ofs : 1; j--;) { + // emit goal + if (parser->cbs->on_goal && !parser->cbs->on_goal(parser, pos)) { + // return failure + return false; + } + + // advance + pos.x++; + } + ofs = 0; + + break; + case '$': + for (size_t j = (ofs > 0) ? ofs : 1; j--;) { + // emit box + if (parser->cbs->on_box && !parser->cbs->on_box(parser, pos)) { + // return failure + return false; + } + + // advance + pos.x++; + } + ofs = 0; + + break; + default: + // emit junk + if (parser->cbs->on_junk && !parser->cbs->on_junk(parser, i, buf[i])) { + // return failure + return false; + } + + // return failure + return false; + } + } + + // return success + return true; +} diff --git a/src/core/sok-solve.c b/src/core/sok-solve.c new file mode 100644 index 0000000..34a8320 --- /dev/null +++ b/src/core/sok-solve.c @@ -0,0 +1,89 @@ +#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) +) { + // check for success + if (sok_ctx_is_done(ctx)) { + // return success + return true; + } + + if (sok_cache_has(cache, ctx)) { + // return failure + return false; + } + + // add to cache + if (!sok_cache_add(cache, ctx)) { + if (on_error) { + // log error + on_error("sok_cache_add() failed"); + } + + // 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)) { + continue; + } + + // recurse, check for success + if (sok_solve_step(ctx, cache, on_error)) { + // return success + return true; + } + + // undo move + 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/core/sok.h b/src/core/sok.h new file mode 100644 index 0000000..1503b5f --- /dev/null +++ b/src/core/sok.h @@ -0,0 +1,257 @@ +#ifndef SOK_H +#define SOK_H + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +#include // uint16_t +#include // size_t + +/*********/ +/* types */ +/*********/ + +typedef struct { + uint16_t x, y; +} sok_pos_t; + +typedef enum { + SOK_DIR_RIGHT, + SOK_DIR_UP, + SOK_DIR_LEFT, + SOK_DIR_DOWN, + SOK_DIR_LAST, +} sok_dir_t; + +#define SOK_DIR_TO_CHAR(dir) ( \ + ((dir) == SOK_DIR_RIGHT) ? 'r' : \ + (((dir) == SOK_DIR_UP) ? 'u' : \ + ((((dir) == SOK_DIR_LEFT) ? 'l' : \ + (((((dir) == SOK_DIR_DOWN) ? 'd' : \ + 'X' \ +))))))) + + +#define SOK_DIR_TO_STR(dir) ( \ + ((dir) == SOK_DIR_RIGHT) ? "r" : \ + (((dir) == SOK_DIR_UP) ? "u" : \ + ((((dir) == SOK_DIR_LEFT) ? "l" : \ + (((((dir) == SOK_DIR_DOWN) ? "d" : \ + "X" \ +))))))) + +typedef struct { + sok_pos_t pos; + sok_dir_t dir; + _Bool is_push; +} sok_move_t; + +/****************/ +/* level parser */ +/****************/ + +typedef struct sok_level_parser_t_ sok_level_parser_t; + +typedef _Bool (*sok_level_parser_pos_cb_t)( + const sok_level_parser_t * const, + const sok_pos_t +); + +typedef _Bool (*sok_level_parser_junk_cb_t)( + const sok_level_parser_t * const, + const size_t, + const char +); + +typedef struct { + sok_level_parser_pos_cb_t on_size, + on_home, + on_wall, + on_goal, + on_box; + sok_level_parser_junk_cb_t on_junk; +} sok_level_parser_cbs_t; + +struct sok_level_parser_t_ { + const sok_level_parser_cbs_t *cbs; + void *user_data; +}; + +void sok_level_parser_init( + sok_level_parser_t * const parser, + const sok_level_parser_cbs_t * const cbs, + void * const user_data +); + +_Bool sok_level_parser_parse( + sok_level_parser_t * const parser, + const char * const buf, + const size_t buf_len +); + +/*********/ +/* level */ +/*********/ + +#define SOK_LEVEL_MAX_WIDTH (1 << 8) +#define SOK_LEVEL_MAX_HEIGHT (1 << 8) +#define SOK_LEVEL_MAX_BOXES 64 +#define SOK_LEVEL_MAX_GOALS 64 + +typedef struct { + sok_pos_t size; + _Bool walls[SOK_LEVEL_MAX_WIDTH * SOK_LEVEL_MAX_HEIGHT]; + + // player home position + sok_pos_t home; + + // boxes + sok_pos_t boxes[SOK_LEVEL_MAX_BOXES]; + size_t num_boxes; + + // goals + sok_pos_t goals[SOK_LEVEL_MAX_GOALS]; + size_t num_goals; +} sok_level_t; + +/***********/ +/* context */ +/***********/ + +#define SOK_CTX_MAX_MOVES 1024 + +typedef struct { + sok_level_t level; + + // moves + sok_move_t moves[SOK_CTX_MAX_MOVES]; + size_t num_moves; + + // number of open goals + size_t num_goals_left; + + // are there boxes in corners? + // _Bool is_lost; + + // player position + sok_pos_t home; + + // box positions + sok_pos_t boxes[SOK_LEVEL_MAX_BOXES]; + + // user data + void *user_data; +} sok_ctx_t; + +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_move(sok_ctx_t * const, const sok_dir_t); +_Bool sok_ctx_undo(sok_ctx_t * const); + +/******************/ +/* context walker */ +/******************/ + +typedef _Bool (*sok_ctx_walk_step_cb_t)( + const sok_ctx_t * const, + void * const +); + +typedef _Bool (*sok_ctx_walk_pos_cb_t)( + const sok_ctx_t * const, + const sok_pos_t, + void * const +); + +typedef _Bool (*sok_ctx_walk_tile_cb_t)( + const sok_ctx_t * const, + const sok_pos_t, + const _Bool, + void * const +); + +typedef _Bool (*sok_ctx_walk_goal_cb_t)( + const sok_ctx_t * const, + const sok_pos_t, + const _Bool has_player, + const _Bool has_box, + void * const +); + +typedef _Bool (*sok_ctx_walk_move_cb_t)( + const sok_ctx_t * const, + const sok_move_t, + void * const +); + +typedef struct { + sok_ctx_walk_pos_cb_t on_size; + + sok_ctx_walk_step_cb_t on_walls_start, + on_walls_end; + sok_ctx_walk_pos_cb_t on_wall; + + sok_ctx_walk_tile_cb_t on_home; + + sok_ctx_walk_step_cb_t on_boxes_start, + on_boxes_end; + sok_ctx_walk_tile_cb_t on_box; + + sok_ctx_walk_step_cb_t on_goals_start, + on_goals_end; + sok_ctx_walk_goal_cb_t on_goal; + + sok_ctx_walk_step_cb_t on_moves_start, + on_moves_end; + sok_ctx_walk_move_cb_t on_move; +} sok_ctx_walk_cbs_t; + +_Bool sok_ctx_walk( + const sok_ctx_t * const, + const sok_ctx_walk_cbs_t * const, + void * const +); + +/****************/ +/* context hash */ +/****************/ + +uint64_t sok_ctx_hash(const sok_ctx_t * 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 */ + +#endif /* SOK_H */ diff --git a/src/libsok/sok-cache.c b/src/libsok/sok-cache.c deleted file mode 100644 index df3c729..0000000 --- a/src/libsok/sok-cache.c +++ /dev/null @@ -1,168 +0,0 @@ -#include // bool -#include // uint64_t -#include // bsearch(), qsort() -#include // memcpy -#include // debug -#include "sok.h" - -#define UNUSED(a) ((void) (a)) -#define GROW_SIZE (4096 / sizeof(uint64_t)) -#define USE_QSORT 1 - -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 * sizeof(uint64_t)); - 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 -) { -#if 0 - for (size_t i = 0; i < cache->num_vals; i++) { - if (cache->vals[i] == hash) { - return true; - } - } - - // return failure - return false; -#else - return !!bsearch( - &hash, - cache->vals, - cache->num_vals, - sizeof(uint64_t), - u64_cmp - ); -#endif /* 0 */ -} - -bool -sok_cache_has( - const sok_cache_t * const cache, - const sok_ctx_t * const ctx -) { - return sok_cache_has_hash(cache, sok_ctx_hash(ctx)); -} - -bool -sok_cache_add( - sok_cache_t * const cache, - const sok_ctx_t * const ctx -) { -/* - * // hash context - * const uint64_t hash = sok_ctx_hash(ctx); - * - * // check for duplicates - * if (sok_cache_has_hash(cache, hash)) { - * return false; - * } - */ - - // check capacity - if (cache->num_vals >= cache->capacity) { - // grow cache - if (!sok_cache_grow(cache)) { - // return failure - return false; - } - } - - // append hash - const uint64_t hash = sok_ctx_hash(ctx); -#if USE_QSORT - cache->vals[cache->num_vals] = hash; - cache->num_vals++; - - // sort values - qsort(cache->vals, cache->num_vals, sizeof(uint64_t), u64_cmp); -#else - size_t i; - for (i = 0; cache->vals[i] < hash && i < cache->num_vals; i++); - if (i < cache->num_vals) { - if (cache->vals[i] == hash) { - return true; - } - - // move remaining data - const size_t num_bytes = (cache->num_vals - i) * sizeof(uint64_t); - memmove(cache->vals + (i + 1), cache->vals + i, num_bytes); - - // insert value - cache->vals[i] = hash; - cache->num_vals++; - } else { - // append value - cache->vals[cache->num_vals] = hash; - cache->num_vals++; - } -#endif /* USE_QSORT */ - - // 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(capacity * sizeof(uint64_t)); - 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-hash.c b/src/libsok/sok-ctx-hash.c deleted file mode 100644 index 61689ea..0000000 --- a/src/libsok/sok-ctx-hash.c +++ /dev/null @@ -1,41 +0,0 @@ -#include // uint16_t -#include "sok.h" - -// fnv64 -// src: https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function -#define FNV_OFFSET 1099511628211 -#define FNV_PRIME 0xcbf29ce484222325 - -static uint64_t -fnv1a( - const uint8_t * const buf, - const size_t len -) { - uint64_t hash = FNV_OFFSET; - - for (size_t i = 0; i < len; i++) { - hash ^= buf[i]; - hash *= FNV_PRIME; - } - - return hash; -} - -uint64_t -sok_ctx_hash( - const sok_ctx_t * const ctx -) { - uint16_t buf[512] = {ctx->home.x, ctx->home.y, 0}; - const size_t BUF_MASK = (sizeof(buf) / sizeof(uint16_t) - 1); - - for (size_t i = 0; i < ctx->level.num_boxes; i++) { - buf[(2 * (i + 1) + 0) & BUF_MASK] = ctx->boxes[i].x; - buf[(2 * (i + 1) + 1) & BUF_MASK] = ctx->boxes[i].y; - } - - // calculate buffer length - const size_t used = 2 * (ctx->level.num_boxes + 1) * sizeof(uint16_t); - const size_t len = (used < sizeof(buf)) ? used : sizeof(buf); - - return fnv1a((uint8_t*) buf, len); -} diff --git a/src/libsok/sok-ctx.c b/src/libsok/sok-ctx.c deleted file mode 100644 index e278af1..0000000 --- a/src/libsok/sok-ctx.c +++ /dev/null @@ -1,636 +0,0 @@ -#include -#include // memset() -#include "sok.h" - -#define UNUSED(a) ((void) (a)) - -#define VALID_POS(pos) ( \ - (pos).x < SOK_LEVEL_MAX_WIDTH && \ - (pos).y < SOK_LEVEL_MAX_HEIGHT \ -) - -#define POINTS_EQUAL(a, b) ( \ - ((a).x == (b).x) && \ - ((a).y == (b).y) \ -) - -static bool -ctx_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 void -ctx_set_wall( - sok_ctx_t * const ctx, - const sok_pos_t pos -) { - ctx->level.walls[pos.y * ctx->level.size.x + pos.x] = true; -} - -static void -ctx_clear_walls( - sok_ctx_t * const ctx -) { - memset(ctx->level.walls, 0, SOK_LEVEL_MAX_WIDTH * SOK_LEVEL_MAX_HEIGHT); -} - -static bool -on_size( - const sok_level_parser_t * const parser, - const sok_pos_t pos -) { - sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; - - if (!VALID_POS(pos)) { - // size out of bounds - return false; - } - - // save width and height - ctx->level.size = pos; - - // return success - return true; -} - -static bool -on_home( - const sok_level_parser_t * const parser, - const sok_pos_t pos -) { - sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; - - if (!VALID_POS(pos)) { - // position out of bounds - return false; - } - - // save start position - ctx->level.home = pos; - - // return success - return true; -} - -static bool -on_wall( - const sok_level_parser_t * const parser, - const sok_pos_t pos -) { - sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; - - if (!VALID_POS(pos)) { - // position out of bounds - return false; - } - - // save wall - ctx_set_wall(ctx, pos); - - // return sucess - return true; -} - -static bool -on_goal( - const sok_level_parser_t * const parser, - const sok_pos_t pos -) { - sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; - - if (!VALID_POS(pos)) { - // position out of bounds - return false; - } - - if (ctx->level.num_goals >= SOK_LEVEL_MAX_GOALS - 1) { - // too many goals - return false; - } - - // save goal - ctx->level.goals[ctx->level.num_goals++] = pos; - - // return sucess - return true; -} - -static bool -on_box( - const sok_level_parser_t * const parser, - const sok_pos_t pos -) { - sok_ctx_t *ctx = (sok_ctx_t*) parser->user_data; - - if (!VALID_POS(pos)) { - // position out of bounds - return false; - } - - if (ctx->level.num_boxes >= SOK_LEVEL_MAX_BOXES - 1) { - // too many boxes - return false; - } - - // save box - ctx->level.boxes[ctx->level.num_boxes++] = pos; - - // return sucess - return true; -} - -static bool -on_junk( - const sok_level_parser_t * const parser, - const size_t ofs, - const char tile -) { - UNUSED(parser); - UNUSED(ofs); - UNUSED(tile); - - // TODO - - // return sucess - return true; -} - -static const sok_level_parser_cbs_t -LEVEL_PARSER_CBS = { - .on_size = on_size, - .on_home = on_home, - .on_wall = on_wall, - .on_goal = on_goal, - .on_box = on_box, - .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 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_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; - * } - */ - -void -sok_ctx_init(sok_ctx_t * const ctx, void *user_data) { - memset(ctx, 0, sizeof(sok_ctx_t)); - ctx->user_data = user_data; -} - -bool -sok_ctx_set_level( - sok_ctx_t * const ctx, - const char * const str -) { - - // clear level - ctx->level.num_goals = 0; - ctx->level.num_boxes = 0; - ctx_clear_walls(ctx); - - // parse level - sok_level_parser_t parser; - sok_level_parser_init(&parser, &LEVEL_PARSER_CBS, ctx); - if (!sok_level_parser_parse(&parser, str, strlen(str))) { - // return failure - return false; - } - - // init moves, player, and boxes - ctx->num_moves = 0; - 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 - ctx->num_goals_left = sok_ctx_count_goals_left(ctx); - // ctx->is_lost = sok_ctx_is_lost(ctx); - - // return success - return true; -} - -static bool -tile_is_floor( - const sok_ctx_t * const ctx, - const sok_pos_t pos -) { - return ( - (pos.x < SOK_LEVEL_MAX_WIDTH - 1) && - (pos.y < SOK_LEVEL_MAX_HEIGHT - 1) && - !ctx_is_wall(ctx, pos) - ); -} - -static bool -tile_is_box( - const sok_ctx_t * const ctx, - const sok_pos_t pos -) { - const size_t num_boxes = ctx->level.num_boxes; - 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, - const sok_dir_t dir, - const bool is_push -) { - if (ctx->num_moves >= SOK_CTX_MAX_MOVES - 1) { - return false; - } - - ctx->moves[ctx->num_moves].pos = ctx->home; - ctx->moves[ctx->num_moves].dir = dir; - ctx->moves[ctx->num_moves].is_push = is_push; - ctx->num_moves++; - - return true; -} - -static bool -sok_ctx_pop_move( - sok_ctx_t * const ctx, - sok_move_t * const ret -) { - if (!ctx->num_moves) { - // return failure - return false; - } - - // decriment moves - ctx->num_moves--; - - if (ret) { - // save popped move - *ret = ctx->moves[ctx->num_moves]; - } - - // return success - return true; -} - -static bool -sok_ctx_move_box( - sok_ctx_t * const ctx, - const sok_pos_t old_pos, - const sok_pos_t new_pos -) { - const size_t num_boxes = ctx->level.num_boxes, - box_ofs = pos_find(old_pos, ctx->boxes, num_boxes); - - if (box_ofs < num_boxes) { - // 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); - - // return success - return true; - } - - // return failure - return false; -} - -bool -sok_ctx_is_done( - const sok_ctx_t * const ctx -) { - return ctx->num_goals_left == 0; -} - -/* - * bool - * sok_ctx_is_lost( - * const sok_ctx_t * const ctx - * ) { - * return ctx->is_lost; - * } - */ - -bool -sok_ctx_move( - sok_ctx_t * const ctx, - const sok_dir_t dir -) { - if (ctx->num_moves >= SOK_CTX_MAX_MOVES - 1) { - // no more move slots available - return false; - } - - 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; - } - - // 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; - } - - // 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); - - - // return success - return true; - } - - // return failure - return false; -} - -bool -sok_ctx_undo( - sok_ctx_t * const ctx -) { - sok_move_t move; - if (!sok_ctx_pop_move(ctx, &move)) { - // return failure - return false; - } - - if (move.is_push) { - 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)), - }; - - sok_ctx_move_box(ctx, box_pos, ctx->home); - } - - // update position - ctx->home = move.pos; - - // return success - return true; -} - -bool sok_ctx_walk( - const sok_ctx_t * const ctx, - const sok_ctx_walk_cbs_t * const cbs, - void * const data -) { - if (!cbs) { - return false; - } - - if (cbs->on_size) { - // emit size - if (!cbs->on_size(ctx, ctx->level.size, data)) { - return false; - } - } - - if (cbs->on_walls_start && !cbs->on_walls_start(ctx, data)) { - return false; - } - - if (cbs->on_wall) { - // walk walls - for (size_t i = 0; i < (ctx->level.size.x * ctx->level.size.y); i++) { - const sok_pos_t pos = { - .y = i / ctx->level.size.x, - .x = i % ctx->level.size.x, - }; - - if (ctx_is_wall(ctx, pos)) { - // emit wall - if (!cbs->on_wall(ctx, pos, data)) { - return false; - } - } - } - } - - if (cbs->on_walls_end && !cbs->on_walls_end(ctx, data)) { - return false; - } - - if (cbs->on_goals_start && !cbs->on_goals_start(ctx, data)) { - return false; - } - - if (cbs->on_goal) { - // walk goals - for (size_t i = 0; i < ctx->level.num_goals; i++) { - const bool has_player = POINTS_EQUAL(ctx->level.goals[i], ctx->home); - const bool has_box = tile_is_box(ctx, ctx->level.goals[i]); - - // emit goal - if (!cbs->on_goal(ctx, ctx->level.goals[i], has_player, has_box, data)) { - return false; - } - } - } - - if (cbs->on_goals_end && !cbs->on_goals_end(ctx, data)) { - return false; - } - - if (cbs->on_boxes_start && !cbs->on_boxes_start(ctx, data)) { - return false; - } - - if (cbs->on_home) { - const bool has_goal = tile_is_goal(ctx, ctx->home); - - // emit home - if (!cbs->on_home(ctx, ctx->home, has_goal, data)) { - return false; - } - } - - if (cbs->on_box) { - // walk boxes - for (size_t i = 0; i < ctx->level.num_boxes; i++) { - const bool has_goal = tile_is_goal(ctx, ctx->boxes[i]); - - // emit box - if (!cbs->on_box(ctx, ctx->boxes[i], has_goal, data)) { - return false; - } - } - } - - if (cbs->on_boxes_end && !cbs->on_boxes_end(ctx, data)) { - return false; - } - - if (cbs->on_moves_start && !cbs->on_moves_start(ctx, data)) { - return false; - } - - if (cbs->on_move) { - // walk moves - for (size_t i = 0; i < ctx->num_moves; i++) { - // emit move - if (!cbs->on_move(ctx, ctx->moves[i], data)) { - return false; - } - } - } - - if (cbs->on_moves_end && !cbs->on_moves_end(ctx, data)) { - return false; - } - - // return success - return true; -} diff --git a/src/libsok/sok-level-parser.c b/src/libsok/sok-level-parser.c deleted file mode 100644 index 276ebcb..0000000 --- a/src/libsok/sok-level-parser.c +++ /dev/null @@ -1,193 +0,0 @@ -#include -#include // size_t -#include "sok.h" - -#define UNUSED(a) ((void) (a)) - -#define IS_DIGIT(c) ((c) >= '0' && (c) <= '9') -#define CASE_DIGIT \ - case '0': \ - case '1': \ - case '2': \ - case '3': \ - case '4': \ - case '5': \ - case '6': \ - case '7': \ - case '8': \ - case '9': - -void -sok_level_parser_init( - sok_level_parser_t * const parser, - const sok_level_parser_cbs_t * const cbs, - void * const user_data -) { - parser->cbs = cbs; - parser->user_data = user_data; -} - -bool -sok_level_parser_parse( - sok_level_parser_t * const parser, - const char * const buf, - const size_t buf_len -) { - sok_pos_t size = { .x = 0, .y = 0 }; - - for (size_t i = 0, ofs = 0, w = 0; i < buf_len; i++) { - if (buf[i] == '|') { - if (w > size.x) { - size.x = w; - } - - // reset column position, increment row count - w = 0; - size.y++; - } else if (IS_DIGIT(buf[i])) { - ofs = 10 * ofs + (buf[i] - '0'); - } else if (ofs > 0) { - w += ofs; - ofs = 0; - } else { - w++; - } - } - - // increment row count - size.y++; - - // emit level size - if ( - parser->cbs->on_size && - !parser->cbs->on_size(parser, size) - ) { - // return failure - return false; - } - - sok_pos_t pos = { 0, 0 }; - for (size_t i = 0, ofs = 0; i < buf_len; i++) { - switch (buf[i]) { - case '|': - // new line - pos.x = 0; - pos.y++; - - break; - CASE_DIGIT - ofs = 10 * ofs + (buf[i] - '0'); - break; - case '-': - case '_': - case ' ': - // advance - pos.x += (ofs > 0) ? ofs : 1; - ofs = 0; - - break; - case '+': - // emit goal - if (parser->cbs->on_goal && !parser->cbs->on_goal(parser, pos)) { - // return failure - return false; - } - - // emit home - if (parser->cbs->on_home && !parser->cbs->on_home(parser, pos)) { - // return failure - return false; - } - - // advance - pos.x++; - - break; - case '@': - // emit home - if (parser->cbs->on_home && !parser->cbs->on_home(parser, pos)) { - // return failure - return false; - } - - // advance - pos.x++; - - break; - case '#': - for (size_t j = (ofs > 0) ? ofs : 1; j; j--) { - // emit wall - if (parser->cbs->on_wall && !parser->cbs->on_wall(parser, pos)) { - // return failure - return false; - } - - // advance - pos.x++; - } - ofs = 0; - - break; - case '*': - for (size_t j = (ofs > 0) ? ofs : 1; j--;) { - // emit goal - if (parser->cbs->on_goal && !parser->cbs->on_goal(parser, pos)) { - // return failure - return false; - } - - // emit box - if (parser->cbs->on_box && !parser->cbs->on_box(parser, pos)) { - // return failure - return false; - } - - // advance - pos.x++; - } - ofs = 0; - - break; - case '.': - for (size_t j = (ofs > 0) ? ofs : 1; j--;) { - // emit goal - if (parser->cbs->on_goal && !parser->cbs->on_goal(parser, pos)) { - // return failure - return false; - } - - // advance - pos.x++; - } - ofs = 0; - - break; - case '$': - for (size_t j = (ofs > 0) ? ofs : 1; j--;) { - // emit box - if (parser->cbs->on_box && !parser->cbs->on_box(parser, pos)) { - // return failure - return false; - } - - // advance - pos.x++; - } - ofs = 0; - - break; - default: - // emit junk - if (parser->cbs->on_junk && !parser->cbs->on_junk(parser, i, buf[i])) { - // return failure - return false; - } - - // return failure - return false; - } - } - - // return success - return true; -} diff --git a/src/libsok/sok-solve.c b/src/libsok/sok-solve.c deleted file mode 100644 index 34a8320..0000000 --- a/src/libsok/sok-solve.c +++ /dev/null @@ -1,89 +0,0 @@ -#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) -) { - // check for success - if (sok_ctx_is_done(ctx)) { - // return success - return true; - } - - if (sok_cache_has(cache, ctx)) { - // return failure - return false; - } - - // add to cache - if (!sok_cache_add(cache, ctx)) { - if (on_error) { - // log error - on_error("sok_cache_add() failed"); - } - - // 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)) { - continue; - } - - // recurse, check for success - if (sok_solve_step(ctx, cache, on_error)) { - // return success - return true; - } - - // undo move - 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 deleted file mode 100644 index 1503b5f..0000000 --- a/src/libsok/sok.h +++ /dev/null @@ -1,257 +0,0 @@ -#ifndef SOK_H -#define SOK_H - -#ifdef __cplusplus -extern "C" { -#endif /* __cplusplus */ - -#include // uint16_t -#include // size_t - -/*********/ -/* types */ -/*********/ - -typedef struct { - uint16_t x, y; -} sok_pos_t; - -typedef enum { - SOK_DIR_RIGHT, - SOK_DIR_UP, - SOK_DIR_LEFT, - SOK_DIR_DOWN, - SOK_DIR_LAST, -} sok_dir_t; - -#define SOK_DIR_TO_CHAR(dir) ( \ - ((dir) == SOK_DIR_RIGHT) ? 'r' : \ - (((dir) == SOK_DIR_UP) ? 'u' : \ - ((((dir) == SOK_DIR_LEFT) ? 'l' : \ - (((((dir) == SOK_DIR_DOWN) ? 'd' : \ - 'X' \ -))))))) - - -#define SOK_DIR_TO_STR(dir) ( \ - ((dir) == SOK_DIR_RIGHT) ? "r" : \ - (((dir) == SOK_DIR_UP) ? "u" : \ - ((((dir) == SOK_DIR_LEFT) ? "l" : \ - (((((dir) == SOK_DIR_DOWN) ? "d" : \ - "X" \ -))))))) - -typedef struct { - sok_pos_t pos; - sok_dir_t dir; - _Bool is_push; -} sok_move_t; - -/****************/ -/* level parser */ -/****************/ - -typedef struct sok_level_parser_t_ sok_level_parser_t; - -typedef _Bool (*sok_level_parser_pos_cb_t)( - const sok_level_parser_t * const, - const sok_pos_t -); - -typedef _Bool (*sok_level_parser_junk_cb_t)( - const sok_level_parser_t * const, - const size_t, - const char -); - -typedef struct { - sok_level_parser_pos_cb_t on_size, - on_home, - on_wall, - on_goal, - on_box; - sok_level_parser_junk_cb_t on_junk; -} sok_level_parser_cbs_t; - -struct sok_level_parser_t_ { - const sok_level_parser_cbs_t *cbs; - void *user_data; -}; - -void sok_level_parser_init( - sok_level_parser_t * const parser, - const sok_level_parser_cbs_t * const cbs, - void * const user_data -); - -_Bool sok_level_parser_parse( - sok_level_parser_t * const parser, - const char * const buf, - const size_t buf_len -); - -/*********/ -/* level */ -/*********/ - -#define SOK_LEVEL_MAX_WIDTH (1 << 8) -#define SOK_LEVEL_MAX_HEIGHT (1 << 8) -#define SOK_LEVEL_MAX_BOXES 64 -#define SOK_LEVEL_MAX_GOALS 64 - -typedef struct { - sok_pos_t size; - _Bool walls[SOK_LEVEL_MAX_WIDTH * SOK_LEVEL_MAX_HEIGHT]; - - // player home position - sok_pos_t home; - - // boxes - sok_pos_t boxes[SOK_LEVEL_MAX_BOXES]; - size_t num_boxes; - - // goals - sok_pos_t goals[SOK_LEVEL_MAX_GOALS]; - size_t num_goals; -} sok_level_t; - -/***********/ -/* context */ -/***********/ - -#define SOK_CTX_MAX_MOVES 1024 - -typedef struct { - sok_level_t level; - - // moves - sok_move_t moves[SOK_CTX_MAX_MOVES]; - size_t num_moves; - - // number of open goals - size_t num_goals_left; - - // are there boxes in corners? - // _Bool is_lost; - - // player position - sok_pos_t home; - - // box positions - sok_pos_t boxes[SOK_LEVEL_MAX_BOXES]; - - // user data - void *user_data; -} sok_ctx_t; - -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_move(sok_ctx_t * const, const sok_dir_t); -_Bool sok_ctx_undo(sok_ctx_t * const); - -/******************/ -/* context walker */ -/******************/ - -typedef _Bool (*sok_ctx_walk_step_cb_t)( - const sok_ctx_t * const, - void * const -); - -typedef _Bool (*sok_ctx_walk_pos_cb_t)( - const sok_ctx_t * const, - const sok_pos_t, - void * const -); - -typedef _Bool (*sok_ctx_walk_tile_cb_t)( - const sok_ctx_t * const, - const sok_pos_t, - const _Bool, - void * const -); - -typedef _Bool (*sok_ctx_walk_goal_cb_t)( - const sok_ctx_t * const, - const sok_pos_t, - const _Bool has_player, - const _Bool has_box, - void * const -); - -typedef _Bool (*sok_ctx_walk_move_cb_t)( - const sok_ctx_t * const, - const sok_move_t, - void * const -); - -typedef struct { - sok_ctx_walk_pos_cb_t on_size; - - sok_ctx_walk_step_cb_t on_walls_start, - on_walls_end; - sok_ctx_walk_pos_cb_t on_wall; - - sok_ctx_walk_tile_cb_t on_home; - - sok_ctx_walk_step_cb_t on_boxes_start, - on_boxes_end; - sok_ctx_walk_tile_cb_t on_box; - - sok_ctx_walk_step_cb_t on_goals_start, - on_goals_end; - sok_ctx_walk_goal_cb_t on_goal; - - sok_ctx_walk_step_cb_t on_moves_start, - on_moves_end; - sok_ctx_walk_move_cb_t on_move; -} sok_ctx_walk_cbs_t; - -_Bool sok_ctx_walk( - const sok_ctx_t * const, - const sok_ctx_walk_cbs_t * const, - void * const -); - -/****************/ -/* context hash */ -/****************/ - -uint64_t sok_ctx_hash(const sok_ctx_t * 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 */ - -#endif /* SOK_H */ diff --git a/src/sdl/action.c b/src/sdl/action.c index 09141a9..8bc01f7 100644 --- a/src/sdl/action.c +++ b/src/sdl/action.c @@ -1,4 +1,4 @@ -#include "../libsok/sok.h" +#include "../core/sok.h" #include "action.h" #define CASE_DIGIT \ diff --git a/src/sdl/draw.h b/src/sdl/draw.h index 1c44320..956e474 100644 --- a/src/sdl/draw.h +++ b/src/sdl/draw.h @@ -4,7 +4,7 @@ #include // size_t #include #include -#include "../libsok/sok.h" +#include "../core/sok.h" #include "../text/levels.h" #include "theme.h" diff --git a/src/sdl/main.c b/src/sdl/main.c index 1d0b11b..6ca9b86 100644 --- a/src/sdl/main.c +++ b/src/sdl/main.c @@ -4,7 +4,7 @@ #include // errno #include #include "../text/levels.h" -#include "../libsok/sok.h" +#include "../core/sok.h" #include "util.h" #include "action.h" #include "warp-buf.h" diff --git a/src/sdl/text-style.h b/src/sdl/text-style.h index 71d9a91..a1cae37 100644 --- a/src/sdl/text-style.h +++ b/src/sdl/text-style.h @@ -1,7 +1,7 @@ #ifndef TEXT_STYLE_H #define TEXT_STYLE_H -#include "../libsok/sok.h" +#include "../core/sok.h" #include typedef enum { diff --git a/src/solve/main.c b/src/solve/main.c index 2a9ed53..c45c5bb 100644 --- a/src/solve/main.c +++ b/src/solve/main.c @@ -2,7 +2,7 @@ #include // atoi() #include // EXIT_{FAILURE,SUCCESS} #include -#include "../libsok/sok.h" +#include "../core/sok.h" #include "../text/util.h" #include "../text/levels.h" diff --git a/src/text/action.c b/src/text/action.c index 3381c0a..9d4cbbc 100644 --- a/src/text/action.c +++ b/src/text/action.c @@ -1,6 +1,6 @@ #include // fgets() #include // atoi() -#include "../libsok/sok.h" +#include "../core/sok.h" #include "action.h" #define CASE_DIGIT \ diff --git a/src/text/draw.c b/src/text/draw.c index 7c23171..af0a132 100644 --- a/src/text/draw.c +++ b/src/text/draw.c @@ -2,7 +2,7 @@ #include // atoi() #include // EXIT_{FAILURE,SUCCESS} #include -#include "../libsok/sok.h" +#include "../core/sok.h" #include "util.h" #include "draw.h" diff --git a/src/text/draw.h b/src/text/draw.h index a4a2a18..c3add0d 100644 --- a/src/text/draw.h +++ b/src/text/draw.h @@ -2,7 +2,7 @@ #define DRAW_H #include -#include "../libsok/sok.h" +#include "../core/sok.h" #include "levels.h" void draw( diff --git a/src/text/levels.c b/src/text/levels.c index 4971604..a091b7f 100644 --- a/src/text/levels.c +++ b/src/text/levels.c @@ -2,7 +2,7 @@ #include // atoi() #include // EXIT_{FAILURE,SUCCESS} #include -#include "../libsok/sok.h" +#include "../core/sok.h" #include "levels.h" static const level_t diff --git a/src/text/main.c b/src/text/main.c index e80e984..1f76bf3 100644 --- a/src/text/main.c +++ b/src/text/main.c @@ -2,7 +2,7 @@ #include // atoi() #include // EXIT_{FAILURE,SUCCESS} #include -#include "../libsok/sok.h" +#include "../core/sok.h" #include "util.h" #include "levels.h" #include "action.h" -- cgit v1.2.3