GLAND_RIVER_PULLDOWN,      ///< Dropdown 'Rivers'

				NWidget(NWID_HORIZONTAL), SetPIP(0, 3, 0),

					NWidget(WWT_TEXT, COLOUR_ORANGE), SetDataTip(STR_MAPGEN_QUANTITY_OF_RIVERS, STR_NULL), SetFill(1, 1),

					NWidget(WWT_DROPDOWN, COLOUR_ORANGE, GLAND_RIVER_PULLDOWN), SetDataTip(STR_JUST_STRING, STR_NULL), SetFill(1, 0),

				EndContainer(),

static const StringID _rivers[]      = {STR_RIVERS_NONE, STR_RIVERS_FEW, STR_RIVERS_MODERATE, STR_RIVERS_LOT, INVALID_STRING_ID};

			case GLAND_RIVER_PULLDOWN:      SetDParam(0, _rivers[_settings_newgame.game_creation.amount_of_rivers]); break;

			case GLAND_RIVER_PULLDOWN:      strs = _rivers; break;

			case GLAND_RIVER_PULLDOWN: // Amount of rivers

				ShowDropDownMenu(this, _rivers, _settings_newgame.game_creation.amount_of_rivers, GLAND_RIVER_PULLDOWN, 0, 0);

				break;

			case GLAND_RIVER_PULLDOWN:         _settings_newgame.game_creation.amount_of_rivers = index; break;

#include "pathfinder/npf/aystar.h"

#include <list>

/**

 * Find the spring of a river.

 * @param tile The tile to consider for being the spring.

 * @param user_data Ignored data.

 * @return True iff it is suitable as a spring.

 */

static bool FindSpring(TileIndex tile, void *user_data)

{

	uint referenceHeight;

	Slope s = GetTileSlope(tile, &referenceHeight);

	if (s != SLOPE_FLAT || IsWaterTile(tile)) return false;

	/* In the tropics rivers start in the rainforest. */

	if (_settings_game.game_creation.landscape == LT_TROPIC && GetTropicZone(tile) != TROPICZONE_RAINFOREST) return false;

	/* Are there enough higher tiles to warrant a 'spring'? */

	uint num = 0;

	for (int dx = -1; dx <= 1; dx++) {

		for (int dy = -1; dy <= 1; dy++) {

			TileIndex t = TileAddWrap(tile, dx, dy);

			if (t != INVALID_TILE && GetTileMaxZ(t) > referenceHeight) num++;

		}

	}

	if (num < 4) return false;

	/* Are we near the top of a hill? */

	for (int dx = -16; dx <= 16; dx++) {

		for (int dy = -16; dy <= 16; dy++) {

			TileIndex t = TileAddWrap(tile, dx, dy);

			if (t != INVALID_TILE && GetTileMaxZ(t) > referenceHeight + 2 * TILE_HEIGHT) return false;

		}

	}

	return true;

}

/**

 * Make a connected lake; fill all tiles in the circular tile search that are connected.

 * @param tile The tile to consider for lake making.

 * @param user_data The height of the lake.

 * @return Always false, so it continues searching.

 */

static bool MakeLake(TileIndex tile, void *user_data)

{

	uint height = *(uint*)user_data;

	if (!IsValidTile(tile) || TileHeight(tile) != height || GetTileSlope(tile, NULL) != SLOPE_FLAT) return false;

	if (_settings_game.game_creation.landscape == LT_TROPIC && GetTropicZone(tile) == TROPICZONE_DESERT) return false;

	for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {

		TileIndex t2 = tile + TileOffsByDiagDir(d);

		if (IsWaterTile(t2)) {

			MakeRiver(tile, Random());

			return false;

		}

	}

	return false;

}

/**

 * Check whether a river at begin could (logically) flow down to end.

 * @param begin The origin of the flow.

 * @param end The destination of the flow.

 * @return True iff the water can be flowing down.

 */

static bool FlowsDown(TileIndex begin, TileIndex end)

