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