Subversion Repositories planix.SVN

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 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 
}