x_maze.c

X Windows下的迷宫程序

    maze[i][maze_size_y-1] |= WALL_BOTTOM;
  }
  
  /* left wall */
  for ( j=0; j<maze_size_y; j++ ) {
    maze[0][j] |= WALL_LEFT;
  }
  
  /* set start square */
  wall = get_random(4);
  switch (wall) {
  case 0:	
    i = get_random(maze_size_x);
    j = 0;
    break;
  case 1:	
    i = maze_size_x - 1;
    j = get_random(maze_size_y);
    break;
  case 2:	
    i = get_random(maze_size_x);
    j = maze_size_y - 1;
    break;
  case 3:	
    i = 0;
    j = get_random(maze_size_y);
    break;
  }
  maze[i][j] |= START_SQUARE;
  maze[i][j] |= ( DOOR_IN_TOP >> wall );
  maze[i][j] &= ~( WALL_TOP >> wall );
  cur_sq_x = i;
  cur_sq_y = j;
  start_x = i;
  start_y = j;
  start_dir = wall;
  sqnum = 0;
  
  /* set end square */
  wall = (wall + 2)%4;
  switch (wall) {
  case 0:
    i = get_random(maze_size_x);
    j = 0;
    break;
  case 1:
    i = maze_size_x - 1;
    j = get_random(maze_size_y);
    break;
  case 2:
    i = get_random(maze_size_x);
    j = maze_size_y - 1;
    break;
  case 3:
    i = 0;
    j = get_random(maze_size_y);
    break;
  }
  maze[i][j] |= END_SQUARE;
  maze[i][j] |= ( DOOR_OUT_TOP >> wall );
  maze[i][j] &= ~( WALL_TOP >> wall );
  end_x = i;
  end_y = j;
  end_dir = wall;
  
  /* set logo */
  if ( (maze_size_x > 15) && (maze_size_y > 15) ) {
    logo_x = get_random(maze_size_x - LOGOSIZE - 6) + 3;
    logo_y = get_random(maze_size_y - LOGOSIZE - 6) + 3;
    
    for (i=0; i<LOGOSIZE; i++) {
      for (j=0; j<LOGOSIZE; j++) {
	maze[logo_x + i][logo_y + j] |= DOOR_IN_TOP;
      }
    }
  }
  else
    logo_y = logo_x = -1;
}


