1 /* SCCS Id: @(#)mkmap.c 3.3 96/05/23 */
2 /* Copyright (c) J. C. Collet, M. Stephenson and D. Cohrs, 1992 */
3 /* NetHack may be freely redistributed. See license for details. */
4
5 #include "hack.h"
6 #include "sp_lev.h"
7
8 #define HEIGHT (ROWNO - 1)
9 #define WIDTH (COLNO - 2)
10
11 STATIC_DCL void FDECL(init_map,(SCHAR_P));
12 STATIC_DCL void FDECL(init_fill,(SCHAR_P,SCHAR_P));
13 STATIC_DCL schar FDECL(get_map,(int,int,SCHAR_P));
14 STATIC_DCL void FDECL(pass_one,(SCHAR_P,SCHAR_P));
15 STATIC_DCL void FDECL(pass_two,(SCHAR_P,SCHAR_P));
16 STATIC_DCL void FDECL(pass_three,(SCHAR_P,SCHAR_P));
17 STATIC_DCL void NDECL(wallify_map);
18 STATIC_DCL void FDECL(join_map,(SCHAR_P,SCHAR_P));
19 STATIC_DCL void FDECL(finish_map,(SCHAR_P,SCHAR_P,XCHAR_P,XCHAR_P));
20 void FDECL(mkmap, (lev_init *));
21
22 char *new_locations;
23 int min_rx, max_rx, min_ry, max_ry; /* rectangle bounds for regions */
24 static int n_loc_filled;
25
26 STATIC_OVL void
init_map(bg_typ)27 init_map(bg_typ)
28 schar bg_typ;
29 {
30 register int i,j;
31
32 for(i=1; i<COLNO; i++)
33 for(j=0; j<ROWNO; j++)
34 levl[i][j].typ = bg_typ;
35 }
36
37 STATIC_OVL void
init_fill(bg_typ,fg_typ)38 init_fill(bg_typ, fg_typ)
39 schar bg_typ, fg_typ;
40 {
41 register int i,j;
42 long limit, count;
43
44 limit = (WIDTH * HEIGHT * 2) / 5;
45 count = 0;
46 while(count < limit) {
47 i = rn1(WIDTH-1, 2);
48 j = rnd(HEIGHT-1);
49 if (levl[i][j].typ == bg_typ) {
50 levl[i][j].typ = fg_typ;
51 count++;
52 }
53 }
54 }
55
56 STATIC_OVL schar
get_map(col,row,bg_typ)57 get_map(col,row, bg_typ)
58 int col,row;
59 schar bg_typ;
60 {
61 if (col <= 0 || row < 0 || col > WIDTH || row >= HEIGHT)
62 return bg_typ;
63 return levl[col][row].typ;
64 }
65
66 static int dirs[16] = {
67 -1, -1 /**/, -1, 0 /**/, -1, 1 /**/,
68 0, -1 /**/, 0, 1 /**/,
69 1, -1 /**/, 1, 0 /**/, 1, 1};
70
71 STATIC_OVL void
pass_one(bg_typ,fg_typ)72 pass_one(bg_typ, fg_typ)
73 schar bg_typ, fg_typ;
74 {
75 register int i,j;
76 short count, dr;
77
78 for(i=2; i<=WIDTH; i++)
79 for(j=1; j<HEIGHT; j++) {
80 for(count=0, dr=0; dr < 8; dr++)
81 if(get_map(i+dirs[dr*2], j+dirs[(dr*2)+1], bg_typ)
82 == fg_typ)
83 count++;
84
85 switch(count) {
86 case 0 : /* death */
87 case 1 :
88 case 2:
89 levl[i][j].typ = bg_typ;
90 break;
91 case 5:
92 case 6:
93 case 7:
94 case 8:
95 levl[i][j].typ = fg_typ;
96 break;
97 default:
98 break;
99 }
100 }
101 }
102
103 #define new_loc(i,j) *(new_locations+ ((j)*(WIDTH+1)) + (i))
104
105 STATIC_OVL void
pass_two(bg_typ,fg_typ)106 pass_two(bg_typ, fg_typ)
107 schar bg_typ, fg_typ;
108 {
109 register int i,j;
110 short count, dr;
111
112 for(i=2; i<=WIDTH; i++)
113 for(j=1; j<HEIGHT; j++) {
114 for(count=0, dr=0; dr < 8; dr++)
115 if(get_map(i+dirs[dr*2], j+dirs[(dr*2)+1], bg_typ)
116 == fg_typ)
117 count++;
118 if (count == 5)
119 new_loc(i,j) = bg_typ;
120 else
121 new_loc(i,j) = get_map(i,j, bg_typ);
122 }
123
124 for(i=2; i<=WIDTH; i++)
125 for(j=1; j<HEIGHT; j++)
126 levl[i][j].typ = new_loc(i,j);
127 }
128
129 STATIC_OVL void
pass_three(bg_typ,fg_typ)130 pass_three(bg_typ, fg_typ)
131 schar bg_typ, fg_typ;
132 {
133 register int i,j;
134 short count, dr;
135
136 for(i=2; i<=WIDTH; i++)
137 for(j=1; j<HEIGHT; j++) {
138 for(count=0, dr=0; dr < 8; dr++)
139 if(get_map(i+dirs[dr*2], j+dirs[(dr*2)+1], bg_typ)
140 == fg_typ)
141 count++;
142 if (count < 3)
143 new_loc(i,j) = bg_typ;
144 else
145 new_loc(i,j) = get_map(i,j, bg_typ);
146 }
147
148 for(i=2; i<=WIDTH; i++)
149 for(j=1; j<HEIGHT; j++)
150 levl[i][j].typ = new_loc(i,j);
151 }
152
153 /*
154 * use a flooding algorithm to find all locations that should
155 * have the same rm number as the current location.
156 * if anyroom is TRUE, use IS_ROOM to check room membership instead of
157 * exactly matching levl[sx][sy].typ and walls are included as well.
158 */
159 void
flood_fill_rm(sx,sy,rmno,lit,anyroom)160 flood_fill_rm(sx, sy, rmno, lit, anyroom)
161 int sx;
162 register int sy;
163 register int rmno;
164 boolean lit;
165 boolean anyroom;
166 {
167 register int i;
168 int nx;
169 schar fg_typ = levl[sx][sy].typ;
170
171 /* back up to find leftmost uninitialized location */
172 while (sx > 0 &&
173 (anyroom ? IS_ROOM(levl[sx][sy].typ) : levl[sx][sy].typ == fg_typ) &&
174 (int) levl[sx][sy].roomno != rmno)
175 sx--;
176 sx++; /* compensate for extra decrement */
177
178 /* assume sx,sy is valid */
179 if(sx < min_rx) min_rx = sx;
180 if(sy < min_ry) min_ry = sy;
181
182 for(i=sx; i<=WIDTH && levl[i][sy].typ == fg_typ; i++) {
183 levl[i][sy].roomno = rmno;
184 levl[i][sy].lit = lit;
185 if(anyroom) {
186 /* add walls to room as well */
187 register int ii,jj;
188 for(ii= (i == sx ? i-1 : i); ii <= i+1; ii++)
189 for(jj = sy-1; jj <= sy+1; jj++)
190 if(isok(ii,jj) &&
191 (IS_WALL(levl[ii][jj].typ) ||
192 IS_DOOR(levl[ii][jj].typ))) {
193 levl[ii][jj].edge = 1;
194 if(lit) levl[ii][jj].lit = lit;
195 if ((int) levl[ii][jj].roomno != rmno)
196 levl[ii][jj].roomno = SHARED;
197 }
198 }
199 n_loc_filled++;
200 }
201 nx = i;
202
203 if(isok(sx,sy-1)) {
204 for(i=sx; i<nx; i++)
205 if(levl[i][sy-1].typ == fg_typ) {
206 if ((int) levl[i][sy-1].roomno != rmno)
207 flood_fill_rm(i,sy-1,rmno,lit,anyroom);
208 } else {
209 if((i>sx || isok(i-1,sy-1)) &&
210 levl[i-1][sy-1].typ == fg_typ) {
211 if ((int) levl[i-1][sy-1].roomno != rmno)
212 flood_fill_rm(i-1,sy-1,rmno,lit,anyroom);
213 }
214 if((i<nx-1 || isok(i+1,sy-1)) &&
215 levl[i+1][sy-1].typ == fg_typ) {
216 if ((int) levl[i+1][sy-1].roomno != rmno)
217 flood_fill_rm(i+1,sy-1,rmno,lit,anyroom);
218 }
219 }
220 }
221 if(isok(sx,sy+1)) {
222 for(i=sx; i<nx; i++)
223 if(levl[i][sy+1].typ == fg_typ) {
224 if ((int) levl[i][sy+1].roomno != rmno)
225 flood_fill_rm(i,sy+1,rmno,lit,anyroom);
226 } else {
227 if((i>sx || isok(i-1,sy+1)) &&
228 levl[i-1][sy+1].typ == fg_typ) {
229 if ((int) levl[i-1][sy+1].roomno != rmno)
230 flood_fill_rm(i-1,sy+1,rmno,lit,anyroom);
231 }
232 if((i<nx-1 || isok(i+1,sy+1)) &&
233 levl[i+1][sy+1].typ == fg_typ) {
234 if ((int) levl[i+1][sy+1].roomno != rmno)
235 flood_fill_rm(i+1,sy+1,rmno,lit,anyroom);
236 }
237 }
238 }
239
240 if(nx > max_rx) max_rx = nx - 1; /* nx is just past valid region */
241 if(sy > max_ry) max_ry = sy;
242 }
243
244 /*
245 * If we have drawn a map without walls, this allows us to
246 * auto-magically wallify it. Taken from lev_main.c.
247 */
248 STATIC_OVL void
wallify_map()249 wallify_map()
250 {
251
252 int x, y, xx, yy;
253
254 for(x = 1; x < COLNO; x++)
255 for(y = 0; y < ROWNO; y++)
256 if(levl[x][y].typ == STONE) {
257 for(yy = y - 1; yy <= y+1; yy++)
258 for(xx = x - 1; xx <= x+1; xx++)
259 if(isok(xx,yy) && levl[xx][yy].typ == ROOM) {
260 if(yy != y) levl[x][y].typ = HWALL;
261 else levl[x][y].typ = VWALL;
262 }
263 }
264 }
265
266 STATIC_OVL void
join_map(bg_typ,fg_typ)267 join_map(bg_typ, fg_typ)
268 schar bg_typ, fg_typ;
269 {
270 register struct mkroom *croom, *croom2;
271
272 register int i, j;
273 int sx, sy;
274 coord sm, em;
275
276 /* first, use flood filling to find all of the regions that need joining */
277 for(i=2; i<=WIDTH; i++)
278 for(j=1; j<HEIGHT; j++) {
279 if(levl[i][j].typ == fg_typ && levl[i][j].roomno == NO_ROOM) {
280 min_rx = max_rx = i;
281 min_ry = max_ry = j;
282 n_loc_filled = 0;
283 flood_fill_rm(i,j,nroom+ROOMOFFSET,FALSE,FALSE);
284 if(n_loc_filled > 3) {
285 add_room(min_rx, min_ry, max_rx, max_ry,
286 FALSE, OROOM, TRUE);
287 rooms[nroom-1].irregular = TRUE;
288 if(nroom >= (MAXNROFROOMS*2))
289 goto joinm;
290 } else {
291 /*
292 * it's a tiny hole; erase it from the map to avoid
293 * having the player end up here with no way out.
294 */
295 for(sx = min_rx; sx<=max_rx; sx++)
296 for(sy = min_ry; sy<=max_ry; sy++)
297 if ((int) levl[sx][sy].roomno ==
298 nroom + ROOMOFFSET) {
299 levl[sx][sy].typ = bg_typ;
300 levl[sx][sy].roomno = NO_ROOM;
301 }
302 }
303 }
304 }
305
306 joinm:
307 /*
308 * Ok, now we can actually join the regions with fg_typ's.
309 * The rooms are already sorted due to the previous loop,
310 * so don't call sort_rooms(), which can screw up the roomno's
311 * validity in the levl structure.
312 */
313 for(croom = &rooms[0], croom2 = croom + 1; croom2 < &rooms[nroom]; ) {
314 /* pick random starting and end locations for "corridor" */
315 if(!somexy(croom, &sm) || !somexy(croom2, &em)) {
316 /* ack! -- the level is going to be busted */
317 /* arbitrarily pick centers of both rooms and hope for the best */
318 impossible("No start/end room loc in join_map.");
319 sm.x = croom->lx + ((croom->hx - croom->lx) / 2);
320 sm.y = croom->ly + ((croom->hy - croom->ly) / 2);
321 em.x = croom2->lx + ((croom2->hx - croom2->lx) / 2);
322 em.y = croom2->ly + ((croom2->hy - croom2->ly) / 2);
323 }
324
325 (void) dig_corridor(&sm, &em, FALSE, fg_typ, bg_typ);
326
327 /* choose next region to join */
328 /* only increment croom if croom and croom2 are non-overlapping */
329 if(croom2->lx > croom->hx ||
330 ((croom2->ly > croom->hy || croom2->hy < croom->ly) && rn2(3))) {
331 croom = croom2;
332 }
333 croom2++; /* always increment the next room */
334 }
335 }
336
337 STATIC_OVL void
finish_map(fg_typ,bg_typ,lit,walled)338 finish_map(fg_typ, bg_typ, lit, walled)
339 schar fg_typ, bg_typ;
340 boolean lit, walled;
341 {
342 int i, j;
343
344 if(walled) wallify_map();
345
346 if(lit) {
347 for(i=1; i<COLNO; i++)
348 for(j=0; j<ROWNO; j++)
349 if((!IS_ROCK(fg_typ) && levl[i][j].typ == fg_typ) ||
350 (!IS_ROCK(bg_typ) && levl[i][j].typ == bg_typ) ||
351 (walled && IS_WALL(levl[i][j].typ)))
352 levl[i][j].lit = TRUE;
353 for(i = 0; i < nroom; i++)
354 rooms[i].rlit = 1;
355 }
356 /* light lava even if everything's otherwise unlit */
357 for(i=1; i<COLNO; i++)
358 for(j=0; j<ROWNO; j++)
359 if (levl[i][j].typ == LAVAPOOL)
360 levl[i][j].lit = TRUE;
361 }
362
363 #define N_P1_ITER 1 /* tune map generation via this value */
364 #define N_P2_ITER 1 /* tune map generation via this value */
365 #define N_P3_ITER 2 /* tune map smoothing via this value */
366
367 void
mkmap(init_lev)368 mkmap(init_lev)
369
370 lev_init *init_lev;
371 {
372 schar bg_typ = init_lev->bg,
373 fg_typ = init_lev->fg;
374 boolean smooth = init_lev->smoothed,
375 join = init_lev->joined;
376 xchar lit = init_lev->lit,
377 walled = init_lev->walled;
378 int i;
379
380 if(lit < 0)
381 lit = (rnd(1+abs(depth(&u.uz))) < 11 && rn2(77)) ? 1 : 0;
382
383 new_locations = (char *)alloc((WIDTH+1) * HEIGHT);
384
385 init_map(bg_typ);
386 init_fill(bg_typ, fg_typ);
387
388 for(i = 0; i < N_P1_ITER; i++)
389 pass_one(bg_typ, fg_typ);
390
391 for(i = 0; i < N_P2_ITER; i++)
392 pass_two(bg_typ, fg_typ);
393
394 if(smooth)
395 for(i = 0; i < N_P3_ITER; i++)
396 pass_three(bg_typ, fg_typ);
397
398 if(join)
399 join_map(bg_typ, fg_typ);
400
401 finish_map(fg_typ, bg_typ, (boolean)lit, (boolean)walled);
402 /* a walled, joined level is cavernous, not mazelike -dlc */
403 if (walled && join) {
404 level.flags.is_maze_lev = FALSE;
405 level.flags.is_cavernous_lev = TRUE;
406 }
407 free(new_locations);
408 }
409
410 /*mkmap.c*/
411