aboutsummaryrefslogtreecommitdiff
path: root/src/environment.h
blob: 91c33ba15967b28e66ffb8f0f4205bdb14567936 (plain)
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/*
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.
*/

#pragma once

/*
	This class is the game's environment.
	It contains:
	- The map
	- Players
	- Other objects
	- The current time in the game
	- etc.
*/

#include <list>
#include <queue>
#include <map>
#include <atomic>
#include <mutex>
#include "irr_v3d.h"
#include "network/networkprotocol.h" // for AccessDeniedCode
#include "util/basic_macros.h"

class IGameDef;
class Map;
struct PointedThing;
class RaycastState;

class Environment
{
public:
	// Environment will delete the map passed to the constructor
	Environment(IGameDef *gamedef);
	virtual ~Environment() = default;
	DISABLE_CLASS_COPY(Environment);

	/*
		Step everything in environment.
		- Move players
		- Step mobs
		- Run timers of map
	*/
	virtual void step(f32 dtime) = 0;

	virtual Map &getMap() = 0;

	u32 getDayNightRatio();

	// 0-23999
	virtual void setTimeOfDay(u32 time);
	u32 getTimeOfDay();
	float getTimeOfDayF();

	void stepTimeOfDay(float dtime);

	void setTimeOfDaySpeed(float speed);

	void setDayNightRatioOverride(bool enable, u32 value);

	u32 getDayCount();

	/*!
	 * Returns false if the given line intersects with a
	 * non-air node, true otherwise.
	 * \param pos1 start of the line
	 * \param pos2 end of the line
	 * \param p output, position of the first non-air node
	 * the line intersects
	 */
	bool line_of_sight(v3f pos1, v3f pos2, v3s16 *p = nullptr);

	/*!
	 * Gets the objects pointed by the shootline as
	 * pointed things.
	 * If this is a client environment, the local player
	 * won't be returned.
	 * @param[in]  shootline_on_map the shootline for
	 * the test in world coordinates
	 *
	 * @param[out] objects          found objects
	 */
	virtual void getSelectedActiveObjects(const core::line3d<f32> &shootline_on_map,
			std::vector<PointedThing> &objects) = 0;

	/*!
	 * Returns the next node or object the shootline meets.
	 * @param state current state of the raycast
	 * @result output, will contain the next pointed thing
	 */
	void continueRaycast(RaycastState *state, PointedThing *result);

	// counter used internally when triggering ABMs
	u32 m_added_objects;

	IGameDef *getGameDef() { return m_gamedef; }

protected:
	std::atomic<float> m_time_of_day_speed;

	/*
	 * Below: values managed by m_time_lock
	 */
	// Time of day in milli-hours (0-23999), determines day and night
	u32 m_time_of_day;
	// Time of day in 0...1
	float m_time_of_day_f;
	// Stores the skew created by the float -> u32 conversion
	// to be applied at next conversion, so that there is no real skew.
	float m_time_conversion_skew = 0.0f;
	// Overriding the day-night ratio is useful for custom sky visuals
	bool m_enable_day_night_ratio_override = false;
	u32 m_day_night_ratio_override = 0.0f;
	// Days from the server start, accounts for time shift
	// in game (e.g. /time or bed usage)
	std::atomic<u32> m_day_count;
	/*
	 * Above: values managed by m_time_lock
	 */

	/* TODO: Add a callback function so these can be updated when a setting
	 *       changes.  At this point in time it doesn't matter (e.g. /set
	 *       is documented to change server settings only)
	 *
	 * TODO: Local caching of settings is not optimal and should at some stage
	 *       be updated to use a global settings object for getting thse values
	 *       (as opposed to the this local caching). This can be addressed in
	 *       a later release.
	 */
	bool m_cache_enable_shaders;
	float m_cache_active_block_mgmt_interval;
	float m_cache_abm_interval;
	float m_cache_nodetimer_interval;

