OpenCores
URL https://opencores.org/ocsvn/or1k_old/or1k_old/trunk

Subversion Repositories or1k_old

[/] [or1k_old/] [trunk/] [mw/] [src/] [demos/] [nanox/] [maze.c] - Blame information for rev 1782

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 770 simons
/******************************************************************************
2
 * [ maze ] ...
3
 *
4
 * modified:  [ 1-04-00 ]  Johannes Keukelaar <johannes@nada.kth.se>
5
 *              Added -ignorant option (not the default) to remove knowlege
6
 *              of the direction in which the exit lies.
7
 *
8
 * modified:  [ 6-28-98 ]  Zack Weinberg <zack@rabi.phys.columbia.edu>
9
 *
10
 *              Made the maze-solver somewhat more intelligent.  There are
11
 *              three optimizations:
12
 *
13
 *              - Straight-line lookahead: the solver does not enter dead-end
14
 *                corridors.  This is a win with all maze generators.
15
 *
16
 *              - First order direction choice: the solver knows where the
17
 *                exit is in relation to itself, and will try paths leading in
18
 *                that direction first. This is a major win on maze generator 1
19
 *                which tends to offer direct routes to the exit.
20
 *
21
 *              - Dead region elimination: the solver already has a map of
22
 *                all squares visited.  Whenever it starts to backtrack, it
23
 *                consults this map and marks off all squares that cannot be
24
 *                reached from the exit without crossing a square already
25
 *                visited.  Those squares can never contribute to the path to
26
 *                the exit, so it doesn't bother checking them.  This helps a
27
 *                lot with maze generator 2 and somewhat less with generator 1.
28
 *
29
 *              Further improvements would require knowledge of the wall map
30
 *              as well as the position of the exit and the squares visited.
31
 *              I would consider that to be cheating.  Generator 0 makes
32
 *              mazes which are remarkably difficult to solve mechanically --
33
 *              even with these optimizations the solver generally must visit
34
 *              at least two-thirds of the squares.  This is partially
35
 *              because generator 0's mazes have longer paths to the exit.
36
 *
37
 * modified:  [ 4-10-97 ]  Johannes Keukelaar <johannes@nada.kth.se>
38
 *              Added multiple maze creators. Robustified solver.
39
 *              Added bridge option.
40
 * modified:  [ 8-11-95 ] Ed James <james@mml.mmc.com>
41
 *              added fill of dead-end box to solve_maze while loop.
42
 * modified:  [ 3-7-93 ]  Jamie Zawinski <jwz@jwz.org>
43
 *              added the XRoger logo, cleaned up resources, made
44
 *              grid size a parameter.
45
 * modified:  [ 3-3-93 ]  Jim Randell <jmr@mddjmr.fc.hp.com>
46
 *              Added the colour stuff and integrated it with jwz's
47
 *              screenhack stuff.  There's still some work that could
48
 *              be done on this, particularly allowing a resource to
49
 *              specify how big the squares are.
50
 * modified:  [ 10-4-88 ]  Richard Hess    ...!uunet!cimshop!rhess
51
 *              [ Revised primary execution loop within main()...
52
 *              [ Extended X event handler, check_events()...
53
 * modified:  [ 1-29-88 ]  Dave Lemke      lemke@sun.com
54
 *              [ Hacked for X11...
55
 *              [  Note the word "hacked" -- this is extremely ugly, but at
56
 *              [   least it does the job.  NOT a good programming example
57
 *              [   for X.
58
 * original:  [ 6/21/85 ]  Martin Weiss    Sun Microsystems  [ SunView ]
59
 *
60
 ******************************************************************************
61
 Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.
62
 
63
 All Rights Reserved
64
 
65
 Permission to use, copy, modify, and distribute this software and its
66
 documentation for any purpose and without fee is hereby granted,
67
 provided that the above copyright notice appear in all copies and that
68
 both that copyright notice and this permission notice appear in
69
 supporting documentation, and that the names of Sun or MIT not be
70
 used in advertising or publicity pertaining to distribution of the
71
 software without specific prior written permission. Sun and M.I.T.
72
 make no representations about the suitability of this software for
73
 any purpose. It is provided "as is" without any express or implied warranty.
74
 
75
 SUN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
76
 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
77
 PURPOSE. IN NO EVENT SHALL SUN BE LIABLE FOR ANY SPECIAL, INDIRECT
78
 OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
79
 OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
80
 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
81
 OR PERFORMANCE OF THIS SOFTWARE.
82
 *****************************************************************************/
83
 
84
static int solve_delay, pre_solve_delay, post_solve_delay;
85
 
86
#include <stdio.h>
87
#include <stdlib.h>
88
//#include <unistd.h>
89
#define usleep(x)
90
#include <math.h>
91
#define MWINCLUDECOLORS
92
#include "nano-X.h"
93
#include "maze.h"
94
 
95
#define MAX_MAZE_SIZE_X 100
96
#define MAX_MAZE_SIZE_Y 100
97
 
98
#define MOVE_LIST_SIZE  (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
99
 
100
#define NOT_DEAD        0x8000
101
#define SOLVER_VISIT    0x4000
102
#define START_SQUARE    0x2000
103
#define END_SQUARE      0x1000
104
 