{

	assert(DistanceManhattan(begin, end) == 1);

	uint heightBegin;

	uint heightEnd;

	Slope slopeBegin = GetTileSlope(begin, &heightBegin);

	Slope slopeEnd   = GetTileSlope(end, &heightEnd);

	return heightEnd <= heightBegin &&

			/* Slope either is inclined or flat; rivers don't support other slopes. */

			(slopeEnd == SLOPE_FLAT || IsInclinedSlope(slopeEnd)) &&

			/* Slope continues, then it must be lower... or either end must be flat. */

			((slopeEnd == slopeBegin && heightEnd < heightBegin) || slopeEnd == SLOPE_FLAT || slopeBegin == SLOPE_FLAT);

}

/* AyStar callback for checking whether we reached our destination. */

static int32 River_EndNodeCheck(AyStar *aystar, OpenListNode *current)

{

	return current->path.node.tile == *(TileIndex*)aystar->user_target ? AYSTAR_FOUND_END_NODE : AYSTAR_DONE;

}

/* AyStar callback for getting the cost of the current node. */

static int32 River_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent)

{

	return 1 + RandomRange(_settings_game.game_creation.river_route_random);

}

/* AyStar callback for getting the estimated cost to the destination. */

static int32 River_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent)

{

	return DistanceManhattan(*(TileIndex*)aystar->user_target, current->tile);

}

/* AyStar callback for getting the neighbouring nodes of the given node. */

static void River_GetNeighbours(AyStar *aystar, OpenListNode *current)

{

	TileIndex tile = current->path.node.tile;

	aystar->num_neighbours = 0;

	for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {

		TileIndex t2 = tile + TileOffsByDiagDir(d);

		if (IsValidTile(t2) && FlowsDown(tile, t2)) {

			aystar->neighbours[aystar->num_neighbours].tile = t2;

			aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;

			aystar->num_neighbours++;

		}

	}

}

/* AyStar callback when an route has been found. */

static void River_FoundEndNode(AyStar *aystar, OpenListNode *current)

{

	for (PathNode *path = &current->path; path != NULL; path = path->parent) {

		if (!IsWaterTile(path->node.tile)) MakeRiver(path->node.tile, Random());

	}

}

static const uint RIVER_HASH_SIZE = 8; ///< The number of bits the hash for river finding should have.

/**

 * Simple hash function for river tiles to be used by AyStar.

 * @param tile The tile to hash.

 * @param dir The unused direction.

 * @return The hash for the tile.

 */

static uint River_Hash(uint tile, uint dir)

{

	return GB(TileHash(TileX(tile), TileY(tile)), 0, RIVER_HASH_SIZE);

}

/**

 * Actually build the river between the begin and end tiles using AyStar.

 * @param begin The begin of the river.

 * @param end The end of the river.

 */

static void BuildRiver(TileIndex begin, TileIndex end)

{

	AyStar finder;

	MemSetT(&finder, 0);

	finder.CalculateG = River_CalculateG;

	finder.CalculateH = River_CalculateH;

	finder.GetNeighbours = River_GetNeighbours;

	finder.EndNodeCheck = River_EndNodeCheck;

	finder.FoundEndNode = River_FoundEndNode;

	finder.user_target = &end;

	finder.Init(River_Hash, 1 << RIVER_HASH_SIZE);

	AyStarNode start;

	start.tile = begin;

	start.direction = INVALID_TRACKDIR;

	finder.AddStartNode(&start, 0);

	finder.Main();

	finder.Free();

}

/**

 * Try to flow the river down from a given begin.

 * @param marks  Array for temporary of iterated tiles.

 * @param spring The springing point of the river.

 * @param begin  The begin point we are looking from; somewhere down hill from the spring.

 * @return True iff a river could/has been built, otherwise false.

 */

static bool FlowRiver(bool *marks, TileIndex spring, TileIndex begin)

