maze.c

一个XWindow下的迷宫游戏

/******************************************************************************
 * [ maze ] ...
 *
 * modified:  [ 10-4-88 ]  Richard Hess    ...!uunet!cimshop!rhess  
 *              [ Revised primary execution loop within main()...
 *              [ Extended X event handler, check_events()...
 * modified:  [ 1-29-88 ]  Dave Lemke      [e-mail]  
 *              [ Hacked for X11...
 *              [  Note the word "hacked" -- this is extremely ugly, but at 
 *              [   least it does the job.  NOT a good programming example 
 *              [   for X.
 * original:  [ 6/21/85 ]  Martin Weiss    Sun Microsystems  [ SunView ]
 *
 ******************************************************************************
 Copyright 1988 by Sun Microsystems, Inc. Mountain View, CA.
  
 All Rights Reserved
  
 Permission to use, copy, modify, and distribute this software and its
 documentation for any purpose and without fee is hereby granted, 
 provided that the above copyright notice appear in all copies and that
 both that copyright notice and this permission notice appear in 
 supporting documentation, and that the names of Sun or MIT not be
 used in advertising or publicity pertaining to distribution of the
 software without specific prior written permission. Sun and M.I.T. 
 make no representations about the suitability of this software for 
 any purpose. It is provided "as is" without any express or implied warranty.
 
 SUN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 PURPOSE. IN NO EVENT SHALL SUN BE LIABLE FOR ANY SPECIAL, INDIRECT
 OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
 OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 
 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
 OR PERFORMANCE OF THIS SOFTWARE.
 *****************************************************************************/

#include  <sys/types.h>
#include  <stdio.h>
#include  <X11/Xlib.h>
#include  <X11/Xutil.h>

#define LOGOSIZE	7
#define MIN_MAZE_SIZE	3
#define MAX_MAZE_SIZE_X	205
#define MAX_MAZE_SIZE_Y	205

#define MOVE_LIST_SIZE  (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
  
#define WALL_TOP	0x8000
#define WALL_RIGHT	0x4000
#define WALL_BOTTOM	0x2000
#define WALL_LEFT	0x1000
  
#define DOOR_IN_TOP	0x800
#define DOOR_IN_RIGHT	0x400
#define DOOR_IN_BOTTOM	0x200
#define DOOR_IN_LEFT	0x100
#define DOOR_IN_ANY	0xF00
  
#define DOOR_OUT_TOP	0x80
#define DOOR_OUT_RIGHT	0x40
#define DOOR_OUT_BOTTOM	0x20
#define DOOR_OUT_LEFT	0x10
  
#define START_SQUARE	0x2
#define END_SQUARE	0x1
  
#define SQ_SIZE_X	10
#define SQ_SIZE_Y       10
  
#define NUM_RANDOM      100
  
#define	BORDERWIDTH     2
#define	border_x        (0)
#define	border_y        (0)
#define	MIN_W	        200
#define	MIN_H	        200
#define	DEF_W	        500
#define	DEF_H	        500
  
#define	get_random(x)	(random() % (x))
  
static int logo_x, logo_y;