105
#define WALL_TOP        0x8
106
#define WALL_RIGHT      0x4
107
#define WALL_BOTTOM     0x2
108
#define WALL_LEFT       0x1
109
#define WALL_ANY        0xF
110
 
111
#define DOOR_IN_TOP     0x800
112
#define DOOR_IN_RIGHT   0x400
113
#define DOOR_IN_BOTTOM  0x200
114
#define DOOR_IN_LEFT    0x100
115
#define DOOR_IN_ANY     0xF00
116
 
117
#define DOOR_OUT_TOP    0x80
118
#define DOOR_OUT_RIGHT  0x40
119
#define DOOR_OUT_BOTTOM 0x20
120
#define DOOR_OUT_LEFT   0x10
121
 
122
 
123
#define border_x        (0)
124
#define border_y        (0)
125
 
126
#define get_random(x)   (random() % (x))
127
 
128
static unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
129
 
130
static struct {
131
  unsigned char x;
132
  unsigned char y;
133
  unsigned char dir, ways;
134
} move_list[MOVE_LIST_SIZE], save_path[MOVE_LIST_SIZE], path[MOVE_LIST_SIZE];
135
 
136
static int maze_size_x, maze_size_y;
137
static int sqnum, cur_sq_x, cur_sq_y, path_length;
138
static int start_x, start_y, start_dir, end_x, end_y, end_dir;
139
static int grid_width, grid_height;
140
static int bw;
141
 
142
static int      x = 0, y = 0, restart = 0, stop = 0, state = 1, max_length;
143
static int      sync_p, bridge_p, ignorant_p;
144
 
145
static GR_GC_ID gc, cgc, tgc, sgc, ugc;
146
GR_GC_ID erase_gc;
147
 
148
static void
149
set_maze_sizes (int width, int height)
150
{
151
  maze_size_x = width / grid_width;
152
  maze_size_y = height / grid_height;
153
}
154
 
155
static void
156
initialize_maze (void) /* draw the surrounding wall and start/end squares */
157
{
158
  register int i, j, wall;
159
 
160
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
161
  /* initialize all squares */
162
  for ( i=0; i<maze_size_x; i++) {
163
    for ( j=0; j<maze_size_y; j++) {
164
      maze[i][j] = 0;
165
    }
166
  }
167
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
168
 
169
  /* top wall */
170
  for ( i=0; i<maze_size_x; i++ ) {
171
    maze[i][0] |= WALL_TOP;
172
  }
173
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
174
 
175
  /* right wall */
176
  for ( j=0; j<maze_size_y; j++ ) {
177
    maze[maze_size_x-1][j] |= WALL_RIGHT;
178
  }
179
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
180
 
181
  /* bottom wall */
182
  for ( i=0; i<maze_size_x; i++ ) {
183
    maze[i][maze_size_y-1] |= WALL_BOTTOM;
184
  }
185
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
186
 
187
  /* left wall */
188
  for ( j=0; j<maze_size_y; j++ ) {
189
    maze[0][j] |= WALL_LEFT;
190
  }
191
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
192
 
193
  /* set start square */
194
  wall = get_random(4);
195
  switch (wall) {
196
  case 0:
197
    i = get_random(maze_size_x);
198
    j = 0;
199
    break;
200
  case 1:
201
    i = maze_size_x - 1;
202
    j = get_random(maze_size_y);
203
    break;
204
  case 2:
205
    i = get_random(maze_size_x);
206
    j = maze_size_y - 1;
207
    break;
208
  case 3:
209
    i = 0;
210
    j = get_random(maze_size_y);
211
    break;
212
  }
213
  maze[i][j] |= START_SQUARE;
214
  maze[i][j] |= ( DOOR_IN_TOP >> wall );
215
  maze[i][j] &= ~( WALL_TOP >> wall );
216
  cur_sq_x = i;
217
  cur_sq_y = j;
218
  start_x = i;
219
  start_y = j;
220
  start_dir = wall;
221
  sqnum = 0;
222
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
223
 
224
  /* set end square */
225
  wall = (wall + 2)%4;
226
  switch (wall) {
227
  case 0:
228
    i = get_random(maze_size_x);
229
    j = 0;
230
    break;
231
  case 1:
232
    i = maze_size_x - 1;
233
    j = get_random(maze_size_y);
234
    break;
235
  case 2:
236
    i = get_random(maze_size_x);
237
    j = maze_size_y - 1;
238
    break;
239
  case 3:
240
    i = 0;
241
    j = get_random(maze_size_y);
242
    break;
243
  }
244
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
245
  maze[i][j] |= END_SQUARE;
246
  maze[i][j] |= ( DOOR_OUT_TOP >> wall );
247
  maze[i][j] &= ~( WALL_TOP >> wall );
248
  end_x = i;
249
  end_y = j;
250
  end_dir = wall;
251
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
252
}
253
 
254
static int choose_door (void);
255
static int backup (void);
256
static void draw_wall (int, int, int, GR_GC_ID);
257
static void draw_solid_square (int, int, int, GR_GC_ID);
258
static void build_wall (int, int, int);
259
 
260
static void join_sets(int, int);
261
 
262
/* For set_create_maze. */
263
/* The sets that our squares are in. */
264
static int *sets = 0;
265
/* The `list' of hedges. */
266
static int *hedges = 0;
267
 
