maze.c

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

/*----------------------------------------------------------------------
  File    : maze.c
  Contents: maze management
  Author  : Christian Borgelt
  History : 14.10.1997 file created
            15.10.1997 first version completed
            31.10.1997 minor improvements
            02.11.1997 use of wall probability corrected
            04.01.1997 bug in maze initialization removed
----------------------------------------------------------------------*/
#include <stdlib.h>
#include "maze.h"

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define DIRMASK  0x03           /* mask for directions */
#define VISITED  0x04           /* flag for 'field visited' */

/*----------------------------------------------------------------------
  Type Definitions
----------------------------------------------------------------------*/
typedef struct {                /* --- direction information --- */
  short dx, dy;                 /* field offsets */
  short wall;                   /* corresponding wall flag */
  short opp;                    /* opposite direction */
} DIRINFO;                      /* (direction information) */

/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
static const DIRINFO dinfo[] = {/* direction information */
  {  1,  0, MZ_EAST,  2 },      /* 0: east,  opposite is 2: west  */
  {  0,  1, MZ_NORTH, 3 },      /* 1: north, opposite is 3: south */
  { -1,  0, MZ_WEST,  0 },      /* 2: west,  opposite is 0: east  */
  {  0, -1, MZ_SOUTH, 1 } };    /* 3: south, opposite is 1: north */

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/

MAZE* mz_create (int xext, int yext)
{                               /* --- create a maze */
  MAZE  *maze;                  /* created maze */
  int   x;                      /* loop variable */
  short **col;                  /* to traverse column vector */

  if (xext <= 0) xext = 1;      /* check maze extensions */
  if (yext <= 0) yext = 1;      /* (both must be at least one) */
  maze = (MAZE*)calloc(1, sizeof(MAZE) +(xext-1) *sizeof(short*));
  if (!maze) return NULL;       /* allocate maze body */
  maze->xext = xext;            /* and initialize fields */
  maze->yext = yext;
  maze->xpos = maze->ypos = -1; /* clear start position */
  col = maze->map;              /* traverse column vector */
  for (x = xext; --x >= 0; col++) {
    *col = (short*)malloc(yext *sizeof(short));
    if (!*col) { mz_delete(maze); return NULL; }
  }                             /* allocate maze columns */
  mz_init(maze, 0, 0.0F, 0, 0); /* and initialize maze */
  return maze;                  /* return created maze */
}  /* mz_create() */

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

void mz_delete (MAZE *maze)
{                               /* --- delete a maze */
  int   x;                      /* loop variable */
  short **col;                  /* to traverse column vector */

  col = maze->map;              /* traverse maze columns */
  for (x = maze->xext; --x >= 0; col++)
    if (*col) free(*col);       /* delete maze columns */
  free(maze);                   /* and maze body */
}  /* mz_delete() */

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

void mz_init (MAZE *maze, double (*randfn)(void),
              float wallprob, int total, int maxcnt)
{                               /* --- initialize a maze */
  short i;                      /* loop variable, buffer */
  int   x, y;                   /* loop variables, field indices */
  short **col;                  /* to traverse column vector */
  short *src, *dst;             /* to traverse columns, buffers */
  int   plen, idx;              /* length of path, field index */
  short dir;                    /* current direction */
  short cand[4];                /* direction candidates */
  short build;                  /* whether to build walls */
  int   cnt;                    /* number of candidates/fields  */
  short mincnt;                 /* minimal number of items per field */
  const DIRINFO *cdi;           /* current direction information */

  /* --- clear maze --- */
  for (col = maze->map, x = maze->xext; --x >= 0; )
    for (src = *col++, y = maze->yext; --y >= 0; )
      *src++ = 0;               /* clear all fields of the maze */
  col = maze->map;              /* traverse column vector */
  src = col[0];                 /* traverse first */
  dst = col[maze->xext-1];      /* and last column */
  for (y = maze->yext; --y >= 0; ) {
    *dst++ |= MZ_EAST; *src++ |= MZ_WEST;
  }                             /* set east and west border */
  i = maze->yext-1;             /* get index of northest row */
  for (x = maze->xext; --x >= 0; col++) {
    (*col)[i] |= MZ_NORTH; (*col)[0] |= MZ_SOUTH;
  }                             /* set north and south border */

  /* --- randomly place walls --- */
  if (randfn && (wallprob > 0.0)) {
    x   = (maze->xext -1) >> 1; /* compute coordinates */
    y   = (maze->yext -1) >> 1; /* of center field and */
    src = maze->map[x] +y;      /* initialize its direction */
    *src |= ((short)(randfn() *4) & DIRMASK) | VISITED;
    plen = 1; build = 0;        /* path contains the center */
    while (plen > 0) {          /* while path is not empty */
      cnt = 0;                  /* clear candidate counter */
      dir = *src & DIRMASK;     /* get direction to current field */
      for (i = 3; --i >= 0; ) { /* traverse remaining directions */
        dir = (dir +1) & DIRMASK;      /* compute next direction */
        cdi = dinfo +dir;       /* and get direction information */
        if (*src & cdi->wall)   /* if direction is blocked, */
          continue;             /* skip this direction */
        dst = maze->map[x +cdi->dx] +(y +cdi->dy);
        if (!(*dst & VISITED))  /* if field has not been visited, */
          cand[cnt++] = dir;    /* note direction candidate */
        else if (build          /* otherwise build a wall randomly */
        &&       ((*dst & DIRMASK) != cdi->opp)
        &&       (randfn() <= wallprob)) {
          *src |= cdi->wall;    /* build wall on current field */
          *dst |= dinfo[cdi->opp].wall;
        }                       /* build wall on destination field */
      }                         /* (for consistency) */
      if (cnt <= 0) {           /* if no candidates found, */
        dir = *src & DIRMASK;   /* get direction by which */
        x += dinfo[dir].dx;     /* current field was entered */
        y += dinfo[dir].dy;     /* and offsets to previous field */
        src = maze->map[x] +y;  /* retrace step (go back on path) */
        plen--; build = 0; }    /* reduce path length, clear flag */
      else {                    /* if at least one candidate found, */
        dir = (short)(randfn() *cnt);
        dir = cand[(dir >= cnt) ? cnt-1 : dir];
        x += dinfo[dir].dx;     /* choose direction to move in, */
        y += dinfo[dir].dy;     /* get offsets to new field */
        src = maze->map[x] +y;  /* and move to new field */
        *src |= dinfo[dir].opp | VISITED;
        plen++; build = 1;      /* note direction from which */
      }                         /* field was entered and */
    }                           /* increase path length */
  }  /* if (randfn && (wallprob > 0.0)) */
  
  /* --- clear markers and place items --- */
  if (maxcnt > MZ_ITEMS)        /* at most MZ_ITEMS items */
    maxcnt = MZ_ITEMS;          /* can be placed on one field */
  cnt = (int)maze->xext *maze->yext -1;
  if (total > cnt *maxcnt)      /* check total number of items */
    total = cnt *maxcnt;        /* against the maze capacity */
  if (!randfn)                  /* compute average number of items */
    maxcnt = (cnt <= 0) ? 0 : (int)(total /cnt +((total %cnt) ? 1 : 0));