src/dungeongen.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
--Minetest
--Copyright (C) 2014 sapier
--
--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.

mt_color_grey  = "#AAAAAA"
mt_color_blue  = "#6389FF"
mt_color_green = "#72FF63"
mt_color_dark_green = "#25C191"
mt_color_orange  = "#FF8800"

local menupath = core.get_mainmenu_path()
local basepath = core.get_builtin_path()
defaulttexturedir = core.get_texturepath_share() .. DIR_DELIM .. "base" ..
					DIR_DELIM .. "pack" .. DIR_DELIM

dofile(basepath .. "common" .. DIR_DELIM .. "filterlist.lua")
dofile(basepath .. "fstk" .. DIR_DELIM .. "buttonbar.lua")
dofile(basepath .. "fstk" .. DIR_DELIM .. "dialog.lua")
dofile(basepath .. "fstk" .. DIR_DELIM .. "tabview.lua")
dofile(basepath .. "fstk" .. DIR_DELIM .. "ui.lua")
dofile(menupath .. DIR_DELIM .. "async_event.lua")
dofile(menupath .. DIR_DELIM .. "common.lua")
dofile(menupath .. DIR_DELIM .. "pkgmgr.lua")
dofile(menupath .. DIR_DELIM .. "serverlistmgr.lua")
dofile(menupath .. DIR_DELIM .. "textures.lua")

dofile(menupath .. DIR_DELIM .. "dlg_config_world.lua")
dofile(menupath .. DIR_DELIM .. "dlg_settings_advanced.lua")
dofile(menupath .. DIR_DELIM .. "dlg_contentstore.lua")
dofile(menupath .. DIR_DELIM .. "dlg_create_world.lua")
dofile(menupath .. DIR_DELIM .. "dlg_delete_content.lua")
dofile(menupath .. DIR_DELIM .. "dlg_delete_world.lua")
dofile(menupath .. DIR_DELIM .. "dlg_rename_modpack.lua")

local tabs = {}

tabs.settings = dofile(menupath .. DIR_DELIM .. "tab_settings.lua")
tabs.content  = dofile(menupath .. DIR_DELIM .. "tab_content.lua")
tabs.credits  = dofile(menupath .. DIR_DELIM .. "tab_credits.lua")
tabs.local_game = dofile(menupath .. DIR_DELIM .. "tab_local.lua")
tabs.play_online = dofile(menupath .. DIR_DELIM .. "tab_online.lua")

--------------------------------------------------------------------------------
local function main_event_handler(tabview, event)
	if event == "MenuQuit" then
		core.close()
	end
	return true
end

--------------------------------------------------------------------------------
local function init_globals()
	-- Init gamedata
	gamedata.worldindex = 0

	menudata.worldlist = filterlist.create(
		core.get_worlds,
		compare_worlds,
		-- Unique id comparison function
		function(element, uid)
			return element.name == uid
		end,
		-- Filter function
		function(element, gameid)
			return element.gameid == gameid
		end
	)

	menudata.worldlist:add_sort_mechanism("alphabetic", sort_worlds_alphabetic)
	menudata.worldlist:set_sortmode("alphabetic")

	if not core.settings:get("menu_last_game") then
		local default_game = core.settings:get("default_game") or "minetest"
		core.settings:set("menu_last_game", default_game)
	end

	mm_texture.init()

	-- Create main tabview
	local tv_main = tabview_create("maintab", {x = 12, y = 5.4}, {x = 0, y = 0})

	tv_main:set_autosave_tab(true)
	tv_main:add(tabs.local_game)
	tv_main:add(tabs.play_online)

	tv_main:add(tabs.content)
	tv_main:add(tabs.settings)
	tv_main:add(tabs.credits)

	tv_main:set_global_event_handler(main_event_handler)
	tv_main:set_fixed_size(false)

	local last_tab = core.settings:get("maintab_LAST")
	if last_tab and tv_main.current_tab ~= last_tab then
		tv_main:set_tab(last_tab)
	end

	-- In case the folder of the last selected game has been deleted,
	-- display "Minetest" as a header
	if tv_main.current_tab == "local" then
		local game = pkgmgr.find_by_gameid(core.settings:get("menu_last_game"))
		if game == nil then
			mm_texture.reset()
		end
	end

	ui.set_default("maintab")
	tv_main:show()

	ui.update()

	core.sound_play("main_menu", true)
