1 #include <stdio.h>
2 #include <time.h>
3
4 static char ID[] = "@(#)maze.c 2.1 ";
5
6
7
8
9
10
11
12
13
14
15 #define SIZE 38
16 unsigned int seed = 0;
17 static int answer = 0;
18 static int b_answer = 0;
19 static int debug = 0;
20 static char a[ SIZE+2 ][ 2*SIZE+4 ];
21 static int b[ SIZE+2 ][ SIZE+2 ];
22 static int i, j;
23 static int i_old, j_old;
24 static int i_first, j_first;
25 extern long clock_ ();
26 long tod;
27 static int i_center, j_center;
28 static int v;
29 static int start, finish;
30 static int backcount = 0;
31 static int quiet = 0;
32
33 main( argc, argv )
34 int argc;
35 char *argv[];
36 {
37 system("stty -delay 0,0,0,0,0,0;|discard_");
38
39 tod=clock_();
40 srand((unsigned int)&tod);
41 seed = ((rand()%600000)+1);
42 seed = seed<<1;
43 if ( seed < 1 ) { printf("\nFatal error.\n");
44
45 exit(1); }
46 if( argc > 1 ) {
47 seed = atoi( argv[1] );
48 answer = 1;
49 }
50 if( argc > 2 ) {
51 while( *argv[2] )
52 switch( *argv[2]++ ) {
53 case 'b':
54 b_answer++;
55 break;
56 case 'n':
57 answer = 0;
58 b_answer = 0;
59 break;
60 case 'q':
61 quiet = 1;
62 break;
63 case 'd':
64 debug++;
65 break;
66 }
67 }
68
69 if (quiet <1) {
70 printf("maze 2.1 - 'maze <seed> [nq]', ");
71 printf("'n'o solution, 'q'uiet\n");
72 }
73 printf("\nMaze seed is %d\n", seed );
74 srand( seed );
75
76 for( i = 0; i < SIZE+2; i++)
77 for( j = 0; j < 2*SIZE+4; j++)
78 a[i][j] = ' ';
79 for( j = 1; j < 2*SIZE+2; j++)
80 a[0][j] = '_';
81 for( i = 1; i < SIZE+1; i++)
82 for( j = 1; j < 2*SIZE+2; j++)
83 if( j%2 )
84 a[i][j] = '|';
85 else
86 a[i][j] = '_';
87 goodpath();
88 badpath();
89 if( debug )
90 prtmaze();
91 verybad();
92 verybad();
93 clean();
94 prtmaze();
95
96 exit( 0 );
97 }
98
99 prtmaze()
100 {
101 int ii, jj;
102 for( ii = 0; ii < SIZE+2; ii++ ) {
103 for( jj = 0; jj < SIZE+2; jj++ ) {
104 if( b[ii][jj] == start )
105 printf("S\b");
106 else if( b[ii][jj] == finish )
107 printf("F\b");
108 else if( answer && b_answer && ii == i_center && jj == j_center )
109 printf("+\b");
110 else if( answer && b_answer && b[ii][jj] < -5000 )
111 printf("~\b");
112 else if( answer && b[ii][jj] > 0 )
113 printf("*\b");
114 printf("%c%c", a[ii][2*jj], a[ii][2*jj+1] );
115 if( 0 < jj && jj <= SIZE &&
116 ( a[ii][2*jj+1] == '|' ) &&
117 ( a[ii][2*jj] == '_' || a[ii][2*jj+2] == '_' ) )
118 printf("\b_");
119 }
120 printf("\n");
121 }
122 if( answer )
123 printf("path length = %d\n", finish - start);
124 if( b_answer )
125 printf("back-outs = %d\n", backcount);
126 }
127
128 goodpath()
129 {
130
131 i = i_old = i_first = i_center = SIZE/2 - SIZE/3 + rand()%(2*SIZE/3);
132 j = j_old = j_first = j_center = SIZE/2 - SIZE/3 + rand()%(2*SIZE/3);
133 b[i][j] = 16000;
134 while( move( &i, &j ) ) {
135 mark( i, j, &i_old, &j_old, 1 );
136 if( surrounded( i, j ) && b[i][j] - 16000 < 4*SIZE )
137 backout( -1 );
138 }
139 finish = b[i][j];
140 edge( i < SIZE/2 ? 0 : SIZE+1, j < SIZE/2 ? 0 : SIZE+1 );
141 i = i_old = i_first;
142 j = j_old = j_first;
143 if( surrounded( i, j ) )
144 backout( 1 );
145 while( move( &i, &j ) ) {
146 mark( i, j, &i_old, &j_old, -1 );
147 if( surrounded( i, j ) && finish - b[i][j] < 8*SIZE )
148 backout( 1 );
149 }
150 start = b[i][j];
151 }
152
153 mark( k, l, k_old, l_old, s)
154 int k, l, *k_old, *l_old, s;
155 {
156 b[k][l] = b[*k_old][*l_old] + s;
157 if( k > *k_old )
158 a[k-1][2*l] = ' ';
159 if( k < *k_old )
160 a[k][2*l] = ' ';
161 if( l > *l_old )
162 a[k][2*l-1] = '_';
163 if( l < *l_old )
164 a[k][2*l+1] = '_';
165 *k_old = k;
166 *l_old = l;
167 }
168
169 badpath()
170 {
171
172 v = b[i][j];
173 edge( 0, 0 );
174 edge( SIZE+1, SIZE+1 );
175 while( nextstart() ) {
176 v = b[i][j];
177 b[i][j] = 1;
178 i_old = i_first = i;
179 j_old = j_first = j;
180 while( move( &i, &j ) ) {
181 mark( i, j, &i_old, &j_old, -2 );
182 if( rand()%5 == 0 )
183 sidepath( i, j, 5 );
184 }
185 i = i_first;
186 j = j_first;
187 }
188 }
189
190 nextstart()
191 {
192 int x;
193
194 for( x = v + 1; x < v + 4 ; x++ ) {
195 if( x == finish )
196 return( 0 );
197 find( x );
198 }
199 return( 1 );
200 }
201
202
203 move( k, l )
204 int *k, *l;
205 {
206 int nk, nl;
207
208 if( surrounded( *k, *l ) )
209 return( 0 );
210 if( *k < 1 || *l < 1 || *k > SIZE || *l > SIZE )
211 return( 0 );
212 do {
213 nk = *k;
214 nl = *l;
215 switch( ( rand() >> 11 )%4 ) {
216 case 0:
217 nk = *k - 1;
218 break;
219 case 1:
220 nk = *k + 1;
221 break;
222 case 2:
223 nl = *l - 1;
224 break;
225 case 3:
226 nl = *l + 1;
227 break;
228 }
229 } while( b[nk][nl] != 0 );
230 *k = nk;
231 *l = nl;
232 return( 1 );
233 }
234
235 surrounded( k, l )
236 int k, l;
237 {
238 if( b[ k+1 ][ l ] != 0 &&
239 b[ k-1 ][ l ] != 0 &&
240 b[ k ][ l+1 ] != 0 &&
241 b[ k ][ l-1 ] != 0 )
242 return( 1 );
243 else
244 return( 0 );
245 }
246
247 edge( k, l )
248 int k, l;
249 {
250 int x;
251 if( k < 1 || k > SIZE )
252 for( x = 0; x < SIZE+2; x++ )
253 if( b[k][x] == 0 )
254 b[k][x] = -2;
255 if( l < 1 || l > SIZE )
256 for( x = 0; x < SIZE+2; x++ )
257 if( b[x][l] == 0 )
258 b[x][l] = -2;
259 }
260
261 sidepath( k, l, chance )
262 int k, l, chance;
263 {
264 int k_old, l_old;
265
266 k_old = k;
267 l_old = l;
268 chance += 15;
269 while( move( &k, &l ) ) {
270 mark( k, l, &k_old, &l_old, -2 );
271 if( rand()%chance == 0 )
272 sidepath( k, l, chance );
273 }
274 }
275
276 backout( d )
277 int d;
278 {
279 int x;
280
281 do {
282 x = b[i][j] + d;
283 b[i][j] *= -1;
284 find( x );
285 } while( surrounded( i, j ) );
286 i_old = i;
287 j_old = j;
288 backcount++;
289 }
290
291 find( x )
292 int x;
293 {
294 if( x == b[i+1][j] )
295 i += 1;
296 else if( x == b[i-1][j] )
297 i -= 1;
298 else if( x == b[i][j+1] )
299 j += 1;
300 else if( x == b[i][j-1] )
301 j -= 1;
302 else
303 printf("help\n");
304 }
305
306 verybad()
307
308
309
310 {
311 int k, l;
312
313 for( i = 1; i < SIZE ; i++ )
314 for( j = 1; j < SIZE ; j++ )
315 if( adjacent( i, j, &k, &l ) ) {
316 if( b[k][l] > 0 )
317 b[k][l] = 1;
318 sidepath( k, l, 5 );
319 }
320 }
321
322 adjacent( i_in, j_in, i_out, j_out )
323 int i_in, j_in, *i_out, *j_out;
324
325
326
327 {
328
329 if( b[i_in][j_in] != 0 )
330 return( 0 );
331 *i_out = i_in;
332 *j_out = j_in;
333 if( b[ i_in ][ j_in-1 ] != 0 && j_in-1 > 0 )
334 *j_out = j_in - 1;
335 else if( b[ i_in ][ j_in+1 ] != 0 && j_in+1 < SIZE+1 )
336 *j_out = j_in + 1;
337 else if( b[ i_in-1 ][ j_in ] != 0 && i_in-1 > 0 )
338 *i_out = i_in - 1;
339 else if( b[ i_in+1 ][ j_in ] != 0 && i_in+1 < SIZE+1 )
340 *i_out = i_in + 1;
341 else
342 return( 0 );
343 return( 1 );
344 }
345
346 clean()
347 {
348 int k, l;
349
350 for( k = 0; k < SIZE; k++ )
351 for( l = 0; l < 2*SIZE; l++ )
352 if( a[k][l+1] == '_' &&
353 (a[k][l] == ' ' && a[k][l+2] == ' ') )
354 a[k][l+1] = ' ';
355 }