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
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
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
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
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
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
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
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
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
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
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
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*/