268
/* Initialise the sets. */
269
static void
270
init_sets(void)
271
{
272
  int i, t, r;
273
 
274
  if(sets)
275
    free(sets);
276
  sets = (int *)malloc(maze_size_x*maze_size_y*sizeof(int));
277
  if(!sets)
278
    abort();
279
  for(i = 0; i < maze_size_x*maze_size_y; i++)
280
    {
281
      sets[i] = i;
282
    }
283
 
284
  if(hedges)
285
    free(hedges);
286
  hedges = (int *)malloc(maze_size_x*maze_size_y*2*sizeof(int));
287
  if(!hedges)
288
    abort();
289
  for(i = 0; i < maze_size_x*maze_size_y*2; i++)
290
    {
291
      hedges[i] = i;
292
    }
293
  /* Mask out outside walls. */
294
  for(i = 0; i < maze_size_y; i++)
295
    {
296
      hedges[2*((maze_size_x)*i+maze_size_x-1)+1] = -1;
297
    }
298
  for(i = 0; i < maze_size_x; i++)
299
    {
300
      hedges[2*((maze_size_y-1)*maze_size_x+i)] = -1;
301
    }
302
 
303
  for(i = 0; i < maze_size_x*maze_size_y*2; i++)
304
    {
305
      t = hedges[i];
306
      r = random()%(maze_size_x*maze_size_y*2);
307
      hedges[i] = hedges[r];
308
      hedges[r] = t;
309
    }
310
}
311
 
312
/* Get the representative of a set. */
313
static int
314
get_set(int num)
315
{
316
  int s;
317
 
318
  if(sets[num]==num)
319
    return num;
320
  else
321
    {
322
      s = get_set(sets[num]);
323
      sets[num] = s;
324
      return s;
325
    }
326
}
327
 
328
/* Join two sets together. */
329
static void
330
join_sets(num1, num2)
331
     int num1, num2;
332
{
333
  int s1, s2;
334
 
335
  s1 = get_set(num1);
336
  s2 = get_set(num2);
337
 
338
  if(s1<s2)
339
    sets[s2] = s1;
340
  else
341
    sets[s1] = s2;
342
}
343
 
344
/* Exitialise the sets. */
345
static void
346
exit_sets(void)
347
{
348
  if(hedges)
349
    free(hedges);
350
  hedges = 0;
351
  if(sets)
352
    free(sets);
353
  sets = 0;
354
}
355
 
356
/* Second alternative maze creator: Put each square in the maze in a
357
 * separate set. Also, make a list of all the hedges. Randomize that list.
358
 * Walk through the list. If, for a certain hedge, the two squares on both
359
 * sides of it are in different sets, union the sets and remove the hedge.
360
 * Continue until all hedges have been processed or only one set remains.
361
 */
362
static void
363
set_create_maze(void)
364
{
365
  int i, h, x, y, dir, v, w;
366
 
367
  /* Do almost all the setup. */
368
  init_sets();
369
 
370
  /* Start running through the hedges. */
371
  for(i = 0; i < 2*maze_size_x*maze_size_y; i++)
372
    {
373
      h = hedges[i];
374
 
375
      /* This one is in the logo or outside border. */
376
      if(h==-1)
377
        continue;
378
 
379
      dir = h%2?1:2;
380
      x = (h>>1)%maze_size_x;
381
      y = (h>>1)/maze_size_x;
382
 
383
      v = x;
384
      w = y;
385
      switch(dir)
386
        {
387
        case 1:
388
          v++;
389
          break;
390
        case 2:
391
          w++;
392
          break;
393
        }
394
 
395
      if(get_set(x+y*maze_size_x)!=get_set(v+w*maze_size_x))
396
        {
397
          join_sets(x+y*maze_size_x, v+w*maze_size_x);
398
          /* Don't draw the wall. */
399
        }
400
      else
401
        {
402
          /* Don't join the sets. */
403
          build_wall(x, y, dir);
404
        }
405
    }
406
 
407
  /* Free some memory. */
408
  exit_sets();
409
}
410
 
411
/* First alternative maze creator: Pick a random, empty corner in the maze.
412
 * Pick a random direction. Draw a wall in that direction, from that corner
413
 * until we hit a wall. Option: Only draw the wall if it's going to be
414
 * shorter than a certain length. Otherwise we get lots of long walls.
415
 */
