c74c2fe80916988cfdb646a61aa2041a9b69d87a
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
53 xy_bddvar_map
*getxy(int x
, int y
, xy_bddvar_map
*map
)
55 xy_bddvar_map k
, *r
= NULL
;
56 memset(&k
, 0, sizeof(xy_bddvar_map
));
59 HASH_FIND(hh
, map
, &k
.key
, sizeof(xy
), r
);
63 bddvar_xy_map
*getbdd(int key
, bddvar_xy_map
*map
)
65 bddvar_xy_map k
, *r
= NULL
;
66 memset(&k
, 0, sizeof(bddvar_xy_map
));
68 HASH_FIND(hh
, map
, &k
.key
, sizeof(int), r
);
72 xy_bddvar_map
*create_xy_bddvar_map(sokoban_screen
*screen
)
76 xy_bddvar_map
*xybdd
= NULL
;
77 for(r
=screen
; r
!= NULL
; r
= (sokoban_screen
*)(r
->hh
.next
)){
78 xy_bddvar_map
*f
= NULL
;
79 //bddvar_xy_map *t = NULL;
81 f
= (xy_bddvar_map
*)malloc(sizeof(xy_bddvar_map
));
82 memset(f
, 0, sizeof(xy_bddvar_map
));
83 f
->key
.x
= r
->coord
.x
;
84 f
->key
.y
= r
->coord
.y
;
85 f
->value
.var
[0] = varcount
;
86 f
->value
.var
[1] = varcount
+ 1;
87 f
->value
.var
[2] = varcount
+ 2;
88 HASH_ADD(hh
, xybdd
, key
, sizeof(xy
), f
);
89 varcount
= varcount
+ 3;
94 bddvar_xy_map
*create_bddvar_xy_map(sokoban_screen
*screen
)
98 bddvar_xy_map
*bddxy
= NULL
;
99 for(r
=screen
; r
!= NULL
; r
= (sokoban_screen
*)(r
->hh
.next
)){
100 for (int i
= 0; i
<3; i
++){
101 bddvar_xy_map
*f
= NULL
;
102 //bddvar_xy_map *t = NULL;
104 f
= (bddvar_xy_map
*)malloc(sizeof(bddvar_xy_map
));
105 memset(f
, 0, sizeof(bddvar_xy_map
));
106 f
->key
= varcount
+ i
;
107 f
->value
.x
= r
->coord
.x
;
108 f
->value
.y
= r
->coord
.y
;
109 HASH_ADD(hh
, bddxy
, key
, sizeof(int), f
);
111 varcount
= varcount
+ 3;
116 bimap
*create_bimap_helper(sokoban_screen
*screen
)
120 xy_bddvar_map
*xybdd
= NULL
;
121 bddvar_xy_map
*bddxy
= NULL
;
122 for(r
=screen
; r
!= NULL
; r
= (sokoban_screen
*)(r
->hh
.next
)){
123 xy_bddvar_map
*f
= NULL
;
124 f
= (xy_bddvar_map
*)malloc(sizeof(xy_bddvar_map
));
125 memset(f
, 0, sizeof(xy_bddvar_map
));
126 f
->key
.x
= r
->coord
.x
;
127 f
->key
.y
= r
->coord
.y
;
128 f
->value
.var
[0] = varcount
;
129 f
->value
.var
[1] = varcount
+ 1;
130 f
->value
.var
[2] = varcount
+ 2;
131 HASH_ADD(hh
, xybdd
, key
, sizeof(xy
), f
);
133 for (int i
= 0; i
<3; i
++){
134 bddvar_xy_map
*t
= NULL
;
135 t
= (bddvar_xy_map
*)malloc(sizeof(bddvar_xy_map
));
136 memset(t
, 0, sizeof(bddvar_xy_map
));
137 t
->key
= varcount
+ i
;
138 t
->value
.x
= r
->coord
.x
;
139 t
->value
.y
= r
->coord
.y
;
140 HASH_ADD(hh
, bddxy
, key
, sizeof(int), t
);
142 varcount
= varcount
+ 3;
145 bm
= (bimap
*)malloc(sizeof(bimap
));
152 * Each coordinate has three related boolean variables. The combination of those boolean variables
160 * 110: Agent on target
161 * In the BDD representation, the state is represented by n * 3 variables, where n is the number of
162 * tiles in the shrinked screen.
163 * It seems that the move variable is not necessary since non-deterministic moves can be emvedded
164 * directly in transition relations.
167 BDD
encode_screen(sokoban_screen
*screen
)
169 BDD state
= sylvan_false
;
173 for(r
=screen
; r
!= NULL
; r
= (sokoban_screen
*)(r
->hh
.next
)){
176 if (state
== sylvan_false
){
177 state
= sylvan_not(sylvan_ithvar(tile_index
));
179 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
181 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
185 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
187 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
189 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
194 if (state
== sylvan_false
){
195 state
= sylvan_not(sylvan_ithvar(tile_index
));
197 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
199 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
203 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
205 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
207 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
212 if (state
== sylvan_false
){
213 state
= sylvan_not(sylvan_ithvar(tile_index
));
215 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
217 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
221 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
223 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
225 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
230 if (state
== sylvan_false
){
231 state
= sylvan_not(sylvan_ithvar(tile_index
));
233 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
235 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
239 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
241 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
243 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
248 if (state
== sylvan_false
){
249 state
= sylvan_ithvar(tile_index
);
251 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
253 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
257 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
259 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
261 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
266 if (state
== sylvan_false
){
267 state
= sylvan_ithvar(tile_index
);
269 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
271 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
275 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
277 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
279 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
284 if (state
== sylvan_false
){
285 state
= sylvan_ithvar(tile_index
);
287 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
289 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
293 state
= sylvan_and(state
, sylvan_ithvar(tile_index
));
295 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
297 state
= sylvan_and(state
, sylvan_not(sylvan_ithvar(tile_index
)));
304 xy_bddvar_map *map = NULL;
305 map = create_xy_bddvar_map(screen);
306 xy_bddvar_map *m = getxy(1, 1, map);
307 bddvar_xy_map *map2 = NULL;
308 map2 = create_bddvar_xy_map(screen);
309 bddvar_xy_map *m2 = getbdd(2, map2);
310 printf("Test1: %d %d\n", m->value.var[0], m->value.var[1]);
311 printf("Test2: %d %d\n", m2->value.x, m2->value.y);
315 bm = create_bimap_helper(screen);
316 xy_bddvar_map *m = getxy(1, 1, bm->f);
317 bddvar_xy_map *m2 = getbdd(2, bm->t);
318 printf("Test1: %d %d\n", m->value.var[0], m->value.var[1]);
319 printf("Test2: %d %d\n", m2->value.x, m2->value.y);
320 printf("%d tiles were encoded\n", tile_index);
321 if (bm != NULL) printf ("WORKS!\n");
326 BDD
encode_rel(sokoban_screen
*screen
)
329 num_tiles
= HASH_COUNT(screen
);
330 printf("Number of tiles: %d\n", num_tiles
);
339 BDD b
= sylvan_not(a
);
340 if (b
== sylvan_false
){
341 printf("BDD works!\n");
343 printf("BDD does not work!\n");
346 BDD c
= sylvan_ithvar(1);
347 if (sylvan_high(c
) == sylvan_true
&& sylvan_low(c
) == sylvan_false
) printf("VAR works 1\n");
348 if (sylvan_var(c
) == 1) printf("Var works 2\n");