Source:NetHack 5.0.0/src/mkmap.c
Jump to navigation
Jump to search
Below is the full text to mkmap.c from the source code of NetHack 5.0.0. To link to a particular line, write [[Source:NetHack 5.0.0/src/mkmap.c#line12]], for example.
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.
1. /* NetHack 5.0 mkmap.c $NHDT-Date: 1717432093 2024/06/03 16:28:13 $ $NHDT-Branch: NetHack-3.7 $:$NHDT-Revision: 1.40 $ */ 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. staticfn void init_map(schar); 12. staticfn void init_fill(schar, schar); 13. staticfn schar get_map(coordxy, coordxy, schar); 14. staticfn void pass_one(schar, schar); 15. staticfn void pass_two(schar, schar); 16. staticfn void pass_three(schar, schar); 17. staticfn void join_map_cleanup(void); 18. staticfn void join_map(schar, schar); 19. staticfn void finish_map(schar, schar, boolean, boolean, boolean); 20. staticfn void remove_room(unsigned); 21. void mkmap(lev_init *); 22. 23. staticfn void 24. init_map(schar bg_typ) 25. { 26. coordxy x, y; 27. 28. for (x = 1; x < COLNO; x++) 29. for (y = 0; y < ROWNO; y++) { 30. levl[x][y].roomno = NO_ROOM; 31. levl[x][y].typ = bg_typ; 32. levl[x][y].lit = FALSE; 33. } 34. } 35. 36. staticfn void 37. init_fill(schar bg_typ, schar fg_typ) 38. { 39. coordxy x, y; 40. long limit, count; 41. 42. limit = (WIDTH * HEIGHT * 2) / 5; 43. count = 0; 44. while (count < limit) { 45. x = (coordxy) rn1(WIDTH - 1, 2); 46. y = (coordxy) rnd(HEIGHT - 1); 47. if (levl[x][y].typ == bg_typ) { 48. levl[x][y].typ = fg_typ; 49. count++; 50. } 51. } 52. } 53. 54. staticfn schar 55. get_map(coordxy col, coordxy row, schar bg_typ) 56. { 57. if (col <= 0 || row < 0 || col > WIDTH || row >= HEIGHT) 58. return bg_typ; 59. return levl[col][row].typ; 60. } 61. 62. staticfn const int dirs[16] = { 63. -1, -1 /**/, -1, 0 /**/, -1, 1 /**/, 0, -1 /**/, 64. 0, 1 /**/, 1, -1 /**/, 1, 0 /**/, 1, 1 65. }; 66. 67. staticfn void 68. pass_one(schar bg_typ, schar fg_typ) 69. { 70. coordxy x, y; 71. short count, dr; 72. 73. for (x = 2; x <= WIDTH; x++) 74. for (y = 1; y < HEIGHT; y++) { 75. for (count = 0, dr = 0; dr < 8; dr++) 76. if (get_map(x + dirs[dr * 2], y + dirs[(dr * 2) + 1], bg_typ) 77. == fg_typ) 78. count++; 79. 80. switch (count) { 81. case 0: /* death */ 82. case 1: 83. case 2: 84. levl[x][y].typ = bg_typ; 85. break; 86. case 5: 87. case 6: 88. case 7: 89. case 8: 90. levl[x][y].typ = fg_typ; 91. break; 92. default: 93. break; 94. } 95. } 96. } 97. 98. #define new_loc(i, j) *(gn.new_locations + ((j) * (WIDTH + 1)) + (i)) 99. 100. staticfn void 101. pass_two(schar bg_typ, schar fg_typ) 102. { 103. coordxy x, y; 104. short count, dr; 105. 106. for (x = 2; x <= WIDTH; x++) 107. for (y = 1; y < HEIGHT; y++) { 108. for (count = 0, dr = 0; dr < 8; dr++) 109. if (get_map(x + dirs[dr * 2], y + dirs[(dr * 2) + 1], bg_typ) 110. == fg_typ) 111. count++; 112. if (count == 5) 113. new_loc(x, y) = bg_typ; 114. else 115. new_loc(x, y) = get_map(x, y, bg_typ); 116. } 117. 118. for (x = 2; x <= WIDTH; x++) 119. for (y = 1; y < HEIGHT; y++) 120. levl[x][y].typ = new_loc(x, y); 121. } 122. 123. staticfn void 124. pass_three(schar bg_typ, schar fg_typ) 125. { 126. coordxy x, y; 127. short count, dr; 128. 129. for (x = 2; x <= WIDTH; x++) 130. for (y = 1; y < HEIGHT; y++) { 131. for (count = 0, dr = 0; dr < 8; dr++) 132. if (get_map(x + dirs[dr * 2], y + dirs[(dr * 2) + 1], bg_typ) 133. == fg_typ) 134. count++; 135. if (count < 3) 136. new_loc(x, y) = bg_typ; 137. else 138. new_loc(x, y) = get_map(x, y, bg_typ); 139. } 140. 141. for (x = 2; x <= WIDTH; x++) 142. for (y = 1; y < HEIGHT; y++) 143. levl[x][y].typ = new_loc(x, y); 144. } 145. 146. /* 147. * use a flooding algorithm to find all locations that should 148. * have the same rm number as the current location. 149. * if anyroom is TRUE, use IS_ROOM to check room membership instead of 150. * exactly matching levl[sx][sy].typ and walls are included as well. 151. */ 152. void 153. flood_fill_rm( 154. coordxy sx, 155. coordxy sy, 156. int rmno, 157. boolean lit, 158. boolean anyroom) 159. { 160. coordxy i, nx; 161. schar fg_typ = levl[sx][sy].typ; 162. 163. /* back up to find leftmost uninitialized location */ 164. while (sx > 0 && (anyroom ? IS_ROOM(levl[sx][sy].typ) 165. : levl[sx][sy].typ == fg_typ) 166. && (int) levl[sx][sy].roomno != rmno) 167. sx--; 168. sx++; /* compensate for extra decrement */ 169. 170. /* assume sx,sy is valid */ 171. if (sx < gm.min_rx) 172. gm.min_rx = sx; 173. if (sy < gm.min_ry) 174. gm.min_ry = sy; 175. 176. for (i = sx; i <= WIDTH && levl[i][sy].typ == fg_typ; i++) { 177. levl[i][sy].roomno = rmno; 178. levl[i][sy].lit = lit; 179. if (anyroom) { 180. /* add walls to room as well */ 181. coordxy ii, jj; 182. for (ii = (i == sx ? i - 1 : i); ii <= i + 1; ii++) 183. for (jj = sy - 1; jj <= sy + 1; jj++) 184. if (isok(ii, jj) && (IS_WALL(levl[ii][jj].typ) 185. || IS_DOOR(levl[ii][jj].typ) 186. || levl[ii][jj].typ == SDOOR)) { 187. levl[ii][jj].edge = 1; 188. if (lit) 189. levl[ii][jj].lit = lit; 190. 191. if (levl[ii][jj].roomno == NO_ROOM) 192. levl[ii][jj].roomno = rmno; 193. else if ((int) levl[ii][jj].roomno != rmno) 194. levl[ii][jj].roomno = SHARED; 195. } 196. } 197. gn.n_loc_filled++; 198. } 199. nx = i; 200. 201. if (isok(sx, sy - 1)) { 202. for (i = sx; i < nx; i++) 203. if (levl[i][sy - 1].typ == fg_typ) { 204. if ((int) levl[i][sy - 1].roomno != rmno) 205. flood_fill_rm(i, sy - 1, rmno, lit, anyroom); 206. } else { 207. if ((i > sx || isok(i - 1, sy - 1)) 208. && levl[i - 1][sy - 1].typ == fg_typ) { 209. if ((int) levl[i - 1][sy - 1].roomno != rmno) 210. flood_fill_rm(i - 1, sy - 1, rmno, lit, anyroom); 211. } 212. if ((i < nx - 1 || isok(i + 1, sy - 1)) 213. && levl[i + 1][sy - 1].typ == fg_typ) { 214. if ((int) levl[i + 1][sy - 1].roomno != rmno) 215. flood_fill_rm(i + 1, sy - 1, rmno, lit, anyroom); 216. } 217. } 218. } 219. if (isok(sx, sy + 1)) { 220. for (i = sx; i < nx; i++) 221. if (levl[i][sy + 1].typ == fg_typ) { 222. if ((int) levl[i][sy + 1].roomno != rmno) 223. flood_fill_rm(i, sy + 1, rmno, lit, anyroom); 224. } else { 225. if ((i > sx || isok(i - 1, sy + 1)) 226. && levl[i - 1][sy + 1].typ == fg_typ) { 227. if ((int) levl[i - 1][sy + 1].roomno != rmno) 228. flood_fill_rm(i - 1, sy + 1, rmno, lit, anyroom); 229. } 230. if ((i < nx - 1 || isok(i + 1, sy + 1)) 231. && levl[i + 1][sy + 1].typ == fg_typ) { 232. if ((int) levl[i + 1][sy + 1].roomno != rmno) 233. flood_fill_rm(i + 1, sy + 1, rmno, lit, anyroom); 234. } 235. } 236. } 237. 238. if (nx > gm.max_rx) 239. gm.max_rx = nx - 1; /* nx is just past valid region */ 240. if (sy > gm.max_ry) 241. gm.max_ry = sy; 242. } 243. 244. /* join_map uses temporary rooms; clean up after it */ 245. staticfn void 246. join_map_cleanup(void) 247. { 248. coordxy x, y; 249. 250. for (x = 1; x < COLNO; x++) 251. for (y = 0; y < ROWNO; y++) 252. levl[x][y].roomno = NO_ROOM; 253. svn.nroom = gn.nsubroom = 0; 254. svr.rooms[svn.nroom].hx = gs.subrooms[gn.nsubroom].hx = -1; 255. } 256. 257. staticfn void 258. join_map(schar bg_typ, schar fg_typ) 259. { 260. struct mkroom *croom, *croom2; 261. 262. coordxy x, y, sx, sy; 263. coord sm, em; 264. 265. /* first, use flood filling to find all of the regions that need joining 266. */ 267. for (x = 2; x <= WIDTH; x++) 268. for (y = 1; y < HEIGHT; y++) { 269. if (levl[x][y].typ == fg_typ && levl[x][y].roomno == NO_ROOM) { 270. gm.min_rx = gm.max_rx = x; 271. gm.min_ry = gm.max_ry = y; 272. gn.n_loc_filled = 0; 273. flood_fill_rm(x, y, svn.nroom + ROOMOFFSET, FALSE, FALSE); 274. if (gn.n_loc_filled > 3) { 275. add_room(gm.min_rx, gm.min_ry, gm.max_rx, gm.max_ry, 276. FALSE, OROOM, TRUE); 277. svr.rooms[svn.nroom - 1].irregular = TRUE; 278. if (svn.nroom >= (MAXNROFROOMS * 2)) 279. goto joinm; 280. } else { 281. /* 282. * it's a tiny hole; erase it from the map to avoid 283. * having the player end up here with no way out. 284. */ 285. for (sx = gm.min_rx; sx <= gm.max_rx; sx++) 286. for (sy = gm.min_ry; sy <= gm.max_ry; sy++) 287. if ((int) levl[sx][sy].roomno 288. == svn.nroom + ROOMOFFSET) { 289. levl[sx][sy].typ = bg_typ; 290. levl[sx][sy].roomno = NO_ROOM; 291. } 292. } 293. } 294. } 295. 296. joinm: 297. /* 298. * Ok, now we can actually join the regions with fg_typ's. 299. * The rooms are already sorted due to the previous loop, 300. * so don't call sort_rooms(), which can screw up the roomno's 301. * validity in the levl structure. 302. */ 303. for (croom = &svr.rooms[0], croom2 = croom + 1; 304. croom2 < &svr.rooms[svn.nroom]; ) { 305. /* pick random starting and end locations for "corridor" */ 306. if (!somexy(croom, &sm) || !somexy(croom2, &em)) { 307. /* ack! -- the level is going to be busted */ 308. /* arbitrarily pick centers of both rooms and hope for the best */ 309. impossible("No start/end room loc in join_map."); 310. sm.x = croom->lx + ((croom->hx - croom->lx) / 2); 311. sm.y = croom->ly + ((croom->hy - croom->ly) / 2); 312. em.x = croom2->lx + ((croom2->hx - croom2->lx) / 2); 313. em.y = croom2->ly + ((croom2->hy - croom2->ly) / 2); 314. } 315. 316. (void) dig_corridor(&sm, &em, NULL, FALSE, fg_typ, bg_typ); 317. 318. /* choose next region to join */ 319. /* only increment croom if croom and croom2 are non-overlapping */ 320. if (croom2->lx > croom->hx 321. || ((croom2->ly > croom->hy || croom2->hy < croom->ly) 322. && rn2(3))) { 323. croom = croom2; 324. } 325. croom2++; /* always increment the next room */ 326. } 327. join_map_cleanup(); 328. } 329. 330. staticfn void 331. finish_map( 332. schar fg_typ, 333. schar bg_typ, 334. boolean lit, 335. boolean walled, 336. boolean icedpools) 337. { 338. coordxy x, y; 339. 340. if (walled) 341. wallify_map(1, 0, COLNO-1, ROWNO-1); 342. 343. if (lit) { 344. for (x = 1; x < COLNO; x++) 345. for (y = 0; y < ROWNO; y++) 346. if ((!IS_OBSTRUCTED(fg_typ) && levl[x][y].typ == fg_typ) 347. || (!IS_OBSTRUCTED(bg_typ) && levl[x][y].typ == bg_typ) 348. || (bg_typ == TREE && levl[x][y].typ == bg_typ) 349. || (walled && IS_WALL(levl[x][y].typ))) 350. levl[x][y].lit = TRUE; 351. for (x = 0; x < svn.nroom; x++) 352. svr.rooms[x].rlit = 1; 353. } 354. /* light lava even if everything's otherwise unlit; 355. ice might be frozen pool rather than frozen moat */ 356. for (x = 1; x < COLNO; x++) 357. for (y = 0; y < ROWNO; y++) { 358. if (levl[x][y].typ == LAVAPOOL) 359. levl[x][y].lit = TRUE; 360. else if (levl[x][y].typ == ICE) 361. levl[x][y].icedpool = icedpools ? ICED_POOL : ICED_MOAT; 362. } 363. } 364. 365. /* 366. * TODO: If we really want to remove rooms after a map is plopped down 367. * in a special level, this needs to be rewritten - the maps may have 368. * holes in them ("x" mapchar), leaving parts of rooms still on the map. 369. * 370. * When level processed by join_map is overlaid by a MAP, some rooms may no 371. * longer be valid. All rooms in the region lx <= x < hx, ly <= y < hy are 372. * removed. Rooms partially in the region are truncated. This function 373. * must be called before the REGIONs or ROOMs of the map are processed, or 374. * those rooms will be removed as well. Assumes roomno fields in the 375. * region are already cleared, and roomno and irregular fields outside the 376. * region are all set. 377. */ 378. void 379. remove_rooms(coordxy lx, coordxy ly, coordxy hx, coordxy hy) 380. { 381. int i; 382. struct mkroom *croom; 383. 384. for (i = svn.nroom - 1; i >= 0; --i) { 385. croom = &svr.rooms[i]; 386. if (croom->hx < lx || croom->lx >= hx || croom->hy < ly 387. || croom->ly >= hy) 388. continue; /* no overlap */ 389. 390. if (croom->lx < lx || croom->hx >= hx || croom->ly < ly 391. || croom->hy >= hy) { /* partial overlap */ 392. /* TODO: ensure remaining parts of room are still joined */ 393. 394. if (!croom->irregular) 395. impossible("regular room in joined map"); 396. } else { 397. /* total overlap, remove the room */ 398. remove_room((unsigned) i); 399. } 400. } 401. } 402. 403. /* 404. * Remove roomno from the rooms array, decrementing nroom. 405. * The last room is swapped with the being-removed room and locations 406. * within it have their roomno field updated. Other rooms are unaffected. 407. * Assumes level structure contents corresponding to roomno have already 408. * been reset. 409. * Currently handles only the removal of rooms that have no subrooms. 410. */ 411. staticfn void 412. remove_room(unsigned int roomno) 413. { 414. struct mkroom *croom = &svr.rooms[roomno]; 415. struct mkroom *maxroom = &svr.rooms[--svn.nroom]; 416. coordxy x, y; 417. unsigned oroomno; 418. 419. if (croom != maxroom) { 420. /* since the order in the array only matters for making corridors, 421. * copy the last room over the one being removed on the assumption 422. * that corridors have already been dug. */ 423. *croom = *maxroom; 424. 425. /* since maxroom moved, update affected level roomno values */ 426. oroomno = svn.nroom + ROOMOFFSET; 427. roomno += ROOMOFFSET; 428. for (x = croom->lx; x <= croom->hx; ++x) 429. for (y = croom->ly; y <= croom->hy; ++y) { 430. if (levl[x][y].roomno == oroomno) 431. levl[x][y].roomno = roomno; 432. } 433. } 434. 435. maxroom->hx = -1; /* just like add_room */ 436. } 437. 438. #define N_P1_ITER 1 /* tune map generation via this value */ 439. #define N_P2_ITER 1 /* tune map generation via this value */ 440. #define N_P3_ITER 2 /* tune map smoothing via this value */ 441. 442. boolean 443. litstate_rnd(int litstate) 444. { 445. if (litstate < 0) 446. return (rnd(1 + abs(depth(&u.uz))) < 11 && rn2(77)) ? TRUE : FALSE; 447. return (boolean) litstate; 448. } 449. 450. void 451. mkmap(lev_init *init_lev) 452. { 453. schar bg_typ = init_lev->bg, fg_typ = init_lev->fg; 454. boolean smooth = init_lev->smoothed, join = init_lev->joined; 455. xint16 lit = init_lev->lit, walled = init_lev->walled; 456. int i; 457. 458. lit = litstate_rnd(lit); 459. 460. gn.new_locations = (char *) alloc((WIDTH + 1) * HEIGHT); 461. 462. init_map(bg_typ); 463. init_fill(bg_typ, fg_typ); 464. 465. for (i = 0; i < N_P1_ITER; i++) 466. pass_one(bg_typ, fg_typ); 467. 468. for (i = 0; i < N_P2_ITER; i++) 469. pass_two(bg_typ, fg_typ); 470. 471. if (smooth) 472. for (i = 0; i < N_P3_ITER; i++) 473. pass_three(bg_typ, fg_typ); 474. 475. if (join) 476. join_map(bg_typ, fg_typ); 477. 478. finish_map(fg_typ, bg_typ, (boolean) lit, (boolean) walled, 479. init_lev->icedpools); 480. /* a walled, joined level is cavernous, not mazelike -dlc */ 481. if (walled && join) { 482. svl.level.flags.is_maze_lev = FALSE; 483. svl.level.flags.is_cavernous_lev = TRUE; 484. } 485. free(gn.new_locations); 486. } 487. 488. /*mkmap.c*/