{

	uint height = TileHeight(begin);

	if (IsWaterTile(begin)) return DistanceManhattan(spring, begin) > _settings_game.game_creation.min_river_length;

	MemSetT(marks, 0, MapSize());

	marks[begin] = true;

	/* Breadth first search for the closest tile we can flow down to. */

	std::list<TileIndex> queue;

	queue.push_back(begin);

	bool found = false;

	uint count = 0; // Number of tiles considered; to be used for lake location guessing.

	TileIndex end;

	do {

		end = queue.front();

		queue.pop_front();

		uint height2 = TileHeight(end);

		if (GetTileSlope(end, NULL) == SLOPE_FLAT && (height2 < height || (height2 == height && IsWaterTile(end)))) {

			found = true;

			break;

		}

		for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {

			TileIndex t2 = end + TileOffsByDiagDir(d);

			if (IsValidTile(t2) && !marks[t2] && FlowsDown(end, t2)) {

				marks[t2] = true;

				count++;

				queue.push_back(t2);

			}

		}

	} while (!queue.empty());

	if (found) {

		/* Flow further down hill. */

		found = FlowRiver(marks, spring, end);

	} else if (count > 10) {

		/* Maybe we can make a lake. Find the Nth of the considered tiles. */

		TileIndex lakeCenter = 0;

		for (int i = RandomRange(count - 1); i != 0; lakeCenter++) {

			if (marks[lakeCenter]) i--;

		}

		if (IsValidTile(lakeCenter) &&

				/* A river, or lake, can only be built on flat slopes. */

				GetTileSlope(lakeCenter, NULL) == SLOPE_FLAT &&

				/* We want the lake to be built at the height of the river. */

				TileHeight(begin) == TileHeight(lakeCenter) &&

				/* We don't want the lake at the entry of the valley. */

				lakeCenter != begin &&

				/* We don't want lakes in the desert. */

				(_settings_game.game_creation.landscape != LT_TROPIC || GetTropicZone(lakeCenter) != TROPICZONE_DESERT) &&

				/* We only want a lake if the river is long enough. */

				DistanceManhattan(spring, lakeCenter) > _settings_game.game_creation.min_river_length) {

			end = lakeCenter;

			MakeRiver(lakeCenter, Random());

			uint range = RandomRange(8) + 3;

			CircularTileSearch(&lakeCenter, range, MakeLake, &height);

			/* Call the search a second time so artefacts from going circular in one direction get (mostly) hidden. */

			lakeCenter = end;

			CircularTileSearch(&lakeCenter, range, MakeLake, &height);

			found = true;

		}

	}

	if (found) BuildRiver(begin, end);

	return found;

}

/**

 * Actually (try to) create some rivers.

 */

static void CreateRivers()

{

	int amount = _settings_game.game_creation.amount_of_rivers;

	if (amount == 0) return;

	bool *marks = CallocT<bool>(MapSize());

	for (uint wells = ScaleByMapSize(4 << _settings_game.game_creation.amount_of_rivers); wells != 0; wells--) {

		for (int tries = 0; tries < 128; tries++) {

			TileIndex t = RandomTile();

			if (!CircularTileSearch(&t, 8, FindSpring, NULL)) continue;

			if (FlowRiver(marks, t, t)) break;

		}

	}

	free(marks);

}

	CreateRivers();

STR_RIVERS_NONE                                                 :None

STR_RIVERS_FEW                                                  :Few

STR_RIVERS_MODERATE                                             :Medium

STR_RIVERS_LOT                                                  :Many

STR_MAPGEN_QUANTITY_OF_RIVERS                                   :{BLACK}Rivers:

 *  163   22767

extern const uint16 SAVEGAME_VERSION = 163; ///< Current savegame version of OpenTTD.

	byte   min_river_length;                 ///< the minimum river length

	byte   river_route_random;               ///< the amount of randomicity for the route finding

	byte   amount_of_rivers;                 ///< the amount of rivers

[SDT_VAR]

base     = GameSettings

var      = game_creation.min_river_length

type     = SLE_UINT8

from     = 163

def      = 16

min      = 2

max      = 255

[SDT_VAR]

base     = GameSettings

var      = game_creation.river_route_random

type     = SLE_UINT8

from     = 163

def      = 5

min      = 1

max      = 255

[SDT_VAR]

base     = GameSettings

var      = game_creation.amount_of_rivers

type     = SLE_UINT8

from     = 163

def      = 2

min      = 0

max      = 3