create_maze()             /* create a maze layout given the intiialized maze */
{
  register int i, newdoor;
  
  do {
    move_list[sqnum].x = cur_sq_x;
    move_list[sqnum].y = cur_sq_y;
    move_list[sqnum].dir = newdoor;
    while ( ( newdoor = choose_door() ) == -1 ) { /* pick a door */
      if ( backup() == -1 ) { /* no more doors ... backup */
	return; /* done ... return */
      }
    }
    
    /* mark the out door */
    maze[cur_sq_x][cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
    
    switch (newdoor) {
    case 0: cur_sq_y--;
      break;
    case 1: cur_sq_x++;
      break;
    case 2: cur_sq_y++;
      break;
    case 3: cur_sq_x--;
      break;
    }
    sqnum++;
    
    /* mark the in door */
    maze[cur_sq_x][cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
    
    /* if end square set path length and save path */
    if ( maze[cur_sq_x][cur_sq_y] & END_SQUARE ) {
      path_length = sqnum;
      for ( i=0; i<path_length; i++) {
	save_path[i].x = move_list[i].x;
	save_path[i].y = move_list[i].y;
	save_path[i].dir = move_list[i].dir;
      }
    }
    
  } while (1);
  
}


choose_door()                                            /* pick a new path */
{
  int candidates[3];
  register int num_candidates;
  
  num_candidates = 0;
  
 topwall:
  /* top wall */
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_TOP )
    goto rightwall;
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_TOP )
    goto rightwall;
  if ( maze[cur_sq_x][cur_sq_y] & WALL_TOP )
    goto rightwall;
  if ( maze[cur_sq_x][cur_sq_y - 1] & DOOR_IN_ANY ) {
    maze[cur_sq_x][cur_sq_y] |= WALL_TOP;
    maze[cur_sq_x][cur_sq_y - 1] |= WALL_BOTTOM;
    draw_wall(cur_sq_x, cur_sq_y, 0);
    goto rightwall;
  }
  candidates[num_candidates++] = 0;
  
 rightwall:
  /* right wall */
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_RIGHT )
    goto bottomwall;
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_RIGHT )
    goto bottomwall;
  if ( maze[cur_sq_x][cur_sq_y] & WALL_RIGHT )
    goto bottomwall;
  if ( maze[cur_sq_x + 1][cur_sq_y] & DOOR_IN_ANY ) {
    maze[cur_sq_x][cur_sq_y] |= WALL_RIGHT;
    maze[cur_sq_x + 1][cur_sq_y] |= WALL_LEFT;
    draw_wall(cur_sq_x, cur_sq_y, 1);
    goto bottomwall;
  }
  candidates[num_candidates++] = 1;
  
 bottomwall:
  /* bottom wall */
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_BOTTOM )
    goto leftwall;
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_BOTTOM )
    goto leftwall;
  if ( maze[cur_sq_x][cur_sq_y] & WALL_BOTTOM )
    goto leftwall;
  if ( maze[cur_sq_x][cur_sq_y + 1] & DOOR_IN_ANY ) {
    maze[cur_sq_x][cur_sq_y] |= WALL_BOTTOM;
    maze[cur_sq_x][cur_sq_y + 1] |= WALL_TOP;
    draw_wall(cur_sq_x, cur_sq_y, 2);
    goto leftwall;
  }
  candidates[num_candidates++] = 2;
  
 leftwall:
  /* left wall */
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_LEFT )
    goto donewall;
  if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_LEFT )
    goto donewall;
  if ( maze[cur_sq_x][cur_sq_y] & WALL_LEFT )
    goto donewall;
  if ( maze[cur_sq_x - 1][cur_sq_y] & DOOR_IN_ANY ) {
    maze[cur_sq_x][cur_sq_y] |= WALL_LEFT;
    maze[cur_sq_x - 1][cur_sq_y] |= WALL_RIGHT;
    draw_wall(cur_sq_x, cur_sq_y, 3);
    goto donewall;
  }
  candidates[num_candidates++] = 3;
  
 donewall:
  if (num_candidates == 0)
    return ( -1 );
  if (num_candidates == 1)
    return ( candidates[0] );
  return ( candidates[ get_random(num_candidates) ] );
  
}


backup()                                                  /* back up a move */
{
  sqnum--;
  cur_sq_x = move_list[sqnum].x;
  cur_sq_y = move_list[sqnum].y;
  return ( sqnum );
}


draw_maze_border()                                  /* draw the maze outline */
{
  register int i, j;
  
  
  for ( i=0; i<maze_size_x; i++) {
    if ( maze[i][0] & WALL_TOP ) {
      XDrawLine(dpy, win, gc,
		border_x + SQ_SIZE_X * i,
		border_y,
		border_x + SQ_SIZE_X * (i+1),
		border_y);
    }
    if ((maze[i][maze_size_y - 1] & WALL_BOTTOM)) {
      XDrawLine(dpy, win, gc,
		border_x + SQ_SIZE_X * i,
		border_y + SQ_SIZE_Y * (maze_size_y),
		border_x + SQ_SIZE_X * (i+1),
		border_y + SQ_SIZE_Y * (maze_size_y));
    }
  }
  for ( j=0; j<maze_size_y; j++) {
    if ( maze[maze_size_x - 1][j] & WALL_RIGHT ) {
      XDrawLine(dpy, win, gc,
		border_x + SQ_SIZE_X * maze_size_x,
		border_y + SQ_SIZE_Y * j,
		border_x + SQ_SIZE_X * maze_size_x,
		border_y + SQ_SIZE_Y * (j+1));
    }
    if ( maze[0][j] & WALL_LEFT ) {
      XDrawLine(dpy, win, gc,
		border_x,
		border_y + SQ_SIZE_Y * j,
		border_x,
		border_y + SQ_SIZE_Y * (j+1));
    }
  }
  
  if (logo_x != -1) {
    XCopyPlane(dpy, logo_map, win, gc,
	       0, 0, logo_width, logo_height,
	       border_x + 3 + SQ_SIZE_X * logo_x,
	       border_y + 3 + SQ_SIZE_Y * logo_y, 1);
  }
  
  draw_solid_square( start_x, start_y, start_dir, gc);
  draw_solid_square( end_x, end_y, end_dir, gc);
}


