ref: b24ed2bfac81798221977ffed8980d2b4eeab199
dir: /sys/src/games/sokoban/route.c/
#include <u.h> #include <libc.h> #include <draw.h> #include "sokoban.h" static int dirlist[] = { Up, Down, Left, Right, Up, Down, Left, Right, }; static int ndir = 4; static Point dir2point(int dir) { switch(dir) { case Up: return Pt(0, -1); case Down: return Pt(0, 1); case Left: return Pt(-1, 0); case Right: return Pt(1, 0); } return Pt(0,0); } int validpush(Point g, Step *s, Point *t) { int i; Point m; if (s == nil) return 0; m = dir2point(s->dir); // first test for Cargo next to us (in direction dir) if (s->count > 0) { g = addpt(g, m); if (!ptinrect(g, Rpt(Pt(0,0), level.max))) return 0; switch (level.board[g.x][g.y]) { case Wall: case Empty: case Goal: return 0; } } // then test for enough free space for us _and_ Cargo for (i=0; i < s->count; i++) { g = addpt(g, m); if (!ptinrect(g, Rpt(Pt(0,0), level.max))) return 0; switch (level.board[g.x][g.y]) { case Wall: case Cargo: case GoalCargo: return 0; } } if (t != nil) *t = g; return 1; } int isvalid(Point s, Route* r, int (*isallowed)(Point, Step*, Point*)) { Point m; Step *p; if (r == nil) return 0; m = s; for (p = r->step; p < r->step + r->nstep; p++) if (!isallowed(m, p, &m)) return 0; return 1; } static Walk* newwalk(void) { Walk *w; w = mallocz(sizeof *w, 1); if (w == nil) sysfatal("cannot allocate walk"); return w; } static void resetwalk(Walk *w) { Route **p; if (w == nil || w->route == nil) return; for (p=w->route; p < w->route + w->nroute; p++) freeroute(*p); w->nroute = 0; } static void freewalk(Walk *w) { if (w == nil) return; resetwalk(w); if(w->route) free(w->route); free(w); } static void addroute(Walk *w, Route *r) { if (w == nil || r == nil) return; if (w->beyond < w->nroute+1) { w->beyond = w->nroute+1; w->route = realloc(w->route, sizeof(Route*)*w->beyond); } if (w->route == nil) sysfatal("cannot allocate route in addroute"); w->route[w->nroute] = r; w->nroute++; } void freeroute(Route *r) { if (r == nil) return; free(r->step); free(r); } Route* extend(Route *rr, int dir, int count, Point dest) { Route *r; r = mallocz(sizeof *r, 1); if (r == nil) sysfatal("cannot allocate route in extend"); r->dest = dest; if (count > 0) { r->nstep = 1; if (rr != nil) r->nstep += rr->nstep; r->step = malloc(sizeof(Step)*r->nstep); if (r->step == nil) sysfatal("cannot allocate step in extend"); if (rr != nil) memmove(r->step, rr->step, sizeof(Step)*rr->nstep); r->step[r->nstep-1].dir = dir; r->step[r->nstep-1].count = count; } return r; } static Step* laststep(Route*r) { if (r != nil && r->nstep > 0) return &r->step[r->nstep-1]; return nil; } static int* startwithdirfromroute(Route *r, int* dl, int n) { Step *s; int *p; if (r == nil || dl == nil) return dl; s = laststep(r); if (s == nil || s->count == 0) return dl; for (p=dl; p < dl + n; p++) if (*p == s->dir) break; return p; } static Route* bfstrydir(Route *r, int dir, Visited *v) { Point m, p, n; if (r == nil) return nil; m = r->dest; p = dir2point(dir); n = addpt(m, p); if (ptinrect(n, Rpt(Pt(0,0), level.max)) && v->board[n.x][n.y] == 0) { v->board[n.x][n.y] = 1; switch (level.board[n.x][n.y]) { case Empty: case Goal: return extend(r, dir, 1, n); } } return nil; } static Route* bfs(Point src, Point dst, Visited *v) { Walk *cur, *new, *tmp; Route *r, **p; int progress, *dirs, *dirp; Point n; if (v == nil) return nil; cur = newwalk(); new = newwalk(); v->board[src.x][src.y] = 1; r = extend(nil, 0, 0, src); if (eqpt(src, dst)) { freewalk(cur); freewalk(new); return r; } addroute(cur, r); progress = 1; while (progress) { progress = 0; for (p=cur->route; p < cur->route + cur->nroute; p++) { dirs = startwithdirfromroute(*p, dirlist, ndir); for (dirp=dirs; dirp < dirs + ndir; dirp++) { r = bfstrydir(*p, *dirp, v); if (r != nil) { progress = 1; n = r->dest; if (eqpt(n, dst)) { freewalk(cur); freewalk(new); return(r); } addroute(new, r); } } } resetwalk(cur); tmp = cur; cur = new; new = tmp; } freewalk(cur); freewalk(new); return nil; } Route* findroute(Point src, Point dst) { Visited v; Route* r; memset(&v, 0, sizeof(Visited)); r = bfs(src, dst, &v); return r; }