1 /**
2 * @file gendung.cpp
3 *
4 * Implementation of general dungeon generation code.
5 */
6 #include "all.h"
7 #include "options.h"
8
9 DEVILUTION_BEGIN_NAMESPACE
10
11 /** Contains the tile IDs of the map. */
12 BYTE dungeon[DMAXX][DMAXY];
13 /** Contains a backup of the tile IDs of the map. */
14 BYTE pdungeon[DMAXX][DMAXY];
15 char dflags[DMAXX][DMAXY];
16 /** Specifies the active set level X-coordinate of the map. */
17 int setpc_x;
18 /** Specifies the active set level Y-coordinate of the map. */
19 int setpc_y;
20 /** Specifies the width of the active set level of the map. */
21 int setpc_w;
22 /** Specifies the height of the active set level of the map. */
23 int setpc_h;
24 /** Contains the contents of the single player quest DUN file. */
25 BYTE *pSetPiece;
26 /** Specifies whether a single player quest DUN has been loaded. */
27 BOOL setloadflag;
28 BYTE *pSpecialCels;
29 /** Specifies the tile definitions of the active dungeon type; (e.g. levels/l1data/l1.til). */
30 BYTE *pMegaTiles;
31 BYTE *pLevelPieces;
32 BYTE *pDungeonCels;
33 /**
34 * List of transparancy masks to use for dPieces
35 */
36 char block_lvid[MAXTILES + 1];
37 /**
38 * List of light blocking dPieces
39 */
40 BOOLEAN nBlockTable[MAXTILES + 1];
41 /**
42 * List of path blocking dPieces
43 */
44 BOOLEAN nSolidTable[MAXTILES + 1];
45 /**
46 * List of transparent dPieces
47 */
48 BOOLEAN nTransTable[MAXTILES + 1];
49 /**
50 * List of missile blocking dPieces
51 */
52 BOOLEAN nMissileTable[MAXTILES + 1];
53 BOOLEAN nTrapTable[MAXTILES + 1];
54 /** Specifies the minimum X-coordinate of the map. */
55 int dminx;
56 /** Specifies the minimum Y-coordinate of the map. */
57 int dminy;
58 /** Specifies the maximum X-coordinate of the map. */
59 int dmaxx;
60 /** Specifies the maximum Y-coordinate of the map. */
61 int dmaxy;
62 int gnDifficulty;
63 /** Specifies the active dungeon type of the current game. */
64 dungeon_type leveltype;
65 /** Specifies the active dungeon level of the current game. */
66 BYTE currlevel;
67 BOOLEAN setlevel;
68 /** Specifies the active quest level of the current game. */
69 BYTE setlvlnum;
70 /** Level type of the active quest level */
71 dungeon_type setlvltype;
72 /** Specifies the player viewpoint X-coordinate of the map. */
73 int ViewX;
74 /** Specifies the player viewpoint Y-coordinate of the map. */
75 int ViewY;
76 int ViewBX;
77 int ViewBY;
78 int ViewDX;
79 int ViewDY;
80 ScrollStruct ScrollInfo;
81 /** Specifies the level viewpoint X-coordinate of the map. */
82 int LvlViewX;
83 /** Specifies the level viewpoint Y-coordinate of the map. */
84 int LvlViewY;
85 int MicroTileLen;
86 char TransVal;
87 /** Specifies the active transparency indices. */
88 BOOLEAN TransList[256];
89 /** Contains the piece IDs of each tile on the map. */
90 int dPiece[MAXDUNX][MAXDUNY];
91 /** Specifies the dungeon piece information for a given coordinate and block number. */
92 MICROS dpiece_defs_map_2[MAXDUNX][MAXDUNY];
93 /** Specifies the transparency at each coordinate of the map. */
94 char dTransVal[MAXDUNX][MAXDUNY];
95 char dLight[MAXDUNX][MAXDUNY];
96 char dPreLight[MAXDUNX][MAXDUNY];
97 char dFlags[MAXDUNX][MAXDUNY];
98 /** Contains the player numbers (players array indices) of the map. */
99 char dPlayer[MAXDUNX][MAXDUNY];
100 /**
101 * Contains the NPC numbers of the map. The NPC number represents a
102 * towner number (towners array index) in Tristram and a monster number
103 * (monsters array index) in the dungeon.
104 */
105 int dMonster[MAXDUNX][MAXDUNY];
106 /**
107 * Contains the dead numbers (deads array indices) and dead direction of
108 * the map, encoded as specified by the pseudo-code below.
109 * dDead[x][y] & 0x1F - index of dead
110 * dDead[x][y] >> 0x5 - direction
111 */
112 char dDead[MAXDUNX][MAXDUNY];
113 /** Contains the object numbers (objects array indices) of the map. */
114 char dObject[MAXDUNX][MAXDUNY];
115 /** Contains the item numbers (items array indices) of the map. */
116 char dItem[MAXDUNX][MAXDUNY];
117 /** Contains the missile numbers (missiles array indices) of the map. */
118 char dMissile[MAXDUNX][MAXDUNY];
119 /**
120 * Contains the arch frame numbers of the map from the special tileset
121 * (e.g. "levels/l1data/l1s.cel"). Note, the special tileset of Tristram (i.e.
122 * "levels/towndata/towns.cel") contains trees rather than arches.
123 */
124 char dSpecial[MAXDUNX][MAXDUNY];
125 int themeCount;
126 THEME_LOC themeLoc[MAXTHEMES];
127
FillSolidBlockTbls()128 void FillSolidBlockTbls()
129 {
130 BYTE bv;
131 DWORD i, dwTiles;
132 BYTE *pSBFile, *pTmp;
133
134 memset(nBlockTable, 0, sizeof(nBlockTable));
135 memset(nSolidTable, 0, sizeof(nSolidTable));
136 memset(nTransTable, 0, sizeof(nTransTable));
137 memset(nMissileTable, 0, sizeof(nMissileTable));
138 memset(nTrapTable, 0, sizeof(nTrapTable));
139
140 switch (leveltype) {
141 case DTYPE_TOWN:
142 if (gbIsHellfire)
143 pSBFile = LoadFileInMem("NLevels\\TownData\\Town.SOL", &dwTiles);
144 else
145 pSBFile = LoadFileInMem("Levels\\TownData\\Town.SOL", &dwTiles);
146 break;
147 case DTYPE_CATHEDRAL:
148 if (currlevel < 17)
149 pSBFile = LoadFileInMem("Levels\\L1Data\\L1.SOL", &dwTiles);
150 else
151 pSBFile = LoadFileInMem("NLevels\\L5Data\\L5.SOL", &dwTiles);
152 break;
153 case DTYPE_CATACOMBS:
154 pSBFile = LoadFileInMem("Levels\\L2Data\\L2.SOL", &dwTiles);
155 break;
156 case DTYPE_CAVES:
157 if (currlevel < 17)
158 pSBFile = LoadFileInMem("Levels\\L3Data\\L3.SOL", &dwTiles);
159 else
160 pSBFile = LoadFileInMem("NLevels\\L6Data\\L6.SOL", &dwTiles);
161 break;
162 case DTYPE_HELL:
163 pSBFile = LoadFileInMem("Levels\\L4Data\\L4.SOL", &dwTiles);
164 break;
165 default:
166 app_fatal("FillSolidBlockTbls");
167 }
168
169 pTmp = pSBFile;
170
171 for (i = 1; i <= dwTiles; i++) {
172 bv = *pTmp++;
173 if (bv & 1)
174 nSolidTable[i] = TRUE;
175 if (bv & 2)
176 nBlockTable[i] = TRUE;
177 if (bv & 4)
178 nMissileTable[i] = TRUE;
179 if (bv & 8)
180 nTransTable[i] = TRUE;
181 if (bv & 0x80)
182 nTrapTable[i] = TRUE;
183 block_lvid[i] = (bv & 0x70) >> 4; /* beta: (bv >> 4) & 7 */
184 }
185
186 mem_free_dbg(pSBFile);
187 }
188
SetDungeonMicros()189 void SetDungeonMicros()
190 {
191 int i, x, y, lv, blocks;
192 WORD *pPiece;
193 MICROS *pMap;
194
195 if (leveltype == DTYPE_TOWN) {
196 MicroTileLen = 16;
197 blocks = 16;
198 } else if (leveltype != DTYPE_HELL) {
199 MicroTileLen = 10;
200 blocks = 10;
201 } else {
202 MicroTileLen = 12;
203 blocks = 16;
204 }
205
206 for (y = 0; y < MAXDUNY; y++) {
207 for (x = 0; x < MAXDUNX; x++) {
208 lv = dPiece[x][y];
209 pMap = &dpiece_defs_map_2[x][y];
210 if (lv != 0) {
211 lv--;
212 if (leveltype != DTYPE_HELL && leveltype != DTYPE_TOWN)
213 pPiece = (WORD *)&pLevelPieces[20 * lv];
214 else
215 pPiece = (WORD *)&pLevelPieces[32 * lv];
216 for (i = 0; i < blocks; i++)
217 pMap->mt[i] = SDL_SwapLE16(pPiece[(i & 1) + blocks - 2 - (i & 0xE)]);
218 } else {
219 for (i = 0; i < blocks; i++)
220 pMap->mt[i] = 0;
221 }
222 }
223 }
224 }
225
DRLG_InitTrans()226 void DRLG_InitTrans()
227 {
228 memset(dTransVal, 0, sizeof(dTransVal));
229 memset(TransList, 0, sizeof(TransList));
230 TransVal = 1;
231 }
232
DRLG_MRectTrans(int x1,int y1,int x2,int y2)233 void DRLG_MRectTrans(int x1, int y1, int x2, int y2)
234 {
235 int i, j;
236
237 x1 = 2 * x1 + 17;
238 y1 = 2 * y1 + 17;
239 x2 = 2 * x2 + 16;
240 y2 = 2 * y2 + 16;
241
242 for (j = y1; j <= y2; j++) {
243 for (i = x1; i <= x2; i++) {
244 dTransVal[i][j] = TransVal;
245 }
246 }
247
248 TransVal++;
249 }
250
DRLG_RectTrans(int x1,int y1,int x2,int y2)251 void DRLG_RectTrans(int x1, int y1, int x2, int y2)
252 {
253 int i, j;
254
255 for (j = y1; j <= y2; j++) {
256 for (i = x1; i <= x2; i++) {
257 dTransVal[i][j] = TransVal;
258 }
259 }
260 TransVal++;
261 }
262
DRLG_CopyTrans(int sx,int sy,int dx,int dy)263 void DRLG_CopyTrans(int sx, int sy, int dx, int dy)
264 {
265 dTransVal[dx][dy] = dTransVal[sx][sy];
266 }
267
DRLG_ListTrans(int num,BYTE * List)268 void DRLG_ListTrans(int num, BYTE *List)
269 {
270 int i;
271 BYTE x1, y1, x2, y2;
272
273 for (i = 0; i < num; i++) {
274 x1 = *List++;
275 y1 = *List++;
276 x2 = *List++;
277 y2 = *List++;
278 DRLG_RectTrans(x1, y1, x2, y2);
279 }
280 }
281
DRLG_AreaTrans(int num,BYTE * List)282 void DRLG_AreaTrans(int num, BYTE *List)
283 {
284 int i;
285 BYTE x1, y1, x2, y2;
286
287 for (i = 0; i < num; i++) {
288 x1 = *List++;
289 y1 = *List++;
290 x2 = *List++;
291 y2 = *List++;
292 DRLG_RectTrans(x1, y1, x2, y2);
293 TransVal--;
294 }
295 TransVal++;
296 }
297
DRLG_InitSetPC()298 void DRLG_InitSetPC()
299 {
300 setpc_x = 0;
301 setpc_y = 0;
302 setpc_w = 0;
303 setpc_h = 0;
304 }
305
DRLG_SetPC()306 void DRLG_SetPC()
307 {
308 int i, j, x, y, w, h;
309
310 w = 2 * setpc_w;
311 h = 2 * setpc_h;
312 x = 2 * setpc_x + 16;
313 y = 2 * setpc_y + 16;
314
315 for (j = 0; j < h; j++) {
316 for (i = 0; i < w; i++) {
317 dFlags[i + x][j + y] |= BFLAG_POPULATED;
318 }
319 }
320 }
321
Make_SetPC(int x,int y,int w,int h)322 void Make_SetPC(int x, int y, int w, int h)
323 {
324 int i, j, dx, dy, dh, dw;
325
326 dw = 2 * w;
327 dh = 2 * h;
328 dx = 2 * x + 16;
329 dy = 2 * y + 16;
330
331 for (j = 0; j < dh; j++) {
332 for (i = 0; i < dw; i++) {
333 dFlags[i + dx][j + dy] |= BFLAG_POPULATED;
334 }
335 }
336 }
337
DRLG_WillThemeRoomFit(int floor,int x,int y,int minSize,int maxSize,int * width,int * height)338 BOOL DRLG_WillThemeRoomFit(int floor, int x, int y, int minSize, int maxSize, int *width, int *height)
339 {
340 int ii, xx, yy;
341 int xSmallest, ySmallest;
342 int xArray[20], yArray[20];
343 int xCount, yCount;
344 BOOL yFlag, xFlag;
345
346 yFlag = TRUE;
347 xFlag = TRUE;
348 xCount = 0;
349 yCount = 0;
350
351 // BUGFIX: change '&&' to '||' (fixed)
352 if (x > DMAXX - maxSize || y > DMAXY - maxSize) {
353 return FALSE;
354 }
355 if (!SkipThemeRoom(x, y)) {
356 return FALSE;
357 }
358
359 memset(xArray, 0, sizeof(xArray));
360 memset(yArray, 0, sizeof(yArray));
361
362 for (ii = 0; ii < maxSize; ii++) {
363 if (xFlag) {
364 for (xx = x; xx < x + maxSize; xx++) {
365 if (dungeon[xx][y + ii] != floor) {
366 if (xx >= minSize) {
367 break;
368 }
369 xFlag = FALSE;
370 } else {
371 xCount++;
372 }
373 }
374 if (xFlag) {
375 xArray[ii] = xCount;
376 xCount = 0;
377 }
378 }
379 if (yFlag) {
380 for (yy = y; yy < y + maxSize; yy++) {
381 if (dungeon[x + ii][yy] != floor) {
382 if (yy >= minSize) {
383 break;
384 }
385 yFlag = FALSE;
386 } else {
387 yCount++;
388 }
389 }
390 if (yFlag) {
391 yArray[ii] = yCount;
392 yCount = 0;
393 }
394 }
395 }
396
397 for (ii = 0; ii < minSize; ii++) {
398 if (xArray[ii] < minSize || yArray[ii] < minSize) {
399 return FALSE;
400 }
401 }
402
403 xSmallest = xArray[0];
404 ySmallest = yArray[0];
405
406 for (ii = 0; ii < maxSize; ii++) {
407 if (xArray[ii] < minSize || yArray[ii] < minSize) {
408 break;
409 }
410 if (xArray[ii] < xSmallest) {
411 xSmallest = xArray[ii];
412 }
413 if (yArray[ii] < ySmallest) {
414 ySmallest = yArray[ii];
415 }
416 }
417
418 *width = xSmallest - 2;
419 *height = ySmallest - 2;
420 return TRUE;
421 }
422
DRLG_CreateThemeRoom(int themeIndex)423 void DRLG_CreateThemeRoom(int themeIndex)
424 {
425 int xx, yy;
426 const int lx = themeLoc[themeIndex].x;
427 const int ly = themeLoc[themeIndex].y;
428 const int hx = lx + themeLoc[themeIndex].width;
429 const int hy = ly + themeLoc[themeIndex].height;
430
431 for (yy = ly; yy < hy; yy++) {
432 for (xx = lx; xx < hx; xx++) {
433 if (leveltype == DTYPE_CATACOMBS) {
434 if (yy == ly || yy == hy - 1) {
435 dungeon[xx][yy] = 2;
436 } else if (xx == lx || xx == hx - 1) {
437 dungeon[xx][yy] = 1;
438 } else {
439 dungeon[xx][yy] = 3;
440 }
441 }
442 if (leveltype == DTYPE_CAVES) {
443 if (yy == ly || yy == hy - 1) {
444 dungeon[xx][yy] = 134;
445 } else if (xx == lx || xx == hx - 1) {
446 dungeon[xx][yy] = 137;
447 } else {
448 dungeon[xx][yy] = 7;
449 }
450 }
451 if (leveltype == DTYPE_HELL) {
452 if (yy == ly || yy == hy - 1) {
453 dungeon[xx][yy] = 2;
454 } else if (xx == lx || xx == hx - 1) {
455 dungeon[xx][yy] = 1;
456 } else {
457 dungeon[xx][yy] = 6;
458 }
459 }
460 }
461 }
462
463 if (leveltype == DTYPE_CATACOMBS) {
464 dungeon[lx][ly] = 8;
465 dungeon[hx - 1][ly] = 7;
466 dungeon[lx][hy - 1] = 9;
467 dungeon[hx - 1][hy - 1] = 6;
468 }
469 if (leveltype == DTYPE_CAVES) {
470 dungeon[lx][ly] = 150;
471 dungeon[hx - 1][ly] = 151;
472 dungeon[lx][hy - 1] = 152;
473 dungeon[hx - 1][hy - 1] = 138;
474 }
475 if (leveltype == DTYPE_HELL) {
476 dungeon[lx][ly] = 9;
477 dungeon[hx - 1][ly] = 16;
478 dungeon[lx][hy - 1] = 15;
479 dungeon[hx - 1][hy - 1] = 12;
480 }
481
482 if (leveltype == DTYPE_CATACOMBS) {
483 switch (random_(0, 2)) {
484 case 0:
485 dungeon[hx - 1][(ly + hy) / 2] = 4;
486 break;
487 case 1:
488 dungeon[(lx + hx) / 2][hy - 1] = 5;
489 break;
490 }
491 }
492 if (leveltype == DTYPE_CAVES) {
493 switch (random_(0, 2)) {
494 case 0:
495 dungeon[hx - 1][(ly + hy) / 2] = 147;
496 break;
497 case 1:
498 dungeon[(lx + hx) / 2][hy - 1] = 146;
499 break;
500 }
501 }
502 if (leveltype == DTYPE_HELL) {
503 switch (random_(0, 2)) {
504 case 0:
505 yy = (ly + hy) / 2;
506 dungeon[hx - 1][yy - 1] = 53;
507 dungeon[hx - 1][yy] = 6;
508 dungeon[hx - 1][yy + 1] = 52;
509 dungeon[hx - 2][yy - 1] = 54;
510 break;
511 case 1:
512 xx = (lx + hx) / 2;
513 dungeon[xx - 1][hy - 1] = 57;
514 dungeon[xx][hy - 1] = 6;
515 dungeon[xx + 1][hy - 1] = 56;
516 dungeon[xx][hy - 2] = 59;
517 dungeon[xx - 1][hy - 2] = 58;
518 break;
519 }
520 }
521 }
522
DRLG_PlaceThemeRooms(int minSize,int maxSize,int floor,int freq,int rndSize)523 void DRLG_PlaceThemeRooms(int minSize, int maxSize, int floor, int freq, int rndSize)
524 {
525 int i, j;
526 int themeW, themeH;
527 int rv2, min, max;
528
529 themeCount = 0;
530 memset(themeLoc, 0, sizeof(*themeLoc));
531 for (j = 0; j < DMAXY; j++) {
532 for (i = 0; i < DMAXX; i++) {
533 if (dungeon[i][j] == floor && !random_(0, freq) && DRLG_WillThemeRoomFit(floor, i, j, minSize, maxSize, &themeW, &themeH)) {
534 if (rndSize) {
535 min = minSize - 2;
536 max = maxSize - 2;
537 rv2 = min + random_(0, random_(0, themeW - min + 1));
538 if (rv2 >= min && rv2 <= max)
539 themeW = rv2;
540 else
541 themeW = min;
542 rv2 = min + random_(0, random_(0, themeH - min + 1));
543 if (rv2 >= min && rv2 <= max)
544 themeH = rv2;
545 else
546 themeH = min;
547 }
548 themeLoc[themeCount].x = i + 1;
549 themeLoc[themeCount].y = j + 1;
550 themeLoc[themeCount].width = themeW;
551 themeLoc[themeCount].height = themeH;
552 if (leveltype == DTYPE_CAVES)
553 DRLG_RectTrans(2 * i + 20, 2 * j + 20, 2 * (i + themeW) + 15, 2 * (j + themeH) + 15);
554 else
555 DRLG_MRectTrans(i + 1, j + 1, i + themeW, j + themeH);
556 themeLoc[themeCount].ttval = TransVal - 1;
557 DRLG_CreateThemeRoom(themeCount);
558 themeCount++;
559 }
560 }
561 }
562 }
563
DRLG_HoldThemeRooms()564 void DRLG_HoldThemeRooms()
565 {
566 int i, x, y, xx, yy;
567
568 for (i = 0; i < themeCount; i++) {
569 for (y = themeLoc[i].y; y < themeLoc[i].y + themeLoc[i].height - 1; y++) {
570 for (x = themeLoc[i].x; x < themeLoc[i].x + themeLoc[i].width - 1; x++) {
571 xx = 2 * x + 16;
572 yy = 2 * y + 16;
573 dFlags[xx][yy] |= BFLAG_POPULATED;
574 dFlags[xx + 1][yy] |= BFLAG_POPULATED;
575 dFlags[xx][yy + 1] |= BFLAG_POPULATED;
576 dFlags[xx + 1][yy + 1] |= BFLAG_POPULATED;
577 }
578 }
579 }
580 }
581
SkipThemeRoom(int x,int y)582 BOOL SkipThemeRoom(int x, int y)
583 {
584 int i;
585
586 for (i = 0; i < themeCount; i++) {
587 if (x >= themeLoc[i].x - 2 && x <= themeLoc[i].x + themeLoc[i].width + 2
588 && y >= themeLoc[i].y - 2 && y <= themeLoc[i].y + themeLoc[i].height + 2)
589 return FALSE;
590 }
591
592 return TRUE;
593 }
594
InitLevels()595 void InitLevels()
596 {
597 #ifdef _DEBUG
598 if (leveldebug)
599 return;
600 #endif
601
602 currlevel = 0;
603 leveltype = DTYPE_TOWN;
604 setlevel = FALSE;
605 }
606
607 DEVILUTION_END_NAMESPACE
608