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