10 #include <gperftools/profiler.h>
21 * Global TODOs for now:
22 * - update the helper maps so it is a single bimap
23 * - make a data structure for relations
24 * - encode relations as a set of four relations for each move
60 xy_bddvar_map
*getxy(int x
, int y
, xy_bddvar_map
*map
)
62 xy_bddvar_map k
, *r
= NULL
;
63 memset(&k
, 0, sizeof(xy_bddvar_map
));
66 HASH_FIND(hh
, map
, &k
.key
, sizeof(xy
), r
);
70 bddvar_xy_map
*getbdd(int key
, bddvar_xy_map
*map
)
72 bddvar_xy_map k
, *r
= NULL
;
73 memset(&k
, 0, sizeof(bddvar_xy_map
));
75 HASH_FIND(hh
, map
, &k
.key
, sizeof(int), r
);
80 xy_bddvar_map *create_xy_bddvar_map(sokoban_screen *screen)
84 xy_bddvar_map *xybdd = NULL;
85 for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
86 xy_bddvar_map *f = NULL;
87 //bddvar_xy_map *t = NULL;
89 f = (xy_bddvar_map *)malloc(sizeof(xy_bddvar_map));
90 memset(f, 0, sizeof(xy_bddvar_map));
91 f->key.x = r->coord.x;
92 f->key.y = r->coord.y;
93 f->value.var[0] = varcount;
94 f->value.var[1] = varcount + 1;
95 f->value.var[2] = varcount + 2;
96 HASH_ADD(hh, xybdd, key, sizeof(xy), f);
97 varcount = varcount + 3;
102 bddvar_xy_map *create_bddvar_xy_map(sokoban_screen *screen)
106 bddvar_xy_map *bddxy = NULL;
107 for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
108 for (int i = 0; i <3; i++){
109 bddvar_xy_map *f = NULL;
110 //bddvar_xy_map *t = NULL;
112 f = (bddvar_xy_map *)malloc(sizeof(bddvar_xy_map));
113 memset(f, 0, sizeof(bddvar_xy_map));
114 f->key = varcount + i;
115 f->value.x = r->coord.x;
116 f->value.y = r->coord.y;
117 HASH_ADD(hh, bddxy, key, sizeof(int), f);
119 varcount = varcount + 3;
125 bimap
*create_bimap_helper(sokoban_screen
*screen
)
129 xy_bddvar_map
*xybdd
= NULL
;
130 bddvar_xy_map
*bddxy
= NULL
;
131 for(r
=screen
; r
!= NULL
; r
= (sokoban_screen
*)(r
->hh
.next
)){
132 xy_bddvar_map
*f
= NULL
;
133 f
= (xy_bddvar_map
*)malloc(sizeof(xy_bddvar_map
));
134 memset(f
, 0, sizeof(xy_bddvar_map
));
135 f
->key
.x
= r
->coord
.x
;
136 f
->key
.y
= r
->coord
.y
;
137 f
->value
.var
[0] = varcount
;
138 f
->value
.var
[1] = varcount
+ 1;
139 f
->value
.var
[2] = varcount
+ 2;
140 HASH_ADD(hh
, xybdd
, key
, sizeof(xy
), f
);
142 for (int i
= 0; i
<3; i
++){
143 bddvar_xy_map
*t
= NULL
;
144 t
= (bddvar_xy_map
*)malloc(sizeof(bddvar_xy_map
));
145 memset(t
, 0, sizeof(bddvar_xy_map
));
146 t
->key
= varcount
+ i
;
147 t
->value
.x
= r
->coord
.x
;
148 t
->value
.y
= r
->coord
.y
;
149 HASH_ADD(hh
, bddxy
, key
, sizeof(int), t
);
151 varcount
= varcount
+ 3;
154 bm
= (bimap
*)malloc(sizeof(bimap
));
161 * Each coordinate has three related boolean variables. The combination of those boolean variables
169 * 110: Agent on target
170 * In the BDD representation, the state is represented by n * 3 variables, where n is the number of
171 * tiles in the shrinked screen.
172 * It seems that the move variable is not necessary since non-deterministic moves can be emvedded
173 * directly in transition relations.
176 state
*encode_screen(sokoban_screen
*screen
)
180 BDDVAR vars
[HASH_COUNT(screen
) * 3];
181 for (uint8_t i
= 0; i
< HASH_COUNT(screen
) * 3; i
++){
185 uint8_t st_enc
[HASH_COUNT(screen
) * 3];
187 BDDSET varset
= sylvan_set_fromarray(vars
, HASH_COUNT(screen
) * 3);
189 state
*fullState
= NULL
;
190 fullState
= (state
*)malloc(sizeof(state
));
191 fullState
->vars
.varset
= varset
;
192 fullState
->vars
.size
= HASH_COUNT(screen
) * 3;
195 for(r
=screen
; r
!= NULL
; r
= (sokoban_screen
*)(r
->hh
.next
)){
198 st_enc
[tile_index
] = 0;
200 st_enc
[tile_index
] = 0;
202 st_enc
[tile_index
] = 1;
206 st_enc
[tile_index
] = 0;
208 st_enc
[tile_index
] = 0;
210 st_enc
[tile_index
] = 0;
214 st_enc
[tile_index
] = 0;
216 st_enc
[tile_index
] = 1;
218 st_enc
[tile_index
] = 0;
222 st_enc
[tile_index
] = 0;
224 st_enc
[tile_index
] = 1;
226 st_enc
[tile_index
] = 1;
230 st_enc
[tile_index
] = 1;
232 st_enc
[tile_index
] = 0;
234 st_enc
[tile_index
] = 1;
237 case TARGAGENT
: //110
238 st_enc
[tile_index
] = 1;
240 st_enc
[tile_index
] = 1;
242 st_enc
[tile_index
] = 0;
246 st_enc
[tile_index
] = 1;
248 st_enc
[tile_index
] = 0;
250 st_enc
[tile_index
] = 0;
256 xy_bddvar_map *map = NULL;
257 map = create_xy_bddvar_map(screen);
258 xy_bddvar_map *m = getxy(1, 1, map);
259 bddvar_xy_map *map2 = NULL;
260 map2 = create_bddvar_xy_map(screen);
261 bddvar_xy_map *m2 = getbdd(2, map2);
262 printf("Test1: %d %d\n", m->value.var[0], m->value.var[1]);
263 printf("Test2: %d %d\n", m2->value.x, m2->value.y);
265 /* some more testing...
267 bm = create_bimap_helper(screen);
268 xy_bddvar_map *m = getxy(1, 1, bm->f);
269 bddvar_xy_map *m2 = getbdd(2, bm->t);
270 printf("Test1: %d %d\n", m->value.var[0], m->value.var[1]);
271 printf("Test2: %d %d\n", m2->value.x, m2->value.y);
272 printf("%d tiles were encoded\n", tile_index);
273 if (bm != NULL) printf ("WORKS!\n");
275 s
= sylvan_cube(varset
, st_enc
);
277 printf("Initial state encoded\n");
281 BDD
encode_rel(sokoban_screen
*screen
)
284 num_tiles
= HASH_COUNT(screen
);
285 printf("Number of tiles: %d\n", num_tiles
);