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\