draw_wall(i, j, dir)                                   /* draw a single wall */
     int i, j, dir;
{
  switch (dir) {
  case 0:
    XDrawLine(dpy, win, gc,
	      border_x + SQ_SIZE_X * i, 
	      border_y + SQ_SIZE_Y * j,
	      border_x + SQ_SIZE_X * (i+1), 
	      border_y + SQ_SIZE_Y * j);
    break;
  case 1:
    XDrawLine(dpy, win, gc,
	      border_x + SQ_SIZE_X * (i+1), 
	      border_y + SQ_SIZE_Y * j,
	      border_x + SQ_SIZE_X * (i+1), 
	      border_y + SQ_SIZE_Y * (j+1));
    break;
  case 2:
    XDrawLine(dpy, win, gc,
	      border_x + SQ_SIZE_X * i, 
	      border_y + SQ_SIZE_Y * (j+1),
	      border_x + SQ_SIZE_X * (i+1), 
	      border_y + SQ_SIZE_Y * (j+1));
    break;
  case 3:
    XDrawLine(dpy, win, gc,
	      border_x + SQ_SIZE_X * i, 
	      border_y + SQ_SIZE_Y * j,
	      border_x + SQ_SIZE_X * i, 
	      border_y + SQ_SIZE_Y * (j+1));
    break;
  }
}


draw_solid_square(i, j, dir, gc)          /* draw a solid square in a square */
     register int i, j, dir;
     GC	gc;
{
  switch (dir) {
  case 0: XFillRectangle(dpy, win, gc,
			 border_x + 3 + SQ_SIZE_X * i, 
			 border_y - 3 + SQ_SIZE_Y * j, 
			 SQ_SIZE_X - 6, SQ_SIZE_Y);
    break;
  case 1: XFillRectangle(dpy, win, gc,
			 border_x + 3 + SQ_SIZE_X * i, 
			 border_y + 3 + SQ_SIZE_Y * j, 
			 SQ_SIZE_X, SQ_SIZE_Y - 6);
    break;
  case 2: XFillRectangle(dpy, win, gc,
			 border_x + 3 + SQ_SIZE_X * i, 
			 border_y + 3 + SQ_SIZE_Y * j, 
			 SQ_SIZE_X - 6, SQ_SIZE_Y);
    break;
  case 3: XFillRectangle(dpy, win, gc,
			 border_x - 3 + SQ_SIZE_X * i, 
			 border_y + 3 + SQ_SIZE_Y * j, 
			 SQ_SIZE_X, SQ_SIZE_Y - 6);
    break;
  }
  XFlush(dpy);
#ifdef	notdef
  (void) check_events();
#endif
}


solve_maze()                             /* solve it with graphical feedback */
{
  int i;
  
  
  /* plug up the surrounding wall */
  maze[start_x][start_y] |= (WALL_TOP >> start_dir);
  maze[end_x][end_y] |= (WALL_TOP >> end_dir);
  
  /* initialize search path */
  i = 0;
  path[i].x = end_x;
  path[i].y = end_y;
  path[i].dir = -1;
  
  /* do it */
  while (1) {
    if ( ++path[i].dir >= 4 ) {
      i--;
      draw_solid_square( (int)(path[i].x), (int)(path[i].y), 
			(int)(path[i].dir), cgc);
    }
    else if ( ! (maze[path[i].x][path[i].y] & 
		 (WALL_TOP >> path[i].dir))  && 
	     ( (i == 0) || ( (path[i].dir != 
			      (path[i-1].dir+2)%4) ) ) ) {
      enter_square(i);
      i++;
      if ( maze[path[i].x][path[i].y] & START_SQUARE ) {
	return;
      }
    } 
    if (check_events()) return;
    /* Abort solve on expose - cheapo repaint strategy */
  }
} 


enter_square(n)                            /* move into a neighboring square */
     int n;
{
  draw_solid_square( (int)path[n].x, (int)path[n].y, 
		    (int)path[n].dir, gc);
  
  path[n+1].dir = -1;
  switch (path[n].dir) {
  case 0: path[n+1].x = path[n].x;
    path[n+1].y = path[n].y - 1;
    break;
  case 1: path[n+1].x = path[n].x + 1;
    path[n+1].y = path[n].y;
    break;
  case 2: path[n+1].x = path[n].x;
    path[n+1].y = path[n].y + 1;
    break;
  case 3: path[n+1].x = path[n].x - 1;
    path[n+1].y = path[n].y;
    break;
  }
}

/* ----<eof> */