Use breadth-first search to find shortest move sequence.
[rsc] --rw-rw-r-- M 209623 rsc sys 799 Sep 5 07:25 sys/src/games/sokoban/README
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/README:17,22 -
/n/sources/plan9/sys/src/games/sokoban/README:17,22
Otherwise, nothing will happen.
- The search algorithm is pretty simplistic;
+ The breadth-first search algorithm should find a fast route.
it can be seen in action by toggling the 'animate'
entry in the button 3 menu.
[rsc] --rw-rw-r-- M 209623 rsc sys 973 Sep 5 07:25 sys/src/games/sokoban/animation.c
[rsc] --rw-rw-r-- M 209623 rsc sys 4486 Sep 5 07:25 sys/src/games/sokoban/route.c
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/route.c:4,11 -
/n/sources/plan9/sys/src/games/sokoban/route.c:4,11
#include "sokoban.h"
- static int trydir(int, Point, Point, Route*, Visited*);
- static int dofind(Point, Point, Route*, Visited*);
+ static int dirlist[] = { Up, Down, Left, Right, Up, Down, Left, Right, };
+ static int ndir = 4;
static Point
dir2point(int dir)
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/route.c:23,95 -
/n/sources/plan9/sys/src/games/sokoban/route.c:23,45
return Pt(0,0);
}
- Route*
- newroute(void)
+ int
+ validpush(Point g, Step *s, Point *t)
{
- Route *r = malloc(sizeof(Route));
- memset(r, 0, sizeof(Route));
- return r;
- }
-
- void
- freeroute(Route *r)
- {
- if (r->step != nil) {
- free(r->step);
- memset(r, 0, sizeof(Route));
- }
- free(r);
- }
-
- void
- reverseroute(Route *r)
- {
int i;
- Step tmp;
+ Point m;
- for (i=1; i< r->nstep; i++) {
- tmp = r->step[i];
- r->step[i] = r->step[i-1];
- r->step[i-1] = tmp;
- }
- }
+ if (s == nil)
+ return 0;
- void
- pushstep(Route *r, int dir, int count)
- {
- if (r->beyond < r->nstep+1) {
- r->beyond = r->nstep+1;
- r->step = realloc(r->step, sizeof(Step)*r->beyond);
- }
- if (r->step == nil)
- exits("pushstep out of memory");
- r->step[r->nstep].dir = dir;
- r->step[r->nstep].count = count;
- r->nstep++;
- }
+ m = dir2point(s->dir);
- void
- popstep(Route*r)
- {
- if (r->nstep > 0) {
- r->nstep--;
- r->step[r->nstep].dir = 0;
- r->step[r->nstep].count = 0;
- }
- }
-
- int
- validpush(Point g, Step s, Point *t)
- {
- int i;
- Point m = dir2point(s.dir);
-
// first test for Cargo next to us (in direction dir)
- if (s.count > 0) {
+ 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]) {
+ switch (level.board[g.x][g.y]) {
case Wall:
case Empty:
case Goal:
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/route.c:97,107 -
/n/sources/plan9/sys/src/games/sokoban/route.c:47,57
}
}
// then test for enough free space for us _and_ Cargo
- for (i=0; i < s.count; i++) {
+ 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]) {
+ switch (level.board[g.x][g.y]) {
case Wall:
case Cargo:
case GoalCargo:
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/route.c:114,230 -
/n/sources/plan9/sys/src/games/sokoban/route.c:64,287
}
int
- validwalk(Point g, Step s, Point *t)
+ isvalid(Point s, Route* r, int (*isallowed)(Point, Step*, Point*))
{
- int i;
- Point m = dir2point(s.dir);
+ Point m;
+ Step *p;
- for (i=0; i < s.count; i++) {
- g = addpt(g, m);
- if (!ptinrect(g, Rpt(Pt(0,0), level.max)))
+ if (r == nil)
+ return 0;
+
+ m = s;
+ for (p=r->step; p < r->step +r->nstep; p++)
+ if (! isallowed(m, p, &m))
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*))
+ static Walk*
+ newwalk(void)
{
- int i;
- Point m = s;
+ Walk *w;
- for (i=0; i< r->nstep; i++)
- if (! isallowed(m, r->step[i], &m))
- return 0;
- return 1;
+ w = malloc(sizeof(Walk));
+ if (w->route == nil)
+ sysfatal("cannot allocate walk");
+ memset(w, 0, sizeof(Walk));
+ return w;
}
- static int
- trydir(int dir, Point m, Point d, Route *r, Visited *v)
+ static void
+ resetwalk(Walk *w)
{
- Point p = dir2point(dir);
- Point n = addpt(m, p);
+ Route **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:
- pushstep(r, dir, 1);
- if (dofind(n, d, r, v))
- return 1;
- else
- popstep(r);
- }
- }
- return 0;
+ if (w == nil || w->route == nil)
+ return;
+
+ for (p=w->route; p < w->route + w->nroute; p++)
+ freeroute(*p);
+ w->nroute = 0;
}
- static int
- dofind(Point m, Point d, Route *r, Visited *v)
+ static void
+ freewalk(Walk *w)
{
- if (eqpt(m, d))
- return 1;
+ if (w == nil)
+ return;
- v->board[m.x][m.y] = 1;
+ resetwalk(w);
+ if(w->route)
+ free(w->route);
+ free(w);
+ }
- return trydir(Left, m, d, r, v) ||
- trydir(Up, m, d, r, v) ||
- trydir(Right, m, d, r, v) ||
- trydir(Down, m, d, r, v);
+ 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++;
}
- static int
- dobfs(Point m, Point d, Route *r, Visited *v)
+ void
+ freeroute(Route *r)
{
- if (eqpt(m, d))
- return 1;
+ if (r == nil)
+ return;
+ if (r->step != nil)
+ free(r->step);
+ free(r);
+ }
- v->board[m.x][m.y] = 1;
+ Route*
+ extend(Route *rr, int dir, int count, Point dest)
+ {
+ Route *r;
- return trydir(Left, m, d, r, v) ||
- trydir(Up, m, d, r, v) ||
- trydir(Right, m, d, r, v) ||
- trydir(Down, m, d, r, v);
+ r = malloc(sizeof(Route));
+ if (r == nil)
+ sysfatal("cannot allocate route in extend");
+
+ memset(r, 0, sizeof(Route));
+
+ 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;
}
- int
- findwalk(Point src, Point dst, Route *r)
+ static Step*
+ laststep(Route*r)
{
- Visited* v;
- int found;
+ if (r != nil && r->nstep > 0) {
+ return &r->step[r->nstep-1];
+ }
+ return nil;
+ }
- v = malloc(sizeof(Visited));
- memset(v, 0, sizeof(Visited));
- found = dofind(src, dst, r, v);
- free(v);
+ static int*
+ startwithdirfromroute(Route *r, int* dl, int n)
+ {
+ Step *s;
+ int *p;
- return found;
+ 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;
}
- void
- applyroute(Route *r)
+ static Route*
+ bfstrydir(Route *r, int dir, Visited *v)
{
- int j, i;
-
- for (i=0; i< r->nstep; i++) {
- j = r->step[i].count;
- while (j > 0) {
- move(r->step[i].dir);
- if (animate) {
- drawscreen();
- sleep(200);
+ 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);
+ }
}
- j--;
}
+ 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;
}
[rsc] --rw-rw-r-- M 209623 jmk sys 6358 Sep 5 07:25 sys/src/games/sokoban/sokoban.c
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.c:18,24 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.c:18,23
char *GoalImage = "/sys/games/lib/sokoban/images/goal.bit";
char *WinImage = "/sys/games/lib/sokoban/images/win.bit";
-
char *buttons[] =
{
"restart",
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.c:29,46 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.c:28,63
0
};
+ char **levelnames;
+
Menu menu =
{
- buttons
+ buttons,
};
Menu lmenu =
{
- nil,
- genlevels,
- 0,
+ levelnames,
};
+ void
+ buildmenu(void)
+ {
+ int i;
+
+ if (levelnames != nil) {
+ for(i=0; levelnames[i] != 0; i++)
+ free(levelnames[i]);
+ }
+ levelnames = realloc(levelnames, sizeof(char*)*(numlevels+1));
+ if (levelnames == nil)
+ sysfatal("cannot allocate levelnames");
+ for(i=0; i < numlevels; i++)
+ levelnames[i] = genlevels(i);
+ levelnames[numlevels] = 0;
+ lmenu.item = levelnames;
+ }
+
Image *
eallocimage(Rectangle r, int repl, uint color)
{
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.c:119,125 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.c:136,142
mouse2route(Mouse m)
{
Point p, q;
- Route *r, *rr;
+ Route *r;
p = subpt(m.xy, screen->r.min);
p.x /= BoardX;
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.c:129,163 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.c:146,171
// fprint(2, "x=%d y=%d\n", q.x, q.y);
if (q.x == 0 && q.y == 0)
- return newroute();
+ return nil;
- r = newroute();
- if (q.x < 0)
- pushstep(r, Left, -q.x);
- if (q.x > 0)
- pushstep(r, Right, q.x);
+ if (q.x == 0 || q.y == 0) {
+ if (q.x < 0)
+ r = extend(nil, Left, -q.x, Pt(level.glenda.x, p.y));
+ else if (q.x > 0)
+ r = extend(nil, Right, q.x, Pt(level.glenda.x, p.y));
+ else if (q.y < 0)
+ r = extend(nil, Up, -q.y, level.glenda);
+ else if (q.y > 0)
+ r = extend(nil, Down, q.y, level.glenda);
+ else
+ r = nil;
- if (q.y < 0)
- pushstep(r, Up, -q.y);
- if (q.y > 0)
- pushstep(r, Down, q.y);
+ if (r != nil && isvalid(level.glenda, r, validpush))
+ return r;
+ freeroute(r);
+ }
- if ((q.x == 0 || q.y == 0) && isvalid(level.glenda, r, validpush))
- return r;
-
- if (isvalid(level.glenda, r, validwalk))
- return r;
- reverseroute(r);
- if (isvalid(level.glenda, r, validwalk))
- return r;
- freeroute(r);
-
- rr = newroute();
- if (findwalk(level.glenda, p, rr))
- return rr;
- freeroute(rr);
-
- return newroute();
+ return findroute(level.glenda, p);
}
char *
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.c:203,211 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.c:211,224
main(int argc, char **argv)
{
Mouse m;
- Event e;
+ Event ev;
+ int e;
Route *r;
+ int timer;
+ Animation a;
+ int animate;
+
if(argc == 2)
levelfile = argv[1];
else
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.c:215,220 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.c:228,234
fprint(2, "usage: %s [levelfile]\n", argv[0]);
exits("usage");
}
+ buildmenu();
animate = 0;
buttons[3] = animate ? "noanimate" : "animate";
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.c:223,241 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.c:237,264
sysfatal("initdraw failed: %r");
einit(Emouse|Ekeyboard);
+ timer = etimer(0, 200);
+ initanimation(&a);
+
allocimages();
glenda = gright;
eresized(0);
for(;;) {
- switch(event(&e)) {
+ e = event(&ev);
+ switch(e) {
case Emouse:
- m = e.mouse;
+ m = ev.mouse;
if(m.buttons&1) {
+ stopanimation(&a);
r = mouse2route(m);
- applyroute(r);
- freeroute(r);
- drawscreen();
+ if (r)
+ setupanimation(&a, r);
+ if (! animate) {
+ while(onestep(&a))
+ ;
+ drawscreen();
+ }
}
if(m.buttons&2) {
int l;
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.c:243,248 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.c:266,272
lmenu.lasthit = level.index;
l=emenuhit(2, &m, &lmenu);
if(l>=0){
+ stopanimation(&a);
level = levels[l];
drawlevel();
drawscreen();
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.c:251,267 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.c:275,296
if(m.buttons&4)
switch(emenuhit(3, &m, &menu)) {
case 0:
+ stopanimation(&a);
level = levels[level.index];
drawlevel();
drawscreen();
break;
case 1:
+ stopanimation(&a);
loadlevels(LEasy);
+ buildmenu();
drawlevel();
drawscreen();
break;
case 2:
+ stopanimation(&a);
loadlevels(LHard);
+ buildmenu();
drawlevel();
drawscreen();
break;
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.c:278,284 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.c:307,315
if(level.done)
break;
- switch(e.kbdc) {
+ stopanimation(&a);
+
+ switch(ev.kbdc) {
case 127:
case 'q':
case 'Q':
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.c:310,321 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.c:341,363
case 61457:
case 61458:
case ' ':
- move(key2move(e.kbdc));
+ move(key2move(ev.kbdc));
drawscreen();
break;
default:
// fprint(2, "key: %d]\n", e.kbdc);
break;
+ }
+ break;
+
+ default:
+ if (e == timer) {
+ if (animate)
+ onestep(&a);
+ else
+ while(onestep(&a))
+ ;
+ drawscreen();
}
break;
}
[rsc] --rw-rw-r-- M 209623 jmk sys 2062 Sep 5 07:25 sys/src/games/sokoban/sokoban.h
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.h:32,52 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.h:32,64
Maxlevels = 200,
};
- typedef struct {
+ typedef struct Step {
uint dir; /* direction */
uint count; /* number of single-step moves */
} Step;
- typedef struct {
- uint nstep; /* number of valid steps */
+ typedef struct Route {
+ uint nstep; /* number of valid Step */
Step *step;
- uint beyond; /* number of allocated Step */
+ Point dest; /* result of step */
} Route;
- typedef struct {
+ typedef struct Walk {
+ uint nroute; /* number of valid Route* */
+ Route **route;
+ uint beyond; /* number of allocated Route* */
+ } Walk;
+
+ typedef struct Visited {
uint board[MazeX][MazeY];
} Visited;
+ typedef struct Animation {
+ Route* route;
+ Step *step;
+ int count;
+ } Animation;
+
typedef struct {
Point glenda;
Point max; /* that's how much the board spans */
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.h:58,64 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.h:70,75
Level level; /* the current level */
Level levels[Maxlevels]; /* all levels from this file */
int numlevels; /* how many levels do we have */
- int animate; /* boolean: animate during multi-step move? */
Image *img; /* buffer */
Image *text; /* for text messages */
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/sokoban.h:90,105 -
/n/sources/plan9/sys/src/games/sokoban/sokoban.h:101,118
void move(int);
/* route.c */
- Route* newroute(void);
+ int validpush(Point, Step*, Point*);
+ int isvalid(Point, Route*, int (*)(Point, Step*, Point*));
void freeroute(Route*);
- void reverseroute(Route*);
- void pushstep(Route*, int, int);
- void popstep(Route*);
- int validwalk(Point, Step, Point*);
- int validpush(Point, Step, Point*);
- int isvalid(Point, Route*, int (*)(Point, Step, Point*));
- int findwalk(Point, Point, Route*);
- void applyroute(Route*);
+ Route* extend(Route*, int, int, Point);
+ Route* findroute(Point, Point);
+
+ /* animation.c */
+ void initanimation(Animation*);
+ void setupanimation(Animation*, Route*);
+ int onestep(Animation*);
+ void stopanimation(Animation*);
+
/* sokoban.c */
char *genlevels(int);
[jmk] --rw-rw-r-- M 209623 jmk sys 261 Sep 5 23:11 sys/src/games/sokoban/mkfile
/n/sourcesdump/2005/0905/plan9/sys/src/games/sokoban/mkfile:3,14 -
/n/sourcesdump/2005/0906/plan9/sys/src/games/sokoban/mkfile:3,14
TARG=sokoban
OFILES=\
- sokoban.$O\
- move.$O\
+ animation.$O\
graphics.$O\
level.$O\
+ move.$O\
+ sokoban.$O\
route.$O\
-
HFILES=sokoban.h\
|
