f5774a6b66ec6f3dbc07771696fd46f82e9ef133
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
));
160 int check_xy_exists(int x
, int y
, bimap
*bm
)
163 if (getxy(x
, y
, bm
->f
) != NULL
) res
= 1;
167 int check_space(int x
, int y
, direction d
, int delta
, bimap
*bm
)
170 case LEFT
: x
= x
- delta
; break;
171 case UP
: y
= y
- delta
; break;
172 case RIGHT
: x
= x
+ delta
; break;
173 case DOWN
: y
= y
+ delta
; break;
175 return check_xy_exists(x
, y
, bm
);
179 * Each coordinate has three related boolean variables. The combination of those boolean variables
187 * 110: Agent on target
188 * In the BDD representation, the state is represented by n * 3 variables, where n is the number of
189 * tiles in the shrinked screen.
190 * It seems that the move variable is not necessary since non-deterministic moves can be emvedded
191 * directly in transition relations.
194 state
*encode_screen(sokoban_screen
*screen
)
198 BDDVAR vars
[HASH_COUNT(screen
) * 3];
199 for (uint8_t i
= 0; i
< HASH_COUNT(screen
) * 3; i
++){
203 uint8_t st_enc
[HASH_COUNT(screen
) * 3];
205 BDDSET varset
= sylvan_set_fromarray(vars
, HASH_COUNT(screen
) * 3);
207 state
*fullState
= NULL
;
208 fullState
= (state
*)malloc(sizeof(state
));
209 fullState
->vars
.varset
= varset
;
210 fullState
->vars
.size
= HASH_COUNT(screen
) * 3;
213 for(r
=screen
; r
!= NULL
; r
= (sokoban_screen
*)(r
->hh
.next
)){
216 st_enc
[tile_index
] = 0;
218 st_enc
[tile_index
] = 0;
220 st_enc
[tile_index
] = 1;
224 st_enc
[tile_index
] = 0;
226 st_enc
[tile_index
] = 0;
228 st_enc
[tile_index
] = 0;
232 st_enc
[tile_index
] = 0;
234 st_enc
[tile_index
] = 1;
236 st_enc
[tile_index
] = 0;
240 st_enc
[tile_index
] = 0;
242 st_enc
[tile_index
] = 1;
244 st_enc
[tile_index
] = 1;
248 st_enc
[tile_index
] = 1;
250 st_enc
[tile_index
] = 0;
252 st_enc
[tile_index
] = 1;
255 case TARGAGENT
: //110
256 st_enc
[tile_index
] = 1;
258 st_enc
[tile_index
] = 1;
260 st_enc
[tile_index
] = 0;
264 st_enc
[tile_index
] = 1;
266 st_enc
[tile_index
] = 0;
268 st_enc
[tile_index
] = 0;
274 xy_bddvar_map *map = NULL;
275 map = create_xy_bddvar_map(screen);
276 xy_bddvar_map *m = getxy(1, 1, map);
277 bddvar_xy_map *map2 = NULL;
278 map2 = create_bddvar_xy_map(screen);
279 bddvar_xy_map *m2 = getbdd(2, map2);
280 printf("Test1: %d %d\n", m->value.var[0], m->value.var[1]);
281 printf("Test2: %d %d\n", m2->value.x, m2->value.y);
283 /* some more testing...
285 bm = create_bimap_helper(screen);
286 xy_bddvar_map *m = getxy(1, 1, bm->f);
287 bddvar_xy_map *m2 = getbdd(2, bm->t);
288 printf("Test1: %d %d\n", m->value.var[0], m->value.var[1]);
289 printf("Test2: %d %d\n", m2->value.x, m2->value.y);
290 printf("%d tiles were encoded\n", tile_index);
291 if (bm != NULL) printf ("WORKS!\n");
293 s
= sylvan_cube(varset
, st_enc
);
295 printf("Initial state encoded\n");
299 BDD
encode_rel(sokoban_screen
*screen
)
302 num_tiles
= HASH_COUNT(screen
);
303 printf("Number of tiles: %d\n", num_tiles
);