sys/src/games/sokoban/route.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <draw.h>
   4
   5 #include "sokoban.h"
   6
   7 static int dirlist[] = { Up, Down, Left, Right, Up, Down, Left, Right, };
   8 static int ndir = 4;
   9
  10 static Point
  11 dir2point(int dir)
  12 {
  13         switch(dir) {
  14         case Up:
  15                 return Pt(0, -1);
  16         case Down:
  17                 return Pt(0, 1);
  18         case Left:
  19                 return Pt(-1, 0);
  20         case Right:
  21                 return Pt(1, 0);
  22         }
  23         return Pt(0,0);
  24 }
  25
  26 int
  27 validpush(Point g, Step *s, Point *t)
  28 {
  29         int i;
  30         Point m;
  31
  32         if (s == nil)
  33                 return 0;
  34
  35         m = dir2point(s->dir);
  36
  37         // first test for  Cargo next to us (in direction dir)
  38         if (s->count > 0) {
  39                 g = addpt(g, m);
  40                 if (!ptinrect(g, Rpt(Pt(0,0), level.max)))
  41                         return 0;
  42                 switch (level.board[g.x][g.y]) {
  43                 case Wall:
  44                 case Empty:
  45                 case Goal:
  46                         return 0;
  47                 }
  48         }
  49         // then test for  enough free space for us _and_ Cargo
  50         for (i=0; i < s->count; i++) {
  51                 g = addpt(g, m);
  52                 if (!ptinrect(g, Rpt(Pt(0,0), level.max)))
  53                         return 0;
  54                 switch (level.board[g.x][g.y]) {
  55                 case Wall:
  56                 case Cargo:
  57                 case GoalCargo:
  58                         return 0;
  59                 }
  60         }
  61         if (t != nil)
  62                 *t = g;
  63         return 1;
  64 }
  65
  66 int
  67 isvalid(Point s, Route* r, int (*isallowed)(Point, Step*, Point*))
  68 {
  69         Point m;
  70         Step *p;
  71
  72         if (r == nil)
  73                 return 0;
  74
  75         m = s;
  76         for (p = r->step; p < r->step + r->nstep; p++)
  77                 if (!isallowed(m, p, &m))
  78                         return 0;
  79         return 1;
  80 }
  81
  82 static Walk*
  83 newwalk(void)
  84 {
  85         Walk *w;
  86
  87         w = mallocz(sizeof *w, 1);
  88         if (w == nil)
  89                 sysfatal("cannot allocate walk");
  90         return w;
  91 }
  92
  93 static void
  94 resetwalk(Walk *w)
  95 {
  96         Route **p;
  97
  98         if (w == nil || w->route == nil)
  99                 return;
 100
 101         for (p=w->route; p < w->route + w->nroute; p++)
 102                 freeroute(*p);
 103         w->nroute = 0;
 104 }
 105
 106 static void
 107 freewalk(Walk *w)
 108 {
 109         if (w == nil)
 110                 return;
 111
 112         resetwalk(w);
 113         if(w->route)
 114                 free(w->route);
 115         free(w);
 116 }
 117
 118 static void
 119 addroute(Walk *w, Route *r)
 120 {
 121         if (w == nil || r == nil)
 122                 return;
 123
 124         if (w->beyond < w->nroute+1) {
 125                 w->beyond = w->nroute+1;
 126                 w->route = realloc(w->route, sizeof(Route*)*w->beyond);
 127         }
 128         if (w->route == nil)
 129                 sysfatal("cannot allocate route in addroute");
 130         w->route[w->nroute] = r;
 131         w->nroute++;
 132 }
 133
 134 void
 135 freeroute(Route *r)
 136 {
 137         if (r == nil)
 138                 return;
 139         free(r->step);
 140         free(r);
 141 }
 142
 143 Route*
 144 extend(Route *rr, int dir, int count, Point dest)
 145 {
 146         Route *r;
 147
 148         r = mallocz(sizeof *r, 1);
 149         if (r == nil)
 150                 sysfatal("cannot allocate route in extend");
 151         r->dest = dest;
 152
 153         if (count > 0) {
 154                 r->nstep = 1;
 155                 if (rr != nil)
 156                         r->nstep += rr->nstep;
 157
 158                 r->step = malloc(sizeof(Step)*r->nstep);
 159                 if (r->step == nil)
 160                         sysfatal("cannot allocate step in extend");
 161
 162                 if (rr != nil)
 163                         memmove(r->step, rr->step, sizeof(Step)*rr->nstep);
 164
 165                 r->step[r->nstep-1].dir = dir;
 166                 r->step[r->nstep-1].count = count;
 167         }
 168         return r;
 169 }
 170
 171 static Step*
 172 laststep(Route*r)
 173 {
 174         if (r != nil && r->nstep > 0)
 175                 return &r->step[r->nstep-1];
 176         return nil;
 177 }
 178
 179 static int*
 180 startwithdirfromroute(Route *r, int* dl, int n)
 181 {
 182         Step *s;
 183         int *p;
 184
 185         if (r == nil || dl == nil)
 186                 return dl;
 187
 188         s =  laststep(r);
 189         if (s == nil || s->count == 0)
 190                 return dl;
 191
 192         for (p=dl; p < dl + n; p++)
 193                 if (*p == s->dir)
 194                         break;
 195         return p;
 196 }
 197
 198 static Route*
 199 bfstrydir(Route *r, int dir, Visited *v)
 200 {
 201         Point m, p, n;
 202
 203         if (r == nil)
 204                 return nil;
 205
 206         m = r->dest;
 207         p = dir2point(dir);
 208         n = addpt(m, p);
 209
 210         if (ptinrect(n, Rpt(Pt(0,0), level.max)) && v->board[n.x][n.y] == 0) {
 211                 v->board[n.x][n.y] = 1;
 212                 switch (level.board[n.x][n.y]) {
 213                 case Empty:
 214                 case Goal:
 215                         return extend(r, dir, 1, n);
 216                 }
 217         }
 218         return nil;
 219 }
 220
 221 static Route*
 222 bfs(Point src, Point dst, Visited *v)
 223 {
 224         Walk *cur, *new, *tmp;
 225         Route *r, **p;
 226         int progress, *dirs, *dirp;
 227         Point n;
 228
 229         if (v == nil)
 230                 return nil;
 231
 232         cur = newwalk();
 233         new = newwalk();
 234         v->board[src.x][src.y] = 1;
 235         r = extend(nil, 0, 0, src);
 236         if (eqpt(src, dst)) {
 237                 freewalk(cur);
 238                 freewalk(new);
 239                 return r;
 240         }
 241         addroute(cur, r);
 242         progress = 1;
 243         while (progress) {
 244                 progress = 0;
 245                 for (p=cur->route; p < cur->route + cur->nroute; p++) {
 246                         dirs = startwithdirfromroute(*p, dirlist, ndir);
 247                         for (dirp=dirs; dirp < dirs + ndir; dirp++) {
 248                                 r = bfstrydir(*p, *dirp, v);
 249                                 if (r != nil) {
 250                                         progress = 1;
 251                                         n = r->dest;
 252                                         if (eqpt(n, dst)) {
 253                                                 freewalk(cur);
 254                                                 freewalk(new);
 255                                                 return(r);
 256                                         }
 257                                         addroute(new, r);
 258                                 }
 259                         }
 260                 }
 261                 resetwalk(cur);
 262                 tmp = cur;
 263                 cur = new;
 264                 new = tmp;
 265         }
 266         freewalk(cur);
 267         freewalk(new);
 268         return nil;
 269 }
 270
 271 Route*
 272 findroute(Point src, Point dst)
 273 {
 274         Visited v;
 275         Route* r;
 276
 277         memset(&v, 0, sizeof(Visited));
 278         r = bfs(src, dst, &v);
 279         return r;
 280 }