Source:NetHack 3.4.3/src/mkmap.c

Below is the full text to src/mkmap.c from NetHack 3.4.3. To link to a particular line, write [[mkmap.c#line123]], for example.

Top of file

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

The NetHack General Public License applies to screenshots, source code and other content from NetHack.

This content was modified from the original NetHack source code distribution (by splitting up NetHack content between wiki pages, and possibly further editing). See the page history for a list of who changed it, and on what dates.

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.   STATIC_DCL void FDECL(remove_room,(unsigned));
21.   void FDECL(mkmap, (lev_init *));
22.   
23.   char *new_locations;
24.   int min_rx, max_rx, min_ry, max_ry; /* rectangle bounds for regions */
25.   static int n_loc_filled;
26.   

init_map

27.   STATIC_OVL void
28.   init_map(bg_typ)
29.   	schar	bg_typ;
30.   {
31.   	register int i,j;
32.   
33.   	for(i=1; i<COLNO; i++)
34.   	    for(j=0; j<ROWNO; j++)
35.   		levl[i][j].typ = bg_typ;
36.   }
37.   

init_fill

38.   STATIC_OVL void
39.   init_fill(bg_typ, fg_typ)
40.   	schar	bg_typ, fg_typ;
41.   {
42.   	register int i,j;
43.   	long limit, count;
44.   
45.   	limit = (WIDTH * HEIGHT * 2) / 5;
46.   	count = 0;
47.   	while(count < limit) {
48.   	    i = rn1(WIDTH-1, 2);
49.   	    j = rnd(HEIGHT-1);
50.   	    if (levl[i][j].typ == bg_typ) {
51.   		levl[i][j].typ = fg_typ;
52.   		count++;
53.   	    }
54.   	}
55.   }
56.   

get_map

57.   STATIC_OVL schar
58.   get_map(col,row, bg_typ)
59.   	int col,row;
60.   	schar	bg_typ;
61.   {
62.   	if (col <= 0 || row < 0 || col > WIDTH || row >= HEIGHT)
63.   		return bg_typ;
64.   	return levl[col][row].typ;
65.   }
66.   
67.   static int dirs[16] = {
68.       -1, -1 /**/, -1, 0 /**/, -1, 1 /**/,
69.        0, -1 /**/,              0, 1 /**/,
70.        1, -1 /**/,  1, 0 /**/,  1, 1};
71.   

pass_one

72.   STATIC_OVL void
73.   pass_one(bg_typ, fg_typ)
74.   	schar	bg_typ, fg_typ;
75.   {
76.   	register int i,j;
77.   	short count, dr;
78.   
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)
83.   								== fg_typ)
84.   			count++;
85.   
86.   		switch(count) {
87.   		  case 0 : /* death */
88.   		  case 1 :
89.   		  case 2:
90.   			  levl[i][j].typ = bg_typ;
91.   			  break;
92.   		  case 5:
93.   		  case 6:
94.   		  case 7:
95.   		  case 8:
96.   			  levl[i][j].typ = fg_typ;
97.   			  break;
98.   		  default:
99.   			  break;
100.  		  }
101.  	    }
102.  }
103.  
104.  #define new_loc(i,j)	*(new_locations+ ((j)*(WIDTH+1)) + (i))
105.  

pass_two

106.  STATIC_OVL void
107.  pass_two(bg_typ, fg_typ)
108.  	schar	bg_typ, fg_typ;
109.  {
110.  	register int i,j;
111.  	short count, dr;
112.  
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)
117.  								== fg_typ)
118.  			count++;
119.  		    if (count == 5)
120.  			new_loc(i,j) = bg_typ;
121.  		    else
122.  			new_loc(i,j) = get_map(i,j, bg_typ);
123.  	    }
124.  
125.  	for(i=2; i<=WIDTH; i++)
126.  	    for(j=1; j<HEIGHT; j++)
127.  		levl[i][j].typ = new_loc(i,j);
128.  }
129.  

pass_three

130.  STATIC_OVL void
131.  pass_three(bg_typ, fg_typ)
132.  	schar	bg_typ, fg_typ;
133.  {
134.  	register int i,j;
135.  	short count, dr;
136.  
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)
141.  								== fg_typ)
142.  			count++;
143.  		if (count < 3)
144.  		    new_loc(i,j) = bg_typ;
145.  		else
146.  		    new_loc(i,j) = get_map(i,j, bg_typ);
147.  	    }
148.  
149.  	for(i=2; i<=WIDTH; i++)
150.  	    for(j=1; j<HEIGHT; j++)
151.  		levl[i][j].typ = new_loc(i,j);
152.  }
153.  

flood_fill_rm

