aboutsummaryrefslogtreecommitdiff
path: root/src/core
diff options
context:
space:
mode:
Diffstat (limited to 'src/core')
-rw-r--r--src/core/sok-cache.c168
-rw-r--r--src/core/sok-ctx-hash.c41
-rw-r--r--src/core/sok-ctx.c636
-rw-r--r--src/core/sok-level-parser.c193
-rw-r--r--src/core/sok-solve.c89
-rw-r--r--src/core/sok.h257
6 files changed, 1384 insertions, 0 deletions
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 <stdbool.h> // bool
+#include <stdint.h> // uint64_t
+#include <stdlib.h> // bsearch(), qsort()
+#include <string.h> // memcpy
+#include <stdio.h> // 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 <stdint.h> // 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 <stdbool.h>
+#include <string.h> // 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 <stdbool.h>
+#include <stddef.h> // 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 <stdbool.h>
+#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 <stdint.h> // uint16_t
+#include <stddef.h> // 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 */
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-19 16:47:53 +0000