	IGameDef *m_gamedef;

private:
	std::mutex m_time_lock;
};
' href='#n501'>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 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809
/*
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 "util/numeric.h"
#include "map.h"
#include "mapgen.h"
#include "mapgen_v5.h"
#include "mapgen_v6.h"
#include "mapgen_v7.h"
#include "cavegen.h"

NoiseParams nparams_caveliquids(0, 1, v3f(150.0, 150.0, 150.0), 776, 3, 0.6, 2.0);


///////////////////////////////////////// Caves V5


CaveV5::CaveV5(MapgenV5 *mg, PseudoRandom *ps)
{
	this->mg             = mg;
	this->vm             = mg->vm;
	this->ndef           = mg->ndef;
	this->water_level    = mg->water_level;
	this->ps             = ps;
	this->c_water_source = mg->c_water_source;
	this->c_lava_source  = mg->c_lava_source;
	this->c_ice          = mg->c_ice;
	this->np_caveliquids = &nparams_caveliquids;

	dswitchint = ps->range(1, 14);
	flooded    = ps->range(1, 2) == 2;

	part_max_length_rs  = ps->range(2, 4);
	tunnel_routepoints  = ps->range(5, ps->range(15, 30));
	min_tunnel_diameter = 5;
	max_tunnel_diameter = ps->range(7, ps->range(8, 24));

	large_cave_is_flat = (ps->range(0, 1) == 0);
}


void CaveV5::makeCave(v3s16 nmin, v3s16 nmax, int max_stone_height)
{
	node_min = nmin;
	node_max = nmax;
	main_direction = v3f(0, 0, 0);

	// Allowed route area size in nodes
	ar = node_max - node_min + v3s16(1, 1, 1);
	// Area starting point in nodes
	of = node_min;

	// Allow a bit more
	//(this should be more than the maximum radius of the tunnel)
	s16 insure = 10;
	s16 more = MYMAX(MAP_BLOCKSIZE - max_tunnel_diameter / 2 - insure, 1);
	ar += v3s16(1,0,1) * more * 2;
	of -= v3s16(1,0,1) * more;

	route_y_min = 0;
	// Allow half a diameter + 7 over stone surface
	route_y_max = -of.Y + max_stone_y + max_tunnel_diameter / 2 + 7;

	// Limit maximum to area
	route_y_max = rangelim(route_y_max, 0, ar.Y - 1);

	s16 min = 0;
		if (node_min.Y < water_level && node_max.Y > water_level) {
			min = water_level - max_tunnel_diameter/3 - of.Y;
			route_y_max = water_level + max_tunnel_diameter/3 - of.Y;
		}
	route_y_min = ps->range(min, min + max_tunnel_diameter);
	route_y_min = rangelim(route_y_min, 0, route_y_max);

	s16 route_start_y_min = route_y_min;
	s16 route_start_y_max = route_y_max;

	route_start_y_min = rangelim(route_start_y_min, 0, ar.Y - 1);
	route_start_y_max = rangelim(route_start_y_max, route_start_y_min, ar.Y - 1);

	// Randomize starting position
	orp = v3f(
		(float)(ps->next() % ar.X) + 0.5,
		(float)(ps->range(route_start_y_min, route_start_y_max)) + 0.5,
		(float)(ps->next() % ar.Z) + 0.5
	);

	// Add generation notify begin event
	v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
	GenNotifyType notifytype = GENNOTIFY_LARGECAVE_BEGIN;
	mg->gennotify.addEvent(notifytype, abs_pos);

	// Generate some tunnel starting from orp
	for (u16 j = 0; j < tunnel_routepoints; j++)
		makeTunnel(j % dswitchint == 0);

	// Add generation notify end event
	abs_pos = v3s16(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
	notifytype = GENNOTIFY_LARGECAVE_END;
	mg->gennotify.addEvent(notifytype, abs_pos);
}


void CaveV5::makeTunnel(bool dirswitch)
{
	// Randomize size
	s16 min_d = min_tunnel_diameter;
	s16 max_d = max_tunnel_diameter;
	rs = ps->range(min_d, max_d);
	s16 rs_part_max_length_rs = rs * part_max_length_rs;

	v3s16 maxlen;
	maxlen = v3s16(
		rs_part_max_length_rs,
		rs_part_max_length_rs / 2,
		rs_part_max_length_rs
	);

	v3f vec;
	// Jump downward sometimes
	vec = v3f(
		(float)(ps->next() % maxlen.X) - (float)maxlen.X / 2,
		(float)(ps->next() % maxlen.Y) - (float)maxlen.Y / 2,
		(float)(ps->next() % maxlen.Z) - (float)maxlen.Z / 2
	);

	// Do not make caves that are above ground.
	// It is only necessary to check the startpoint and endpoint.
	v3s16 orpi(orp.X, orp.Y, orp.Z);
	v3s16 veci(vec.X, vec.Y, vec.Z);
	v3s16 p;

	p = orpi + veci + of + rs / 2;
	if (p.Z >= node_min.Z && p.Z <= node_max.Z &&
			p.X >= node_min.X && p.X <= node_max.X) {
		u32 index = (p.Z - node_min.Z) * mg->ystride + (p.X - node_min.X);
		s16 h = mg->heightmap[index];
		if (h < p.Y)
			return;
	} else if (p.Y > water_level) {
		return; // If it's not in our heightmap, use a simple heuristic
	}

	p = orpi + of + rs / 2;
	if (p.Z >= node_min.Z && p.Z <= node_max.Z &&
			p.X >= node_min.X && p.X <= node_max.X) {
		u32 index = (p.Z - node_min.Z) * mg->ystride + (p.X - node_min.X);
		s16 h = mg->heightmap[index];
		if (h < p.Y)
			return;
	} else if (p.Y > water_level) {
		return;
	}

	vec += main_direction;

	v3f rp = orp + vec;
	if (rp.X < 0)
		rp.X = 0;
	else if (rp.X >= ar.X)
		rp.X = ar.X - 1;

	if (rp.Y < route_y_min)
		rp.Y = route_y_min;
	else if (rp.Y >= route_y_max)
		rp.Y = route_y_max - 1;

	if (rp.Z < 0)
		rp.Z = 0;
	else if (rp.Z >= ar.Z)
		rp.Z = ar.Z - 1;

	vec = rp - orp;

	float veclen = vec.getLength();
	if (veclen < 0.05)
		veclen = 1.0;

	// Every second section is rough
	bool randomize_xz = (ps->range(1, 2) == 1);

	// Carve routes
	for (float f = 0; f < 1.0; f += 1.0 / veclen)
		carveRoute(vec, f, randomize_xz);

	orp = rp;
}


void CaveV5::carveRoute(v3f vec, float f, bool randomize_xz) 
{
	MapNode airnode(CONTENT_AIR);
	MapNode waternode(c_water_source);
	MapNode lavanode(c_lava_source);

	v3s16 startp(orp.X, orp.Y, orp.Z);
	startp += of;

	float nval = NoisePerlin3D(np_caveliquids, startp.X,
		startp.Y, startp.Z, mg->seed);
	MapNode liquidnode = nval < 0.40 ? lavanode : waternode;

	v3f fp = orp + vec * f;
	fp.X += 0.1 * ps->range(-10, 10);
	fp.Z += 0.1 * ps->range(-10, 10);
	v3s16 cp(fp.X, fp.Y, fp.Z);

	s16 d0 = -rs/2;
	s16 d1 = d0 + rs;
	if (randomize_xz) {
		d0 += ps->range(-1, 1);
		d1 += ps->range(-1, 1);
	}

	for (s16 z0 = d0; z0 <= d1; z0++) {
		s16 si = rs / 2 - MYMAX(0, abs(z0) - rs / 7 - 1);
		for (s16 x0 = -si - ps->range(0,1); x0 <= si - 1 + ps->range(0,1); x0++) {
			s16 maxabsxz = MYMAX(abs(x0), abs(z0));

			s16 si2 = rs / 2 - MYMAX(0, maxabsxz - rs / 7 - 1);

			for (s16 y0 = -si2; y0 <= si2; y0++) {
				if (large_cave_is_flat) {
					// Make large caves not so tall
					if (rs > 7 && abs(y0) >= rs / 3)
						continue;
				}

				v3s16 p(cp.X + x0, cp.Y + y0, cp.Z + z0);
				p += of;

				if (vm->m_area.contains(p) == false)
					continue;

				u32 i = vm->m_area.index(p);
				content_t c = vm->m_data[i].getContent();
				if (!ndef->get(c).is_ground_content)
					continue;

				int full_ymin = node_min.Y - MAP_BLOCKSIZE;
				int full_ymax = node_max.Y + MAP_BLOCKSIZE;

				if (flooded && full_ymin < water_level &&
						full_ymax > water_level)
					vm->m_data[i] = (p.Y <= water_level) ?
						waternode : airnode;
				else if (flooded && full_ymax < water_level)
					vm->m_data[i] = (p.Y < startp.Y - 4) ?
						liquidnode : airnode;
				else
					vm->m_data[i] = airnode;
			}
		}
	}
}


///////////////////////////////////////// Caves V6


CaveV6::CaveV6(MapgenV6 *mg, PseudoRandom *ps, PseudoRandom *ps2, bool is_large_cave)
{
	this->mg             = mg;
	this->vm             = mg->vm;
	this->ndef           = mg->ndef;
	this->water_level    = mg->water_level;
	this->large_cave     = is_large_cave;
	this->ps             = ps;
	this->ps2            = ps2;
	this->c_water_source = mg->c_water_source;
	this->c_lava_source  = mg->c_lava_source;

	min_tunnel_diameter = 2;
	max_tunnel_diameter = ps->range(2, 6);
	dswitchint          = ps->range(1, 14);
	flooded             = true;

	if (large_cave) {
		part_max_length_rs  = ps->range(2,4);
		tunnel_routepoints  = ps->range(5, ps->range(15,30));
		min_tunnel_diameter = 5;
		max_tunnel_diameter = ps->range(7, ps->range(8,24));
	} else {
		part_max_length_rs = ps->range(2,9);
		tunnel_routepoints = ps->range(10, ps->range(15,30));
	}

	large_cave_is_flat = (ps->range(0,1) == 0);
}


void CaveV6::makeCave(v3s16 nmin, v3s16 nmax, int max_stone_height)
{
	node_min = nmin;
	node_max = nmax;
	max_stone_y = max_stone_height;
	main_direction = v3f(0, 0, 0);

	// Allowed route area size in nodes
	ar = node_max - node_min + v3s16(1, 1, 1);
	// Area starting point in nodes
	of = node_min;

	// Allow a bit more
	//(this should be more than the maximum radius of the tunnel)
	const s16 max_spread_amount = MAP_BLOCKSIZE;
	s16 insure = 10;
	s16 more = MYMAX(max_spread_amount - max_tunnel_diameter / 2 - insure, 1);
	ar += v3s16(1,0,1) * more * 2;
	of -= v3s16(1,0,1) * more;

	route_y_min = 0;
	// Allow half a diameter + 7 over stone surface
	route_y_max = -of.Y + max_stone_y + max_tunnel_diameter / 2 + 7;

	// Limit maximum to area
	route_y_max = rangelim(route_y_max, 0, ar.Y - 1);

	if (large_cave) {
		s16 min = 0;
		if (node_min.Y < water_level && node_max.Y > water_level) {
			min = water_level - max_tunnel_diameter/3 - of.Y;
			route_y_max = water_level + max_tunnel_diameter/3 - of.Y;
		}
		route_y_min = ps->range(min, min + max_tunnel_diameter);
		route_y_min = rangelim(route_y_min, 0, route_y_max);
	}

	s16 route_start_y_min = route_y_min;
	s16 route_start_y_max = route_y_max;

	route_start_y_min = rangelim(route_start_y_min, 0, ar.Y-1);
	route_start_y_max = rangelim(route_start_y_max, route_start_y_min, ar.Y-1);

	// Randomize starting position
	orp = v3f(
		(float)(ps->next() % ar.X) + 0.5,
		(float)(ps->range(route_start_y_min, route_start_y_max)) + 0.5,
		(float)(ps->next() % ar.Z) + 0.5
	);

	// Add generation notify begin event
	v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
	GenNotifyType notifytype = large_cave ?
		GENNOTIFY_LARGECAVE_BEGIN : GENNOTIFY_CAVE_BEGIN;
	mg->gennotify.addEvent(notifytype, abs_pos);

	// Generate some tunnel starting from orp
	for (u16 j = 0; j < tunnel_routepoints; j++)
		makeTunnel(j % dswitchint == 0);

	// Add generation notify end event
	abs_pos = v3s16(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
	notifytype = large_cave ?
		GENNOTIFY_LARGECAVE_END : GENNOTIFY_CAVE_END;
	mg->gennotify.addEvent(notifytype, abs_pos);
}


void CaveV6::makeTunnel(bool dirswitch)
{
	if (dirswitch && !large_cave) {
		main_direction = v3f(
			((float)(ps->next() % 20) - (float)10) / 10,
			((float)(ps->next() % 20) - (float)10) / 30,
			((float)(ps->next() % 20) - (float)10) / 10
		);
		main_direction *= (float)ps->range(0, 10) / 10;
	}

	// Randomize size
	s16 min_d = min_tunnel_diameter;
	s16 max_d = max_tunnel_diameter;
	rs = ps->range(min_d, max_d);
	s16 rs_part_max_length_rs = rs * part_max_length_rs;

	v3s16 maxlen;
	if (large_cave) {
		maxlen = v3s16(
			rs_part_max_length_rs,
			rs_part_max_length_rs / 2,
			rs_part_max_length_rs
		);
	} else {
		maxlen = v3s16(
			rs_part_max_length_rs,
			ps->range(1, rs_part_max_length_rs),
			rs_part_max_length_rs
		);
	}

	v3f vec(
		(float)(ps->next() % maxlen.X) - (float)maxlen.X / 2,
		(float)(ps->next() % maxlen.Y) - (float)maxlen.Y / 2,
		(float)(ps->next() % maxlen.Z) - (float)maxlen.Z / 2
	);

	// Jump downward sometimes
	if (!large_cave && ps->range(0, 12) == 0) {
		vec = v3f(
			(float)(ps->next() % maxlen.X) - (float)maxlen.X / 2,
			(float)(ps->next() % (maxlen.Y * 2)) - (float)maxlen.Y,
			(float)(ps->next() % maxlen.Z) - (float)maxlen.Z / 2
		);
	}

	// Do not make caves that are entirely above ground, to fix
	// shadow bugs caused by overgenerated large caves.
	// It is only necessary to check the startpoint and endpoint.
	v3s16 orpi(orp.X, orp.Y, orp.Z);
	v3s16 veci(vec.X, vec.Y, vec.Z);
	s16 h1;
	s16 h2;

	v3s16 p1 = orpi + veci + of + rs / 2;
	if (p1.Z >= node_min.Z && p1.Z <= node_max.Z &&
			p1.X >= node_min.X && p1.X <= node_max.X) {
		u32 index1 = (p1.Z - node_min.Z) * mg->ystride +
			(p1.X - node_min.X);
		h1 = mg->heightmap[index1];
	} else {
		h1 = water_level; // If not in heightmap
	}

	v3s16 p2 = orpi + of + rs / 2;
	if (p2.Z >= node_min.Z && p2.Z <= node_max.Z &&
			p2.X >= node_min.X && p2.X <= node_max.X) {
		u32 index2 = (p2.Z - node_min.Z) * mg->ystride +
			(p2.X - node_min.X);
		h2 = mg->heightmap[index2];
	} else {
		h2 = water_level;
	}

	// If startpoint and endpoint are above ground,
	// disable placing of nodes in carveRoute while
	// still running all pseudorandom calls to ensure
	// caves consistent with existing worlds.
	bool tunnel_above_ground = p1.Y > h1 && p2.Y > h2;

	vec += main_direction;

	v3f rp = orp + vec;
	if (rp.X < 0)
		rp.X = 0;
	else if (rp.X >= ar.X)
		rp.X = ar.X - 1;

	if (rp.Y < route_y_min)
		rp.Y = route_y_min;
	else if (rp.Y >= route_y_max)
		rp.Y = route_y_max - 1;

	if (rp.Z < 0)
		rp.Z = 0;
	else if (rp.Z >= ar.Z)
		rp.Z = ar.Z - 1;

	vec = rp - orp;

	float veclen = vec.getLength();
	// As odd as it sounds, veclen is *exactly* 0.0 sometimes, causing a FPE
	if (veclen < 0.05)
		veclen = 1.0;

	// Every second section is rough
	bool randomize_xz = (ps2->range(1, 2) == 1);

	// Carve routes
	for (float f = 0; f < 1.0; f += 1.0 / veclen)
		carveRoute(vec, f, randomize_xz, tunnel_above_ground);

	orp = rp;
}


void CaveV6::carveRoute(v3f vec, float f, bool randomize_xz, bool tunnel_above_ground)
{
	MapNode airnode(CONTENT_AIR);
	MapNode waternode(c_water_source);
	MapNode lavanode(c_lava_source);

	v3s16 startp(orp.X, orp.Y, orp.Z);
	startp += of;

	v3f fp = orp + vec * f;
	fp.X += 0.1 * ps->range(-10, 10);
	fp.Z += 0.1 * ps->range(-10, 10);
	v3s16 cp(fp.X, fp.Y, fp.Z);

	s16 d0 = -rs/2;
	s16 d1 = d0 + rs;
	if (randomize_xz) {
		d0 += ps->range(-1, 1);
		d1 += ps->range(-1, 1);
	}

	for (s16 z0 = d0; z0 <= d1; z0++) {
		s16 si = rs / 2 - MYMAX(0, abs(z0) - rs / 7 - 1);
		for (s16 x0 = -si - ps->range(0,1); x0 <= si - 1 + ps->range(0,1); x0++) {
			if (tunnel_above_ground)
				continue;

			s16 maxabsxz = MYMAX(abs(x0), abs(z0));
			s16 si2 = rs / 2 - MYMAX(0, maxabsxz - rs / 7 - 1);
			for (s16 y0 = -si2; y0 <= si2; y0++) {
				if (large_cave_is_flat) {
					// Make large caves not so tall
					if (rs > 7 && abs(y0) >= rs / 3)
						continue;
				}

				v3s16 p(cp.X + x0, cp.Y + y0, cp.Z + z0);
				p += of;

				if (vm->m_area.contains(p) == false)
					continue;

				u32 i = vm->m_area.index(p);
				content_t c = vm->m_data[i].getContent();
				if (!ndef->get(c).is_ground_content)
					continue;

				if (large_cave) {
					int full_ymin = node_min.Y - MAP_BLOCKSIZE;
					int full_ymax = node_max.Y + MAP_BLOCKSIZE;

					if (flooded && full_ymin < water_level &&
							full_ymax > water_level) {
						vm->m_data[i] = (p.Y <= water_level) ?
							waternode : airnode;
					} else if (flooded && full_ymax < water_level) {
						vm->m_data[i] = (p.Y < startp.Y - 2) ?
							lavanode : airnode;
					} else {
						vm->m_data[i] = airnode;
					}
				} else {
					if (c == CONTENT_IGNORE || c == CONTENT_AIR)
						continue;

					vm->m_data[i] = airnode;
					vm->m_flags[i] |= VMANIP_FLAG_CAVE;
				}
			}
		}
	}
}


///////////////////////////////////////// Caves V7


CaveV7::CaveV7(MapgenV7 *mg, PseudoRandom *ps)
{
	this->mg             = mg;
	this->vm             = mg->vm;
	this->ndef           = mg->ndef;
	this->water_level    = mg->water_level;
	this->ps             = ps;
	this->c_water_source = mg->c_water_source;
	this->c_lava_source  = mg->c_lava_source;
	this->c_ice          = mg->c_ice;
	this->np_caveliquids = &nparams_caveliquids;

	dswitchint = ps->range(1, 14);
	flooded    = ps->range(1, 2) == 2;

	part_max_length_rs  = ps->range(2, 4);
	tunnel_routepoints  = ps->range(5, ps->range(15, 30));
	min_tunnel_diameter = 5;
	max_tunnel_diameter = ps->range(7, ps->range(8, 24));

	large_cave_is_flat = (ps->range(0, 1) == 0);
}


void CaveV7::makeCave(v3s16 nmin, v3s16 nmax, int max_stone_height)
{
	node_min = nmin;
	node_max = nmax;
	max_stone_y = max_stone_height;
	main_direction = v3f(0, 0, 0);

	// Allowed route area size in nodes
	ar = node_max - node_min + v3s16(1, 1, 1);
	// Area starting point in nodes
	of = node_min;

	// Allow a bit more
	//(this should be more than the maximum radius of the tunnel)
	s16 insure = 10;
	s16 more = MYMAX(MAP_BLOCKSIZE - max_tunnel_diameter / 2 - insure, 1);
	ar += v3s16(1,0,1) * more * 2;
	of -= v3s16(1,0,1) * more;

	route_y_min = 0;
	// Allow half a diameter + 7 over stone surface
	route_y_max = -of.Y + max_stone_y + max_tunnel_diameter / 2 + 7;

	// Limit maximum to area
	route_y_max = rangelim(route_y_max, 0, ar.Y - 1);

	s16 min = 0;
	if (node_min.Y < water_level && node_max.Y > water_level) {
		min = water_level - max_tunnel_diameter/3 - of.Y;
		route_y_max = water_level + max_tunnel_diameter/3 - of.Y;
	}
	route_y_min = ps->range(min, min + max_tunnel_diameter);
	route_y_min = rangelim(route_y_min, 0, route_y_max);

	s16 route_start_y_min = route_y_min;
	s16 route_start_y_max = route_y_max;

	route_start_y_min = rangelim(route_start_y_min, 0, ar.Y - 1);
	route_start_y_max = rangelim(route_start_y_max, route_start_y_min, ar.Y - 1);

	// Randomize starting position
	orp = v3f(
		(float)(ps->next() % ar.X) + 0.5,
		(float)(ps->range(route_start_y_min, route_start_y_max)) + 0.5,
		(float)(ps->next() % ar.Z) + 0.5
	);

	// Add generation notify begin event
	v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
	GenNotifyType notifytype = GENNOTIFY_LARGECAVE_BEGIN;
	mg->gennotify.addEvent(notifytype, abs_pos);

	// Generate some tunnel starting from orp
	for (u16 j = 0; j < tunnel_routepoints; j++)
		makeTunnel(j % dswitchint == 0);

	// Add generation notify end event
	abs_pos = v3s16(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
	notifytype = GENNOTIFY_LARGECAVE_END;
	mg->gennotify.addEvent(notifytype, abs_pos);
}


void CaveV7::makeTunnel(bool dirswitch)
{
	// Randomize size
	s16 min_d = min_tunnel_diameter;
	s16 max_d = max_tunnel_diameter;
	rs = ps->range(min_d, max_d);
	s16 rs_part_max_length_rs = rs * part_max_length_rs;

	v3s16 maxlen;
	maxlen = v3s16(
		rs_part_max_length_rs,
		rs_part_max_length_rs / 2,
		rs_part_max_length_rs
	);

	v3f vec;
	// Jump downward sometimes
	vec = v3f(
		(float)(ps->next() % maxlen.X) - (float)maxlen.X / 2,
		(float)(ps->next() % maxlen.Y) - (float)maxlen.Y / 2,
		(float)(ps->next() % maxlen.Z) - (float)maxlen.Z / 2
	);

	// Do not make caves that are above ground.
	// It is only necessary to check the startpoint and endpoint.
	v3s16 orpi(orp.X, orp.Y, orp.Z);
	v3s16 veci(vec.X, vec.Y, vec.Z);
	v3s16 p;

	p = orpi + veci + of + rs / 2;
	if (p.Z >= node_min.Z && p.Z <= node_max.Z &&
			p.X >= node_min.X && p.X <= node_max.X) {
		u32 index = (p.Z - node_min.Z) * mg->ystride + (p.X - node_min.X);
		s16 h = mg->ridge_heightmap[index];
		if (h < p.Y)
			return;
	} else if (p.Y > water_level) {
		return; // If it's not in our heightmap, use a simple heuristic
	}

	p = orpi + of + rs / 2;
	if (p.Z >= node_min.Z && p.Z <= node_max.Z &&
			p.X >= node_min.X && p.X <= node_max.X) {
		u32 index = (p.Z - node_min.Z) * mg->ystride + (p.X - node_min.X);
		s16 h = mg->ridge_heightmap[index];
		if (h < p.Y)
			return;
	} else if (p.Y > water_level) {
		return;
	}

	vec += main_direction;

	v3f rp = orp + vec;
	if (rp.X < 0)
		rp.X = 0;
	else if (rp.X >= ar.X)
		rp.X = ar.X - 1;

	if (rp.Y < route_y_min)
		rp.Y = route_y_min;
	else if (rp.Y >= route_y_max)
		rp.Y = route_y_max - 1;

	if (rp.Z < 0)
		rp.Z = 0;
	else if (rp.Z >= ar.Z)
		rp.Z = ar.Z - 1;

	vec = rp - orp;

	float veclen = vec.getLength();
	if (veclen < 0.05)
		veclen = 1.0;

	// Every second section is rough
	bool randomize_xz = (ps->range(1, 2) == 1);

	// Carve routes
	for (float f = 0; f < 1.0; f += 1.0 / veclen)
		carveRoute(vec, f, randomize_xz);

	orp = rp;
}


void CaveV7::carveRoute(v3f vec, float f, bool randomize_xz)
{
	MapNode airnode(CONTENT_AIR);
	MapNode waternode(c_water_source);
	MapNode lavanode(c_lava_source);

	v3s16 startp(orp.X, orp.Y, orp.Z);
	startp += of;

	float nval = NoisePerlin3D(np_caveliquids, startp.X,
		startp.Y, startp.Z, mg->seed);
	MapNode liquidnode = (nval < 0.40 && node_max.Y < MGV7_LAVA_DEPTH) ?
		lavanode : waternode;

	v3f fp = orp + vec * f;
	fp.X += 0.1 * ps->range(-10, 10);
	fp.Z += 0.1 * ps->range(-10, 10);
	v3s16 cp(fp.X, fp.Y, fp.Z);

	s16 d0 = -rs/2;
	s16 d1 = d0 + rs;
	if (randomize_xz) {
		d0 += ps->range(-1, 1);
		d1 += ps->range(-1, 1);
	}

	for (s16 z0 = d0; z0 <= d1; z0++) {
		s16 si = rs / 2 - MYMAX(0, abs(z0) - rs / 7 - 1);
		for (s16 x0 = -si - ps->range(0,1); x0 <= si - 1 + ps->range(0,1); x0++) {
			s16 maxabsxz = MYMAX(abs(x0), abs(z0));

			s16 si2 = rs / 2 - MYMAX(0, maxabsxz - rs / 7 - 1);