1 /* SCCS Id: @(#)mkmap.c 3.4 1996/05/23 */
2 /* Copyright (c) J. C. Collet, M. Stephenson and D. Cohrs, 1992 */
3 /* NetHack may be freely redistributed. See license for details. */
8 #define HEIGHT (ROWNO - 1)
9 #define WIDTH (COLNO - 2)
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 STATIC_DCL void FDECL(remove_room,(unsigned));
21 void FDECL(mkmap, (lev_init *));
24 int min_rx, max_rx, min_ry, max_ry; /* rectangle bounds for regions */
25 static int n_loc_filled;
33 for(i=1; i<COLNO; i++)
34 for(j=0; j<ROWNO; j++)
35 levl[i][j].typ = bg_typ;
39 init_fill(bg_typ, fg_typ)
45 limit = (WIDTH * HEIGHT * 2) / 5;
47 while(count < limit) {
50 if (levl[i][j].typ == bg_typ) {
51 levl[i][j].typ = fg_typ;
58 get_map(col,row, bg_typ)
62 if (col <= 0 || row < 0 || col > WIDTH || row >= HEIGHT)
64 return levl[col][row].typ;
67 static int dirs[16] = {
68 -1, -1 /**/, -1, 0 /**/, -1, 1 /**/,
69 0, -1 /**/, 0, 1 /**/,
70 1, -1 /**/, 1, 0 /**/, 1, 1};
73 pass_one(bg_typ, fg_typ)
79 for(i=2; i<=WIDTH; i++)
80 for(j=1; j<HEIGHT; j++) {
81 for(count=0, dr=0; dr < 8; dr++)
82 if(get_map(i+dirs[dr*2], j+dirs[(dr*2)+1], bg_typ)
90 levl[i][j].typ = bg_typ;
96 levl[i][j].typ = fg_typ;
104 #define new_loc(i,j) *(new_locations+ ((j)*(WIDTH+1)) + (i))
107 pass_two(bg_typ, fg_typ)
108 schar bg_typ, fg_typ;
113 for(i=2; i<=WIDTH; i++)
114 for(j=1; j<HEIGHT; j++) {
115 for(count=0, dr=0; dr < 8; dr++)
116 if(get_map(i+dirs[dr*2], j+dirs[(dr*2)+1], bg_typ)
120 new_loc(i,j) = bg_typ;
122 new_loc(i,j) = get_map(i,j, bg_typ);
125 for(i=2; i<=WIDTH; i++)
126 for(j=1; j<HEIGHT; j++)
127 levl[i][j].typ = new_loc(i,j);
131 pass_three(bg_typ, fg_typ)
132 schar bg_typ, fg_typ;
137 for(i=2; i<=WIDTH; i++)
138 for(j=1; j<HEIGHT; j++) {
139 for(count=0, dr=0; dr < 8; dr++)
140 if(get_map(i+dirs[dr*2], j+dirs[(dr*2)+1], bg_typ)
144 new_loc(i,j) = bg_typ;
146 new_loc(i,j) = get_map(i,j, bg_typ);
149 for(i=2; i<=WIDTH; i++)
150 for(j=1; j<HEIGHT; j++)
151 levl[i][j].typ = new_loc(i,j);
155 * use a flooding algorithm to find all locations that should
156 * have the same rm number as the current location.
157 * if anyroom is TRUE, use IS_ROOM to check room membership instead of
158 * exactly matching levl[sx][sy].typ and walls are included as well.
161 flood_fill_rm(sx, sy, rmno, lit, anyroom)
170 schar fg_typ = levl[sx][sy].typ;
172 /* back up to find leftmost uninitialized location */
174 (anyroom ? IS_ROOM(levl[sx][sy].typ) : levl[sx][sy].typ == fg_typ) &&
175 (int) levl[sx][sy].roomno != rmno)
177 sx++; /* compensate for extra decrement */
179 /* assume sx,sy is valid */
180 if(sx < min_rx) min_rx = sx;
181 if(sy < min_ry) min_ry = sy;
183 for(i=sx; i<=WIDTH && levl[i][sy].typ == fg_typ; i++) {
184 levl[i][sy].roomno = rmno;
185 levl[i][sy].lit = lit;
187 /* add walls to room as well */
189 for(ii= (i == sx ? i-1 : i); ii <= i+1; ii++)
190 for(jj = sy-1; jj <= sy+1; jj++)
192 (IS_WALL(levl[ii][jj].typ) ||
193 IS_DOOR(levl[ii][jj].typ))) {
194 levl[ii][jj].edge = 1;
195 if(lit) levl[ii][jj].lit = lit;
196 if ((int) levl[ii][jj].roomno != rmno)
197 levl[ii][jj].roomno = SHARED;
206 if(levl[i][sy-1].typ == fg_typ) {
207 if ((int) levl[i][sy-1].roomno != rmno)
208 flood_fill_rm(i,sy-1,rmno,lit,anyroom);
210 if((i>sx || isok(i-1,sy-1)) &&
211 levl[i-1][sy-1].typ == fg_typ) {
212 if ((int) levl[i-1][sy-1].roomno != rmno)
213 flood_fill_rm(i-1,sy-1,rmno,lit,anyroom);
215 if((i<nx-1 || isok(i+1,sy-1)) &&
216 levl[i+1][sy-1].typ == fg_typ) {
217 if ((int) levl[i+1][sy-1].roomno != rmno)
218 flood_fill_rm(i+1,sy-1,rmno,lit,anyroom);
224 if(levl[i][sy+1].typ == fg_typ) {
225 if ((int) levl[i][sy+1].roomno != rmno)
226 flood_fill_rm(i,sy+1,rmno,lit,anyroom);
228 if((i>sx || isok(i-1,sy+1)) &&
229 levl[i-1][sy+1].typ == fg_typ) {
230 if ((int) levl[i-1][sy+1].roomno != rmno)
231 flood_fill_rm(i-1,sy+1,rmno,lit,anyroom);
233 if((i<nx-1 || isok(i+1,sy+1)) &&
234 levl[i+1][sy+1].typ == fg_typ) {
235 if ((int) levl[i+1][sy+1].roomno != rmno)
236 flood_fill_rm(i+1,sy+1,rmno,lit,anyroom);
241 if(nx > max_rx) max_rx = nx - 1; /* nx is just past valid region */
242 if(sy > max_ry) max_ry = sy;
246 * If we have drawn a map without walls, this allows us to
247 * auto-magically wallify it. Taken from lev_main.c.
255 for(x = 1; x < COLNO; x++)
256 for(y = 0; y < ROWNO; y++)
257 if(levl[x][y].typ == STONE) {
258 for(yy = y - 1; yy <= y+1; yy++)
259 for(xx = x - 1; xx <= x+1; xx++)
260 if(isok(xx,yy) && levl[xx][yy].typ == ROOM) {
261 if(yy != y) levl[x][y].typ = HWALL;
262 else levl[x][y].typ = VWALL;
268 join_map(bg_typ, fg_typ)
269 schar bg_typ, fg_typ;
271 register struct mkroom *croom, *croom2;
277 /* first, use flood filling to find all of the regions that need joining */
278 for(i=2; i<=WIDTH; i++)
279 for(j=1; j<HEIGHT; j++) {
280 if(levl[i][j].typ == fg_typ && levl[i][j].roomno == NO_ROOM) {
284 flood_fill_rm(i,j,nroom+ROOMOFFSET,FALSE,FALSE);
285 if(n_loc_filled > 3) {
286 add_room(min_rx, min_ry, max_rx, max_ry,
288 rooms[nroom-1].irregular = TRUE;
289 if(nroom >= (MAXNROFROOMS*2))
293 * it's a tiny hole; erase it from the map to avoid
294 * having the player end up here with no way out.
296 for(sx = min_rx; sx<=max_rx; sx++)
297 for(sy = min_ry; sy<=max_ry; sy++)
298 if ((int) levl[sx][sy].roomno ==
299 nroom + ROOMOFFSET) {
300 levl[sx][sy].typ = bg_typ;
301 levl[sx][sy].roomno = NO_ROOM;
309 * Ok, now we can actually join the regions with fg_typ's.
310 * The rooms are already sorted due to the previous loop,
311 * so don't call sort_rooms(), which can screw up the roomno's
312 * validity in the levl structure.
314 for(croom = &rooms[0], croom2 = croom + 1; croom2 < &rooms[nroom]; ) {
315 /* pick random starting and end locations for "corridor" */
316 if(!somexy(croom, &sm) || !somexy(croom2, &em)) {
317 /* ack! -- the level is going to be busted */
318 /* arbitrarily pick centers of both rooms and hope for the best */
319 impossible("No start/end room loc in join_map.");
320 sm.x = croom->lx + ((croom->hx - croom->lx) / 2);
321 sm.y = croom->ly + ((croom->hy - croom->ly) / 2);
322 em.x = croom2->lx + ((croom2->hx - croom2->lx) / 2);
323 em.y = croom2->ly + ((croom2->hy - croom2->ly) / 2);
326 (void) dig_corridor(&sm, &em, FALSE, fg_typ, bg_typ);
328 /* choose next region to join */
329 /* only increment croom if croom and croom2 are non-overlapping */
330 if(croom2->lx > croom->hx ||
331 ((croom2->ly > croom->hy || croom2->hy < croom->ly) && rn2(3))) {
334 croom2++; /* always increment the next room */
339 finish_map(fg_typ, bg_typ, lit, walled)
340 schar fg_typ, bg_typ;
345 if(walled) wallify_map();
348 for(i=1; i<COLNO; i++)
349 for(j=0; j<ROWNO; j++)
350 if((!IS_ROCK(fg_typ) && levl[i][j].typ == fg_typ) ||
351 (!IS_ROCK(bg_typ) && levl[i][j].typ == bg_typ) ||
352 (bg_typ == TREE && levl[i][j].typ == bg_typ) ||
353 (walled && IS_WALL(levl[i][j].typ)))
354 levl[i][j].lit = TRUE;
355 for(i = 0; i < nroom; i++)
358 /* light lava even if everything's otherwise unlit */
359 for(i=1; i<COLNO; i++)
360 for(j=0; j<ROWNO; j++)
361 if (levl[i][j].typ == LAVAPOOL)
362 levl[i][j].lit = TRUE;
366 * When level processed by join_map is overlaid by a MAP, some rooms may no
367 * longer be valid. All rooms in the region lx <= x < hx, ly <= y < hy are
368 * removed. Rooms partially in the region are truncated. This function
369 * must be called before the REGIONs or ROOMs of the map are processed, or
370 * those rooms will be removed as well. Assumes roomno fields in the
371 * region are already cleared, and roomno and irregular fields outside the
372 * region are all set.
375 remove_rooms(lx, ly, hx, hy)
379 struct mkroom *croom;
381 for (i = nroom - 1; i >= 0; --i) {
383 if (croom->hx < lx || croom->lx >= hx ||
384 croom->hy < ly || croom->ly >= hy) continue; /* no overlap */
386 if (croom->lx < lx || croom->hx >= hx ||
387 croom->ly < ly || croom->hy >= hy) { /* partial overlap */
388 /* TODO: ensure remaining parts of room are still joined */
390 if (!croom->irregular) impossible("regular room in joined map");
392 /* total overlap, remove the room */
393 remove_room((unsigned)i);
399 * Remove roomno from the rooms array, decrementing nroom. Also updates
400 * all level roomno values of affected higher numbered rooms. Assumes
401 * level structure contents corresponding to roomno have already been reset.
402 * Currently handles only the removal of rooms that have no subrooms.
408 struct mkroom *croom = &rooms[roomno];
409 struct mkroom *maxroom = &rooms[--nroom];
413 if (croom != maxroom) {
414 /* since the order in the array only matters for making corridors,
415 * copy the last room over the one being removed on the assumption
416 * that corridors have already been dug. */
417 (void) memcpy((genericptr_t)croom, (genericptr_t)maxroom,
418 sizeof(struct mkroom));
420 /* since maxroom moved, update affected level roomno values */
421 oroomno = nroom + ROOMOFFSET;
422 roomno += ROOMOFFSET;
423 for (i = croom->lx; i <= croom->hx; ++i)
424 for (j = croom->ly; j <= croom->hy; ++j) {
425 if (levl[i][j].roomno == oroomno)
426 levl[i][j].roomno = roomno;
430 maxroom->hx = -1; /* just like add_room */
433 #define N_P1_ITER 1 /* tune map generation via this value */
434 #define N_P2_ITER 1 /* tune map generation via this value */
435 #define N_P3_ITER 2 /* tune map smoothing via this value */
441 schar bg_typ = init_lev->bg,
442 fg_typ = init_lev->fg;
443 boolean smooth = init_lev->smoothed,
444 join = init_lev->joined;
445 xchar lit = init_lev->lit,
446 walled = init_lev->walled;
450 lit = (rnd(1+abs(depth(&u.uz))) < 11 && rn2(77)) ? 1 : 0;
452 new_locations = (char *)alloc((WIDTH+1) * HEIGHT);
455 init_fill(bg_typ, fg_typ);
457 for(i = 0; i < N_P1_ITER; i++)
458 pass_one(bg_typ, fg_typ);
460 for(i = 0; i < N_P2_ITER; i++)
461 pass_two(bg_typ, fg_typ);
464 for(i = 0; i < N_P3_ITER; i++)
465 pass_three(bg_typ, fg_typ);
468 join_map(bg_typ, fg_typ);
470 finish_map(fg_typ, bg_typ, (boolean)lit, (boolean)walled);
471 /* a walled, joined level is cavernous, not mazelike -dlc */
472 if (walled && join) {
473 level.flags.is_maze_lev = FALSE;
474 level.flags.is_cavernous_lev = TRUE;