416
static void
417
alt_create_maze(void)
418
{
419
  char *corners;
420
  int *c_idx;
421
  int i, j, height, width, open_corners, k, dir, x, y;
422
 
423
  height = maze_size_y+1;
424
  width = maze_size_x+1;
425
 
426
  /* Allocate and clear some mem. */
427
  corners = (char *)calloc(height*width, 1);
428
  if(!corners)
429
    return;
430
 
431
  /* Set up the indexing array. */
432
  c_idx = (int *)malloc(sizeof(int)*height*width);
433
  if(!c_idx)
434
    {
435
      free(corners);
436
      return;
437
    }
438
  for(i = 0; i < height*width; i++)
439
    c_idx[i] = i;
440
  for(i = 0; i < height*width; i++)
441
    {
442
      j = c_idx[i];
443
      k = random()%(height*width);
444
      c_idx[i] = c_idx[k];
445
      c_idx[k] = j;
446
    }
447
 
448
  /* Set up some initial walls. */
449
  /* Outside walls. */
450
  for(i = 0; i < width; i++)
451
    {
452
      corners[i] = 1;
453
      corners[i+width*(height-1)] = 1;
454
    }
455
  for(i = 0; i < height; i++)
456
    {
457
      corners[i*width] = 1;
458
      corners[i*width+width-1] = 1;
459
    }
460
 
461
  /* Count open gridpoints. */
462
  open_corners = 0;
463
  for(i = 0; i < width; i++)
464
    for(j = 0; j < height; j++)
465
      if(!corners[i+width*j])
466
        open_corners++;
467
 
468
  /* Now do actual maze generation. */
469
  while(open_corners>0)
470
    {
471
      for(i = 0; i < width*height; i++)
472
        {
473
          if(!corners[c_idx[i]])
474
            {
475
              x = c_idx[i]%width;
476
              y = c_idx[i]/width;
477
              /* Choose a random direction. */
478
              dir = random()%4;
479
 
480
              k = 0;
481
              /* Measure the length of the wall we'd draw. */
482
              while(!corners[x+width*y])
483
                {
484
                  k++;
485
                  switch(dir)
486
                    {
487
                    case 0:
488
                      y--;
489
                      break;
490
                    case 1:
491
                      x++;
492
                      break;
493
                    case 2:
494
                      y++;
495
                      break;
496
                    case 3:
497
                      x--;
498
                      break;
499
                    }
500
                }
501
 
502
              if(k<=max_length)
503
                {
504
                  x = c_idx[i]%width;
505
                  y = c_idx[i]/width;
506
 
507
                  /* Draw a wall until we hit something. */
508
                  while(!corners[x+width*y])
509
                    {
510
                      open_corners--;
511
                      corners[x+width*y] = 1;
512
                      switch(dir)
513
                        {
514
                        case 0:
515
                          build_wall(x-1, y-1, 1);
516
                          y--;
517
                          break;
518
                        case 1:
519
                          build_wall(x, y, 0);
520
                          x++;
521
                          break;
522
                        case 2:
523
                          build_wall(x, y, 3);
524
                          y++;
525
                          break;
526
                        case 3:
527
                          build_wall(x-1, y-1, 2);
528
                          x--;
529
                          break;
530
                        }
531
                    }
532
                }
533
            }
534
        }
535
    }
536
 
537
  /* Free some memory we used. */
538
  free(corners);
539
  free(c_idx);
540
}
541
 
542
/* The original maze creator. Start somewhere. Take a step in a random
543
 * direction. Keep doing this until we hit a wall. Then, backtrack until
544
 * we find a point where we can go in another direction.
545
 */
546
static void
547
create_maze (void)    /* create a maze layout given the initialized maze */
548
{
549
  register int i, newdoor = 0;
550
 
551
  do {
552
    move_list[sqnum].x = cur_sq_x;
553
    move_list[sqnum].y = cur_sq_y;
554
    move_list[sqnum].dir = newdoor;
555
    while ( ( newdoor = choose_door() ) == -1 ) { /* pick a door */
556
      if ( backup() == -1 ) { /* no more doors ... backup */
557
        return; /* done ... return */
558
      }
559
    }
560
 
561
    /* mark the out door */
562
    maze[cur_sq_x][cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
563
 
564
    switch (newdoor) {
565
    case 0: cur_sq_y--;
566
      break;
567
    case 1: cur_sq_x++;
568
      break;
569
    case 2: cur_sq_y++;
570
      break;
571
    case 3: cur_sq_x--;
572
      break;
573
    }
574
    sqnum++;
575
 
576
    /* mark the in door */
577
    maze[cur_sq_x][cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
578
 
579
    /* if end square set path length and save path */
580
    if ( maze[cur_sq_x][cur_sq_y] & END_SQUARE ) {
581
      path_length = sqnum;
582
      for ( i=0; i<path_length; i++) {
583
        save_path[i].x = move_list[i].x;
584
        save_path[i].y = move_list[i].y;
585
        save_path[i].dir = move_list[i].dir;
586
      }
587
    }
588
 
589
  } while (1);
590
 
591
}
592
 
593
 
594
static int
595
choose_door (void)                                   /* pick a new path */
596
{
597
  int candidates[3];
598
  register int num_candidates;
599
 
600
  num_candidates = 0;
601
 
602
  /* top wall */
603
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_TOP )
604
    goto rightwall;
605
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_TOP )
606
    goto rightwall;
607
  if ( maze[cur_sq_x][cur_sq_y] & WALL_TOP )
608
    goto rightwall;
609
  if ( maze[cur_sq_x][cur_sq_y - 1] & DOOR_IN_ANY ) {
610
    maze[cur_sq_x][cur_sq_y] |= WALL_TOP;
611
    maze[cur_sq_x][cur_sq_y - 1] |= WALL_BOTTOM;
612
    draw_wall(cur_sq_x, cur_sq_y, 0, gc);
613
    goto rightwall;
614
  }
615
  candidates[num_candidates++] = 0;
616
 
617
 rightwall:
618
  /* right wall */
619
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_RIGHT )
620
    goto bottomwall;