#define logo_width 64
#define logo_height 64
static char logo_bits[] = {
   0xff, 0xff, 0xff, 0x3f, 0xfc, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x0f,
   0xf0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x07, 0xe0, 0xff, 0xff, 0xff,
   0xff, 0xff, 0xff, 0x03, 0xc0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x03,
   0x80, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01, 0x00, 0xff, 0xff, 0xff,
   0xff, 0xff, 0xff, 0x81, 0x00, 0xfe, 0xff, 0xff, 0xff, 0xff, 0xbf, 0x01,
   0x01, 0xfc, 0xff, 0xff, 0xff, 0xff, 0x1f, 0x03, 0x02, 0xf8, 0xff, 0xff,
   0xff, 0xff, 0x0f, 0x02, 0x04, 0xf0, 0xff, 0xff, 0xff, 0xff, 0x07, 0x04,
   0x08, 0xe0, 0xff, 0xff, 0xff, 0xff, 0x0b, 0x08, 0x10, 0xc0, 0xff, 0xff,
   0xff, 0xff, 0x11, 0x10, 0x20, 0x80, 0xff, 0xff, 0xff, 0xff, 0x20, 0x20,
   0x40, 0x00, 0xff, 0xff, 0xff, 0x7f, 0x40, 0x40, 0x80, 0x00, 0xff, 0xff,
   0xff, 0x7f, 0x80, 0x80, 0x00, 0x81, 0xfc, 0xff, 0xff, 0x9f, 0x00, 0x01,
   0x01, 0x42, 0xf8, 0xff, 0xff, 0x0f, 0x01, 0x02, 0x02, 0x24, 0xf0, 0xff,
   0xff, 0x07, 0x02, 0x04, 0x04, 0x18, 0xe0, 0xff, 0xff, 0x03, 0x04, 0x08,
   0x08, 0x08, 0xd0, 0xff, 0xff, 0x01, 0x0a, 0x10, 0x10, 0x04, 0x88, 0xff,
   0xff, 0x00, 0x11, 0x20, 0x30, 0x02, 0x04, 0xff, 0x7f, 0x80, 0x20, 0x40,
   0x60, 0x01, 0x02, 0xfe, 0x3f, 0x40, 0x40, 0x00, 0xe0, 0x00, 0x01, 0xff,
   0x1f, 0x20, 0xe0, 0x00, 0x60, 0x80, 0x80, 0xff, 0x0f, 0x10, 0xf0, 0x01,
   0x30, 0x40, 0xc0, 0xf8, 0x07, 0x08, 0x18, 0x03, 0x10, 0x20, 0x20, 0xe0,
   0x03, 0x04, 0x04, 0x04, 0x08, 0x10, 0x10, 0xc0, 0x01, 0x02, 0x02, 0x18,
   0x06, 0x08, 0x08, 0x80, 0x01, 0x01, 0x01, 0xf8, 0x07, 0x04, 0x04, 0x80,
   0x80, 0x80, 0x00, 0xf0, 0x03, 0x02, 0x02, 0x00, 0x40, 0x40, 0x00, 0xf0,
   0x03, 0x01, 0x01, 0x00, 0x00, 0x20, 0x20, 0xf0, 0x03, 0x80, 0x00, 0x01,
   0x00, 0x10, 0x10, 0xf0, 0x03, 0x40, 0x80, 0x00, 0x01, 0x08, 0x08, 0xf8,
   0x07, 0x20, 0x40, 0x80, 0x01, 0x04, 0x04, 0x18, 0x06, 0x10, 0x20, 0x80,
   0x03, 0x02, 0x02, 0x04, 0x08, 0x08, 0x10, 0xc0, 0x8f, 0x01, 0x01, 0x02,
   0x30, 0x06, 0x08, 0xe0, 0xff, 0x80, 0x00, 0x03, 0xe0, 0x03, 0x04, 0xf0,
   0x7f, 0x40, 0x80, 0x01, 0xc0, 0x01, 0x02, 0xf8, 0x3f, 0x20, 0xc0, 0x01,
   0x80, 0x00, 0x01, 0xfc, 0x7f, 0x10, 0xa0, 0x81, 0x00, 0x81, 0x00, 0xfe,
   0xff, 0x08, 0x10, 0x03, 0x01, 0x42, 0x00, 0xff, 0xff, 0x05, 0x08, 0x02,
   0x02, 0x24, 0x80, 0xff, 0xff, 0x03, 0x04, 0x04, 0x04, 0x18, 0xc0, 0xff,
   0xff, 0x07, 0x0a, 0x08, 0x08, 0x10, 0xe0, 0xff, 0xff, 0x0f, 0x11, 0x10,
   0x10, 0x20, 0xf0, 0xff, 0xff, 0x9f, 0x20, 0x20, 0x20, 0x40, 0xf8, 0xff,
   0xff, 0x7f, 0x40, 0x40, 0x40, 0x80, 0xfc, 0xff, 0xff, 0x7f, 0x80, 0x80,
   0x80, 0x00, 0xff, 0xff, 0xff, 0xff, 0x00, 0x01, 0x01, 0x01, 0xff, 0xff,
   0xff, 0xff, 0x01, 0x02, 0x02, 0x82, 0xff, 0xff, 0xff, 0xff, 0x03, 0x04,
   0x04, 0xc4, 0xff, 0xff, 0xff, 0xff, 0x07, 0x08, 0x08, 0xe8, 0xff, 0xff,
   0xff, 0xff, 0x0f, 0x10, 0x10, 0xf0, 0xff, 0xff, 0xff, 0xff, 0x1f, 0x20,
   0x20, 0xf8, 0xff, 0xff, 0xff, 0xff, 0x3f, 0x40, 0x60, 0xfc, 0xff, 0xff,
   0xff, 0xff, 0x7f, 0x80, 0xc0, 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
   0xc0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01, 0xc0, 0xff, 0xff, 0xff,
   0xff, 0xff, 0xff, 0x03, 0xe0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x07,
   0xe0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x0f, 0xf0, 0xff, 0xff, 0xff,
   0xff, 0xff, 0xff, 0x3f, 0xfc, 0xff, 0xff, 0xff};
