maze.c

数据挖掘中de一个算法 hamster的实例

  col = maze->map;              /* traverse column vector */
  for (x = maze->xext; --x >= 0; ) {
    dst = *col++;               /* traverse columns */
    for (y = maze->yext; --y >= 0; dst++, cnt--) {
      if (total < maxcnt)       /* if less than 'maxcnt' items left, */
        maxcnt = (int)total;    /* reduce upper limit to 'total' */
      idx    = total -(cnt-1) *maxcnt;  /* compute lower limit on the */
      mincnt = (idx < 1) ? 1 : (int)idx; /* number of items per field */
      if (!randfn               /* if no random number function given */
      ||  (mincnt >= maxcnt))   /* or number of items is fixed, */
        i = maxcnt;             /* choose maximal number of items */
      else {                    /* if number of items is variable */
        i = (int)(mincnt +randfn() *(maxcnt-mincnt+1));
        if (i < mincnt) i = mincnt;
        if (i > maxcnt) i = maxcnt;
      }                         /* choose number of items randomly */
      *dst   = (*dst & MZ_WALLS) | i;
      total -= i;               /* place 'i' items on the field */
    }                           /* and reduce total number of items */
  }                             /* by the same amount */
    
  /* --- shuffle item counters of fields --- */
  if (randfn) {                 /* if random number function given */
    i   = 1;                    /* set first field flag */
    cnt = maze->xext *maze->yext;     /* compute number of fields */
    col = maze->map +maze->xext;      /* traverse column vector */
    for (x = maze->xext; --x >= 0; ) {
      dst = (*--col) +maze->yext;     /* traverse columns */
      for (y = maze->yext; --y >= 0; cnt--) {
        if (i) {                      /* if this is the first field, */
          dst--; i = 0; continue; }   /* skip start position buffer */
        idx = (int)(randfn() *cnt);   /* choose random field index */
        if ((idx < 0) || (idx >= cnt)) idx = 0;
        src = maze->map[idx /maze->yext] +(idx %maze->yext);
        dir  = *--dst & MZ_ITEMS;
        *dst = (*dst & ~MZ_ITEMS) | (*src & MZ_ITEMS);
        *src = (*src & ~MZ_ITEMS) | ( dir & MZ_ITEMS);
      }                         /* exchange the item counters */
    }                           /* of the randomly chosen field */
  }                             /* and the current field */

  /* --- choose start position --- */
  if (!randfn)                  /* if no random number function given, */
    maze->xpos = maze->ypos = 0;/* start from south west corner */
  else {                        /* if random number function given */
    maze->xpos = (int)(randfn() *maze->xext);
    if ((maze->xpos < 0) || (maze->xpos >= maze->xext))
      maze->xpos = 0;           /* choose random x-coordinate */
    maze->ypos = (int)(randfn() *maze->yext);
    if ((maze->xpos < 0) || (maze->ypos >= maze->yext))
      maze->ypos = 0;           /* choose random y-coordinate */
  }                             /* of the start position */
  src = maze->map[maze->xext-1] +(maze->yext-1);
  dst = maze->map[maze->xpos]   + maze->ypos;
  *src |= (*dst &  MZ_ITEMS);   /* clear and mark start position */
  *dst  = (*dst & ~MZ_ITEMS) | MZ_HOME;
}  /* mz_init() */

/*--------------------------------------------------------------------*/

void mz_setpos (MAZE *maze, int x, int y)
{                               /* --- set start position */
  short ox, oy;                 /* coordinates of old start position */
  short tmp;                    /* temporary buffer */
  
  ox = maze->xpos; oy = maze->ypos;
  if ((ox >= 0) && (oy >= 0))   /* if old position was valid, */
    maze->map[ox][oy] &= ~MZ_HOME;   /* clear home flag */
  if ((x < 0) || (x >= maze->xext)   /* if new position */
  ||  (y < 0) || (y >= maze->yext))  /* is invalid, */
    maze->xpos = maze->ypos = -1;    /* clear coordinates */
  else {                        /* if new position is valid */
    maze->xpos = x; maze->ypos = y;  /* note coordinates and */
    tmp = maze->map[x][y];           /* clear counter, set home flag */
    maze->map[x][y] = (tmp & ~MZ_ITEMS) | MZ_HOME;
    if ((ox >= 0) && (oy >= 0)) /* if old position was valid */
      maze->map[ox][oy] |= tmp & MZ_ITEMS;
  }                             /* transfer items to old field */
}  /* mz_setpos() */

