Home | History | Annotate | Line # | Download | only in huntd
makemaze.c revision 1.1 
      1 /*
      2  *  Hunt
      3  *  Copyright (c) 1985 Conrad C. Huang, Gregory S. Couch, Kenneth C.R.C. Arnold
      4  *  San Francisco, California
      5  */
      6 
      7 # include	"hunt.h"
      8 
      9 # define	ISCLEAR(y,x)	(Maze[y][x] == SPACE)
     10 # define	ODD(n)		((n) & 01)
     11 
     12 makemaze()
     13 {
     14 	register char	*sp;
     15 	register int	y, x;
     16 
     17 	/*
     18 	 * fill maze with walls
     19 	 */
     20 	sp = &Maze[0][0];
     21 	while (sp < &Maze[HEIGHT - 1][WIDTH])
     22 		*sp++ = DOOR;
     23 
     24 	x = rand_num(WIDTH / 2) * 2 + 1;
     25 	y = rand_num(HEIGHT / 2) * 2 + 1;
     26 	dig_maze(x, y);
     27 	remap();
     28 }
     29 
     30 # define	NPERM	24
     31 # define	NDIR	4
     32 
     33 int	dirs[NPERM][NDIR] = {
     34 		{0,1,2,3},	{3,0,1,2},	{0,2,3,1},	{0,3,2,1},
     35 		{1,0,2,3},	{2,3,0,1},	{0,2,1,3},	{2,3,1,0},
     36 		{1,0,3,2},	{1,2,0,3},	{3,1,2,0},	{2,0,3,1},
     37 		{1,3,0,2},	{0,3,1,2},	{1,3,2,0},	{2,0,1,3},
     38 		{0,1,3,2},	{3,1,0,2},	{2,1,0,3},	{1,2,3,0},
     39 		{2,1,3,0},	{3,0,2,1},	{3,2,0,1},	{3,2,1,0}
     40 	};
     41 
     42 int	incr[NDIR][2] = {
     43 		{0, 1}, {1, 0}, {0, -1}, {-1, 0}
     44 	};
     45 
     46 dig(y, x)
     47 int	y, x;
     48 {
     49 	register int	*dp;
     50 	register int	*ip;
     51 	register int	ny, nx;
     52 	register int	*endp;
     53 
     54 	Maze[y][x] = SPACE;			/* Clear this spot */
     55 	dp = dirs[rand_num(NPERM)];
     56 	endp = &dp[NDIR];
     57 	while (dp < endp) {
     58 		ip = &incr[*dp++][0];
     59 		ny = y + *ip++;
     60 		nx = x + *ip;
     61 		if (candig(ny, nx))
     62 			dig(ny, nx);
     63 	}
     64 }
     65 
     66 /*
     67  * candig:
     68  *	Is it legal to clear this spot?
     69  */
     70 candig(y, x)
     71 register int	y, x;
     72 {
     73 	register int	i;
     74 
     75 	if (ODD(x) && ODD(y))
     76 		return FALSE;		/* can't touch ODD spots */
     77 
     78 	if (y < UBOUND || y >= DBOUND)
     79 		return FALSE;		/* Beyond vertical bounds, NO */
     80 	if (x < LBOUND || x >= RBOUND)
     81 		return FALSE;		/* Beyond horizontal bounds, NO */
     82 
     83 	if (ISCLEAR(y, x))
     84 		return FALSE;		/* Already clear, NO */
     85 
     86 	i = ISCLEAR(y, x + 1);
     87 	i += ISCLEAR(y, x - 1);
     88 	if (i > 1)
     89 		return FALSE;		/* Introduces cycle, NO */
     90 	i += ISCLEAR(y + 1, x);
     91 	if (i > 1)
     92 		return FALSE;		/* Introduces cycle, NO */
     93 	i += ISCLEAR(y - 1, x);
     94 	if (i > 1)
     95 		return FALSE;		/* Introduces cycle, NO */
     96 
     97 	return TRUE;			/* OK */
     98 }
     99 
    100 dig_maze(x, y)
    101 int	x, y;
    102 {
    103 	register int	tx, ty;
    104 	register int	i, j;
    105 	int		order[4];
    106 #define	MNORTH	0x1
    107 #define	MSOUTH	0x2
    108 #define	MEAST	0x4
    109 #define	MWEST	0x8
    110 
    111 	Maze[y][x] = SPACE;
    112 	order[0] = MNORTH;
    113 	for (i = 1; i < 4; i++) {
    114 		j = rand_num(i + 1);
    115 		order[i] = order[j];
    116 		order[j] = 0x1 << i;
    117 	}
    118 	for (i = 0; i < 4; i++) {
    119 		switch (order[i]) {
    120 		  case MNORTH:
    121 			tx = x;
    122 			ty = y - 2;
    123 			break;
    124 		  case MSOUTH:
    125 			tx = x;
    126 			ty = y + 2;
    127 			break;
    128 		  case MEAST:
    129 			tx = x + 2;
    130 			ty = y;
    131 			break;
    132 		  case MWEST:
    133 			tx = x - 2;
    134 			ty = y;
    135 			break;
    136 		}
    137 		if (tx < 0 || ty < 0 || tx >= WIDTH || ty >= HEIGHT)
    138 			continue;
    139 		if (Maze[ty][tx] == SPACE)
    140 			continue;
    141 		Maze[(y + ty) / 2][(x + tx) / 2] = SPACE;
    142 		dig_maze(tx, ty);
    143 	}
    144 }
    145 
    146 remap()
    147 {
    148 	register int	y, x;
    149 	register char	*sp;
    150 	register int	stat;
    151 
    152 	for (y = 0; y < HEIGHT; y++)
    153 		for (x = 0; x < WIDTH; x++) {
    154 			sp = &Maze[y][x];
    155 			if (*sp == SPACE)
    156 				continue;
    157 			stat = 0;
    158 			if (y - 1 >= 0 && Maze[y - 1][x] != SPACE)
    159 				stat |= NORTH;
    160 			if (y + 1 < HEIGHT && Maze[y + 1][x] != SPACE)
    161 				stat |= SOUTH;
    162 			if (x + 1 < WIDTH && Maze[y][x + 1] != SPACE)
    163 				stat |= EAST;
    164 			if (x - 1 >= 0 && Maze[y][x - 1] != SPACE)
    165 				stat |= WEST;
    166 			switch (stat) {
    167 			  case WEST | EAST:
    168 			  case EAST:
    169 			  case WEST:
    170 				*sp = WALL1;
    171 				break;
    172 			  case NORTH | SOUTH:
    173 			  case NORTH:
    174 			  case SOUTH:
    175 				*sp = WALL2;
    176 				break;
    177 			  case 0:
    178 # ifdef RANDOM
    179 				*sp = DOOR;
    180 # endif
    181 # ifdef REFLECT
    182 				*sp = rand_num(2) ? WALL4 : WALL5;
    183 # endif
    184 				break;
    185 			  default:
    186 				*sp = WALL3;
    187 				break;
    188 			}
    189 		}
    190 	memcpy(Orig_maze, Maze, sizeof Maze);
    191 }
    192