X-Git-Url: https://git.martlubbers.net/?a=blobdiff_plain;f=modelchecker%2Fcoord.c;h=f6e22340bb2e0ebde55d3b223d25c73b0d1798e5;hb=c8455397d13fa68cd94263f6d5e00797bed58d27;hp=68ad5a3ae0715810355e31bbf6e84f9ed2d46b8d;hpb=3461b7c4dd08242328dd59b44c6ddbcc00af6a0e;p=mc1516pa.git

diff --git a/modelchecker/coord.c b/modelchecker/coord.c
index 68ad5a3..f6e2234 100644
--- a/modelchecker/coord.c
+++ b/modelchecker/coord.c
@@ -17,6 +17,102 @@
 #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;
+
+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;
+		printf("test!: %d %d\n", r->coord.x, 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;
+}
 
 /*
  * Each coordinate has three related boolean variables. The combination of those boolean variables
@@ -30,14 +126,158 @@
  * 110: Agent on target
  * In the BDD representation, the state is represented by n * 3 variables, where n is the number of
  * tiles in the shrinked screen.
+ * It seems that the move variable is not necessary since non-deterministic moves can be emvedded
+ * directly in transition relations.
  */
 
 BDD encode_screen(sokoban_screen *screen)
 {
-	int num_tiles;
-	num_tiles = HASH_COUNT(screen);
-	printf("Number of tiles: %d\n", num_tiles);
-	return sylvan_true;
+	BDD state = sylvan_false;
+	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++;
+			}
+			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++;
+			}
+			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++;
+			}
+			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++;
+			}
+			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++;
+			}
+			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++;
+			}
+			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++;
+			}
+			break;
+		}
+	}
+	/*
+	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);
+	*/
+	printf("%d tiles were encoded\n", tile_index);
+	return state;
 }
 
 BDD encode_rel(sokoban_screen *screen)