154.  /*
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.
159.   */
160.  void
161.  flood_fill_rm(sx, sy, rmno, lit, anyroom)
162.      int sx;
163.      register int sy;
164.      register int rmno;
165.      boolean lit;
166.      boolean anyroom;
167.  {
168.      register int i;
169.      int nx;
170.      schar fg_typ = levl[sx][sy].typ;
171.  
172.      /* back up to find leftmost uninitialized location */
173.      while (sx > 0 &&
174.  	  (anyroom ? IS_ROOM(levl[sx][sy].typ) : levl[sx][sy].typ == fg_typ) &&
175.  	  (int) levl[sx][sy].roomno != rmno)
176.  	sx--;
177.      sx++; /* compensate for extra decrement */
178.  
179.      /* assume sx,sy is valid */
180.      if(sx < min_rx) min_rx = sx;
181.      if(sy < min_ry) min_ry = sy;
182.  
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;
186.  	if(anyroom) {
187.  	    /* add walls to room as well */
188.  	    register int ii,jj;
189.  	    for(ii= (i == sx ? i-1 : i); ii <= i+1; ii++)
190.  		for(jj = sy-1; jj <= sy+1; jj++)
191.  		    if(isok(ii,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;
198.  		    }
199.  	}
200.  	n_loc_filled++;
201.      }
202.      nx = i;
203.  
204.      if(isok(sx,sy-1)) {
205.  	for(i=sx; i<nx; i++)
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);
209.  	    } else {
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);
214.  		}
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);
219.  		}
220.  	    }
221.      }
222.      if(isok(sx,sy+1)) {
223.  	for(i=sx; i<nx; i++)
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);
227.  	    } else {
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);
232.  		}
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);
237.  		}
238.  	    }
239.      }
240.  
241.      if(nx > max_rx) max_rx = nx - 1; /* nx is just past valid region */
242.      if(sy > max_ry) max_ry = sy;
243.  }
244.  

wallify_map

245.  /*
246.   *	If we have drawn a map without walls, this allows us to
247.   *	auto-magically wallify it.  Taken from lev_main.c.
248.   */
249.  STATIC_OVL void
250.  wallify_map()
251.  {
252.  
253.      int x, y, xx, yy;
254.  
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;
263.  			}
264.  	    }
265.  }
266.  

join_map

267.  STATIC_OVL void
268.  join_map(bg_typ, fg_typ)
269.  	schar	bg_typ, fg_typ;
270.  {
271.      register struct mkroom *croom, *croom2;
272.  
273.      register int i, j;
274.      int sx, sy;
275.      coord sm, em;
276.  
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) {
281.  		min_rx = max_rx = i;
282.  		min_ry = max_ry = j;
283.  		n_loc_filled = 0;
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,
287.  			     FALSE, OROOM, TRUE);
288.  		    rooms[nroom-1].irregular = TRUE;
289.  		    if(nroom >= (MAXNROFROOMS*2))
290.  			goto joinm;
291.  		} else {
292.  		    /*
293.  		     * it's a tiny hole; erase it from the map to avoid
294.  		     * having the player end up here with no way out.
295.  		     */
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;
302.  			    }
303.  		}
304.  	    }
305.  	}
306.  
307.  joinm:
308.      /*
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.
313.       */
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);
324.  	}
325.  
326.  	(void) dig_corridor(&sm, &em, FALSE, fg_typ, bg_typ);
327.  
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))) {
332.  	    croom = croom2;
333.  	}
334.  	croom2++; /* always increment the next room */
335.      }
336.  }
337.  

finish_map

338.  STATIC_OVL void
339.  finish_map(fg_typ, bg_typ, lit, walled)
340.  	schar	fg_typ, bg_typ;
341.  	boolean	lit, walled;
342.  {
343.  	int	i, j;
344.  
345.  	if(walled) wallify_map();
346.  
347.  	if(lit) {
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++)
356.  		rooms[i].rlit = 1;
357.  	}
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;
363.  }
364.  

remove_rooms

365.  /*
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.
373.   */
374.  void
375.  remove_rooms(lx, ly, hx, hy)
376.      int lx, ly, hx, hy;
377.  {
378.      int i;
379.      struct mkroom *croom;
380.  
381.      for (i = nroom - 1; i >= 0; --i) {
382.  	croom = &rooms[i];
383.  	if (croom->hx < lx || croom->lx >= hx ||
384.  	    croom->hy < ly || croom->ly >= hy) continue; /* no overlap */
385.  
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 */
389.  
390.  	    if (!croom->irregular) impossible("regular room in joined map");
391.  	} else {
392.  	    /* total overlap, remove the room */
393.  	    remove_room((unsigned)i);
394.  	}
395.      }
396.  }
397.  

remove_room

398.  /*
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.
403.   */
404.  STATIC_OVL void
405.  remove_room(roomno)
406.      unsigned roomno;
407.  {
408.      struct mkroom *croom = &rooms[roomno];
409.      struct mkroom *maxroom = &rooms[--nroom];
410.      int i, j;
411.      unsigned oroomno;
412.  
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));
419.  
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;
427.  	    }
428.      }
429.  
430.      maxroom->hx = -1;			/* just like add_room */
431.  }
432.  

mkmap

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 */
436.  
437.  void
438.  mkmap(init_lev)
439.  	lev_init	*init_lev;
440.  {
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;
447.  	int i;
448.  
449.  	if(lit < 0)
450.  	    lit = (rnd(1+abs(depth(&u.uz))) < 11 && rn2(77)) ? 1 : 0;
451.  
452.  	new_locations = (char *)alloc((WIDTH+1) * HEIGHT);
453.  
454.  	init_map(bg_typ);
455.  	init_fill(bg_typ, fg_typ);
456.  
457.  	for(i = 0; i < N_P1_ITER; i++)
458.  	    pass_one(bg_typ, fg_typ);
459.  
460.  	for(i = 0; i < N_P2_ITER; i++)
461.  	pass_two(bg_typ, fg_typ);
462.  
463.  	if(smooth)
464.  	    for(i = 0; i < N_P3_ITER; i++)
465.  		pass_three(bg_typ, fg_typ);
466.  
467.  	if(join)
468.  	    join_map(bg_typ, fg_typ);
469.  
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;
475.  	}
476.  	free(new_locations);
477.  }
478.  
479.  /*mkmap.c*/