621
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_RIGHT )
622
    goto bottomwall;
623
  if ( maze[cur_sq_x][cur_sq_y] & WALL_RIGHT )
624
    goto bottomwall;
625
  if ( maze[cur_sq_x + 1][cur_sq_y] & DOOR_IN_ANY ) {
626
    maze[cur_sq_x][cur_sq_y] |= WALL_RIGHT;
627
    maze[cur_sq_x + 1][cur_sq_y] |= WALL_LEFT;
628
    draw_wall(cur_sq_x, cur_sq_y, 1, gc);
629
    goto bottomwall;
630
  }
631
  candidates[num_candidates++] = 1;
632
 
633
 bottomwall:
634
  /* bottom wall */
635
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_BOTTOM )
636
    goto leftwall;
637
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_BOTTOM )
638
    goto leftwall;
639
  if ( maze[cur_sq_x][cur_sq_y] & WALL_BOTTOM )
640
    goto leftwall;
641
  if ( maze[cur_sq_x][cur_sq_y + 1] & DOOR_IN_ANY ) {
642
    maze[cur_sq_x][cur_sq_y] |= WALL_BOTTOM;
643
    maze[cur_sq_x][cur_sq_y + 1] |= WALL_TOP;
644
    draw_wall(cur_sq_x, cur_sq_y, 2, gc);
645
    goto leftwall;
646
  }
647
  candidates[num_candidates++] = 2;
648
 
649
 leftwall:
650
  /* left wall */
651
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_LEFT )
652
    goto donewall;
653
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_LEFT )
654
    goto donewall;
655
  if ( maze[cur_sq_x][cur_sq_y] & WALL_LEFT )
656
    goto donewall;
657
  if ( maze[cur_sq_x - 1][cur_sq_y] & DOOR_IN_ANY ) {
658
    maze[cur_sq_x][cur_sq_y] |= WALL_LEFT;
659
    maze[cur_sq_x - 1][cur_sq_y] |= WALL_RIGHT;
660
    draw_wall(cur_sq_x, cur_sq_y, 3, gc);
661
    goto donewall;
662
  }
663
  candidates[num_candidates++] = 3;
664
 
665
 donewall:
666
  if (num_candidates == 0)
667
    return ( -1 );
668
  if (num_candidates == 1)
669
    return ( candidates[0] );
670
  return ( candidates[ get_random(num_candidates) ] );
671
 
672
}
673
 
674
 
675
static int
676
backup (void)                                          /* back up a move */
677
{
678
  sqnum--;
679
  cur_sq_x = move_list[sqnum].x;
680
  cur_sq_y = move_list[sqnum].y;
681
  return ( sqnum );
682
}
683
 
684
 
685
static void
686
draw_maze_border (void)                         /* draw the maze outline */
687
{
688
  register int i, j;
689
 
690
 
691
  for ( i=0; i<maze_size_x; i++) {
692
    if ( maze[i][0] & WALL_TOP ) {
693
      GrLine(wid, gc,
694
                border_x + grid_width * i,
695
                border_y,
696
                border_x + grid_width * (i+1) - 1,
697
                border_y);
698
    }
699
    if ((maze[i][maze_size_y - 1] & WALL_BOTTOM)) {
700
      GrLine(wid, gc,
701
                border_x + grid_width * i,
702
                border_y + grid_height * (maze_size_y) - 1,
703
                border_x + grid_width * (i+1) - 1,
704
                border_y + grid_height * (maze_size_y) - 1);
705
    }
706
  }
707
  for ( j=0; j<maze_size_y; j++) {
708
    if ( maze[maze_size_x - 1][j] & WALL_RIGHT ) {
709
      GrLine(wid, gc,
710
                border_x + grid_width * maze_size_x - 1,
711
                border_y + grid_height * j,
712
                border_x + grid_width * maze_size_x - 1,
713
                border_y + grid_height * (j+1) - 1);
714
    }
715
    if ( maze[0][j] & WALL_LEFT ) {
716
      GrLine(wid, gc,
717
                border_x,
718
                border_y + grid_height * j,
719
                border_x,
720
                border_y + grid_height * (j+1) - 1);
721
    }
722
  }
723
 
724
  draw_solid_square (start_x, start_y, WALL_TOP >> start_dir, tgc);
725
  draw_solid_square (end_x, end_y, WALL_TOP >> end_dir, tgc);
726
}
727
 
728
 
729
static void
730
draw_wall(int i, int j, int dir, GR_GC_ID gc)                /* draw a single wall */
731
{
732
  switch (dir) {
733
  case 0:
734
    GrLine(wid, gc,
735
              border_x + grid_width * i,
736
              border_y + grid_height * j,
737
              border_x + grid_width * (i+1),
738
              border_y + grid_height * j);
739
    break;
740
  case 1:
741
    GrLine(wid, gc,
742
              border_x + grid_width * (i+1),
743
              border_y + grid_height * j,
744
              border_x + grid_width * (i+1),
745
              border_y + grid_height * (j+1));
746
    break;
747
  case 2:
748
    GrLine(wid, gc,
749
              border_x + grid_width * i,
750
              border_y + grid_height * (j+1),
751
              border_x + grid_width * (i+1),
752
              border_y + grid_height * (j+1));
753
    break;
754
  case 3:
755
    GrLine(wid, gc,
756
              border_x + grid_width * i,
757
              border_y + grid_height * j,
758
              border_x + grid_width * i,
759
              border_y + grid_height * (j+1));
760
    break;
761
  }
762
  if(sync_p)
763
    wait_sync ();
764
}
765
 