static long int randnum[NUM_RANDOM];
static u_short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];

static struct {
  u_char x;
  u_char y;
  u_char dir;
} move_list[MOVE_LIST_SIZE], save_path[MOVE_LIST_SIZE], path[MOVE_LIST_SIZE];

static int maze_size_x, maze_size_y;
static int sqnum, cur_sq_x, cur_sq_y, path_length;
static int start_x, start_y, start_dir, end_x, end_y, end_dir;
static int maze_restart_flag, random_index;

Display	*dpy;
Window	win;
Window	iwin;
GC	gc, cgc;
XWindowAttributes win_attr;
int	screen;
char	*defgeo = "=500x500+10+10" ;
long	background;
Pixmap	logo_map;
int	reverse = 0;

int	width = DEF_W, height = DEF_H ;
int	x = 10, y = 10, restart = 0, stop = 1, state = 1;


main(argc,argv)                                               /* main module */
     int argc;
     char **argv;
{
  extern int	optind;
  extern char	*optarg;
  char	*display = NULL;
  char	*geo = NULL;
  char	*cmd;
  char	c;
  extern char	*getenv();
  int	screen_saver = 0;
  Pixmap	backmap, bdrmap;
  XSizeHints size_hints;
  XWindowAttributes	wind_info;

  cmd = argv[0];
  while ((c = getopt(argc, argv, "rSd:g:")) != EOF)
    switch(c)	{
      
    case 'S':
      screen_saver = 1;
      break;
    case 'd':
      display = optarg;
      break;
    case 'g':
      geo = optarg;
      break;
    case 'r':
      reverse = 1;
      break;
    case '?':
      usage(cmd);
      exit(0);
    }
  
  if ((dpy = XOpenDisplay(display)) == NULL)	{
    fprintf(stderr, "Can\'t open display: %s\n",
	    (display ? display : getenv("DISPLAY")));
    exit(0);
  }
  screen = DefaultScreen(dpy);
  
  if (screen_saver)	{
    width = DisplayWidth(dpy, screen) - 2 * BORDERWIDTH;
    height = DisplayHeight(dpy, screen) - 2 * BORDERWIDTH;
    x = 0; y = 0;
  }
  else	{
    int flags;
    
    if (geo == NULL)
      geo = defgeo;
    flags = XParseGeometry(geo, &x, &y, &width, &height); 
    if ((flags & XValue) && (flags & XNegative))
      x += DisplayWidth(dpy, screen) - width;
    if ((flags & YValue) && (flags & YNegative))
      y += DisplayHeight(dpy, screen) - height;
  }

  if (reverse)
    background = BlackPixel(dpy, screen) ;
  else
    background = WhitePixel(dpy, screen) ;

  win = XCreateSimpleWindow(dpy, RootWindow(dpy, screen), x, y, width,
			    height, BORDERWIDTH, 1, background );
  
  set_maze_sizes(width, height);
  XSelectInput(dpy, win,
	       ExposureMask | ButtonPressMask | StructureNotifyMask );
  
  gc = XCreateGC(dpy, win, 0, 0);
  cgc = XCreateGC(dpy, win, 0, 0);
  
  if (reverse)	{
      XSetForeground(dpy, gc, WhitePixel(dpy, screen));
      XSetBackground(dpy, gc, BlackPixel(dpy, screen));
      XSetForeground(dpy, cgc, BlackPixel(dpy, screen)); 
      XSetBackground(dpy, cgc, WhitePixel(dpy, screen)); 
      XSetWindowBackground(dpy, win, BlackPixel(dpy, screen));
  }
  else {
      XSetForeground(dpy, gc, BlackPixel(dpy, screen));
      XSetBackground(dpy, gc, WhitePixel(dpy, screen));
      XSetForeground(dpy, cgc, WhitePixel(dpy, screen)); 
      XSetBackground(dpy, cgc, BlackPixel(dpy, screen)); 
      XSetWindowBackground(dpy, win, WhitePixel(dpy, screen)); 
    }
  
  if  (!(logo_map = XCreateBitmapFromData(dpy, win, logo_bits,
					  logo_width, logo_height))) {
    fprintf(stderr, "Can't create logo pixmap\n");
    exit (1);
  }
  size_hints.flags =  USPosition | USSize | PMinSize ;
  size_hints.x = x;
  size_hints.y = y;
  size_hints.width = width;
  size_hints.height = height;
  size_hints.min_width = MIN_W;
  size_hints.min_height = MIN_H;
  
  XSetStandardProperties(dpy, win, "Xmaze", "Xmaze", logo_map,
			 argv, argc, &size_hints);
  XMapWindow(dpy, win);
  srandom(getpid());

  while (1) {                            /* primary execution loop [ rhess ] */
    if (check_events()) continue ;
    if (restart || stop) goto pop;
    switch (state) {
    case 1:
      initialize_maze();
      break;
    case 2:
      XClearWindow(dpy, win);
      draw_maze_border();
      break;
    case 3:
      create_maze();
      break;
    case 4:
      XFlush(dpy);
      sleep(2);
      break;
    case 5:
      solve_maze();
      break;
    default:
      XFlush(dpy) ;
      sleep(4) ;
      state = 0 ;
      break;
    }
    state = ++state ;
  pop:
    if (restart) {
      restart = 0 ;
      stop = 0 ;
      state = 1 ;
      XGetWindowAttributes(dpy, win, &win_attr);
      width = win_attr.width ;
      height = win_attr.height ;
      set_maze_sizes(width, height);
      XClearWindow(dpy, win);
      XFlush(dpy) ;
    }
  }
}


