aboutsummaryrefslogtreecommitdiff
path: root/src/gui
Commit message (Expand)AuthorAge
* label[]: Fix cut-off translated textSmallJoker2019-09-07
* Fix Irrlicht 1.9 supportsfan52019-09-06
* Add ItemStack:get_description() to get tooltip (#8847)Paul Ouellette2019-08-24
* Add support for set_formspec_prepend in main menu (#8611)rubenwardy2019-08-12
* guiVolumeChange: Fix child not being removedANAND2019-08-08
* guiConfirmRegistration: Set focus to text field (#8761)ANAND2019-08-07
* Clean up and fix freetype=false crashes (#8641)SmallJoker2019-08-06
* Unify OpenGL ES supportsfan52019-08-04
* Add formspec testing to test mod in minimalrubenwardy2019-08-03
* Add styles to most elementsrubenwardy2019-08-03
* Add style[] tag with button supportrubenwardy2019-08-03
* Add custom colorable GUIButton implementationrubenwardy2019-08-03
* Fix negative offsets not being supported by container[]rubenwardy2019-08-03
* Rename guiScrollBar to GUIScrollBarDS-Minetest2019-07-29
* guiScrollBar: move directly to clicked pos if clicked into trayDS-Minetest2019-07-28
* Add compatible, consistent coordinate system to FormSpecs. (#8524)v-rob2019-06-27
* Add support for 9-sliced backgrounds (#8600)rubenwardy2019-06-22
* Formspecs: Close on metadata removal (#8348)SmallJoker2019-06-10
* Do not drag-place stack into 'craftpreview' slot (#8514)SmallJoker2019-05-25
* Add IGUIScrollbar implementation with variable bar sizes (#8507)stujones112019-05-24
* Optimize string (mis)handling (#8128)Jozef Behran2019-05-18
* Correct the checkbox selection box position (#8246)SmallJoker2019-04-27
* Change pitch fly binding to 'P', add to change keys menu (#8314)rubenwardy2019-04-03
* Add newline before itemstring in item tooltip (#8213)Wuzzy2019-03-17
* LINT fixes since recent tooling updateLoïc Blot2019-03-14
* Drop GUIConfirmRegistration::m_address unused fieldLoïc Blot2019-03-12
* Confirm registration GUI: Remove positional strings to fix Windows bug (#8258)Paramat2019-03-10
* Replace for loop with call to standard library function (#8194)Benjamin Lindley2019-03-05
* Fix coloured fog in main menu (#8181)random-geek2019-02-15
* Don't append itemname to itemname in tooltip (#8176)Wuzzy2019-02-09
* Fix cloud color in loading screen and main menu (#8174)random-geek2019-02-04
* Update color of main menu clouds (#8172)random-geek2019-02-04
* Fix core.download_file() creating empty files on HTTP errorrubenwardy2019-02-03
* DragonFly BSD is somewhat identical to FreeBSD (#8159)Leonid Bobrov2019-02-03
* Android: Fix memory leak when displaying images in the mainmenu (#8011)rubenwardy2018-12-22
* Android: Move touchscreen rare controls inline with settings icon (#8006)stujones112018-12-20
* Fix Android build errors (caused by 5f1cd55)Juozas2018-12-03
* Move client-specific files to 'src/client' (#7902)Quentin Bazin2018-11-28
* Make non-formspec modal menus respect gui scale (#7850)stujones112018-11-26
* Client-side autojump. Remove Android-only stepheight autojump (#7228)Ben Deutsch2018-11-22
* Android: Improve UI scaling on smaller high-density displays (#7834)stujones112018-11-18
* Minor changes for IrrLicht 1.9 supportnumber Zero2018-11-11
* Drop .NET-specific workaround: _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIXnumber Zero2018-11-11
* Formspecs: Fix text clipped by scrollbars (#7816)random-geek2018-11-06
* Remove un-needed header inclusionstujones112018-10-29
* Move touchscreen input handling to base GUIModalMenu classstujones112018-10-29
* Android buttons: Inset 'rare controls', inset and resize 'gear icon' (#7792)Paramat2018-10-19
* Formspecs: Fix invalid background warningrubenwardy2018-08-20
* Formspecs: Fix missing trim() when checking for no_prepend[]rubenwardy2018-08-15
* Formspecs: Add tooltip element for arearubenwardy2018-08-05
436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674
/*
Minetest
Copyright (C) 2010-2018 celeron55, Perttu Ahola <celeron55@gmail.com>
Copyright (C) 2015-2018 paramat

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#include "dungeongen.h"
#include <cmath>
#include "mapgen.h"
#include "voxel.h"
#include "noise.h"
#include "mapblock.h"
#include "mapnode.h"
#include "map.h"
#include "nodedef.h"
#include "settings.h"

//#define DGEN_USE_TORCHES


///////////////////////////////////////////////////////////////////////////////


DungeonGen::DungeonGen(const NodeDefManager *ndef,
	GenerateNotifier *gennotify, DungeonParams *dparams)
{
	assert(ndef);

	this->ndef      = ndef;
	this->gennotify = gennotify;

#ifdef DGEN_USE_TORCHES
	c_torch  = ndef->getId("default:torch");
#endif

	if (dparams) {
		dp = *dparams;
	} else {
		// Default dungeon parameters
		dp.seed = 0;

		dp.c_wall     = ndef->getId("mapgen_cobble");
		dp.c_alt_wall = ndef->getId("mapgen_mossycobble");
		dp.c_stair    = ndef->getId("mapgen_stair_cobble");

		dp.diagonal_dirs       = false;
		dp.only_in_ground      = true;
		dp.holesize            = v3s16(1, 2, 1);
		dp.corridor_len_min    = 1;
		dp.corridor_len_max    = 13;
		dp.room_size_min       = v3s16(4, 4, 4);
		dp.room_size_max       = v3s16(8, 6, 8);
		dp.room_size_large_min = v3s16(8, 8, 8);
		dp.room_size_large_max = v3s16(16, 16, 16);
		dp.large_room_chance   = 1;
		dp.num_rooms           = 8;
		dp.num_dungeons        = 1;
		dp.notifytype          = GENNOTIFY_DUNGEON;

		dp.np_alt_wall = 
			NoiseParams(-0.4, 1.0, v3f(40.0, 40.0, 40.0), 32474, 6, 1.1, 2.0);
	}
}


void DungeonGen::generate(MMVManip *vm, u32 bseed, v3s16 nmin, v3s16 nmax)
{
	if (dp.num_dungeons == 0)
		return;

	assert(vm);

	//TimeTaker t("gen dungeons");

	this->vm = vm;
	this->blockseed = bseed;
	random.seed(bseed + 2);

	// Dungeon generator doesn't modify places which have this set
	vm->clearFlag(VMANIP_FLAG_DUNGEON_INSIDE | VMANIP_FLAG_DUNGEON_PRESERVE);

	if (dp.only_in_ground) {
		// Set all air and liquid drawtypes to be untouchable to make dungeons generate
		// in ground only.
		// Set 'ignore' to be untouchable to prevent generation in ungenerated neighbor
		// mapchunks, to avoid dungeon rooms generating outside ground.
		// Like randomwalk caves, preserve nodes that have 'is_ground_content = false',
		// to avoid dungeons that generate out beyond the edge of a mapchunk destroying
		// nodes added by mods in 'register_on_generated()'.
		for (s16 z = nmin.Z; z <= nmax.Z; z++) {
			for (s16 y = nmin.Y; y <= nmax.Y; y++) {
				u32 i = vm->m_area.index(nmin.X, y, z);
				for (s16 x = nmin.X; x <= nmax.X; x++) {
					content_t c = vm->m_data[i].getContent();
					NodeDrawType dtype = ndef->get(c).drawtype;
					if (dtype == NDT_AIRLIKE || dtype == NDT_LIQUID ||
							c == CONTENT_IGNORE || !ndef->get(c).is_ground_content)
						vm->m_flags[i] |= VMANIP_FLAG_DUNGEON_PRESERVE;
					i++;
				}
			}
		}
	}

	// Add them
	for (u32 i = 0; i < dp.num_dungeons; i++)
		makeDungeon(v3s16(1, 1, 1) * MAP_BLOCKSIZE);

	// Optionally convert some structure to alternative structure
	if (dp.c_alt_wall == CONTENT_IGNORE)
		return;

	for (s16 z = nmin.Z; z <= nmax.Z; z++)
	for (s16 y = nmin.Y; y <= nmax.Y; y++) {
		u32 i = vm->m_area.index(nmin.X, y, z);
		for (s16 x = nmin.X; x <= nmax.X; x++) {
			if (vm->m_data[i].getContent() == dp.c_wall) {
				if (NoisePerlin3D(&dp.np_alt_wall, x, y, z, blockseed) > 0.0f)
					vm->m_data[i].setContent(dp.c_alt_wall);
			}
			i++;
		}
	}

	//printf("== gen dungeons: %dms\n", t.stop());
}


void DungeonGen::makeDungeon(v3s16 start_padding)
{
	const v3s16 &areasize = vm->m_area.getExtent();
	v3s16 roomsize;
	v3s16 roomplace;

	/*
		Find place for first room.
	*/
	bool fits = false;
	for (u32 i = 0; i < 100 && !fits; i++) {
		if (dp.large_room_chance >= 1) {
			roomsize.Z = random.range(dp.room_size_large_min.Z, dp.room_size_large_max.Z);
			roomsize.Y = random.range(dp.room_size_large_min.Y, dp.room_size_large_max.Y);
			roomsize.X = random.range(dp.room_size_large_min.X, dp.room_size_large_max.X);
		} else {
			roomsize.Z = random.range(dp.room_size_min.Z, dp.room_size_max.Z);
			roomsize.Y = random.range(dp.room_size_min.Y, dp.room_size_max.Y);
			roomsize.X = random.range(dp.room_size_min.X, dp.room_size_max.X);
		}

		// start_padding is used to disallow starting the generation of
		// a dungeon in a neighboring generation chunk
		roomplace = vm->m_area.MinEdge + start_padding;
		roomplace.Z += random.range(0, areasize.Z - roomsize.Z - start_padding.Z);
		roomplace.Y += random.range(0, areasize.Y - roomsize.Y - start_padding.Y);
		roomplace.X += random.range(0, areasize.X - roomsize.X - start_padding.X);

		/*
			Check that we're not putting the room to an unknown place,
			otherwise it might end up floating in the air
		*/
		fits = true;
		for (s16 z = 0; z < roomsize.Z; z++)
		for (s16 y = 0; y < roomsize.Y; y++)
		for (s16 x = 0; x < roomsize.X; x++) {
			v3s16 p = roomplace + v3s16(x, y, z);
			u32 vi = vm->m_area.index(p);
			if ((vm->m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE) ||
					vm->m_data[vi].getContent() == CONTENT_IGNORE) {
				fits = false;
				break;
			}
		}
	}
	// No place found
	if (!fits)
		return;

	/*
		Stores the center position of the last room made, so that
		a new corridor can be started from the last room instead of
		the new room, if chosen so.
	*/
	v3s16 last_room_center = roomplace + v3s16(roomsize.X / 2, 1, roomsize.Z / 2);

	for (u32 i = 0; i < dp.num_rooms; i++) {
		// Make a room to the determined place
		makeRoom(roomsize, roomplace);

		v3s16 room_center = roomplace + v3s16(roomsize.X / 2, 1, roomsize.Z / 2);
		if (gennotify)
			gennotify->addEvent(dp.notifytype, room_center);

#ifdef DGEN_USE_TORCHES
		// Place torch at room center (for testing)
		vm->m_data[vm->m_area.index(room_center)] = MapNode(c_torch);
#endif

		// Quit if last room
		if (i + 1 == dp.num_rooms)
			break;

		// Determine walker start position

		bool start_in_last_room = (random.range(0, 2) != 0);

		v3s16 walker_start_place;

		if (start_in_last_room) {
			walker_start_place = last_room_center;
		} else {
			walker_start_place = room_center;
			// Store center of current room as the last one
			last_room_center = room_center;
		}

		// Create walker and find a place for a door
		v3s16 doorplace;
		v3s16 doordir;

		m_pos = walker_start_place;
		if (!findPlaceForDoor(doorplace, doordir))
			return;

		if (random.range(0, 1) == 0)
			// Make the door
			makeDoor(doorplace, doordir);
		else
			// Don't actually make a door
			doorplace -= doordir;

		// Make a random corridor starting from the door
		v3s16 corridor_end;
		v3s16 corridor_end_dir;
		makeCorridor(doorplace, doordir, corridor_end, corridor_end_dir);

		// Find a place for a random sized room
		if (dp.large_room_chance > 1 && random.range(1, dp.large_room_chance) == 1) {
			// Large room
			roomsize.Z = random.range(dp.room_size_large_min.Z, dp.room_size_large_max.Z);
			roomsize.Y = random.range(dp.room_size_large_min.Y, dp.room_size_large_max.Y);
			roomsize.X = random.range(dp.room_size_large_min.X, dp.room_size_large_max.X);
		} else {
			roomsize.Z = random.range(dp.room_size_min.Z, dp.room_size_max.Z);
			roomsize.Y = random.range(dp.room_size_min.Y, dp.room_size_max.Y);
			roomsize.X = random.range(dp.room_size_min.X, dp.room_size_max.X);
		}

		m_pos = corridor_end;
		m_dir = corridor_end_dir;
		if (!findPlaceForRoomDoor(roomsize, doorplace, doordir, roomplace))
			return;

		if (random.range(0, 1) == 0)
			// Make the door
			makeDoor(doorplace, doordir);
		else
			// Don't actually make a door
			roomplace -= doordir;
	}
}


void DungeonGen::makeRoom(v3s16 roomsize, v3s16 roomplace)
{
	MapNode n_wall(dp.c_wall);
	MapNode n_air(CONTENT_AIR);

	// Make +-X walls
	for (s16 z = 0; z < roomsize.Z; z++)
	for (s16 y = 0; y < roomsize.Y; y++) {
		{
			v3s16 p = roomplace + v3s16(0, y, z);
			if (!vm->m_area.contains(p))
				continue;
			u32 vi = vm->m_area.index(p);
			if (vm->m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
				continue;
			vm->m_data[vi] = n_wall;
		}
		{
			v3s16 p = roomplace + v3s16(roomsize.X - 1, y, z);
			if (!vm->m_area.contains(p))
				continue;
			u32 vi = vm->m_area.index(p);
			if (vm->m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
				continue;
			vm->m_data[vi] = n_wall;
		}
	}

	// Make +-Z walls
	for (s16 x = 0; x < roomsize.X; x++)
	for (s16 y = 0; y < roomsize.Y; y++) {
		{
			v3s16 p = roomplace + v3s16(x, y, 0);
			if (!vm->m_area.contains(p))
				continue;
			u32 vi = vm->m_area.index(p);
			if (vm->m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
				continue;
			vm->m_data[vi] = n_wall;
		}
		{
			v3s16 p = roomplace + v3s16(x, y, roomsize.Z - 1);
			if (!vm->m_area.contains(p))
				continue;
			u32 vi = vm->m_area.index(p);
			if (vm->m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
				continue;
			vm->m_data[vi] = n_wall;
		}
	}

	// Make +-Y walls (floor and ceiling)
	for (s16 z = 0; z < roomsize.Z; z++)
	for (s16 x = 0; x < roomsize.X; x++) {
		{
			v3s16 p = roomplace + v3s16(x, 0, z);
			if (!vm->m_area.contains(p))
				continue;
			u32 vi = vm->m_area.index(p);
			if (vm->m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
				continue;
			vm->m_data[vi] = n_wall;
		}
		{
			v3s16 p = roomplace + v3s16(x,roomsize. Y - 1, z);
			if (!vm->m_area.contains(p))
				continue;
			u32 vi = vm->m_area.index(p);
			if (vm->m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
				continue;
			vm->m_data[vi] = n_wall;
		}
	}

	// Fill with air
	for (s16 z = 1; z < roomsize.Z - 1; z++)
	for (s16 y = 1; y < roomsize.Y - 1; y++)
	for (s16 x = 1; x < roomsize.X - 1; x++) {
		v3s16 p = roomplace + v3s16(x, y, z);
		if (!vm->m_area.contains(p))
			continue;
		u32 vi = vm->m_area.index(p);
		vm->m_flags[vi] |= VMANIP_FLAG_DUNGEON_UNTOUCHABLE;
		vm->m_data[vi] = n_air;
	}
}


void DungeonGen::makeFill(v3s16 place, v3s16 size,
	u8 avoid_flags, MapNode n, u8 or_flags)
{
	for (s16 z = 0; z < size.Z; z++)
	for (s16 y = 0; y < size.Y; y++)
	for (s16 x = 0; x < size.X; x++) {
		v3s16 p = place + v3s16(x, y, z);
		if (!vm->m_area.contains(p))
			continue;
		u32 vi = vm->m_area.index(p);
		if (vm->m_flags[vi] & avoid_flags)
			continue;
		vm->m_flags[vi] |= or_flags;
		vm->m_data[vi] = n;
	}
}


void DungeonGen::makeHole(v3s16 place)
{
	makeFill(place, dp.holesize, 0, MapNode(CONTENT_AIR),
		VMANIP_FLAG_DUNGEON_INSIDE);
}


void DungeonGen::makeDoor(v3s16 doorplace, v3s16 doordir)
{
	makeHole(doorplace);

#ifdef DGEN_USE_TORCHES
	// Place torch (for testing)
	vm->m_data[vm->m_area.index(doorplace)] = MapNode(c_torch);
#endif
}


void DungeonGen::makeCorridor(v3s16 doorplace, v3s16 doordir,
	v3s16 &result_place, v3s16 &result_dir)
{
	makeHole(doorplace);
	v3s16 p0 = doorplace;
	v3s16 dir = doordir;
	u32 length = random.range(dp.corridor_len_min, dp.corridor_len_max);
	u32 partlength = random.range(dp.corridor_len_min, dp.corridor_len_max);
	u32 partcount = 0;
	s16 make_stairs = 0;

	if (random.next() % 2 == 0 && partlength >= 3)
		make_stairs = random.next() % 2 ? 1 : -1;

	for (u32 i = 0; i < length; i++) {
		v3s16 p = p0 + dir;
		if (partcount != 0)
			p.Y += make_stairs;

		// Check segment of minimum size corridor is in voxelmanip
		if (vm->m_area.contains(p) && vm->m_area.contains(p + v3s16(0, 1, 0))) {
			if (make_stairs) {
				makeFill(p + v3s16(-1, -1, -1),
					dp.holesize + v3s16(2, 3, 2),
					VMANIP_FLAG_DUNGEON_UNTOUCHABLE,
					MapNode(dp.c_wall),
					0);
				makeFill(p, dp.holesize, VMANIP_FLAG_DUNGEON_UNTOUCHABLE,
					MapNode(CONTENT_AIR), VMANIP_FLAG_DUNGEON_INSIDE);
				makeFill(p - dir, dp.holesize, VMANIP_FLAG_DUNGEON_UNTOUCHABLE,
					MapNode(CONTENT_AIR), VMANIP_FLAG_DUNGEON_INSIDE);

				// TODO: fix stairs code so it works 100%
				// (quite difficult)

				// exclude stairs from the bottom step
				// exclude stairs from diagonal steps
				if (((dir.X ^ dir.Z) & 1) &&
						(((make_stairs ==  1) && i != 0) ||
						((make_stairs == -1) && i != length - 1))) {
					// rotate face 180 deg if
					// making stairs backwards
					int facedir = dir_to_facedir(dir * make_stairs);
					v3s16 ps = p;
					u16 stair_width = (dir.Z != 0) ? dp.holesize.X : dp.holesize.Z;
					// Stair width direction vector
					v3s16 swv = (dir.Z != 0) ? v3s16(1, 0, 0) : v3s16(0, 0, 1);

					for (u16 st = 0; st < stair_width; st++) {
						if (make_stairs == -1) {
							u32 vi = vm->m_area.index(ps.X - dir.X, ps.Y - 1, ps.Z - dir.Z);
							if (vm->m_area.contains(ps + v3s16(-dir.X, -1, -dir.Z)) &&
									vm->m_data[vi].getContent() == dp.c_wall) {
								vm->m_flags[vi] |= VMANIP_FLAG_DUNGEON_UNTOUCHABLE;
								vm->m_data[vi] = MapNode(dp.c_stair, 0, facedir);
							}
						} else if (make_stairs == 1) {
							u32 vi = vm->m_area.index(ps.X, ps.Y - 1, ps.Z);
							if (vm->m_area.contains(ps + v3s16(0, -1, 0)) &&
									vm->m_data[vi].getContent() == dp.c_wall) {
								vm->m_flags[vi] |= VMANIP_FLAG_DUNGEON_UNTOUCHABLE;
								vm->m_data[vi] = MapNode(dp.c_stair, 0, facedir);
							}
						}
						ps += swv;
					}
				}
			} else {
				makeFill(p + v3s16(-1, -1, -1),
					dp.holesize + v3s16(2, 2, 2),
					VMANIP_FLAG_DUNGEON_UNTOUCHABLE,
					MapNode(dp.c_wall),
					0);
				makeHole(p);
			}

			p0 = p;
		} else {
			// Can't go here, turn away
			dir = turn_xz(dir, random.range(0, 1));
			make_stairs = -make_stairs;
			partcount = 0;
			partlength = random.range(1, length);
			continue;
		}

		partcount++;
		if (partcount >= partlength) {
			partcount = 0;

			random_turn(random, dir);

			partlength = random.range(1, length);

			make_stairs = 0;
			if (random.next() % 2 == 0 && partlength >= 3)
				make_stairs = random.next() % 2 ? 1 : -1;
		}
	}
	result_place = p0;
	result_dir = dir;
}


bool DungeonGen::findPlaceForDoor(v3s16 &result_place, v3s16 &result_dir)
{
	for (u32 i = 0; i < 100; i++) {
		v3s16 p = m_pos + m_dir;
		v3s16 p1 = p + v3s16(0, 1, 0);
		if (!vm->m_area.contains(p) || !vm->m_area.contains(p1) || i % 4 == 0) {
			randomizeDir();
			continue;
		}
		if (vm->getNodeNoExNoEmerge(p).getContent() == dp.c_wall &&
				vm->getNodeNoExNoEmerge(p1).getContent() == dp.c_wall) {
			// Found wall, this is a good place!
			result_place = p;
			result_dir = m_dir;
			// Randomize next direction
			randomizeDir();
			return true;
		}
		/*
			Determine where to move next
		*/
		// Jump one up if the actual space is there
		if (vm->getNodeNoExNoEmerge(p +
				v3s16(0, 0, 0)).getContent() == dp.c_wall &&
				vm->getNodeNoExNoEmerge(p +
				v3s16(0, 1, 0)).getContent() == CONTENT_AIR &&
				vm->getNodeNoExNoEmerge(p +
				v3s16(0, 2, 0)).getContent() == CONTENT_AIR)
			p += v3s16(0,1,0);
		// Jump one down if the actual space is there
		if (vm->getNodeNoExNoEmerge(p +
				v3s16(0, 1, 0)).getContent() == dp.c_wall &&
				vm->getNodeNoExNoEmerge(p +
				v3s16(0, 0, 0)).getContent() == CONTENT_AIR &&
				vm->getNodeNoExNoEmerge(p +
				v3s16(0, -1, 0)).getContent() == CONTENT_AIR)
			p += v3s16(0, -1, 0);
		// Check if walking is now possible
		if (vm->getNodeNoExNoEmerge(p).getContent() != CONTENT_AIR ||
				vm->getNodeNoExNoEmerge(p +
				v3s16(0, 1, 0)).getContent() != CONTENT_AIR) {
			// Cannot continue walking here
			randomizeDir();
			continue;
		}
		// Move there
		m_pos = p;
	}
	return false;
}


bool DungeonGen::findPlaceForRoomDoor(v3s16 roomsize, v3s16 &result_doorplace,
	v3s16 &result_doordir, v3s16 &result_roomplace)
{
	for (s16 trycount = 0; trycount < 30; trycount++) {
		v3s16 doorplace;
		v3s16 doordir;
		bool r = findPlaceForDoor(doorplace, doordir);
		if (!r)
			continue;
		v3s16 roomplace;
		// X east, Z north, Y up
		if (doordir == v3s16(1, 0, 0)) // X+
			roomplace = doorplace +
				v3s16(0, -1, random.range(-roomsize.Z + 2, -2));
		if (doordir == v3s16(-1, 0, 0)) // X-
			roomplace = doorplace +
				v3s16(-roomsize.X + 1, -1, random.range(-roomsize.Z + 2, -2));
		if (doordir == v3s16(0, 0, 1)) // Z+
			roomplace = doorplace +
				v3s16(random.range(-roomsize.X + 2, -2), -1, 0);
		if (doordir == v3s16(0, 0, -1)) // Z-
			roomplace = doorplace +
				v3s16(random.range(-roomsize.X + 2, -2), -1, -roomsize.Z + 1);

		// Check fit
		bool fits = true;
		for (s16 z = 1; z < roomsize.Z - 1; z++)
		for (s16 y = 1; y < roomsize.Y - 1; y++)
		for (s16 x = 1; x < roomsize.X - 1; x++) {
			v3s16 p = roomplace + v3s16(x, y, z);
			if (!vm->m_area.contains(p)) {
				fits = false;
				break;
			}
			if (vm->m_flags[vm->m_area.index(p)] & VMANIP_FLAG_DUNGEON_INSIDE) {
				fits = false;
				break;
			}
		}
		if (!fits) {
			// Find new place
			continue;
		}
		result_doorplace = doorplace;
		result_doordir   = doordir;
		result_roomplace = roomplace;
		return true;
	}
	return false;
}


v3s16 rand_ortho_dir(PseudoRandom &random, bool diagonal_dirs)
{
	// Make diagonal directions somewhat rare
	if (diagonal_dirs && (random.next() % 4 == 0)) {
		v3s16 dir;
		int trycount = 0;

		do {
			trycount++;

			dir.Z = random.next() % 3 - 1;
			dir.Y = 0;
			dir.X = random.next() % 3 - 1;
		} while ((dir.X == 0 || dir.Z == 0) && trycount < 10);

		return dir;
	}

	if (random.next() % 2 == 0)
		return random.next() % 2 ? v3s16(-1, 0, 0) : v3s16(1, 0, 0);

	return random.next() % 2 ? v3s16(0, 0, -1) : v3s16(0, 0, 1);
}


v3s16 turn_xz(v3s16 olddir, int t)
{
	v3s16 dir;
	if (t == 0) {
		// Turn right
		dir.X = olddir.Z;
		dir.Z = -olddir.X;
		dir.Y = olddir.Y;
	} else {
		// Turn left
		dir.X = -olddir.Z;
		dir.Z = olddir.X;
		dir.Y = olddir.Y;
	}
	return dir;
}


void random_turn(PseudoRandom &random, v3s16 &dir)
{
	int turn = random.range(0, 2);
	if (turn == 0) {
		// Go straight: nothing to do
		return;
	} else if (turn == 1) {
		// Turn right
		dir = turn_xz(dir, 0);
	} else {
		// Turn left
		dir = turn_xz(dir, 1);
	}
}


int dir_to_facedir(v3s16 d)
{
	if (abs(d.X) > abs(d.Z))
		return d.X < 0 ? 3 : 1;

	return d.Z < 0 ? 2 : 0;
}