766
/* Actually build a wall. */
767
static void
768
build_wall(i, j, dir)
769
     int i, j, dir;
770
{
771
  /* Draw it on the screen. */
772
  draw_wall(i, j, dir, gc);
773
  /* Put it in the maze. */
774
  switch(dir)
775
    {
776
    case 0:
777
      maze[i][j] |= WALL_TOP;
778
      if(j>0)
779
        maze[i][j-1] |= WALL_BOTTOM;
780
      break;
781
    case 1:
782
      maze[i][j] |= WALL_RIGHT;
783
      if(i<maze_size_x-1)
784
        maze[i+1][j] |= WALL_LEFT;
785
      break;
786
    case 2:
787
      maze[i][j] |= WALL_BOTTOM;
788
      if(j<maze_size_y-1)
789
        maze[i][j+1] |= WALL_TOP;
790
      break;
791
    case 3:
792
      maze[i][j] |= WALL_LEFT;
793
      if(i>0)
794
        maze[i-1][j] |= WALL_RIGHT;
795
      break;
796
    }
797
}
798
 
799
static void
800
draw_solid_square(int i, int j,          /* draw a solid square in a square */
801
                  int dir, GR_GC_ID gc)
802
{
803
  switch (dir) {
804
  case WALL_TOP:
805
      GrFillRect(wid, gc,
806
                     border_x + bw + grid_width * i,
807
                     border_y - bw + grid_height * j,
808
                     grid_width - (bw+bw), grid_height);
809
      break;
810
  case WALL_RIGHT:
811
      GrFillRect(wid, gc,
812
                     border_x + bw + grid_width * i,
813
                     border_y + bw + grid_height * j,
814
                     grid_width, grid_height - (bw+bw));
815
      break;
816
  case WALL_BOTTOM:
817
      GrFillRect(wid, gc,
818
                     border_x + bw + grid_width * i,
819
                     border_y + bw + grid_height * j,
820
                     grid_width - (bw+bw), grid_height);
821
      break;
822
  case WALL_LEFT:
823
      GrFillRect(wid, gc,
824
                     border_x - bw + grid_width * i,
825
                     border_y + bw + grid_height * j,
826
                     grid_width, grid_height - (bw+bw));
827
      break;
828
  }
829
  wait_sync ();
830
}
831
 
832
int
833
longdeadend_p(int x1, int y1, int x2, int y2, int endwall)
834
{
835
    int dx = x2 - x1, dy = y2 - y1;
836
    int sidewalls;
837
 
838
    sidewalls = endwall | (endwall >> 2 | endwall << 2);
839
    sidewalls = ~sidewalls & WALL_ANY;
840
 
841
    while((maze[x2][y2] & WALL_ANY) == sidewalls)
842
    {
843
        x2 += dx;
844
        y2 += dy;
845
    }
846
 
847
    if((maze[x2][y2] & WALL_ANY) == (sidewalls | endwall))
848
    {
849
        endwall = (endwall >> 2 | endwall << 2) & WALL_ANY;
850
        while(x1 != x2 || y1 != y2)
851
        {
852
            x1 += dx;
853
            y1 += dy;
854
            draw_solid_square(x1, y1, endwall, sgc);
855
            maze[x1][y1] |= SOLVER_VISIT;
856
        }
857
        return 1;
858
    }
859
    else
860
        return 0;
861
}
862
 
863
/* Find all dead regions -- areas from which the goal cannot be reached --
864
   and mark them visited. */
865
void
866
find_dead_regions(void)
867
{
868
    int x, y, flipped;
869
 
870
    /* Find all not SOLVER_VISIT squares bordering NOT_DEAD squares
871
       and mark them NOT_DEAD also.  Repeat until no more such squares. */
872
    maze[start_x][start_y] |= NOT_DEAD;
873
 
874
    do
875
    {
876
        flipped = 0;
877
        for(x = 0; x < maze_size_x; x++)
878
            for(y = 0; y < maze_size_y; y++)
879
                if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
880
                   && (   (x && (maze[x-1][y] & NOT_DEAD))
881
                       || (y && (maze[x][y-1] & NOT_DEAD))))
882
                {
883
                    flipped = 1;
884
                    maze[x][y] |= NOT_DEAD;
885
                }
886
        for(x = maze_size_x-1; x >= 0; x--)
887
            for(y = maze_size_y-1; y >= 0; y--)
888
                if(!(maze[x][y] & (SOLVER_VISIT | NOT_DEAD))
889
                   && (   (x != maze_size_x-1 && (maze[x+1][y] & NOT_DEAD))
890
                       || (y != maze_size_y-1 && (maze[x][y+1] & NOT_DEAD))))
891
                {
892
                    flipped = 1;
893
                    maze[x][y] |= NOT_DEAD;
894
                }
895
    }
896
    while(flipped);
897
 
898
    for (y = 0; y < maze_size_y; y++)
