← Back to branch summary

~cyphermox/ubuntu/precise/xscreensaver/merge-5.15-2

« back to all changes in this revision

Viewing changes to hacks/maze.c

  • Committer: Bazaar Package Importer
  • Author(s): Robert Ancell
  • Date: 2009-06-29 09:30:05 UTC
  • mfrom: (1.1.7 upstream)
  • Revision ID: james.westby@ubuntu.com-20090629093005-kcpcwnmr3nw4dlpo
Tags: 5.08-0ubuntu1
https://launchpad.net/bugs/392374
* New upstream release (LP: #392374)
  - New hack, `photopile'.
  - Rewrote `sonar' and `jigsaw' as OpenGL programs.
  - Minor tweaks to `maze', `m6502', `hypnowheel', and `timetunnel'.
  - Savers that load images now obey EXIF rotation tags.
  - Arrgh, more RANDR noise!  Fixes this time for rotated screens, and for
    systems where RANDR lies and says the screen size is 0x0.
  - When the password dialog has timed out or been cancelled, don't pop it
    right back up a second time.
  - Password timeouts/cancels don't count as "failed logins".
  - Retired some of the older, less interesting savers:
    say goodbye to `bubbles', `critical', `flag', `forest',
    `glforestfire', `lmorph', `laser', `lightning', `lisa',
    `lissie', `rotor', `sphere', `spiral', `t3d', `vines',
    `whirlygig', and `worm'.
  - Merged `munch' and `mismunch'.
  - Updated `webcollage' to use twitpics.com as well.
* debian/patches/20_hacks_Makefile.patch:
  - Refreshed
* debian/patches/24_hacks_xsublim_enable.patch:
  - Refreshed
* debian/patches/25_xsublim_missing_man_page.patch
  - Put back removed man page
* debian/patches/53_XScreenSaver.ad.in.patch:
  - Refreshed
* debian/screensavers-desktop-files/*:
  debian/xscreensaver.files:
  debian/xscreensaver-data-extra.files:
  debian/xscreensaver-gl-extra.files:
  - Updated for new/removed/changed screensavers
* debian/control: Added Bzr link

Show diffs side-by-side

added added

removed removed

Lines of Context:
hacks/maze.c
1
1
/******************************************************************************
2
2
 * [ maze ] ...
3
3
 *
 
4
 * modified:  [ 13-08-08 ] Jamie Zawinski <jwz@jwz.org>
 
5
 *              Removed the bridge option: it didn't look good, and it made
 
6
 *              the code a lot harder to understand.
 
7
 *              Made the maze stay out of the area used for the -fps display.
 
8
 *              Cleaned up and commented.
 
9
 *
4
10
 * modified:  [ 1-04-00 ]  Johannes Keukelaar <johannes@nada.kth.se>
5
11
 *              Added -ignorant option (not the default) to remove knowlege
6
12
 *              of the direction in which the exit lies.
144
150
 
145
151
  GC    gc, cgc, tgc, sgc, ugc, logo_gc, erase_gc;
146
152
  Pixmap logo_map;
147
 
  int logo_width, logo_height; /* in pixels */
 
153
 
 
154
  int logo_x, logo_y;           /* in grid cells (or -1) */
 
155
  int logo_width, logo_height;  /* in pixels */
 
156
  int fps_width, fps_height;    /* in pixels */
148
157
 
149
158
  int solve_delay, pre_solve_delay, post_solve_delay;
150
 
  int logo_x, logo_y;
151
159
 
152
160
  unsigned short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
153
161
 
163
171
 
164
172
  int x, y, restart, stop, state, max_length;
165
173
  int sync_p, sync_tick;
166
 
  int bridge_p, ignorant_p;
 
174
  int ignorant_p;
167
175
 
168
176
  struct solve_state *solve_state;
169
177
 
180
188
};
181
189
 
182
190
 
 
191
static void draw_wall (struct state *, int, int, int, GC);
 
192
static void draw_solid_square (struct state *, int, int, int, GC);
 
193
static void build_wall (struct state *, int, int, int);
 
194
 
 
195
 
183
196
static void
184
197
set_maze_sizes (struct state *st, int width, int height)
185
198
{
191
204
}
192
205
 
193
206
 
 
207
/* Resets the maze grid, picks the starting and ending points,
 
208
   and the position of the logo, if any.
 
209
 */
194
210
static void
195
 
initialize_maze (struct state *st) /* draw the surrounding wall and start/end squares */
 
211
initialize_maze (struct state *st)
196
212
{
197
 
  register int i, j, wall;
 
213
  int i, j, wall;
198
214
  int logow = 1 + st->logo_width / st->grid_width;
199
215
  int logoh = 1 + st->logo_height / st->grid_height;
200
216
  
 
217
 AGAIN:
 
218
 
201
219
  /* initialize all squares */
202
220
  for ( i=0; i<st->maze_size_x; i++) {
203
221
    for ( j=0; j<st->maze_size_y; j++) {
285
303
  /* set logo */
286
304
  if ((st->maze_size_x-logow >= 6) && (st->maze_size_y-logoh >= 6))
287
305
    {
288
 
      /* not closer than 3 grid units from a wall */
 
306
      /* not closer than 3 grid units from a wall, to ensure that it
 
307
         won't overlap the entrance or exit. */
289
308
      st->logo_x = get_random (st->maze_size_x - logow - 5) + 3;
290
309
      st->logo_y = get_random (st->maze_size_y - logoh - 5) + 3;
291
310
      for (i=0; i<logow; i++)
292
311
        for (j=0; j<logoh; j++)
293
 
          st->maze[st->logo_x + i][st->logo_y + j] |= DOOR_IN_TOP;
 
312
          /* mark as having doors to prevent these cells being used in maze. */
 
313
          st->maze[st->logo_x + i][st->logo_y + j] |= DOOR_IN_ANY;
294
314
    }
295
315
  else
296
316
    st->logo_y = st->logo_x = -1;
297
317
 
298
 
  /* #### should mask out the cells covered by the FPS display if "doFPS"
299
 
          is true.  But that's hard, because the "logo_x" crap that does
300
 
          that trick for the logo is scattered all around the code... */
 
318
  /* mask out the fps area */
 
319
  if (st->fps_width > 0)
 
320
    {
 
321
      int fpsw = 1 + st->fps_width  / st->grid_width;
 
322
      int fpsh = 1 + st->fps_height / st->grid_width;
 
323
 
 
324
      /* if the chosen logo position overlapped the fps area, try again! */
 
325
      if (st->logo_x < fpsw+3 && st->logo_y+logoh > st->maze_size_y-fpsh-4)
 
326
        goto AGAIN;
 
327
 
 
328
      /* if the start or end point is inside the fps area, try again! */
 
329
      if ((st->start_x <= fpsw && st->start_y >= st->maze_size_y-fpsh-1) ||
 
330
          (st->end_x   <= fpsw && st->end_y   >= st->maze_size_y-fpsh-1))
 
331
        goto AGAIN;
 
332
 
 
333
      for (i=0; i<fpsw; i++)
 
334
        for (j=0; j<fpsh; j++) {
 
335
          /* mark as having doors to prevent these cells being used in maze.
 
336
             mark as visit to prevent it being colored "unreachable". */
 
337
          st->maze[i][st->maze_size_y - j - 1] |= DOOR_IN_ANY|SOLVER_VISIT;
 
338
          /* take off left/bottom wall or the FPS text overlaps it */
 
339
          st->maze[i][st->maze_size_y - j - 1] &= ~(WALL_BOTTOM|WALL_LEFT);
 
340
        }
 
341
    }
301
342
}
302
343
 
303
 
static int choose_door (struct state *st);
304
 
static int backup (struct state *st);
305
 
static void draw_wall (struct state *, int, int, int, GC);
306
 
static void draw_solid_square (struct state *, int, int, int, GC);
307
 
/*static void enter_square (struct state *, int);*/
308
 
static void build_wall (struct state *, int, int, int);
309
 
/*static void break_wall (struct state *, int, int, int);*/
310
 
 
311
 
static void join_sets(struct state *, int, int);
312
 
 
313
 
#define DEBUG_SETS 0
 
344
 
 
345
/****************************************************************************
 
346
 Generator 2: Set-based maze generator.
 
347
 
 
348
 Put each square in the maze in a separate set.  Also, make a list of all the
 
349
 hedges.  Randomize that list.  Walk through the list. If, for a certain
 
350
 hedge, the two squares on both sides of it are in different sets, union the
 
351
 sets and remove the hedge.  Continue until all hedges have been processed or
 
352
 only one set remains.
 
353
 
 
354
 This is essentially the "Kruskal" algorithm.
 
355
 
 
356
 ****************************************************************************/
 
357
 
 
358
static void mask_out_set_rect(struct state *st, int x, int y, int w, int h);
314
359
 
315
360
/* Initialise the sets. */
316
361
static void 
317
362
init_sets(struct state *st)
318
363
{
319
 
  int i, t, r, xx, yy;
 
364
  int i, t, r;
320
365
 
321
366
  if(st->sets)
322
367
    free(st->sets);
346
391
    {
347
392
      st->hedges[2*((st->maze_size_y-1)*st->maze_size_x+i)] = -1;
348
393
    }
349
 
  /* Mask out a possible logo. */
 
394
 
 
395
  /* Mask out the logo area. */
350
396
  if(st->logo_x!=-1)
351
397
    {
352
 
      int logow = 1 + st->logo_width / st->grid_width;
 
398
      int logow = 1 + st->logo_width  / st->grid_width;
353
399
      int logoh = 1 + st->logo_height / st->grid_height;
354
 
      int bridge_dir, bridge_c;
355
 
 
356
 
      if(st->bridge_p && logoh>=3 && logow>=3)
357
 
        {
358
 
          bridge_dir = 1+random()%2;
359
 
          if(bridge_dir==1)
360
 
            {
361
 
              bridge_c = st->logo_y+random()%(logoh-2)+1;
362
 
            }
363
 
          else
364
 
            {
365
 
              bridge_c = st->logo_x+random()%(logow-2)+1;
366
 
            }
367
 
        }
368
 
      else
369
 
        {
370
 
          bridge_dir = 0;
371
 
          bridge_c = -1;
372
 
        }
373
 
 
374
 
      for(xx = st->logo_x; xx < st->logo_x+logow; xx++)
375
 
        for(yy = st->logo_y; yy < st->logo_y+logoh; yy++)
376
 
          {
377
 
            /* I should check for the bridge here, except that I join the
378
 
             * bridge together below.
379
 
             */
380
 
            st->hedges[2*(xx+st->maze_size_x*yy)+1] = -1;
381
 
            st->hedges[2*(xx+st->maze_size_x*yy)] = -1;
382
 
          }
383
 
      for(xx = st->logo_x; xx < st->logo_x+logow; xx++)
384
 
        {
385
 
          if(!(bridge_dir==2 && xx==bridge_c))
386
 
            {
387
 
              build_wall(st, xx, st->logo_y, 0);
388
 
              build_wall(st, xx, st->logo_y+logoh, 0);
389
 
            }
390
 
          st->hedges[2*(xx+st->maze_size_x*(st->logo_y-1))] = -1;
391
 
          if(bridge_dir==1)
392
 
            {
393
 
              build_wall(st, xx, bridge_c, 0);
394
 
              build_wall(st, xx, bridge_c, 2);
395
 
            }
396
 
        }
397
 
      for(yy = st->logo_y; yy < st->logo_y+logoh; yy++)
398
 
        {
399
 
          if(!(bridge_dir==1 && yy==bridge_c))
400
 
            {
401
 
              build_wall(st, st->logo_x, yy, 3);
402
 
              build_wall(st, st->logo_x+logow, yy, 3);
403
 
            }
404
 
          st->hedges[2*(st->logo_x-1+st->maze_size_x*yy)+1] = -1;
405
 
          if(bridge_dir==2)
406
 
            {
407
 
              build_wall(st, bridge_c, yy, 1);
408
 
              build_wall(st, bridge_c, yy, 3);
409
 
            }
410
 
        }
411
 
      /* Join the whole bridge together. */
412
 
      if(st->bridge_p)
413
 
        {
414
 
          if(bridge_dir==1)
415
 
            {
416
 
              xx = st->logo_x-1;
417
 
              yy = bridge_c;
418
 
              for(i = st->logo_x; i < st->logo_x+logow+1; i++)
419
 
                join_sets(st, xx+yy*st->maze_size_x, i+yy*st->maze_size_x);
420
 
            }
421
 
          else
422
 
            {
423
 
              yy = st->logo_y-1;
424
 
              xx = bridge_c;
425
 
              for(i = st->logo_y; i < st->logo_y+logoh+1; i++)
426
 
                join_sets(st, xx+yy*st->maze_size_x, xx+i*st->maze_size_x);
427
 
            }
428
 
        }
 
400
      mask_out_set_rect(st, st->logo_x, st->logo_y, logow, logoh);
 
401
    }
 
402
 
 
403
  /* Mask out the FPS area. */
 
404
  if(st->fps_width > 0)
 
405
    {
 
406
      int fpsw = 1 + st->fps_width  / st->grid_width;
 
407
      int fpsh = 1 + st->fps_height / st->grid_height;
 
408
      mask_out_set_rect(st, 0, st->maze_size_y-fpsh, fpsw, fpsh);
429
409
    }
430
410
 
431
411
  for(i = 0; i < st->maze_size_x*st->maze_size_y*2; i++)
480
460
  st->sets = 0;
481
461
}
482
462
 
483
 
#if DEBUG_SETS
484
 
/* Temporary hack. */
485
 
static void
486
 
show_set(int num, GC gc)
487
 
{
488
 
  int st->x, st->y, set;
489
 
 
490
 
  set = get_set(num);
491
 
 
492
 
  for(st->x = 0; st->x < st->maze_size_x; st->x++)
493
 
    for(st->y = 0; st->y < st->maze_size_y; st->y++)
494
 
      {
495
 
        if(get_set(st->x+st->y*st->maze_size_x)==set)
496
 
          {
497
 
            XFillRectangle(st->dpy, st->window, st->gc,  border_x + st->bw + st->grid_width * st->x, 
498
 
                         border_y + st->bw + st->grid_height * st->y, 
499
 
                         st->grid_width-2*st->bw , st->grid_height-2*st->bw);
500
 
          }
501
 
      }
502
 
}
503
 
#endif
504
 
 
505
 
/* Second alternative maze creator: Put each square in the maze in a 
506
 
 * separate set. Also, make a list of all the hedges. Randomize that list.
507
 
 * Walk through the list. If, for a certain hedge, the two squares on both
508
 
 * sides of it are in different sets, union the sets and remove the hedge.
509
 
 * Continue until all hedges have been processed or only one set remains.
510
 
 */
 
463
 
511
464
static void
512
465
set_create_maze(struct state *st)
513
466
{
514
467
  int i, h, xx, yy, dir, v, w;
515
 
#if DEBUG_SETS
516
 
  int cont = 0;
517
 
  char c;
518
 
#endif
519
468
 
520
469
  /* Do almost all the setup. */
521
470
  init_sets(st);
545
494
          break;
546
495
        }
547
496
 
548
 
#if DEBUG_SETS
549
 
      show_set(st, xx+yy*st->maze_size_x, st->logo_gc);
550
 
      show_set(st, v+w*st->maze_size_x, st->tgc);
551
 
#endif
552
497
      if(get_set(st, xx+yy*st->maze_size_x)!=get_set(st, v+w*st->maze_size_x))
553
498
        {
554
 
#if DEBUG_SETS
555
 
          printf("Join!");
556
 
#endif
557
499
          join_sets(st, xx+yy*st->maze_size_x, v+w*st->maze_size_x);
558
500
          /* Don't draw the wall. */
559
501
        }
560
502
      else
561
503
        {
562
 
#if DEBUG_SETS
563
 
          printf("Build.");
564
 
#endif
565
504
          /* Don't join the sets. */
566
505
          build_wall(st, xx, yy, dir); 
567
506
        }
568
 
#if DEBUG_SETS
569
 
      if(!cont)
570
 
        {
571
 
          XSync(st->dpy, False);
572
 
          c = getchar();
573
 
          if(c=='c')
574
 
            cont = 1;
575
 
        }
576
 
      show_set(xx+yy*st->maze_size_x, st->erase_gc);
577
 
      show_set(v+w*st->maze_size_x, st->erase_gc);
578
 
#endif
579
507
    }
580
508
 
581
509
  /* Free some memory. */
582
510
  exit_sets(st);
583
511
}
584
512
 
585
 
/* First alternative maze creator: Pick a random, empty corner in the maze.
586
 
 * Pick a random direction. Draw a wall in that direction, from that corner
587
 
 * until we hit a wall. Option: Only draw the wall if it's going to be 
588
 
 * shorter than a certain length. Otherwise we get lots of long walls.
589
 
 */
 
513
/* mark a rectangle as being unavailable for usage in the maze */
 
514
static void
 
515
mask_out_set_rect(struct state *st, int x, int y, int w, int h)
 
516
{
 
517
  int xx, yy;
 
518
  for(xx = x; xx < x+w; xx++)
 
519
    for(yy = y; yy < y+h; yy++)
 
520
      {
 
521
        st->hedges[2*(xx+st->maze_size_x*yy)+1] = -1;
 
522
        st->hedges[2*(xx+st->maze_size_x*yy)] = -1;
 
523
      }
 
524
  for(xx = x; xx < x+w; xx++)
 
525
    {
 
526
      build_wall(st, xx, y, 0);
 
527
      build_wall(st, xx, y+h, 0);
 
528
      st->hedges[2*(xx+st->maze_size_x*(y-1))] = -1;
 
529
    }
 
530
  for(yy = y; yy < y+h; yy++)
 
531
    {
 
532
      build_wall(st, x, yy, 3);
 
533
      build_wall(st, x+w, yy, 3);
 
534
      st->hedges[2*(x-1+st->maze_size_x*yy)+1] = -1;
 
535
    }
 
536
}
 
537
 
 
538
 
 
539
/****************************************************************************
 
540
 Generator 1: Wall-building maze generator.
 
541
 
 
542
 Pick a random, empty corner in the maze.  Pick a random direction. Draw a
 
543
 wall in that direction, from that corner until we hit a wall.  Option: Only
 
544
 draw the wall if it's going to be shorter than a certain length.  Otherwise
 
545
 we get lots of long walls.
 
546
 
 
547
 This is essentially the "Prim" algorithm.
 
548
 ****************************************************************************/
 
549
 
 
550
static void alt_mask_out_rect(struct state *st, char *corners, 
 
551
                              int x, int y, int w, int h);
 
552
 
590
553
static void
591
554
alt_create_maze(struct state *st)
592
555
{
631
594
      corners[i*width] = 1;
632
595
      corners[i*width+width-1] = 1;
633
596
    }
634
 
  /* Walls around logo. In fact, inside the logo, too. */
635
 
  /* Also draw the walls. */
 
597
 
 
598
  /* mask out the logo area */
636
599
  if(st->logo_x!=-1)
637
600
    {
638
601
      int logow = 1 + st->logo_width / st->grid_width;
639
602
      int logoh = 1 + st->logo_height / st->grid_height;
640
 
      int bridge_dir, bridge_c;
 
603
      alt_mask_out_rect (st, corners, st->logo_x, st->logo_y, logow, logoh);
 
604
    }
641
605
 
642
 
      if(st->bridge_p && logoh>=3 && logow>=3)
643
 
        {
644
 
          bridge_dir = 1+random()%2;
645
 
          if(bridge_dir==1)
646
 
            {
647
 
              bridge_c = st->logo_y+random()%(logoh-2)+1;
648
 
            }
649
 
          else
650
 
            {
651
 
              bridge_c = st->logo_x+random()%(logow-2)+1;
652
 
            }
653
 
        }
654
 
      else
655
 
        {
656
 
          bridge_dir = 0;
657
 
          bridge_c = -1;
658
 
        }
659
 
      for(i = st->logo_x; i <= st->logo_x + logow; i++)
660
 
        {
661
 
          for(j = st->logo_y; j <= st->logo_y + logoh; j++)
662
 
            {
663
 
              corners[i+width*j] = 1;
664
 
            }
665
 
        }
666
 
      for(xx = st->logo_x; xx < st->logo_x+logow; xx++)
667
 
        {
668
 
          if(!(bridge_dir==2 && xx==bridge_c))
669
 
            {
670
 
              build_wall(st, xx, st->logo_y, 0);
671
 
              build_wall(st, xx, st->logo_y+logoh, 0);
672
 
            }
673
 
          if(bridge_dir==1)
674
 
            {
675
 
              build_wall(st, xx, bridge_c, 0);
676
 
              build_wall(st, xx, bridge_c, 2);
677
 
            }
678
 
        }
679
 
      for(yy = st->logo_y; yy < st->logo_y+logoh; yy++)
680
 
        {
681
 
          if(!(bridge_dir==1 && yy==bridge_c))
682
 
            {
683
 
              build_wall(st, st->logo_x, yy, 3);
684
 
              build_wall(st, st->logo_x+logow, yy, 3);
685
 
            }
686
 
          if(bridge_dir==2)
687
 
            {
688
 
              build_wall(st, bridge_c, yy, 1);
689
 
              build_wall(st, bridge_c, yy, 3);
690
 
            }
691
 
        }
692
 
      /* Connect one wall of the logo with an outside wall. */
693
 
      if(st->bridge_p)
694
 
        dir = (bridge_dir+1)%4;
695
 
      else
696
 
        dir = random()%4;
697
 
      switch(dir)
698
 
        {
699
 
        case 0:
700
 
          xx = st->logo_x+(random()%(logow+1));
701
 
          yy = st->logo_y;
702
 
          break;
703
 
        case 1:
704
 
          xx = st->logo_x+logow;
705
 
          yy = st->logo_y+(random()%(logoh+1));
706
 
          break;
707
 
        case 2:
708
 
          xx = st->logo_x+(random()%(logow+1));
709
 
          yy = st->logo_y+logoh;
710
 
          break;
711
 
        case 3:
712
 
          xx = st->logo_x;
713
 
          yy = st->logo_y+(random()%(logoh+1));
714
 
          break;
715
 
        }
716
 
      do
717
 
        {
718
 
          corners[xx+width*yy] = 1;
719
 
          switch(dir)
720
 
            {
721
 
            case 0:
722
 
              build_wall(st, xx-1, yy-1, 1);
723
 
              yy--;
724
 
              break;
725
 
            case 1:
726
 
              build_wall(st, xx, yy, 0);
727
 
              xx++;
728
 
              break;
729
 
            case 2:
730
 
              build_wall(st, xx, yy, 3);
731
 
              yy++;
732
 
              break;
733
 
            case 3:
734
 
              build_wall(st, xx-1, yy-1, 2);
735
 
              xx--;
736
 
              break;      
737
 
            }
738
 
        }
739
 
      while(!corners[xx+width*yy]);
740
 
      if(st->bridge_p)
741
 
        {
742
 
          dir = (dir+2)%4;
743
 
          switch(dir)
744
 
            {
745
 
            case 0:
746
 
              xx = st->logo_x+(random()%(logow+1));
747
 
              yy = st->logo_y;
748
 
              break;
749
 
            case 1:
750
 
              xx = st->logo_x+logow;
751
 
              yy = st->logo_y+(random()%(logoh+1));
752
 
              break;
753
 
            case 2:
754
 
              xx = st->logo_x+(random()%(logow+1));
755
 
              yy = st->logo_y+logoh;
756
 
              break;
757
 
            case 3:
758
 
              xx = st->logo_x;
759
 
              yy = st->logo_y+(random()%(logoh+1));
760
 
              break;
761
 
            }
762
 
          do
763
 
            {
764
 
              corners[xx+width*yy] = 1;
765
 
              switch(dir)
766
 
                {
767
 
                case 0:
768
 
                  build_wall(st, xx-1, yy-1, 1);
769
 
                  yy--;
770
 
                  break;
771
 
                case 1:
772
 
                  build_wall(st, xx, yy, 0);
773
 
                  xx++;
774
 
                  break;
775
 
                case 2:
776
 
                  build_wall(st, xx, yy, 3);
777
 
                  yy++;
778
 
                  break;
779
 
                case 3:
780
 
                  build_wall(st, xx-1, yy-1, 2);
781
 
                  xx--;
782
 
                  break;          
783
 
                }
784
 
            }
785
 
          while(!corners[xx+width*yy]);
786
 
        }
 
606
  /* mask out the FPS area */
 
607
  if(st->fps_width>0)
 
608
    {
 
609
      int fpsw = 1 + st->fps_width  / st->grid_width;
 
610
      int fpsh = 1 + st->fps_height / st->grid_height;
 
611
      alt_mask_out_rect (st, corners, 0, st->maze_size_y-fpsh, fpsw, fpsh);
787
612
    }
788
613
 
789
614
  /* Count open gridpoints. */
867
692
  free(c_idx);
868
693
}
869
694
 
870
 
/* The original maze creator. Start somewhere. Take a step in a random 
871
 
 * direction. Keep doing this until we hit a wall. Then, backtrack until
872
 
 * we find a point where we can go in another direction.
873
 
 */
 
695
 
 
696
/* mark a rectangle as being unavailable for usage in the maze */
 
697
static void
 
698
alt_mask_out_rect(struct state *st, char *corners, int x, int y, int w, int h)
 
699
{
 
700
  int i, j, xx, yy;
 
701
  int mazew = st->maze_size_x+1;
 
702
 
 
703
  for(i = x; i <= x+w; i++)
 
704
    for(j = y; j <= y+h; j++)
 
705
      corners[i+mazew*j] = 1;
 
706
 
 
707
  for(xx = x; xx < x+w; xx++)
 
708
    {
 
709
      build_wall(st, xx, y, 0);
 
710
      if (y+h < st->maze_size_y)
 
711
        build_wall(st, xx, y+h, 0);
 
712
    }
 
713
  for(yy = y; yy < y+h; yy++)
 
714
    {
 
715
      if (x > 0)
 
716
        build_wall(st, x, yy, 3);
 
717
      build_wall(st, x+w, yy, 3);
 
718
    }
 
719
}
 
720
 
 
721
 
 
722
/****************************************************************************
 
723
 Generator 0: The original maze generator.
 
724
 
 
725
 Start somewhere.  Take a step in a random direction.  Keep doing this until
 
726
 we hit a wall.  Then, backtrack until we find a point where we can go in
 
727
 another direction.
 
728
 
 
729
 This is essentially the "depth-first recursive backtracker" algorithm.
 
730
 ****************************************************************************/
 
731
 
 
732
static int choose_door (struct state *st);
 
733
static int backup (struct state *st);
 
734
 
874
735
static void
875
736
create_maze (struct state *st)    /* create a maze layout given the initialized maze */
876
737
{
877
 
  register int i, newdoor = 0;
878
 
  int logow = 1 + st->logo_width / st->grid_width;
879
 
  int logoh = 1 + st->logo_height / st->grid_height;
 
738
  int i, newdoor = 0;
880
739
  
881
 
  /* Maybe we should make a bridge? */
882
 
  if(st->bridge_p && st->logo_x >= 0 && logow>=3 && logoh>=3)
883
 
    {
884
 
      int bridge_dir, bridge_c;
885
 
 
886
 
      bridge_dir = 1+random()%2;
887
 
      if(bridge_dir==1)
888
 
        {
889
 
          if(logoh>=3)
890
 
            bridge_c = st->logo_y+random()%(logoh-2)+1;
891
 
          else
892
 
            bridge_c = st->logo_y+random()%logoh;
893
 
        }
894
 
      else
895
 
        {
896
 
          if(logow>=3)
897
 
            bridge_c = st->logo_x+random()%(logow-2)+1;
898
 
          else
899
 
            bridge_c = st->logo_x+random()%logow;
900
 
        }
901
 
 
902
 
      if(bridge_dir==1)
903
 
        {
904
 
          for(i = st->logo_x; i < st->logo_x+logow; i++)
905
 
            {
906
 
              st->maze[i][bridge_c] &= ~DOOR_IN_TOP;
907
 
            }
908
 
        }
909
 
      else
910
 
        {
911
 
          for(i = st->logo_y; i < st->logo_y+logoh; i++)
912
 
            {
913
 
              st->maze[bridge_c][i] &= ~DOOR_IN_TOP;
914
 
            }
915
 
        }
916
 
    }
917
 
 
918
740
  do {
919
741
    st->move_list[st->sqnum].x = st->cur_sq_x;
920
742
    st->move_list[st->sqnum].y = st->cur_sq_y;
962
784
choose_door (struct state *st)                                   /* pick a new path */
963
785
{
964
786
  int candidates[3];
965
 
  register int num_candidates;
 
787
  int num_candidates;
966
788
  
967
789
  num_candidates = 0;
968
790
  
1049
871
}
1050
872
 
1051
873
 
 
874
/****************************************************************************
 
875
 Drawing the maze
 
876
 ****************************************************************************/
 
877
 
 
878
/* draws the maze outline, and the logo */
1052
879
static void
1053
 
draw_maze_border (struct state *st)                         /* draw the maze outline */
 
880
draw_maze_border (struct state *st)
1054
881
{
1055
 
  register int i, j;
1056
 
  
1057
 
  
 
882
  int i, j;
 
883
 
1058
884
  for ( i=0; i<st->maze_size_x; i++) {
1059
885
    if ( st->maze[i][0] & WALL_TOP ) {
1060
886
      XDrawLine(st->dpy, st->window, st->gc,
1130
956
}
1131
957
 
1132
958
 
 
959
/* Mark the maze grid as having a wall at the given coordinate,
 
960
   and draw that wall on the screen. */
 
961
static void
 
962
build_wall(struct state *st, int i, int j, int dir)
 
963
{
 
964
  /* Draw it on the screen. */
 
965
  draw_wall(st, i, j, dir, st->gc);
 
966
  /* Put it in the maze. */
 
967
  switch(dir)
 
968
    {
 
969
    case 0:
 
970
      st->maze[i][j] |= WALL_TOP;
 
971
      if(j>0)
 
972
        st->maze[i][j-1] |= WALL_BOTTOM;
 
973
      break;
 
974
    case 1:
 
975
      st->maze[i][j] |= WALL_RIGHT;
 
976
      if(i<st->maze_size_x-1)
 
977
        st->maze[i+1][j] |= WALL_LEFT;
 
978
      break;
 
979
    case 2:
 
980
      st->maze[i][j] |= WALL_BOTTOM;
 
981
      if(j<st->maze_size_y-1)
 
982
        st->maze[i][j+1] |= WALL_TOP;
 
983
      break;
 
984
    case 3:
 
985
      st->maze[i][j] |= WALL_LEFT;
 
986
      if(i>0)
 
987
        st->maze[i-1][j] |= WALL_RIGHT;
 
988
      break;
 
989
    }
 
990
}
 
991
 
 
992
 
1133
993
static void
1134
994
draw_wall(struct state *st, int i, int j, int dir, GC with_gc)                /* draw a single wall */
1135
995
{
1176
1036
  }
1177
1037
}
1178
1038
 
1179
 
/* Actually build a wall. */
1180
 
static void
1181
 
build_wall(struct state *st, int i, int j, int dir)
1182
 
{
1183
 
  /* Draw it on the screen. */
1184
 
  draw_wall(st, i, j, dir, st->gc);
1185
 
  /* Put it in the maze. */
1186
 
  switch(dir)
1187
 
    {
1188
 
    case 0:
1189
 
      st->maze[i][j] |= WALL_TOP;
1190
 
      if(j>0)
1191
 
        st->maze[i][j-1] |= WALL_BOTTOM;
1192
 
      break;
1193
 
    case 1:
1194
 
      st->maze[i][j] |= WALL_RIGHT;
1195
 
      if(i<st->maze_size_x-1)
1196
 
        st->maze[i+1][j] |= WALL_LEFT;
1197
 
      break;
1198
 
    case 2:
1199
 
      st->maze[i][j] |= WALL_BOTTOM;
1200
 
      if(j<st->maze_size_y-1)
1201
 
        st->maze[i][j+1] |= WALL_TOP;
1202
 
      break;
1203
 
    case 3:
1204
 
      st->maze[i][j] |= WALL_LEFT;
1205
 
      if(i>0)
1206
 
        st->maze[i-1][j] |= WALL_RIGHT;
1207
 
      break;
1208
 
    }
1209
 
}
1210
 
 
1211
 
/* Break out a wall. */
1212
 
#if 0
1213
 
static void
1214
 
break_wall(i, j, dir)
1215
 
     int i, j, dir;
1216
 
{
1217
 
  /* Draw it on the screen. */
1218
 
  draw_wall(i, j, dir, st->erase_gc);
1219
 
  /* Put it in the maze. */
1220
 
  switch(dir)
1221
 
    {
1222
 
    case 0:
1223
 
      st->maze[i][j] &= ~WALL_TOP;
1224
 
      if(j>0)
1225
 
        maze[i][j-1] &= ~WALL_BOTTOM;
1226
 
      break;
1227
 
    case 1:
1228
 
      st->maze[i][j] &= ~WALL_RIGHT;
1229
 
      if(i<st->maze_size_x-1)
1230
 
        maze[i+1][j] &= ~WALL_LEFT;
1231
 
      break;
1232
 
    case 2:
1233
 
      st->maze[i][j] &= ~WALL_BOTTOM;
1234
 
      if(j<st->maze_size_y-1)
1235
 
        maze[i][j+1] &= ~WALL_BOTTOM;
1236
 
      break;
1237
 
    case 3:
1238
 
      st->maze[i][j] &= ~WALL_LEFT;
1239
 
      if(i>0)
1240
 
        maze[i-1][j] &= ~WALL_RIGHT;
1241
 
      break;
1242
 
    }
1243
 
}
1244
 
#endif /* 0 */
1245
 
 
1246
1039
 
1247
1040
static void
1248
1041
draw_solid_square(struct state *st, 
1249
 
                  int i, int j,          /* draw a solid square in a square */
 
1042
                  int i, int j,
1250
1043
                  int dir, GC with_gc)
1251
1044
{
1252
1045
  switch (dir) {
1277
1070
  }
1278
1071
}
1279
1072
 
 
1073
/****************************************************************************
 
1074
 Solving the maze
 
1075
 ****************************************************************************/
 
1076
 
1280
1077
static int
1281
1078
longdeadend_p(struct state *st, int x1, int y1, int x2, int y2, int endwall)
1282
1079
{
1380
1177
      }
1381
1178
}
1382
1179
 
 
1180
/* solve the maze by one more tick */
1383
1181
static int
1384
 
solve_maze (struct state *st)                     /* solve it with graphical feedback */
 
1182
solve_maze (struct state *st)
1385
1183
{
1386
1184
  struct solve_state *ss = st->solve_state;
1387
1185
  if (!ss)
1542
1340
    return 0;
1543
1341
} 
1544
1342
 
1545
 
#if 0
1546
 
static void
1547
 
enter_square (int n)                      /* move into a neighboring square */
1548
 
{
1549
 
  draw_solid_square( (int)st->path[n].x, (int)st->path[n].y, 
1550
 
                    (int)st->path[n].dir, st->tgc);
1551
 
  
1552
 
  st->path[n+1].dir = -1;
1553
 
  switch (st->path[n].dir) {
1554
 
  case 0: st->path[n+1].x = st->path[n].x;
1555
 
    st->path[n+1].y = st->path[n].y - 1;
1556
 
    break;
1557
 
  case 1: st->path[n+1].x = st->path[n].x + 1;
1558
 
    st->path[n+1].y = st->path[n].y;
1559
 
    break;
1560
 
  case 2: st->path[n+1].x = st->path[n].x;
1561
 
    st->path[n+1].y = st->path[n].y + 1;
1562
 
    break;
1563
 
  case 3: st->path[n+1].x = st->path[n].x - 1;
1564
 
    st->path[n+1].y = st->path[n].y;
1565
 
    break;
1566
 
  }
1567
 
}
1568
 
#endif /* 0 */
1569
 
 
1570
 
 
1571
 
/*
1572
 
 *  jmr additions for Jamie Zawinski's <jwz@jwz.org> screensaver stuff,
1573
 
 *  note that the code above this has probably been hacked about in some
1574
 
 *  arbitrary way.
1575
 
 */
 
1343
 
 
1344
/****************************************************************************
 
1345
 XScreenSaver boilerplate: resources, command line options, and main loop.
 
1346
 ****************************************************************************/
1576
1347
 
1577
1348
static const char *maze_defaults[] = {
1578
1349
  ".background:    black",
1581
1352
  "*gridSize:      0",
1582
1353
  "*generator:     -1",
1583
1354
  "*maxLength:     5",
1584
 
  "*bridge:        False",
1585
1355
  "*ignorant:      False",
1586
1356
 
1587
1357
  "*solveDelay:    10000",
1611
1381
  { "-surround-color",  ".surroundColor",XrmoptionSepArg, 0 },
1612
1382
  { "-generator",       ".generator",   XrmoptionSepArg, 0 },
1613
1383
  { "-max-length",      ".maxLength",   XrmoptionSepArg, 0 },
1614
 
  { "-bridge",          ".bridge",      XrmoptionNoArg, "True" },
1615
 
  { "-no-bridge",       ".bridge",      XrmoptionNoArg, "False" },
1616
1384
  { 0, 0, 0, 0 }
1617
1385
};
1618
1386
 
1622
1390
maze_init (Display *dpy_arg, Window window_arg)
1623
1391
{
1624
1392
  struct state *st = (struct state *) calloc (1, sizeof(*st));
1625
 
# ifdef DO_STIPPLE
1626
 
  Pixmap gray;
1627
 
# endif
1628
1393
  int size;
1629
1394
  XWindowAttributes xgwa;
1630
1395
  unsigned long bg, fg, pfg, pbg, sfg, ufg;
1645
1410
  st->post_solve_delay = get_integer_resource (st->dpy, "postDelay", "Integer");
1646
1411
  generator = get_integer_resource(st->dpy, "generator", "Integer");
1647
1412
  st->max_length = get_integer_resource(st->dpy, "maxLength", "Integer");
1648
 
  st->bridge_p = get_boolean_resource(st->dpy, "bridge", "Boolean");
1649
1413
  st->ignorant_p = get_boolean_resource(st->dpy, "ignorant", "Boolean");
1650
1414
 
 
1415
  if (get_boolean_resource (st->dpy, "doFPS", "DoFPS"))
 
1416
    {
 
1417
      /* Just guess, rather than loading and measuring the "fpsFont"... */
 
1418
      st->fps_width = 210;
 
1419
      st->fps_height = 62;
 
1420
    }
 
1421
 
1651
1422
  if (!size) st->ifrandom = 1;
1652
1423
 
1653
1424
  if (size < 2) size = 7 + (random () % 30);
1669
1440
  st->logo_gc = XCreateGC(st->dpy, st->window, 0, 0);
1670
1441
  st->erase_gc = XCreateGC(st->dpy, st->window, 0, 0);
1671
1442
  
1672
 
# ifdef DO_STIPPLE
1673
 
  gray = XCreateBitmapFromData (st->dpy,st->window,gray1_bits,gray1_width,gray1_height);
1674
 
# endif
1675
 
 
1676
1443
  bg  = get_pixel_resource (st->dpy, xgwa.colormap, "background","Background");
1677
1444
  fg  = get_pixel_resource (st->dpy, xgwa.colormap, "foreground","Foreground");
1678
1445
  pfg = get_pixel_resource (st->dpy, xgwa.colormap, "liveColor", "Foreground");
1695
1462
  XSetForeground (st->dpy, st->erase_gc, bg);
1696
1463
  XSetBackground (st->dpy, st->erase_gc, bg);
1697
1464
 
1698
 
# ifdef DO_STIPPLE
1699
 
  XSetStipple (st->dpy, st->cgc, gray);
1700
 
  XSetFillStyle (st->dpy, st->cgc, FillOpaqueStippled);
1701
 
  XSetStipple (st->dpy, st->sgc, gray);
1702
 
  XSetFillStyle (st->dpy, st->sgc, FillOpaqueStippled);
1703
 
  XSetStipple (st->dpy, st->ugc, gray);
1704
 
  XSetFillStyle (st->dpy, st->ugc, FillOpaqueStippled);
1705
 
# endif
1706
 
  
1707
1465
  {
1708
1466
    Window r;
1709
1467
    int x, y;