From 0041408e4fa59b0639bfbd475314421c343a3ce8 Mon Sep 17 00:00:00 2001 From: rubidium Date: Sat, 20 Aug 2011 14:14:17 +0000 Subject: (svn r22767) -Add: river generation --- src/genworld_gui.cpp | 13 +++ src/landscape.cpp | 266 ++++++++++++++++++++++++++++++++++++++++++++++ src/lang/english.txt | 6 ++ src/saveload/saveload.cpp | 3 +- src/settings_type.h | 3 + src/table/settings.ini | 27 +++++ 6 files changed, 317 insertions(+), 1 deletion(-) 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 #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 = ¤t->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 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(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] -- cgit v1.2.3-54-g00ecf