899
      for (x = 0; x < maze_size_x; x++)
900
      {
901
        if (maze[x][y] & NOT_DEAD)
902
          maze[x][y] &= ~NOT_DEAD;
903
        else if (!(maze[x][y] & SOLVER_VISIT))
904
        {
905
          maze[x][y] |= SOLVER_VISIT;
906
          {
907
            if (!maze[x][y] & WALL_ANY)
908
              GrFillRect(wid, ugc,
909
                             border_x + bw + grid_width * x,
910
                             border_y + bw + grid_height * y,
911
                             grid_width - (bw+bw), grid_height - (bw+bw));
912
            else
913
            {
914
              if (! (maze[x][y] & WALL_LEFT))
915
                draw_solid_square(x, y, WALL_LEFT, ugc);
916
              if (! (maze[x][y] & WALL_RIGHT))
917
                draw_solid_square(x, y, WALL_RIGHT, ugc);
918
              if (! (maze[x][y] & WALL_TOP))
919
                draw_solid_square(x, y, WALL_TOP, ugc);
920
              if (! (maze[x][y] & WALL_BOTTOM))
921
                draw_solid_square(x, y, WALL_BOTTOM, ugc);
922
            }
923
          }
924
        }
925
      }
926
    wait_sync ();
927
}
928
 
929
static void
930
solve_maze (void)                     /* solve it with graphical feedback */
931
{
932
    int i, dir, from, x, y, ways, bt = 0;
933
 
934
    /* plug up the surrounding wall */
935
    maze[end_x][end_y] |= (WALL_TOP >> end_dir);
936
 
937
    /* initialize search path */
938
    i = 0;
939
    path[i].x = end_x;
940
    path[i].y = end_y;
941
    path[i].dir = 0;
942
    maze[end_x][end_y] |= SOLVER_VISIT;
943
 
944
    /* do it */
945
    while (1)
946
    {
947
        if ( maze[path[i].x][path[i].y] & START_SQUARE )
948
            return;
949
 
950
        if (solve_delay) usleep(solve_delay);
951
 
952
        if(!path[i].dir)
953
        {
954
            ways = 0;
955
            /* First visit this square.  Which adjacent squares are open? */
956
            for(dir = WALL_TOP; dir & WALL_ANY; dir >>= 1)
957
            {
958
                if(maze[path[i].x][path[i].y] & dir)
959
                    continue;
960
 
961
                y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
962
                x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
963
 
964
                if(maze[x][y] & SOLVER_VISIT)
965
                    continue;
966
 
967
                from = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
968
                /* don't enter obvious dead ends */
969
                if(((maze[x][y] & WALL_ANY) | from) != WALL_ANY)
970
                {
971
                    if(!longdeadend_p(path[i].x, path[i].y, x, y, dir))
972
                        ways |= dir;
973
                }
974
                else
975
                {
976
                    draw_solid_square(x, y, from, sgc);
977
                    maze[x][y] |= SOLVER_VISIT;
978
                }
979
            }
980
        }
981
        else
982
            ways = path[i].ways;
983
        /* ways now has a bitmask of open paths. */
984
 
985
        if(!ways)
986
            goto backtrack;
987
 
988
        if (!ignorant_p)
989
          {
990
            x = path[i].x - start_x;
991
            y = path[i].y - start_y;
992
            /* choice one */
993
            if(abs(y) <= abs(x))
994
              dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
995
            else
996
              dir = (y > 0) ? WALL_TOP : WALL_BOTTOM;
997
 
998
            if(dir & ways)
999
              goto found;
1000
 
1001
            /* choice two */
1002
            switch(dir)
1003
              {
1004
              case WALL_LEFT:
1005
              case WALL_RIGHT:
1006
                dir = (y > 0) ? WALL_TOP : WALL_BOTTOM; break;
1007
              case WALL_TOP:
1008
              case WALL_BOTTOM:
1009
                dir = (x > 0) ? WALL_LEFT : WALL_RIGHT;
1010
              }
1011
 
1012
            if(dir & ways)
1013
              goto found;
1014
 
1015
            /* choice three */
1016
 
1017
            dir = (dir << 2 & WALL_ANY) | (dir >> 2 & WALL_ANY);
1018
            if(dir & ways)
1019
              goto found;
1020
 
1021
            /* choice four */
1022
            dir = ways;
1023
            if(!dir)
1024
              goto backtrack;
1025
 
1026
          found: ;
1027
          }
1028
        else
1029
          {
1030
            if(ways&WALL_TOP)
1031
              dir = WALL_TOP;
1032
            else if(ways&WALL_LEFT)
1033
              dir = WALL_LEFT;
1034
            else if(ways&WALL_BOTTOM)
1035
              dir = WALL_BOTTOM;
1036
            else if(ways&WALL_RIGHT)
1037
              dir = WALL_RIGHT;
1038
            else
1039
              goto backtrack;
1040
          }
1041
        bt = 0;
1042
        ways &= ~dir;  /* tried this one */
1043
 
1044
        y = path[i].y - !!(dir & WALL_TOP) + !!(dir & WALL_BOTTOM);
1045
        x = path[i].x + !!(dir & WALL_RIGHT) - !!(dir & WALL_LEFT);
1046
 
1047
        /* advance in direction dir */
1048
        path[i].dir = dir;
1049
        path[i].ways = ways;
1050
        draw_solid_square(path[i].x, path[i].y, dir, tgc);
1051
 
1052
        i++;
1053
        path[i].dir = 0;
1054
        path[i].ways = 0;
1055
        path[i].x = x;
1056
        path[i].y = y;
1057
        maze[x][y] |= SOLVER_VISIT;
1058
        continue;
1059
 
1060
    backtrack:
1061
        if(i == 0)
1062
        {
1063
            printf("Unsolvable maze.\n");
1064
            return;
1065
        }
1066
 
1067
        if(!bt && !ignorant_p)
1068
            find_dead_regions();
1069
        bt = 1;
1070
        from = path[i-1].dir;
1071
        from = (from << 2 & WALL_ANY) | (from >> 2 & WALL_ANY);
1072
 
1073
        draw_solid_square(path[i].x, path[i].y, from, cgc);
1074
        i--;
1075
    }
1076
}
1077
 
