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
77 xy_bddvar_map
*getxy(int x
, int y
, xy_bddvar_map
*map
)
79 xy_bddvar_map k
, *r
= NULL
;
80 memset(&k
, 0, sizeof(xy_bddvar_map
));
83 HASH_FIND(hh
, map
, &k
.key
, sizeof(xy
), r
);
87 bddvar_xy_map
*getbdd(int key
, bddvar_xy_map
*map
)
89 bddvar_xy_map k
, *r
= NULL
;
90 memset(&k
, 0, sizeof(bddvar_xy_map
));
92 HASH_FIND(hh
, map
, &k
.key
, sizeof(int), r
);
97 xy_bddvar_map *create_xy_bddvar_map(sokoban_screen *screen)
101 xy_bddvar_map *xybdd = NULL;
102 for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
103 xy_bddvar_map *f = NULL;
104 //bddvar_xy_map *t = NULL;
106 f = (xy_bddvar_map *)malloc(sizeof(xy_bddvar_map));
107 memset(f, 0, sizeof(xy_bddvar_map));
108 f->key.x = r->coord.x;
109 f->key.y = r->coord.y;
110 f->value.var[0] = varcount;
111 f->value.var[1] = varcount + 1;
112 f->value.var[2] = varcount + 2;
113 HASH_ADD(hh, xybdd, key, sizeof(xy), f);
114 varcount = varcount + 3;
119 bddvar_xy_map *create_bddvar_xy_map(sokoban_screen *screen)
123 bddvar_xy_map *bddxy = NULL;
124 for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
125 for (int i = 0; i <3; i++){
126 bddvar_xy_map *f = NULL;
127 //bddvar_xy_map *t = NULL;
129 f = (bddvar_xy_map *)malloc(sizeof(bddvar_xy_map));
130 memset(f, 0, sizeof(bddvar_xy_map));
131 f->key = varcount + i;
132 f->value.x = r->coord.x;
133 f->value.y = r->coord.y;
134 HASH_ADD(hh, bddxy, key, sizeof(int), f);
136 varcount = varcount + 3;
142 bimap
*create_bimap_helper(sokoban_screen
*screen
)
146 xy_bddvar_map
*xybdd
= NULL
;
147 bddvar_xy_map
*bddxy
= NULL
;
148 for(r
=screen
; r
!= NULL
; r
= (sokoban_screen
*)(r
->hh
.next
)){
149 xy_bddvar_map
*f
= NULL
;
150 f
= (xy_bddvar_map
*)malloc(sizeof(xy_bddvar_map
));
151 memset(f
, 0, sizeof(xy_bddvar_map
));
152 f
->key
.x
= r
->coord
.x
;
153 f
->key
.y
= r
->coord
.y
;
154 f
->value
.var
[0] = varcount
;
155 f
->value
.var
[1] = varcount
+ 1;
156 f
->value
.var
[2] = varcount
+ 2;
157 HASH_ADD(hh
, xybdd
, key
, sizeof(xy
), f
);
159 for (int i
= 0; i
<3; i
++){
160 bddvar_xy_map
*t
= NULL
;
161 t
= (bddvar_xy_map
*)malloc(sizeof(bddvar_xy_map
));
162 memset(t
, 0, sizeof(bddvar_xy_map
));
163 t
->key
= varcount
+ i
;
164 t
->value
.x
= r
->coord
.x
;
165 t
->value
.y
= r
->coord
.y
;
166 HASH_ADD(hh
, bddxy
, key
, sizeof(int), t
);
168 varcount
= varcount
+ 3;
171 bm
= (bimap
*)malloc(sizeof(bimap
));
178 * Each coordinate has three related boolean variables. The combination of those boolean variables
186 * 110: Agent on target
187 * In the BDD representation, the state is represented by n * 3 variables, where n is the number of
188 * tiles in the shrinked screen.
189 * It seems that the move variable is not necessary since non-deterministic moves can be emvedded
190 * directly in transition relations.
193 BDD
encode_screen(sokoban_screen
*screen
)
197 BDDVAR vars
[HASH_COUNT(screen
) * 3];
198 for (uint8_t i
= 0; i
< HASH_COUNT(screen
) * 3; i
++){
202 uint8_t st_enc
[HASH_COUNT(screen
) * 3];
204 BDDSET varset
= sylvan_set_fromarray(vars
, HASH_COUNT(screen
) * 3);
208 for(r
=screen
; r
!= NULL
; r
= (sokoban_screen
*)(r
->hh
.next
)){
211 st_enc
[tile_index
] = 0;
213 st_enc
[tile_index
] = 0;
215 st_enc
[tile_index
] = 1;
219 st_enc
[tile_index
] = 0;
221 st_enc
[tile_index
] = 0;
223 st_enc
[tile_index
] = 0;
227 st_enc
[tile_index
] = 0;
229 st_enc
[tile_index
] = 1;
231 st_enc
[tile_index
] = 0;
235 st_enc
[tile_index
] = 0;
237 st_enc
[tile_index
] = 1;
239 st_enc
[tile_index
] = 1;
243 st_enc
[tile_index
] = 1;
245 st_enc
[tile_index
] = 0;
247 st_enc
[tile_index
] = 1;
250 case TARGAGENT
: //110
251 st_enc
[tile_index
] = 1;
253 st_enc
[tile_index
] = 1;
255 st_enc
[tile_index
] = 0;
259 st_enc
[tile_index
] = 1;
261 st_enc
[tile_index
] = 0;
263 st_enc
[tile_index
] = 0;
269 xy_bddvar_map *map = NULL;
270 map = create_xy_bddvar_map(screen);
271 xy_bddvar_map *m = getxy(1, 1, map);
272 bddvar_xy_map *map2 = NULL;
273 map2 = create_bddvar_xy_map(screen);
274 bddvar_xy_map *m2 = getbdd(2, map2);
275 printf("Test1: %d %d\n", m->value.var[0], m->value.var[1]);
276 printf("Test2: %d %d\n", m2->value.x, m2->value.y);
278 /* some more testing...
280 bm = create_bimap_helper(screen);
281 xy_bddvar_map *m = getxy(1, 1, bm->f);
282 bddvar_xy_map *m2 = getbdd(2, bm->t);
283 printf("Test1: %d %d\n", m->value.var[0], m->value.var[1]);
284 printf("Test2: %d %d\n", m2->value.x, m2->value.y);
285 printf("%d tiles were encoded\n", tile_index);
286 if (bm != NULL) printf ("WORKS!\n");
288 state
= sylvan_cube(varset
, st_enc
);
289 printf("Initial state encoded\n");
293 BDD
encode_rel(sokoban_screen
*screen
)
296 num_tiles
= HASH_COUNT(screen
);
297 printf("Number of tiles: %d\n", num_tiles
);