[dragonfly.git] / games / hunt / huntd / makemaze.c

/*
 * Copyright (c) 1983-2003, Regents of the University of California.
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are 
 * met:
 * 
 * + Redistributions of source code must retain the above copyright 
 *   notice, this list of conditions and the following disclaimer.
 * + Redistributions in binary form must reproduce the above copyright 
 *   notice, this list of conditions and the following disclaimer in the 
 *   documentation and/or other materials provided with the distribution.
 * + Neither the name of the University of California, San Francisco nor 
 *   the names of its contributors may be used to endorse or promote 
 *   products derived from this software without specific prior written 
 *   permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 
 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * $OpenBSD: makemaze.c,v 1.6 2003/06/11 08:45:33 pjanzen Exp $
 * $NetBSD: makemaze.c,v 1.2 1997/10/10 16:33:43 lukem Exp $
 * $DragonFly: src/games/hunt/huntd/makemaze.c,v 1.2 2008/09/04 16:12:51 swildner Exp $
 */

#include <string.h>

#include "hunt.h"
#include "server.h"
#include "conf.h"

# define	ISCLEAR(y,x)	(Maze[y][x] == SPACE)
# define	ODD(n)		((n) & 01)

static	void	dig_maze(int, int);
static	void	remap(void);

void
makemaze(void)
{
	char	*sp;
	int	y, x;

	/*
	 * fill maze with walls
	 */
	sp = &Maze[0][0];
	while (sp < &Maze[HEIGHT - 1][WIDTH])
		*sp++ = DOOR;

	x = rand_num(WIDTH / 2) * 2 + 1;
	y = rand_num(HEIGHT / 2) * 2 + 1;
	dig_maze(x, y);
	remap();
}

# define	NPERM	24
# define	NDIR	4

int	dirs[NPERM][NDIR] = {
		{0,1,2,3},	{3,0,1,2},	{0,2,3,1},	{0,3,2,1},
		{1,0,2,3},	{2,3,0,1},	{0,2,1,3},	{2,3,1,0},
		{1,0,3,2},	{1,2,0,3},	{3,1,2,0},	{2,0,3,1},
		{1,3,0,2},	{0,3,1,2},	{1,3,2,0},	{2,0,1,3},
		{0,1,3,2},	{3,1,0,2},	{2,1,0,3},	{1,2,3,0},
		{2,1,3,0},	{3,0,2,1},	{3,2,0,1},	{3,2,1,0}
	};

int	incr[NDIR][2] = {
		{0, 1}, {1, 0}, {0, -1}, {-1, 0}
	};

static void
dig_maze(int x, int y)
{
	int	tx, ty;
	int	i, j;
	int	order[4];
#define	MNORTH	0x1
#define	MSOUTH	0x2
#define	MEAST	0x4
#define	MWEST	0x8

	tx = ty = 0;
	Maze[y][x] = SPACE;
	order[0] = MNORTH;
	for (i = 1; i < 4; i++) {
		j = rand_num(i + 1);
		order[i] = order[j];
		order[j] = 0x1 << i;
	}
	for (i = 0; i < 4; i++) {
		switch (order[i]) {
		  case MNORTH:
			tx = x;
			ty = y - 2;
			break;
		  case MSOUTH:
			tx = x;
			ty = y + 2;
			break;
		  case MEAST:
			tx = x + 2;
			ty = y;
			break;
		  case MWEST:
			tx = x - 2;
			ty = y;
			break;
		}
		if (tx < 0 || ty < 0 || tx >= WIDTH || ty >= HEIGHT)
			continue;
		if (Maze[ty][tx] == SPACE)
			continue;
		Maze[(y + ty) / 2][(x + tx) / 2] = SPACE;
		dig_maze(tx, ty);
	}
}

static void
remap(void)
{
	int	y, x;
	char	*sp;
	int	stat;

	for (y = 0; y < HEIGHT; y++)
		for (x = 0; x < WIDTH; x++) {
			sp = &Maze[y][x];
			if (*sp == SPACE)
				continue;
			/* Find occupied adjacent cells. */
			stat = 0;
			if (y - 1 >= 0 && Maze[y - 1][x] != SPACE)
				stat |= NORTH;
			if (y + 1 < HEIGHT && Maze[y + 1][x] != SPACE)
				stat |= SOUTH;
			if (x + 1 < WIDTH && Maze[y][x + 1] != SPACE)
				stat |= EAST;
			if (x - 1 >= 0 && Maze[y][x - 1] != SPACE)
				stat |= WEST;
			switch (stat) {
			  case WEST | EAST:
			  case EAST:
			  case WEST:
				*sp = WALL1;			   /* - */
				break;
			  case NORTH | SOUTH:
			  case NORTH:
			  case SOUTH:
				*sp = WALL2;			   /* | */
				break;
			  case 0:
				if (conf_random)
					*sp = DOOR;
				if (conf_reflect)
					*sp = rand_num(2) ? WALL4 : WALL5;
				break;
			  default:
				*sp = WALL3;			   /* + */
				break;
			}
		}
	memcpy(Orig_maze, Maze, sizeof Orig_maze);
}
Commit	Line	Data
82a5c12e MD	1	/*
	2	* Copyright (c) 1983-2003, Regents of the University of California.
	3	* All rights reserved.
	4	*
	5	* Redistribution and use in source and binary forms, with or without
	6	* modification, are permitted provided that the following conditions are
	7	* met:
	8	*
	9	* + Redistributions of source code must retain the above copyright
	10	* notice, this list of conditions and the following disclaimer.
	11	* + Redistributions in binary form must reproduce the above copyright
	12	* notice, this list of conditions and the following disclaimer in the
	13	* documentation and/or other materials provided with the distribution.
	14	* + Neither the name of the University of California, San Francisco nor
	15	* the names of its contributors may be used to endorse or promote
	16	* products derived from this software without specific prior written
	17	* permission.
	18	*
	19	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
	20	* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
	21	* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
	22	* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	23	* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	24	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	25	* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	26	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	27	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	28	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	29	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	30	*
	31	* $OpenBSD: makemaze.c,v 1.6 2003/06/11 08:45:33 pjanzen Exp $
	32	* $NetBSD: makemaze.c,v 1.2 1997/10/10 16:33:43 lukem Exp $
6beb426b	33	* $DragonFly: src/games/hunt/huntd/makemaze.c,v 1.2 2008/09/04 16:12:51 swildner Exp $
82a5c12e MD	34	*/
	35
	36	#include <string.h>
	37
	38	#include "hunt.h"
	39	#include "server.h"
	40	#include "conf.h"
	41
	42	# define ISCLEAR(y,x) (Maze[y][x] == SPACE)
	43	# define ODD(n) ((n) & 01)
	44
