1#include <u.h>
  2#include <libc.h>
  3#include <draw.h>
  4
  5#include "sokoban.h"
  6
  7static int dirlist[] = { Up, Down, Left, Right, Up, Down, Left, Right, };
  8static int ndir = 4;
  9
 10static Point
 11dir2point(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
 26int
 27validpush(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
 66int
 67isvalid(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
 82static Walk*
 83newwalk(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
 93static void
 94resetwalk(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
106static void
107freewalk(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
118static void
119addroute(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
134void
135freeroute(Route *r)
136{
137	if (r == nil)
138		return;
139	free(r->step);
140	free(r);
141}
142
143Route*
144extend(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
171static Step*
172laststep(Route*r)
173{
174	if (r != nil && r->nstep > 0)
175		return &r->step[r->nstep-1];
176	return nil;
177}
178
179static int*
180startwithdirfromroute(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
198static Route*
199bfstrydir(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
221static Route*
222bfs(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
271Route*
272findroute(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}
281