#include "coord.h"
#include "sokoban.h"
+/*
+ * Global TODOs for now:
+ * - update the helper maps so it is a single bimap
+ * - make a data structure for relations
+ * - encode relations as a set of four relations for each move
+ */
+
+typedef struct {
+ int x;
+ int y;
+} xy;
+
+typedef struct {
+ int var[3];
+} bddvar;
+
+typedef struct {
+ xy key;
+ bddvar value;
+ UT_hash_handle hh;
+} xy_bddvar_map;
+
+typedef struct {
+ int key;
+ xy value;
+ UT_hash_handle hh;
+} bddvar_xy_map;
+
+typedef struct {
+ xy_bddvar_map *f;
+ bddvar_xy_map *t;
+} bimap;
+
+typedef struct {
+ BDD *rell;
+ BDD *relu;
+ BDD *relr;
+ BDD *reld;
+} rels;
+
+typedef struct {
+ uint8_t *vars;
+ int size;
+} variables;
+
+typedef struct
+{
+ BDD bdd;
+ BDD variables;
+} *state;
+
+typedef struct
+{
+ BDD bdd;
+ BDD variables;
+} *trans;
+
+xy_bddvar_map *getxy(int x, int y, xy_bddvar_map *map)
+{
+ xy_bddvar_map k, *r = NULL;
+ memset(&k, 0, sizeof(xy_bddvar_map));
+ k.key.x = x;
+ k.key.y = y;
+ HASH_FIND(hh, map, &k.key, sizeof(xy), r);
+ return r;
+}
+
+bddvar_xy_map *getbdd(int key, bddvar_xy_map *map)
+{
+ bddvar_xy_map k, *r = NULL;
+ memset(&k, 0, sizeof(bddvar_xy_map));
+ k.key = key;
+ HASH_FIND(hh, map, &k.key, sizeof(int), r);
+ return r;
+}
+
+/*
+xy_bddvar_map *create_xy_bddvar_map(sokoban_screen *screen)
+{
+ int varcount = 0;
+ sokoban_screen *r;
+ xy_bddvar_map *xybdd = NULL;
+ for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
+ xy_bddvar_map *f = NULL;
+ //bddvar_xy_map *t = NULL;
+
+ f = (xy_bddvar_map *)malloc(sizeof(xy_bddvar_map));
+ memset(f, 0, sizeof(xy_bddvar_map));
+ f->key.x = r->coord.x;
+ f->key.y = r->coord.y;
+ f->value.var[0] = varcount;
+ f->value.var[1] = varcount + 1;
+ f->value.var[2] = varcount + 2;
+ HASH_ADD(hh, xybdd, key, sizeof(xy), f);
+ varcount = varcount + 3;
+ }
+ return xybdd;
+}
+
+bddvar_xy_map *create_bddvar_xy_map(sokoban_screen *screen)
+{
+ int varcount = 0;
+ sokoban_screen *r;
+ bddvar_xy_map *bddxy = NULL;
+ for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
+ for (int i = 0; i <3; i++){
+ bddvar_xy_map *f = NULL;
+ //bddvar_xy_map *t = NULL;
+
+ f = (bddvar_xy_map *)malloc(sizeof(bddvar_xy_map));
+ memset(f, 0, sizeof(bddvar_xy_map));
+ f->key = varcount + i;
+ f->value.x = r->coord.x;
+ f->value.y = r->coord.y;
+ HASH_ADD(hh, bddxy, key, sizeof(int), f);
+ }
+ varcount = varcount + 3;
+ }
+ return bddxy;
+}
+*/
+
+bimap *create_bimap_helper(sokoban_screen *screen)
+{
+ int varcount = 0;
+ sokoban_screen *r;
+ xy_bddvar_map *xybdd = NULL;
+ bddvar_xy_map *bddxy = NULL;
+ for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
+ xy_bddvar_map *f = NULL;
+ f = (xy_bddvar_map *)malloc(sizeof(xy_bddvar_map));
+ memset(f, 0, sizeof(xy_bddvar_map));
+ f->key.x = r->coord.x;
+ f->key.y = r->coord.y;
+ f->value.var[0] = varcount;
+ f->value.var[1] = varcount + 1;
+ f->value.var[2] = varcount + 2;
+ HASH_ADD(hh, xybdd, key, sizeof(xy), f);
+
+ for (int i = 0; i <3; i++){
+ bddvar_xy_map *t = NULL;
+ t = (bddvar_xy_map *)malloc(sizeof(bddvar_xy_map));
+ memset(t, 0, sizeof(bddvar_xy_map));
+ t->key = varcount + i;
+ t->value.x = r->coord.x;
+ t->value.y = r->coord.y;
+ HASH_ADD(hh, bddxy, key, sizeof(int), t);
+ }
+ varcount = varcount + 3;
+ }
+ bimap *bm = NULL;
+ bm = (bimap *)malloc(sizeof(bimap));
+ bm->f = xybdd;
+ bm->t = bddxy;
+ return bm;
+}
/*
* Each coordinate has three related boolean variables. The combination of those boolean variables
BDD encode_screen(sokoban_screen *screen)
{
- BDD state = sylvan_false;
+ LACE_ME;
+
+ BDDVAR vars[HASH_COUNT(screen) * 3];
+ for (uint8_t i = 0; i < HASH_COUNT(screen) * 3; i++){
+ vars[i] = i;
+ }
+
+ uint8_t st_enc[HASH_COUNT(screen) * 3];
+
+ BDDSET varset = sylvan_set_fromarray(vars, HASH_COUNT(screen) * 3);
+ BDD state;
int tile_index = 0;
sokoban_screen *r;
- LACE_ME;
for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
switch(r->tile){
- case FREE:
- if (state == sylvan_false){
- state = sylvan_not(sylvan_ithvar(tile_index));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- }
- else {
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- }
- printf("x = %d y = %d FREE\n", r->coord.x, r->coord.y);
+ case FREE: //001
+ st_enc[tile_index] = 0;
+ tile_index++;
+ st_enc[tile_index] = 0;
+ tile_index++;
+ st_enc[tile_index] = 1;
+ tile_index++;
break;
- case WALL:
- if (state == sylvan_false){
- state = sylvan_not(sylvan_ithvar(tile_index));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- }
- else {
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- }
- printf("x = %d y = %d WALL\n", r->coord.x, r->coord.y);
+ case WALL: //000
+ st_enc[tile_index] = 0;
+ tile_index++;
+ st_enc[tile_index] = 0;
+ tile_index++;
+ st_enc[tile_index] = 0;
+ tile_index++;
break;
- case BOX:
- if (state == sylvan_false){
- state = sylvan_not(sylvan_ithvar(tile_index));
- tile_index++;
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- }
- else {
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- }
- printf("x = %d y = %d BOX\n", r->coord.x, r->coord.y);
+ case BOX: //010
+ st_enc[tile_index] = 0;
+ tile_index++;
+ st_enc[tile_index] = 1;
+ tile_index++;
+ st_enc[tile_index] = 0;
+ tile_index++;
break;
- case TARGET:
- if (state == sylvan_false){
- state = sylvan_not(sylvan_ithvar(tile_index));
- tile_index++;
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- }
- else {
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- }
- printf("x = %d y = %d TARGET\n", r->coord.x, r->coord.y);
+ case TARGET: //011
+ st_enc[tile_index] = 0;
+ tile_index++;
+ st_enc[tile_index] = 1;
+ tile_index++;
+ st_enc[tile_index] = 1;
+ tile_index++;
break;
- case AGENT:
- if (state == sylvan_false){
- state = sylvan_ithvar(tile_index);
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- }
- else {
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- }
- printf("x = %d y = %d AGENT\n", r->coord.x, r->coord.y);
+ case AGENT: //101
+ st_enc[tile_index] = 1;
+ tile_index++;
+ st_enc[tile_index] = 0;
+ tile_index++;
+ st_enc[tile_index] = 1;
+ tile_index++;
break;
- case TARGAGENT:
- if (state == sylvan_false){
- state = sylvan_ithvar(tile_index);
- tile_index++;
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- }
- else {
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- }
- printf("x = %d y = %d TARGAGENT\n", r->coord.x, r->coord.y);
+ case TARGAGENT: //110
+ st_enc[tile_index] = 1;
+ tile_index++;
+ st_enc[tile_index] = 1;
+ tile_index++;
+ st_enc[tile_index] = 0;
+ tile_index++;
break;
- case TARGBOX:
- if (state == sylvan_false){
- state = sylvan_ithvar(tile_index);
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- }
- else {
- state = sylvan_and(state, sylvan_ithvar(tile_index));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- state = sylvan_and(state, sylvan_not(sylvan_ithvar(tile_index)));
- tile_index++;
- }
- printf("x = %d y = %d TARGBOX\n", r->coord.x, r->coord.y);
+ case TARGBOX: //100
+ st_enc[tile_index] = 1;
+ tile_index++;
+ st_enc[tile_index] = 0;
+ tile_index++;
+ st_enc[tile_index] = 0;
+ tile_index++;
break;
}
}
+ /* some testing...
+ xy_bddvar_map *map = NULL;
+ map = create_xy_bddvar_map(screen);
+ xy_bddvar_map *m = getxy(1, 1, map);
+ bddvar_xy_map *map2 = NULL;
+ map2 = create_bddvar_xy_map(screen);
+ bddvar_xy_map *m2 = getbdd(2, map2);
+ printf("Test1: %d %d\n", m->value.var[0], m->value.var[1]);
+ printf("Test2: %d %d\n", m2->value.x, m2->value.y);
+ */
+ /* some more testing...
+ bimap *bm = NULL;
+ bm = create_bimap_helper(screen);
+ xy_bddvar_map *m = getxy(1, 1, bm->f);
+ bddvar_xy_map *m2 = getbdd(2, bm->t);
+ printf("Test1: %d %d\n", m->value.var[0], m->value.var[1]);
+ printf("Test2: %d %d\n", m2->value.x, m2->value.y);
+ printf("%d tiles were encoded\n", tile_index);
+ if (bm != NULL) printf ("WORKS!\n");
+ */
+ state = sylvan_cube(varset, st_enc);
+ printf("Initial state encoded\n");
return state;
}
int num_tiles;
num_tiles = HASH_COUNT(screen);
printf("Number of tiles: %d\n", num_tiles);
- return sylvan_true;
-}
-void test()
-{
+ //left relation
- printf("Test!\n");
- BDD a = sylvan_true;
- BDD b = sylvan_not(a);
- if (b == sylvan_false){
- printf("BDD works!\n");
- } else {
- printf("BDD does not work!\n");
- }
- LACE_ME;
- BDD c = sylvan_ithvar(1);
- if (sylvan_high(c) == sylvan_true && sylvan_low(c) == sylvan_false) printf("VAR works 1\n");
- if (sylvan_var(c) == 1) printf("Var works 2\n");
+ //up relation
+
+ //right relation
+
+ //down relation
+
+ return sylvan_true;
}
repositories / mc1516pa.git / blobdiff