/*--------------------------------------------------------------------*/

short mz_getfld (MAZE *maze, int x, int y)
{                               /* --- get field contents */
  if ((x < 0) || (x >= maze->xext)
  ||  (y < 0) || (y >= maze->yext))
    return 0;                   /* if field is not in maze, abort */
  return maze->map[x][y];       /* return field contents */
}  /* mz_getfld() */

/*--------------------------------------------------------------------*/

short mz_setfld (MAZE *maze, int x, int y, short mask, short cont)
{                               /* --- set field contents */
  short *fld;                   /* maze field to change */
  short chgd;                   /* changed walls */

  if ((x < 0) || (x >= maze->xext)
  ||  (y < 0) || (y >= maze->yext))
    return 0;                   /* if field is not in maze, abort */
  fld = maze->map[x] +y;        /* get maze field to change */
  chgd = (*fld ^ cont) & mask;  /* get change and set new contents */
  *fld = (*fld & ~mask) | (cont & mask);
  if (!(chgd & MZ_WALLS))       /* if no walls were changed, */
    return *fld;                /* abort function */
  if      (x >= maze->xext-1) *fld              |= MZ_EAST;
  else if (chgd & MZ_EAST)    maze->map[x+1][y] ^= MZ_WEST;
  if      (x <= 0)            *fld              |= MZ_WEST;
  else if (chgd & MZ_WEST)    maze->map[x-1][y] ^= MZ_EAST;
  if      (y >= maze->yext-1) *fld              |= MZ_NORTH;
  else if (chgd & MZ_NORTH)   maze->map[x][y+1] ^= MZ_SOUTH;
  if      (y <= 0)            *fld              |= MZ_SOUTH;
  else if (chgd & MZ_SOUTH)   maze->map[x][y-1] ^= MZ_NORTH;
  return *fld;                  /* update wall flags */
}  /* mz_setfld() */

/*--------------------------------------------------------------------*/

int mz_save (MAZE *maze, FILE *file)
{                               /* --- save a maze */
  int   x, y;                   /* loop variables */
  short **col;                  /* to traverse column vector */

  fprintf(file, "%i %i ",  maze->xext, maze->yext);
  fprintf(file, "%i %i\n", maze->xpos, maze->ypos);
  for (y = maze->yext; --y >= 0; ) { /* traverse rows */
    col = maze->map;            /* traverse columns */
    for (x = maze->xext; --x > 0; col++)
      fprintf(file, "%04hx ", (*col)[y]);
    fprintf(file, "%04hx\n", (*col)[y]);
  }                             /* print field contents */
  return ferror(file) ? -1 : 0; /* return error status */
}  /* mz_save() */

/*--------------------------------------------------------------------*/

MAZE* mz_load (FILE *file)
{                               /* --- load a maze */
  MAZE  *maze;                  /* loaded maze */
  int   x, y, sx, sy;           /* loop variables, buffers */
  short **col;                  /* to traverse column vector */
  
  if ((fscanf(file, "%i %i ",  &x,  &y)  != 2)
  ||  (fscanf(file, "%i %i\n", &sx, &sy) != 2))
    return NULL;                /* read maze extensions and */
  maze = mz_create(x, y);       /* start position coordinates */
  if (!maze) return NULL;       /* create a maze */
  maze->xpos = sx; maze->ypos = sy;
  for (y = maze->yext; --y >= 0; ) { /* traverse rows */
    col = maze->map;            /* traverse columns */
    for (x = maze->xext; --x >= 0; col++) {
      if (fscanf(file, "%04hx", (*col)+y) != 1) {
        mz_delete(maze); return NULL; }
    }                           /* read maze field contents */
  }                             /* and store it */
  return maze;                  /* return loaded maze */
}  /* mz_load() */