check_events()                                  /* X event handler [ rhess ] */
{
  XEvent	e;

  while (XPending(dpy))	{
    XNextEvent(dpy, &e);
    switch (e.type) {
    case ButtonPress:
      switch (e.xbutton.button) {
      case 3:
	XFreeGC(dpy, gc);
	XFreeGC(dpy, cgc);
	XDestroyWindow(dpy, win);
	XCloseDisplay(dpy);
	exit(0);
	break;
      case 2:
	stop = !stop ;
	if (state == 5) state = 4 ;
	else {
	  restart = 1;
	  stop = 0;
	}
	break;
      default:
	restart = 1 ;
	stop = 0 ;
	break;
      }
      break;
    case ConfigureNotify:
      restart = 1;
      break;
    case UnmapNotify:
      stop = 1;
      XClearWindow(dpy, win);
      XFlush(dpy);
      break;
    case Expose:
      restart = 1;
      break;
    }
    return(1);
  }
  return(0);
}	  


usage(cmd)
     char	*cmd;
{
  fprintf(stderr, "usage: %s -S -r [-g geometry] [-d display]\n", cmd);
}


set_maze_sizes(width, height)
{
  maze_size_x = width / SQ_SIZE_X;
  maze_size_y = height / SQ_SIZE_Y;
  
}


initialize_maze()         /* draw the surrounding wall and start/end squares */
{
  register int i, j, wall;
  
  /* initialize all squares */
  for ( i=0; i<maze_size_x; i++) {
    for ( j=0; j<maze_size_y; j++) {
      maze[i][j] = 0;
    }
  }
  
  /* top wall */
  for ( i=0; i<maze_size_x; i++ ) {
    maze[i][0] |= WALL_TOP;
  }
  
  /* right wall */
  for ( j=0; j<maze_size_y; j++ ) {
    maze[maze_size_x-1][j] |= WALL_RIGHT;
  }
  
  /* bottom wall */
  for ( i=0; i<maze_size_x; i++ ) {