06ef40a943fede620fad2341c6a7b4f3a7decaa5
[dragonfly.git] / games / hunt / huntd / makemaze.c
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 $
33  * $DragonFly: src/games/hunt/huntd/makemaze.c,v 1.2 2008/09/04 16:12:51 swildner Exp $
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
45 static  int     candig(int, int);
46 static  void    dig(int, int);
47 static  void    dig_maze(int, int);
48 static  void    remap(void);
49
50 void
51 makemaze(void)
52 {
53         char    *sp;
54         int     y, x;
55
56         /*
57          * fill maze with walls
58          */
59         sp = &Maze[0][0];
60         while (sp < &Maze[HEIGHT - 1][WIDTH])
61                 *sp++ = DOOR;
62
63         x = rand_num(WIDTH / 2) * 2 + 1;
64         y = rand_num(HEIGHT / 2) * 2 + 1;
65         dig_maze(x, y);
66         remap();
67 }
68
69 # define        NPERM   24
70 # define        NDIR    4
71
72 int     dirs[NPERM][NDIR] = {
73                 {0,1,2,3},      {3,0,1,2},      {0,2,3,1},      {0,3,2,1},
74                 {1,0,2,3},      {2,3,0,1},      {0,2,1,3},      {2,3,1,0},
75                 {1,0,3,2},      {1,2,0,3},      {3,1,2,0},      {2,0,3,1},
76                 {1,3,0,2},      {0,3,1,2},      {1,3,2,0},      {2,0,1,3},
77                 {0,1,3,2},      {3,1,0,2},      {2,1,0,3},      {1,2,3,0},
78                 {2,1,3,0},      {3,0,2,1},      {3,2,0,1},      {3,2,1,0}
79         };
80
81 int     incr[NDIR][2] = {
82                 {0, 1}, {1, 0}, {0, -1}, {-1, 0}
83         };
84
85 static void
86 dig(int y, int x)
87 {
88         int     *dp;
89         int     *ip;
90         int     ny, nx;
91         int     *endp;
92
93         Maze[y][x] = SPACE;                     /* Clear this spot */
94         dp = dirs[rand_num(NPERM)];
95         endp = &dp[NDIR];
96         while (dp < endp) {
97                 ip = &incr[*dp++][0];
98                 ny = y + *ip++;
99                 nx = x + *ip;
100                 if (candig(ny, nx))
101                         dig(ny, nx);
102         }
103 }
104
105 /*
106  * candig:
107  *      Is it legal to clear this spot?
108  */
109 static int
110 candig(int y, int x)
111 {
112         int     i;
113
114         if (ODD(x) && ODD(y))
115                 return FALSE;           /* can't touch ODD spots */
116
117         if (y < UBOUND || y >= DBOUND)
118                 return FALSE;           /* Beyond vertical bounds, NO */
119         if (x < LBOUND || x >= RBOUND)
120                 return FALSE;           /* Beyond horizontal bounds, NO */
121
122         if (ISCLEAR(y, x))
123                 return FALSE;           /* Already clear, NO */
124
125         i = ISCLEAR(y, x + 1);
126         i += ISCLEAR(y, x - 1);
127         if (i > 1)
128                 return FALSE;           /* Introduces cycle, NO */
129         i += ISCLEAR(y + 1, x);
130         if (i > 1)
131                 return FALSE;           /* Introduces cycle, NO */
132         i += ISCLEAR(y - 1, x);
133         if (i > 1)
134                 return FALSE;           /* Introduces cycle, NO */
135
136         return TRUE;                    /* OK */
137 }
138
139 static void
140 dig_maze(int x, int y)
141 {
142         int     tx, ty;
143         int     i, j;
144         int     order[4];
145 #define MNORTH  0x1
146 #define MSOUTH  0x2
147 #define MEAST   0x4
148 #define MWEST   0x8
149
150         tx = ty = 0;
151         Maze[y][x] = SPACE;
152         order[0] = MNORTH;
153         for (i = 1; i < 4; i++) {
154                 j = rand_num(i + 1);
155                 order[i] = order[j];
156                 order[j] = 0x1 << i;
157         }
158         for (i = 0; i < 4; i++) {
159                 switch (order[i]) {
160                   case MNORTH:
161                         tx = x;
162                         ty = y - 2;
163                         break;
164                   case MSOUTH:
165                         tx = x;
166                         ty = y + 2;
167                         break;
168                   case MEAST:
169                         tx = x + 2;
170                         ty = y;
171                         break;
172                   case MWEST:
173                         tx = x - 2;
174                         ty = y;
175                         break;
176                 }
177                 if (tx < 0 || ty < 0 || tx >= WIDTH || ty >= HEIGHT)
178                         continue;
179                 if (Maze[ty][tx] == SPACE)
180                         continue;
181                 Maze[(y + ty) / 2][(x + tx) / 2] = SPACE;
182                 dig_maze(tx, ty);
183         }
184 }
185
186 static void
187 remap(void)
188 {
189         int     y, x;
190         char    *sp;
191         int     stat;
192
193         for (y = 0; y < HEIGHT; y++)
194                 for (x = 0; x < WIDTH; x++) {
195                         sp = &Maze[y][x];
196                         if (*sp == SPACE)
197                                 continue;
198                         /* Find occupied adjacent cells. */
199                         stat = 0;
200                         if (y - 1 >= 0 && Maze[y - 1][x] != SPACE)
201                                 stat |= NORTH;
202                         if (y + 1 < HEIGHT && Maze[y + 1][x] != SPACE)
203                                 stat |= SOUTH;
204                         if (x + 1 < WIDTH && Maze[y][x + 1] != SPACE)
205                                 stat |= EAST;
206                         if (x - 1 >= 0 && Maze[y][x - 1] != SPACE)
207                                 stat |= WEST;
208                         switch (stat) {
209                           case WEST | EAST:
210                           case EAST:
211                           case WEST:
212                                 *sp = WALL1;                       /* - */
213                                 break;
214                           case NORTH | SOUTH:
215                           case NORTH:
216                           case SOUTH:
217                                 *sp = WALL2;                       /* | */
218                                 break;
219                           case 0:
220                                 if (conf_random)
221                                         *sp = DOOR;
222                                 if (conf_reflect)
223                                         *sp = rand_num(2) ? WALL4 : WALL5;
224                                 break;
225                           default:
226                                 *sp = WALL3;                       /* + */
227                                 break;
228                         }
229                 }
230         memcpy(Orig_maze, Maze, sizeof Orig_maze);
231 }