82a5c12e MD	45	static void dig_maze(int, int);
	46	static void remap(void);
	47
	48	void
6beb426b	49	makemaze(void)
82a5c12e MD	50	{
	51	char *sp;
	52	int y, x;
	53
	54	/*
	55	* fill maze with walls
	56	*/
	57	sp = &Maze[0][0];
	58	while (sp < &Maze[HEIGHT - 1][WIDTH])
	59	*sp++ = DOOR;
	60
	61	x = rand_num(WIDTH / 2) * 2 + 1;
	62	y = rand_num(HEIGHT / 2) * 2 + 1;
	63	dig_maze(x, y);
	64	remap();
	65	}
	66
	67	# define NPERM 24
	68	# define NDIR 4
	69
	70	int dirs[NPERM][NDIR] = {
	71	{0,1,2,3}, {3,0,1,2}, {0,2,3,1}, {0,3,2,1},
	72	{1,0,2,3}, {2,3,0,1}, {0,2,1,3}, {2,3,1,0},
	73	{1,0,3,2}, {1,2,0,3}, {3,1,2,0}, {2,0,3,1},
	74	{1,3,0,2}, {0,3,1,2}, {1,3,2,0}, {2,0,1,3},
	75	{0,1,3,2}, {3,1,0,2}, {2,1,0,3}, {1,2,3,0},
	76	{2,1,3,0}, {3,0,2,1}, {3,2,0,1}, {3,2,1,0}
	77	};
	78
	79	int incr[NDIR][2] = {
	80	{0, 1}, {1, 0}, {0, -1}, {-1, 0}
	81	};
	82
	83	static void
6beb426b	84	dig_maze(int x, int y)
82a5c12e MD	85	{
	86	int tx, ty;
	87	int i, j;
	88	int order[4];
	89	#define MNORTH 0x1
	90	#define MSOUTH 0x2
	91	#define MEAST 0x4
	92	#define MWEST 0x8
	93
	94	tx = ty = 0;
	95	Maze[y][x] = SPACE;
	96	order[0] = MNORTH;
	97	for (i = 1; i < 4; i++) {
	98	j = rand_num(i + 1);
	99	order[i] = order[j];
	100	order[j] = 0x1 << i;
	101	}
	102	for (i = 0; i < 4; i++) {
	103	switch (order[i]) {
	104	case MNORTH:
	105	tx = x;
	106	ty = y - 2;
	107	break;
	108	case MSOUTH:
	109	tx = x;
	110	ty = y + 2;
	111	break;
	112	case MEAST:
	113	tx = x + 2;
	114	ty = y;
	115	break;
	116	case MWEST:
	117	tx = x - 2;
	118	ty = y;
	119	break;
	120	}
	121	if (tx < 0 \|\| ty < 0 \|\| tx >= WIDTH \|\| ty >= HEIGHT)
	122	continue;
	123	if (Maze[ty][tx] == SPACE)
	124	continue;
	125	Maze[(y + ty) / 2][(x + tx) / 2] = SPACE;
	126	dig_maze(tx, ty);
	127	}
	128	}
	129
	130	static void
6beb426b	131	remap(void)
82a5c12e MD	132	{
	133	int y, x;
	134	char *sp;
	135	int stat;
	136
	137	for (y = 0; y < HEIGHT; y++)
	138	for (x = 0; x < WIDTH; x++) {
	139	sp = &Maze[y][x];
	140	if (*sp == SPACE)
	141	continue;
	142	/* Find occupied adjacent cells. */
	143	stat = 0;
	144	if (y - 1 >= 0 && Maze[y - 1][x] != SPACE)
	145	stat \|= NORTH;
	146	if (y + 1 < HEIGHT && Maze[y + 1][x] != SPACE)
	147	stat \|= SOUTH;
	148	if (x + 1 < WIDTH && Maze[y][x + 1] != SPACE)
	149	stat \|= EAST;
	150	if (x - 1 >= 0 && Maze[y][x - 1] != SPACE)
	151	stat \|= WEST;
	152	switch (stat) {
	153	case WEST \| EAST:
	154	case EAST:
	155	case WEST:
	156	sp = WALL1; / - */
	157	break;
	158	case NORTH \| SOUTH:
	159	case NORTH:
	160	case SOUTH:
	161	sp = WALL2; / \| */
	162	break;
	163	case 0:
	164	if (conf_random)
	165	*sp = DOOR;
	166	if (conf_reflect)
	167	*sp = rand_num(2) ? WALL4 : WALL5;
	168	break;
	169	default:
	170	sp = WALL3; / + */
	171	break;
	172	}
	173	}
	174	memcpy(Orig_maze, Maze, sizeof Orig_maze);
	175	}