end

init_globals()
/*
Minetest
Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>

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 "mapgen.h"
#include "voxel.h"
#include "noise.h"
#include "mapblock.h"
#include "mapnode.h"
#include "map.h"
#include "nodedef.h"
#include "profiler.h"
#include "settings.h"

//#define DGEN_USE_TORCHES

NoiseParams nparams_dungeon_density(0.9, 0.5, v3f(500.0, 500.0, 500.0), 0, 2, 0.8, 2.0);
NoiseParams nparams_dungeon_alt_wall(-0.4, 1.0, v3f(40.0, 40.0, 40.0), 32474, 6, 1.1, 2.0);


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


DungeonGen::DungeonGen(INodeDefManager *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) {
		memcpy(&dp, dparams, sizeof(dp));
	} else {
		// Default dungeon parameters
		dp.seed = 0;

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

		if (dp.c_river_water == CONTENT_IGNORE)
			dp.c_river_water = ndef->getId("mapgen_water_source");

		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.rooms_min           = 2;
		dp.rooms_max           = 16;
		dp.y_min               = -MAX_MAP_GENERATION_LIMIT;
		dp.y_max               = MAX_MAP_GENERATION_LIMIT;
		dp.notifytype          = GENNOTIFY_DUNGEON;

		dp.np_density  = nparams_dungeon_density;
		dp.np_alt_wall = nparams_dungeon_alt_wall;
	}
}


void DungeonGen::generate(MMVManip *vm, u32 bseed, v3s16 nmin, v3s16 nmax)
{
	assert(vm);

	//TimeTaker t("gen dungeons");
	if (nmin.Y < dp.y_min || nmax.Y > dp.y_max)
		return;

	float nval_density = NoisePerlin3D(&dp.np_density, nmin.X, nmin.Y, nmin.Z, dp.seed);
	if (nval_density < 1.0f)
		return;

	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 water to be untouchable
		// to make dungeons open to caves and open air
		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();
					if (c == CONTENT_AIR || c == dp.c_water ||
							c == dp.c_river_water)
						vm->m_flags[i] |= VMANIP_FLAG_DUNGEON_PRESERVE;
					i++;
				}
			}
		}
	}

	// Add them
	for (u32 i = 0; i < floor(nval_density); 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)
{
	v3s16 areasize = vm->m_area.getExtent();
	v3s16 roomsize;
	v3s16 roomplace;

	/*
		Find place for first room.
		There is a 1 in 4 chance of the first room being 'large',
		all other rooms are not 'large'.
	*/
	bool fits = false;
	for (u32 i = 0; i < 100 && !fits; i++) {
		bool is_large_room = ((random.next() & 3) == 1);
		if (is_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);
		}

		// 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 == false)
		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);

	u32 room_count = random.range(dp.rooms_min, dp.rooms_max);
	for (u32 i = 0; i < room_count; 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 == room_count - 1)
			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
		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);
				makeHole(p);
				makeHole(p - dir);

				// 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++) {
						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_data[vi] = MapNode(dp.c_stair, 0, facedir);

						vi = vm->m_area.index(ps.X, ps.Y, ps.Z);
						if (vm->m_area.contains(ps) &&
								vm->m_data[vi].getContent() == dp.c_wall)
							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;

			dir = 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 == false)
			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 == false) {
			// 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;
	} else {
		if (random.next() % 2 == 0)
			return random.next() % 2 ? v3s16(-1, 0, 0) : v3s16(1, 0, 0);
		else
			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;
}


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


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