summaryrefslogtreecommitdiff
path: root/src/landscape.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/landscape.cpp')
-rw-r--r--src/landscape.cpp266
1 files changed, 266 insertions, 0 deletions
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();