modelchecker/sokoban.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include "sokoban.h"
   4
   5 sokoban_screen *add_coord(int x, int y, sokoban_tile tile, sokoban_screen *screen)
   6 {
   7         sokoban_screen *r = NULL;
   8
   9         r = (sokoban_screen *)malloc(sizeof(sokoban_screen));
  10         memset(r, 0, sizeof(sokoban_screen));
  11         r->coord.x = x;
  12         r->coord.y = y;
  13         r->tile = tile;
  14         HASH_ADD(hh, screen, coord, sizeof(record_key), r);
  15         return screen;
  16 }
  17
  18 sokoban_screen *get_coord(int x, int y, sokoban_screen *screen)
  19 {
  20         sokoban_screen k, *r = NULL;
  21         memset(&k, 0, sizeof(sokoban_screen));
  22         k.coord.x = x;
  23         k.coord.y = y;
  24         HASH_FIND(hh, screen, &k.coord, sizeof(record_key), r);
  25         return r;
  26 }
  27
  28 sokoban_screen *delete_coord(int x, int y, sokoban_screen *screen)
  29 {
  30         sokoban_screen *r = NULL;
  31         r = get_coord(x, y, screen);
  32         if (r) HASH_DEL(screen, r);
  33         return screen;
  34 }
  35
  36 void sokoban_print(sokoban_screen *screen)
  37 {
  38         sokoban_screen *r;
  39         for(r=screen; r != NULL; r = (sokoban_screen *)(r->hh.next)){
  40                 switch(r->tile){
  41                 case FREE: printf("x = %d y = %d FREE\n", r->coord.x, r->coord.y); break;
  42                 case WALL: printf("x = %d y = %d WALL\n", r->coord.x, r->coord.y); break;
  43                 case BOX: printf("x = %d y = %d BOX\n", r->coord.x, r->coord.y); break;
  44                 case TARGET: printf("x = %d y = %d TARGET\n", r->coord.x, r->coord.y); break;
  45                 case AGENT: printf("x = %d y = %d AGENT\n", r->coord.x, r->coord.y); break;
  46                 case TARGAGENT: printf("x = %d y = %d TARGAGENT\n", r->coord.x, r->coord.y); break;
  47                 case TARGBOX: printf("x = %d y = %d TARGBOX\n", r->coord.x, r->coord.y); break;
  48                 }
  49         }
  50 }
  51
  52 sokoban_screen *sokoban_shrink(int x, int y, sokoban_screen *screen, sokoban_screen *newscreen)
  53 {
  54         sokoban_screen *c, *nc = NULL;
  55         c = get_coord(x, y, screen);
  56         if (c) {
  57                 nc = get_coord(c->coord.x, c->coord.y, newscreen);
  58                 if (c->tile != WALL && nc == NULL) {
  59                         newscreen = add_coord(x, y, c->tile, newscreen);
  60                         newscreen = sokoban_shrink(x-1, y, screen, newscreen);
  61                         newscreen = sokoban_shrink(x+1, y, screen, newscreen);
  62                         newscreen = sokoban_shrink(x, y-1, screen, newscreen);
  63                         newscreen = sokoban_shrink(x, y+1, screen, newscreen);
  64                 }
  65         }
  66         return newscreen;
  67 }
  68
  69 void sokoban_free(sokoban_screen *screen)
  70 {
  71         sokoban_screen *r, *tmp = NULL;
  72         HASH_ITER(hh, screen, r, tmp) {
  73                 HASH_DEL(screen, r);
  74                 free(r);
  75         }
  76 }
  77
  78 sokoban_screen *parse_screen(FILE *stream, bool safe)
  79 {
  80         int buffer, x, y, agent_x, agent_y, boxes, targets, agents;
  81         x = 0;
  82         y = 0;
  83         agent_x = 0;
  84         agent_y = 0;
  85         boxes = 0;
  86         targets = 0;
  87         agents = 0;
  88         sokoban_screen *screen = NULL;
  89         while((buffer = fgetc(stream)) != EOF){
  90                 if (buffer == '\n'){
  91                         x = 0;
  92                         y++;
  93                 }
  94                 else {
  95                         switch(buffer) {
  96                         case ' ': screen = add_coord(x, y, FREE, screen); break;
  97                         case '@':
  98                                 screen = add_coord(x, y, AGENT, screen);
  99                                 agent_x = x;
 100                                 agent_y = y;
 101                                 agents++;
 102                                 break;
 103                         case '.':
 104                                 screen = add_coord(x, y, TARGET, screen);
 105                                 targets++;
 106                                 break;
 107                         case '#': screen = add_coord(x, y, WALL, screen); break;
 108                         case '$':
 109                                 screen = add_coord(x, y, BOX, screen);
 110                                 boxes++;
 111                                 break;
 112                         case '*':
 113                                 screen = add_coord(x, y, TARGBOX, screen);
 114                                 boxes++;
 115                                 targets++;
 116                                 break;
 117                         case '+':
 118                                 screen = add_coord(x, y, TARGAGENT, screen);
 119                                 agent_x = x;
 120                                 agent_y = y;
 121                                 agents++;
 122                                 targets++;
 123                                 break;
 124                         default: return NULL;
 125                         }
 126                         x++;
 127                 }
 128         }
 129         if(safe == true && boxes == 0){
 130                 fprintf(stderr,
 131                         "Invalid screen. You need at least 1 box\n");
 132                 exit(1);
 133         }
 134         if(safe == true && boxes != targets){
 135                 fprintf(stderr,
 136                         "Invalid screen. Boxes: %d, Targets: %d\n", boxes, targets);
 137                 exit(1);
 138         }
 139         if(safe == true && agents != 1){
 140                 fprintf(stderr,
 141                         "Invalid screen. There has to be exactly one agent. Found: %d\n",
 142                         agents);
 143                 exit(1);
 144         }
 145
 146         sokoban_screen *newscreen = NULL;
 147         newscreen = sokoban_shrink(agent_x, agent_y, screen, newscreen);
 148         sokoban_free(screen);
 149         return newscreen;
 150 }