(svn r22767) -Add: river generation

6 files changed, 317 insertions, 1 deletions

diff --git a/src/genworld_gui.cpp b/src/genworld_gui.cpp
index b6905ada7..440e88b0d 100644
--- a/src/genworld_gui.cpp
+++ b/src/genworld_gui.cpp
@@ -92,6 +92,7 @@ enum GenerateLandscapeWindowWidgets {
 
 	GLAND_TERRAIN_PULLDOWN,    ///< Dropdown 'Terrain type'
 	GLAND_WATER_PULLDOWN,      ///< Dropdown 'Sea level'
+	GLAND_RIVER_PULLDOWN,      ///< Dropdown 'Rivers'
 	GLAND_SMOOTHNESS_PULLDOWN, ///< Dropdown 'Smoothness'
 	GLAND_VARIETY_PULLDOWN,    ///< Dropdown 'Variety distribution'
 
@@ -181,6 +182,10 @@ static const NWidgetPart _nested_generate_landscape_widgets[] = {
 					EndContainer(),
 				EndContainer(),
 				NWidget(WWT_TEXTBTN, COLOUR_ORANGE, GLAND_RANDOM_BUTTON), SetDataTip(STR_MAPGEN_RANDOM, STR_MAPGEN_RANDOM_HELP), SetFill(1, 0),
+				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(),
 				NWidget(NWID_SPACER), SetFill(1, 1),
 				NWidget(WWT_TEXTBTN, COLOUR_GREEN, GLAND_GENERATE_BUTTON), SetMinimalSize(84, 30), SetDataTip(STR_MAPGEN_GENERATE, STR_NULL), SetFill(1, 0),
 			EndContainer(),
@@ -331,6 +336,7 @@ static DropDownList *BuildMapsizeDropDown()
 
 static const StringID _elevations[]  = {STR_TERRAIN_TYPE_VERY_FLAT, STR_TERRAIN_TYPE_FLAT, STR_TERRAIN_TYPE_HILLY, STR_TERRAIN_TYPE_MOUNTAINOUS, INVALID_STRING_ID};
 static const StringID _sea_lakes[]   = {STR_SEA_LEVEL_VERY_LOW, STR_SEA_LEVEL_LOW, STR_SEA_LEVEL_MEDIUM, STR_SEA_LEVEL_HIGH, STR_SEA_LEVEL_CUSTOM, INVALID_STRING_ID};
+static const StringID _rivers[]      = {STR_RIVERS_NONE, STR_RIVERS_FEW, STR_RIVERS_MODERATE, STR_RIVERS_LOT, INVALID_STRING_ID};
 static const StringID _smoothness[]  = {STR_CONFIG_SETTING_ROUGHNESS_OF_TERRAIN_VERY_SMOOTH, STR_CONFIG_SETTING_ROUGHNESS_OF_TERRAIN_SMOOTH, STR_CONFIG_SETTING_ROUGHNESS_OF_TERRAIN_ROUGH, STR_CONFIG_SETTING_ROUGHNESS_OF_TERRAIN_VERY_ROUGH, INVALID_STRING_ID};
 static const StringID _tree_placer[] = {STR_CONFIG_SETTING_TREE_PLACER_NONE, STR_CONFIG_SETTING_TREE_PLACER_ORIGINAL, STR_CONFIG_SETTING_TREE_PLACER_IMPROVED, INVALID_STRING_ID};
 static const StringID _rotation[]    = {STR_CONFIG_SETTING_HEIGHTMAP_ROTATION_COUNTER_CLOCKWISE, STR_CONFIG_SETTING_HEIGHTMAP_ROTATION_CLOCKWISE, INVALID_STRING_ID};
@@ -404,6 +410,7 @@ struct GenerateLandscapeWindow : public QueryStringBaseWindow {
 				}
 				break;
 
+			case GLAND_RIVER_PULLDOWN:      SetDParam(0, _rivers[_settings_newgame.game_creation.amount_of_rivers]); break;
 			case GLAND_SMOOTHNESS_PULLDOWN: SetDParam(0, _smoothness[_settings_newgame.game_creation.tgen_smoothness]); break;
 			case GLAND_VARIETY_PULLDOWN:    SetDParam(0, _variety[_settings_newgame.game_creation.variety]); break;
 			case GLAND_BORDERS_RANDOM:      SetDParam(0, (_settings_newgame.game_creation.water_borders == BORDERS_RANDOM) ? STR_MAPGEN_BORDER_RANDOMIZE : STR_MAPGEN_BORDER_MANUAL); break;
@@ -517,6 +524,7 @@ struct GenerateLandscapeWindow : public QueryStringBaseWindow {
 				*size = GetStringBoundingBox(STR_SEA_LEVEL_CUSTOM_PERCENTAGE);
 				break;
 
+			case GLAND_RIVER_PULLDOWN:      strs = _rivers; break;
 			case GLAND_SMOOTHNESS_PULLDOWN: strs = _smoothness; break;
 			case GLAND_VARIETY_PULLDOWN:    strs = _variety; break;
 			case GLAND_HEIGHTMAP_ROTATION_PULLDOWN: strs = _rotation; break;
@@ -691,6 +699,10 @@ struct GenerateLandscapeWindow : public QueryStringBaseWindow {
 				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_SMOOTHNESS_PULLDOWN: // Map smoothness
 				ShowDropDownMenu(this, _smoothness, _settings_newgame.game_creation.tgen_smoothness, GLAND_SMOOTHNESS_PULLDOWN, 0, 0);
 				break;
@@ -761,6 +773,7 @@ struct GenerateLandscapeWindow : public QueryStringBaseWindow {
 			case GLAND_MAPSIZE_X_PULLDOWN:     _settings_newgame.game_creation.map_x = index; break;
 			case GLAND_MAPSIZE_Y_PULLDOWN:     _settings_newgame.game_creation.map_y = index; break;
 			case GLAND_TREE_PULLDOWN:          _settings_newgame.game_creation.tree_placer = index; break;
+			case GLAND_RIVER_PULLDOWN:         _settings_newgame.game_creation.amount_of_rivers = index; break;
 			case GLAND_SMOOTHNESS_PULLDOWN:    _settings_newgame.game_creation.tgen_smoothness = index;  break;
 			case GLAND_VARIETY_PULLDOWN:       _settings_newgame.game_creation.variety = index; break;
 			case GLAND_LANDSCAPE_PULLDOWN:     _settings_newgame.game_creation.land_generator = index; break;
diff --git a/src/landscape.cpp b/src/landscape.cpp
index d095dec53..0aec2cc8c 100644
--- a/src/landscape.cpp
+++ b/src/landscape.cpp
@@ -32,6 +32,8 @@
 #include "water_map.h"
 #include "economy_func.h"
 #include "company_func.h"
+#include "pathfinder/npf/aystar.h"
+#include <list>
 
 #include "table/strings.h"
 #include "table/sprites.h"
@@ -916,6 +918,268 @@ static void CreateDesertOrRainForest()
 	}
 }
 
+/**
+ * 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);
+}
+
 void GenerateLandscape(byte mode)
 {
 	/** Number of steps of landscape generation */
@@ -997,6 +1261,8 @@ void GenerateLandscape(byte mode)
 	IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
 
 	if (_settings_game.game_creation.landscape == LT_TROPIC) CreateDesertOrRainForest();
+
+	CreateRivers();
 }
 
 void OnTick_Town();
diff --git a/src/lang/english.txt b/src/lang/english.txt
index 109a2e70a..ff3de3157 100644
--- a/src/lang/english.txt
+++ b/src/lang/english.txt
@@ -1059,6 +1059,11 @@ STR_SEA_LEVEL_HIGH                                              :High
 STR_SEA_LEVEL_CUSTOM                                            :Custom
 STR_SEA_LEVEL_CUSTOM_PERCENTAGE                                 :Custom ({NUM}%)
 
+STR_RIVERS_NONE                                                 :None
+STR_RIVERS_FEW                                                  :Few
+STR_RIVERS_MODERATE                                             :Medium
+STR_RIVERS_LOT                                                  :Many
+
 STR_DISASTER_NONE                                               :None
 STR_DISASTER_REDUCED                                            :Reduced
 STR_DISASTER_NORMAL                                             :Normal
@@ -2317,6 +2322,7 @@ STR_MAPGEN_LAND_GENERATOR                                       :{BLACK}Land gen
 STR_MAPGEN_TREE_PLACER                                          :{BLACK}Tree algorithm:
 STR_MAPGEN_TERRAIN_TYPE                                         :{BLACK}Terrain type:
 STR_MAPGEN_QUANTITY_OF_SEA_LAKES                                :{BLACK}Sea level:
+STR_MAPGEN_QUANTITY_OF_RIVERS                                   :{BLACK}Rivers:
 STR_MAPGEN_SMOOTHNESS                                           :{BLACK}Smoothness:
 STR_MAPGEN_VARIETY                                              :{BLACK}Variety distribution:
 STR_MAPGEN_GENERATE                                             :{WHITE}Generate
diff --git a/src/saveload/saveload.cpp b/src/saveload/saveload.cpp
index 162776533..8933baed6 100644
--- a/src/saveload/saveload.cpp
+++ b/src/saveload/saveload.cpp
@@ -227,8 +227,9 @@
  *  160   21974
  *  161   22567
  *  162   22713
+ *  163   22767
  */
-extern const uint16 SAVEGAME_VERSION = 162; ///< Current savegame version of OpenTTD.
+extern const uint16 SAVEGAME_VERSION = 163; ///< Current savegame version of OpenTTD.
 
 SavegameType _savegame_type; ///< type of savegame we are loading
 
diff --git a/src/settings_type.h b/src/settings_type.h
index 5ff4a0637..f9c1abdb1 100644
--- a/src/settings_type.h
+++ b/src/settings_type.h
@@ -219,6 +219,9 @@ struct GameCreationSettings {
 	uint16 custom_town_number;               ///< manually entered number of towns
 	byte   variety;                          ///< variety level applied to TGP
 	byte   custom_sea_level;                 ///< manually entered percentage of water in the map
+	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
 };
 
 /** Settings related to construction in-game */
diff --git a/src/table/settings.ini b/src/table/settings.ini
index c5fe20ee4..03d9654f0 100644
--- a/src/table/settings.ini
+++ b/src/table/settings.ini
@@ -1860,6 +1860,33 @@ def      = 1
 min      = 2
 max      = 90
 
+[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
+
 ; locale
 
 [SDT_OMANY]