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
dir2point(int dir)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
validpush(Point g,Step * s,Point * t)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
isvalid(Point s,Route * r,int (* isallowed)(Point,Step *,Point *))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*
newwalk(void)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
resetwalk(Walk * w)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
freewalk(Walk * w)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
addroute(Walk * w,Route * r)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
freeroute(Route * r)135 freeroute(Route *r)
136 {
137 if (r == nil)
138 return;
139 free(r->step);
140 free(r);
141 }
142
143 Route*
extend(Route * rr,int dir,int count,Point dest)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*
laststep(Route * r)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*
startwithdirfromroute(Route * r,int * dl,int n)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*
bfstrydir(Route * r,int dir,Visited * v)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*
bfs(Point src,Point dst,Visited * v)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*
findroute(Point src,Point dst)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 }
281