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 ++++++++++++++++++ 6 files changed, 1384 insertions(+) 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 (limited to 'src/core') 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 */ -- cgit v1.2.3