3 Copyright (C) 2010-2018 celeron55, Perttu Ahola <celeron55@gmail.com>
4 Copyright (C) 2015-2018 paramat
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU Lesser General Public License as published by
8 the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public License along
17 with this program; if not, write to the Free Software Foundation, Inc.,
18 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 #include "dungeongen.h"
32 //#define DGEN_USE_TORCHES
35 ///////////////////////////////////////////////////////////////////////////////
38 DungeonGen::DungeonGen(const NodeDefManager
*ndef
,
39 GenerateNotifier
*gennotify
, DungeonParams
*dparams
)
44 this->gennotify
= gennotify
;
46 #ifdef DGEN_USE_TORCHES
47 c_torch
= ndef
->getId("default:torch");
53 // Default dungeon parameters
56 dp
.c_wall
= ndef
->getId("mapgen_cobble");
57 dp
.c_alt_wall
= ndef
->getId("mapgen_mossycobble");
58 dp
.c_stair
= ndef
->getId("mapgen_stair_cobble");
60 dp
.diagonal_dirs
= false;
61 dp
.only_in_ground
= true;
62 dp
.holesize
= v3s16(1, 2, 1);
63 dp
.corridor_len_min
= 1;
64 dp
.corridor_len_max
= 13;
65 dp
.room_size_min
= v3s16(4, 4, 4);
66 dp
.room_size_max
= v3s16(8, 6, 8);
67 dp
.room_size_large_min
= v3s16(8, 8, 8);
68 dp
.room_size_large_max
= v3s16(16, 16, 16);
69 dp
.large_room_chance
= 1;
72 dp
.notifytype
= GENNOTIFY_DUNGEON
;
75 NoiseParams(-0.4, 1.0, v3f(40.0, 40.0, 40.0), 32474, 6, 1.1, 2.0);
80 void DungeonGen::generate(MMVManip
*vm
, u32 bseed
, v3s16 nmin
, v3s16 nmax
)
82 if (dp
.num_dungeons
== 0)
87 //TimeTaker t("gen dungeons");
90 this->blockseed
= bseed
;
91 random
.seed(bseed
+ 2);
93 // Dungeon generator doesn't modify places which have this set
94 vm
->clearFlag(VMANIP_FLAG_DUNGEON_INSIDE
| VMANIP_FLAG_DUNGEON_PRESERVE
);
96 if (dp
.only_in_ground
) {
97 // Set all air and liquid drawtypes to be untouchable to make dungeons generate
99 // Set 'ignore' to be untouchable to prevent generation in ungenerated neighbor
100 // mapchunks, to avoid dungeon rooms generating outside ground.
101 // Like randomwalk caves, preserve nodes that have 'is_ground_content = false',
102 // to avoid dungeons that generate out beyond the edge of a mapchunk destroying
103 // nodes added by mods in 'register_on_generated()'.
104 for (s16 z
= nmin
.Z
; z
<= nmax
.Z
; z
++) {
105 for (s16 y
= nmin
.Y
; y
<= nmax
.Y
; y
++) {
106 u32 i
= vm
->m_area
.index(nmin
.X
, y
, z
);
107 for (s16 x
= nmin
.X
; x
<= nmax
.X
; x
++) {
108 content_t c
= vm
->m_data
[i
].getContent();
109 NodeDrawType dtype
= ndef
->get(c
).drawtype
;
110 if (dtype
== NDT_AIRLIKE
|| dtype
== NDT_LIQUID
||
111 c
== CONTENT_IGNORE
|| !ndef
->get(c
).is_ground_content
)
112 vm
->m_flags
[i
] |= VMANIP_FLAG_DUNGEON_PRESERVE
;
120 for (u32 i
= 0; i
< dp
.num_dungeons
; i
++)
121 makeDungeon(v3s16(1, 1, 1) * MAP_BLOCKSIZE
);
123 // Optionally convert some structure to alternative structure
124 if (dp
.c_alt_wall
== CONTENT_IGNORE
)
127 for (s16 z
= nmin
.Z
; z
<= nmax
.Z
; z
++)
128 for (s16 y
= nmin
.Y
; y
<= nmax
.Y
; y
++) {
129 u32 i
= vm
->m_area
.index(nmin
.X
, y
, z
);
130 for (s16 x
= nmin
.X
; x
<= nmax
.X
; x
++) {
131 if (vm
->m_data
[i
].getContent() == dp
.c_wall
) {
132 if (NoisePerlin3D(&dp
.np_alt_wall
, x
, y
, z
, blockseed
) > 0.0f
)
133 vm
->m_data
[i
].setContent(dp
.c_alt_wall
);
139 //printf("== gen dungeons: %dms\n", t.stop());
143 void DungeonGen::makeDungeon(v3s16 start_padding
)
145 const v3s16
&areasize
= vm
->m_area
.getExtent();
150 Find place for first room.
153 for (u32 i
= 0; i
< 100 && !fits
; i
++) {
154 if (dp
.large_room_chance
>= 1) {
155 roomsize
.Z
= random
.range(dp
.room_size_large_min
.Z
, dp
.room_size_large_max
.Z
);
156 roomsize
.Y
= random
.range(dp
.room_size_large_min
.Y
, dp
.room_size_large_max
.Y
);
157 roomsize
.X
= random
.range(dp
.room_size_large_min
.X
, dp
.room_size_large_max
.X
);
159 roomsize
.Z
= random
.range(dp
.room_size_min
.Z
, dp
.room_size_max
.Z
);
160 roomsize
.Y
= random
.range(dp
.room_size_min
.Y
, dp
.room_size_max
.Y
);
161 roomsize
.X
= random
.range(dp
.room_size_min
.X
, dp
.room_size_max
.X
);
164 // start_padding is used to disallow starting the generation of
165 // a dungeon in a neighboring generation chunk
166 roomplace
= vm
->m_area
.MinEdge
+ start_padding
;
167 roomplace
.Z
+= random
.range(0, areasize
.Z
- roomsize
.Z
- start_padding
.Z
);
168 roomplace
.Y
+= random
.range(0, areasize
.Y
- roomsize
.Y
- start_padding
.Y
);
169 roomplace
.X
+= random
.range(0, areasize
.X
- roomsize
.X
- start_padding
.X
);
172 Check that we're not putting the room to an unknown place,
173 otherwise it might end up floating in the air
176 for (s16 z
= 0; z
< roomsize
.Z
; z
++)
177 for (s16 y
= 0; y
< roomsize
.Y
; y
++)
178 for (s16 x
= 0; x
< roomsize
.X
; x
++) {
179 v3s16 p
= roomplace
+ v3s16(x
, y
, z
);
180 u32 vi
= vm
->m_area
.index(p
);
181 if ((vm
->m_flags
[vi
] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE
) ||
182 vm
->m_data
[vi
].getContent() == CONTENT_IGNORE
) {
193 Stores the center position of the last room made, so that
194 a new corridor can be started from the last room instead of
195 the new room, if chosen so.
197 v3s16 last_room_center
= roomplace
+ v3s16(roomsize
.X
/ 2, 1, roomsize
.Z
/ 2);
199 for (u32 i
= 0; i
< dp
.num_rooms
; i
++) {
200 // Make a room to the determined place
201 makeRoom(roomsize
, roomplace
);
203 v3s16 room_center
= roomplace
+ v3s16(roomsize
.X
/ 2, 1, roomsize
.Z
/ 2);
205 gennotify
->addEvent(dp
.notifytype
, room_center
);
207 #ifdef DGEN_USE_TORCHES
208 // Place torch at room center (for testing)
209 vm
->m_data
[vm
->m_area
.index(room_center
)] = MapNode(c_torch
);
213 if (i
+ 1 == dp
.num_rooms
)
216 // Determine walker start position
218 bool start_in_last_room
= (random
.range(0, 2) != 0);
220 v3s16 walker_start_place
;
222 if (start_in_last_room
) {
223 walker_start_place
= last_room_center
;
225 walker_start_place
= room_center
;
226 // Store center of current room as the last one
227 last_room_center
= room_center
;
230 // Create walker and find a place for a door
234 m_pos
= walker_start_place
;
235 if (!findPlaceForDoor(doorplace
, doordir
))
238 if (random
.range(0, 1) == 0)
240 makeDoor(doorplace
, doordir
);
242 // Don't actually make a door
243 doorplace
-= doordir
;
245 // Make a random corridor starting from the door
247 v3s16 corridor_end_dir
;
248 makeCorridor(doorplace
, doordir
, corridor_end
, corridor_end_dir
);
250 // Find a place for a random sized room
251 if (dp
.large_room_chance
> 1 && random
.range(1, dp
.large_room_chance
) == 1) {
253 roomsize
.Z
= random
.range(dp
.room_size_large_min
.Z
, dp
.room_size_large_max
.Z
);
254 roomsize
.Y
= random
.range(dp
.room_size_large_min
.Y
, dp
.room_size_large_max
.Y
);
255 roomsize
.X
= random
.range(dp
.room_size_large_min
.X
, dp
.room_size_large_max
.X
);
257 roomsize
.Z
= random
.range(dp
.room_size_min
.Z
, dp
.room_size_max
.Z
);
258 roomsize
.Y
= random
.range(dp
.room_size_min
.Y
, dp
.room_size_max
.Y
);
259 roomsize
.X
= random
.range(dp
.room_size_min
.X
, dp
.room_size_max
.X
);
262 m_pos
= corridor_end
;
263 m_dir
= corridor_end_dir
;
264 if (!findPlaceForRoomDoor(roomsize
, doorplace
, doordir
, roomplace
))
267 if (random
.range(0, 1) == 0)
269 makeDoor(doorplace
, doordir
);
271 // Don't actually make a door
272 roomplace
-= doordir
;
277 void DungeonGen::makeRoom(v3s16 roomsize
, v3s16 roomplace
)
279 MapNode
n_wall(dp
.c_wall
);
280 MapNode
n_air(CONTENT_AIR
);
283 for (s16 z
= 0; z
< roomsize
.Z
; z
++)
284 for (s16 y
= 0; y
< roomsize
.Y
; y
++) {
286 v3s16 p
= roomplace
+ v3s16(0, y
, z
);
287 if (!vm
->m_area
.contains(p
))
289 u32 vi
= vm
->m_area
.index(p
);
290 if (vm
->m_flags
[vi
] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE
)
292 vm
->m_data
[vi
] = n_wall
;
295 v3s16 p
= roomplace
+ v3s16(roomsize
.X
- 1, y
, z
);
296 if (!vm
->m_area
.contains(p
))
298 u32 vi
= vm
->m_area
.index(p
);
299 if (vm
->m_flags
[vi
] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE
)
301 vm
->m_data
[vi
] = n_wall
;
306 for (s16 x
= 0; x
< roomsize
.X
; x
++)
307 for (s16 y
= 0; y
< roomsize
.Y
; y
++) {
309 v3s16 p
= roomplace
+ v3s16(x
, y
, 0);
310 if (!vm
->m_area
.contains(p
))
312 u32 vi
= vm
->m_area
.index(p
);
313 if (vm
->m_flags
[vi
] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE
)
315 vm
->m_data
[vi
] = n_wall
;
318 v3s16 p
= roomplace
+ v3s16(x
, y
, roomsize
.Z
- 1);
319 if (!vm
->m_area
.contains(p
))
321 u32 vi
= vm
->m_area
.index(p
);
322 if (vm
->m_flags
[vi
] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE
)
324 vm
->m_data
[vi
] = n_wall
;
328 // Make +-Y walls (floor and ceiling)
329 for (s16 z
= 0; z
< roomsize
.Z
; z
++)
330 for (s16 x
= 0; x
< roomsize
.X
; x
++) {
332 v3s16 p
= roomplace
+ v3s16(x
, 0, z
);
333 if (!vm
->m_area
.contains(p
))
335 u32 vi
= vm
->m_area
.index(p
);
336 if (vm
->m_flags
[vi
] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE
)
338 vm
->m_data
[vi
] = n_wall
;
341 v3s16 p
= roomplace
+ v3s16(x
,roomsize
. Y
- 1, z
);
342 if (!vm
->m_area
.contains(p
))
344 u32 vi
= vm
->m_area
.index(p
);
345 if (vm
->m_flags
[vi
] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE
)
347 vm
->m_data
[vi
] = n_wall
;
352 for (s16 z
= 1; z
< roomsize
.Z
- 1; z
++)
353 for (s16 y
= 1; y
< roomsize
.Y
- 1; y
++)
354 for (s16 x
= 1; x
< roomsize
.X
- 1; x
++) {
355 v3s16 p
= roomplace
+ v3s16(x
, y
, z
);
356 if (!vm
->m_area
.contains(p
))
358 u32 vi
= vm
->m_area
.index(p
);
359 vm
->m_flags
[vi
] |= VMANIP_FLAG_DUNGEON_UNTOUCHABLE
;
360 vm
->m_data
[vi
] = n_air
;
365 void DungeonGen::makeFill(v3s16 place
, v3s16 size
,
366 u8 avoid_flags
, MapNode n
, u8 or_flags
)
368 for (s16 z
= 0; z
< size
.Z
; z
++)
369 for (s16 y
= 0; y
< size
.Y
; y
++)
370 for (s16 x
= 0; x
< size
.X
; x
++) {
371 v3s16 p
= place
+ v3s16(x
, y
, z
);
372 if (!vm
->m_area
.contains(p
))
374 u32 vi
= vm
->m_area
.index(p
);
375 if (vm
->m_flags
[vi
] & avoid_flags
)
377 vm
->m_flags
[vi
] |= or_flags
;
383 void DungeonGen::makeHole(v3s16 place
)
385 makeFill(place
, dp
.holesize
, 0, MapNode(CONTENT_AIR
),
386 VMANIP_FLAG_DUNGEON_INSIDE
);
390 void DungeonGen::makeDoor(v3s16 doorplace
, v3s16 doordir
)
394 #ifdef DGEN_USE_TORCHES
395 // Place torch (for testing)
396 vm
->m_data
[vm
->m_area
.index(doorplace
)] = MapNode(c_torch
);
401 void DungeonGen::makeCorridor(v3s16 doorplace
, v3s16 doordir
,
402 v3s16
&result_place
, v3s16
&result_dir
)
405 v3s16 p0
= doorplace
;
407 u32 length
= random
.range(dp
.corridor_len_min
, dp
.corridor_len_max
);
408 u32 partlength
= random
.range(dp
.corridor_len_min
, dp
.corridor_len_max
);
412 if (random
.next() % 2 == 0 && partlength
>= 3)
413 make_stairs
= random
.next() % 2 ? 1 : -1;
415 for (u32 i
= 0; i
< length
; i
++) {
420 // Check segment of minimum size corridor is in voxelmanip
421 if (vm
->m_area
.contains(p
) && vm
->m_area
.contains(p
+ v3s16(0, 1, 0))) {
423 makeFill(p
+ v3s16(-1, -1, -1),
424 dp
.holesize
+ v3s16(2, 3, 2),
425 VMANIP_FLAG_DUNGEON_UNTOUCHABLE
,
428 makeFill(p
, dp
.holesize
, VMANIP_FLAG_DUNGEON_UNTOUCHABLE
,
429 MapNode(CONTENT_AIR
), VMANIP_FLAG_DUNGEON_INSIDE
);
430 makeFill(p
- dir
, dp
.holesize
, VMANIP_FLAG_DUNGEON_UNTOUCHABLE
,
431 MapNode(CONTENT_AIR
), VMANIP_FLAG_DUNGEON_INSIDE
);
433 // TODO: fix stairs code so it works 100%
436 // exclude stairs from the bottom step
437 // exclude stairs from diagonal steps
438 if (((dir
.X
^ dir
.Z
) & 1) &&
439 (((make_stairs
== 1) && i
!= 0) ||
440 ((make_stairs
== -1) && i
!= length
- 1))) {
441 // rotate face 180 deg if
442 // making stairs backwards
443 int facedir
= dir_to_facedir(dir
* make_stairs
);
445 u16 stair_width
= (dir
.Z
!= 0) ? dp
.holesize
.X
: dp
.holesize
.Z
;
446 // Stair width direction vector
447 v3s16 swv
= (dir
.Z
!= 0) ? v3s16(1, 0, 0) : v3s16(0, 0, 1);
449 for (u16 st
= 0; st
< stair_width
; st
++) {
450 if (make_stairs
== -1) {
451 u32 vi
= vm
->m_area
.index(ps
.X
- dir
.X
, ps
.Y
- 1, ps
.Z
- dir
.Z
);
452 if (vm
->m_area
.contains(ps
+ v3s16(-dir
.X
, -1, -dir
.Z
)) &&
453 vm
->m_data
[vi
].getContent() == dp
.c_wall
) {
454 vm
->m_flags
[vi
] |= VMANIP_FLAG_DUNGEON_UNTOUCHABLE
;
455 vm
->m_data
[vi
] = MapNode(dp
.c_stair
, 0, facedir
);
457 } else if (make_stairs
== 1) {
458 u32 vi
= vm
->m_area
.index(ps
.X
, ps
.Y
- 1, ps
.Z
);
459 if (vm
->m_area
.contains(ps
+ v3s16(0, -1, 0)) &&
460 vm
->m_data
[vi
].getContent() == dp
.c_wall
) {
461 vm
->m_flags
[vi
] |= VMANIP_FLAG_DUNGEON_UNTOUCHABLE
;
462 vm
->m_data
[vi
] = MapNode(dp
.c_stair
, 0, facedir
);
469 makeFill(p
+ v3s16(-1, -1, -1),
470 dp
.holesize
+ v3s16(2, 2, 2),
471 VMANIP_FLAG_DUNGEON_UNTOUCHABLE
,
479 // Can't go here, turn away
480 dir
= turn_xz(dir
, random
.range(0, 1));
481 make_stairs
= -make_stairs
;
483 partlength
= random
.range(1, length
);
488 if (partcount
>= partlength
) {
491 random_turn(random
, dir
);
493 partlength
= random
.range(1, length
);
496 if (random
.next() % 2 == 0 && partlength
>= 3)
497 make_stairs
= random
.next() % 2 ? 1 : -1;
505 bool DungeonGen::findPlaceForDoor(v3s16
&result_place
, v3s16
&result_dir
)
507 for (u32 i
= 0; i
< 100; i
++) {
508 v3s16 p
= m_pos
+ m_dir
;
509 v3s16 p1
= p
+ v3s16(0, 1, 0);
510 if (!vm
->m_area
.contains(p
) || !vm
->m_area
.contains(p1
) || i
% 4 == 0) {
514 if (vm
->getNodeNoExNoEmerge(p
).getContent() == dp
.c_wall
&&
515 vm
->getNodeNoExNoEmerge(p1
).getContent() == dp
.c_wall
) {
516 // Found wall, this is a good place!
519 // Randomize next direction
524 Determine where to move next
526 // Jump one up if the actual space is there
527 if (vm
->getNodeNoExNoEmerge(p
+
528 v3s16(0, 0, 0)).getContent() == dp
.c_wall
&&
529 vm
->getNodeNoExNoEmerge(p
+
530 v3s16(0, 1, 0)).getContent() == CONTENT_AIR
&&
531 vm
->getNodeNoExNoEmerge(p
+
532 v3s16(0, 2, 0)).getContent() == CONTENT_AIR
)
534 // Jump one down if the actual space is there
535 if (vm
->getNodeNoExNoEmerge(p
+
536 v3s16(0, 1, 0)).getContent() == dp
.c_wall
&&
537 vm
->getNodeNoExNoEmerge(p
+
538 v3s16(0, 0, 0)).getContent() == CONTENT_AIR
&&
539 vm
->getNodeNoExNoEmerge(p
+
540 v3s16(0, -1, 0)).getContent() == CONTENT_AIR
)
541 p
+= v3s16(0, -1, 0);
542 // Check if walking is now possible
543 if (vm
->getNodeNoExNoEmerge(p
).getContent() != CONTENT_AIR
||
544 vm
->getNodeNoExNoEmerge(p
+
545 v3s16(0, 1, 0)).getContent() != CONTENT_AIR
) {
546 // Cannot continue walking here
557 bool DungeonGen::findPlaceForRoomDoor(v3s16 roomsize
, v3s16
&result_doorplace
,
558 v3s16
&result_doordir
, v3s16
&result_roomplace
)
560 for (s16 trycount
= 0; trycount
< 30; trycount
++) {
563 bool r
= findPlaceForDoor(doorplace
, doordir
);
567 // X east, Z north, Y up
568 if (doordir
== v3s16(1, 0, 0)) // X+
569 roomplace
= doorplace
+
570 v3s16(0, -1, random
.range(-roomsize
.Z
+ 2, -2));
571 if (doordir
== v3s16(-1, 0, 0)) // X-
572 roomplace
= doorplace
+
573 v3s16(-roomsize
.X
+ 1, -1, random
.range(-roomsize
.Z
+ 2, -2));
574 if (doordir
== v3s16(0, 0, 1)) // Z+
575 roomplace
= doorplace
+
576 v3s16(random
.range(-roomsize
.X
+ 2, -2), -1, 0);
577 if (doordir
== v3s16(0, 0, -1)) // Z-
578 roomplace
= doorplace
+
579 v3s16(random
.range(-roomsize
.X
+ 2, -2), -1, -roomsize
.Z
+ 1);
583 for (s16 z
= 1; z
< roomsize
.Z
- 1; z
++)
584 for (s16 y
= 1; y
< roomsize
.Y
- 1; y
++)
585 for (s16 x
= 1; x
< roomsize
.X
- 1; x
++) {
586 v3s16 p
= roomplace
+ v3s16(x
, y
, z
);
587 if (!vm
->m_area
.contains(p
)) {
591 if (vm
->m_flags
[vm
->m_area
.index(p
)] & VMANIP_FLAG_DUNGEON_INSIDE
) {
600 result_doorplace
= doorplace
;
601 result_doordir
= doordir
;
602 result_roomplace
= roomplace
;
609 v3s16
rand_ortho_dir(PseudoRandom
&random
, bool diagonal_dirs
)
611 // Make diagonal directions somewhat rare
612 if (diagonal_dirs
&& (random
.next() % 4 == 0)) {
619 dir
.Z
= random
.next() % 3 - 1;
621 dir
.X
= random
.next() % 3 - 1;
622 } while ((dir
.X
== 0 || dir
.Z
== 0) && trycount
< 10);
627 if (random
.next() % 2 == 0)
628 return random
.next() % 2 ? v3s16(-1, 0, 0) : v3s16(1, 0, 0);
630 return random
.next() % 2 ? v3s16(0, 0, -1) : v3s16(0, 0, 1);
634 v3s16
turn_xz(v3s16 olddir
, int t
)
652 void random_turn(PseudoRandom
&random
, v3s16
&dir
)
654 int turn
= random
.range(0, 2);
656 // Go straight: nothing to do
658 } else if (turn
== 1) {
660 dir
= turn_xz(dir
, 0);
663 dir
= turn_xz(dir
, 1);
668 int dir_to_facedir(v3s16 d
)
670 if (abs(d
.X
) > abs(d
.Z
))
671 return d
.X
< 0 ? 3 : 1;
673 return d
.Z
< 0 ? 2 : 0;