1078
/*
1079
 *  jmr additions for Jamie Zawinski's <jwz@jwz.org> screensaver stuff,
1080
 *  note that the code above this has probably been hacked about in some
1081
 *  arbitrary way.
1082
 */
1083
 
1084
void init_maze ()
1085
{
1086
  int size;
1087
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1088
  size = 0;
1089
  solve_delay = 5000;
1090
  pre_solve_delay = 2000000;
1091
  post_solve_delay = 4000000;
1092
  max_length = 5;
1093
  bridge_p = 0;
1094
  ignorant_p = 0;
1095
 
1096
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1097
  if (size < 2) size = 7 + (random () % 30);
1098
  grid_width = grid_height = size;
1099
  bw = (size > 6 ? 3 : (size-1)/2);
1100
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1101
  x = 0;
1102
  y = 0;
1103
 
1104
  set_maze_sizes (WINDOW_WIDTH, WINDOW_HEIGHT);
1105
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1106
  gc  = GrNewGC();
1107
  cgc = GrNewGC();
1108
  tgc = GrNewGC();
1109
  sgc = GrNewGC();
1110
  ugc = GrNewGC();
1111
  erase_gc = GrNewGC();
1112
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1113
  GrSetGCForeground (gc, WHITE);
1114
  GrSetGCBackground (gc, BLACK);
1115
  GrSetGCForeground (cgc, RED);
1116
  GrSetGCBackground (cgc, BLACK);
1117
  GrSetGCForeground (tgc, LTGREEN);
1118
  GrSetGCBackground (tgc, BLACK);
1119
  GrSetGCForeground (sgc, BROWN);
1120
  GrSetGCBackground (sgc, BLACK);
1121
  GrSetGCForeground (ugc, BLUE);
1122
  GrSetGCBackground (ugc, BLACK);
1123
  GrSetGCForeground (erase_gc, BLACK);
1124
  GrSetGCBackground (erase_gc, BLACK);
1125
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1126
  restart = 1;
1127
 
1128
  sync_p = !(random() % 10);
1129
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1130
}
1131
 
1132
static int this_gen, generator = -1;
1133
void do_clock ()
1134
{
1135
  {
1136
_print ("%i", state);
1137
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1138
    fflush (stdout);
1139
    if (restart || stop) goto pop;
1140
    switch (state) {
1141
    case 1:
1142
      initialize_maze();
1143
      break;
1144
    case 2:
1145
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1146
      GrFillRect (wid, erase_gc, 0, 0, WINDOW_WIDTH, WINDOW_HEIGHT);
1147
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1148
      draw_maze_border();
1149
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1150
      break;
1151
    case 3:
1152
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1153
      this_gen = generator;
1154
      if(this_gen<0 || this_gen>2)
1155
        this_gen = random()%3;
1156
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1157
      switch(this_gen)
1158
        {
1159
        case 0:
1160
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1161
          create_maze();
1162
          break;
1163
        case 1:
1164
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1165
          alt_create_maze();
1166
          break;
1167
        case 2:
1168
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1169
          set_create_maze();
1170
          break;
1171
        }
1172
      break;
1173
    case 4:
1174
      wait_sync ();
1175
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1176
      usleep(pre_solve_delay);
1177
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1178
      break;
1179
    case 5:
1180
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1181
      solve_maze();
1182
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1183
      break;
1184
    case 6:
1185
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1186
      wait_sync ();
1187
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1188
      usleep(post_solve_delay);
1189
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1190
      state = 0 ;
1191
      erase_full_window();
1192
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1193
      break;
1194
    default:
1195
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1196
      abort ();
1197
    }
1198
    ++state;
1199
  pop:
1200
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1201
    if (restart)
1202
      {
1203
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1204
        restart = 0;
1205
        stop = 0;
1206
        state = 1;
1207
        set_maze_sizes (WINDOW_WIDTH, WINDOW_HEIGHT);
1208
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1209
        GrFillRect (wid, erase_gc, 0, 0, WINDOW_WIDTH, WINDOW_HEIGHT);
1210
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1211
        wait_sync ();
1212
        sync_p = !(random() % 10);
1213
_print("%s - %s:%d\n",__FILE__,__FUNCTION__,__LINE__);
1214
      }
1215
  }
1216
}
1217
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.