src/landscape.cpp

   1 /* $Id$ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   6  * OpenTTD 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.
   7  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   8  */
   9
  10 /** @file landscape.cpp Functions related to the landscape (slopes etc.). */
  11
  12 /** @defgroup SnowLineGroup Snowline functions and data structures */
  13
  14 #include "stdafx.h"
  15 #include "heightmap.h"
  16 #include "clear_map.h"
  17 #include "spritecache.h"
  18 #include "viewport_func.h"
  19 #include "command_func.h"
  20 #include "tunnelbridge_map.h"
  21 #include "landscape.h"
  22 #include "void_map.h"
  23 #include "tgp.h"
  24 #include "genworld.h"
  25 #include "fios.h"
  26 #include "date_func.h"
  27 #include "water.h"
  28 #include "effectvehicle_func.h"
  29 #include "landscape_type.h"
  30 #include "animated_tile_func.h"
  31 #include "core/random_func.hpp"
  32 #include "object_base.h"
  33 #include "company_func.h"
  34 #include "pathfinder/npf/aystar.h"
  35 #include "saveload/saveload.h"
  36 #include "3rdparty/cpp-btree/btree_set.h"
  37 #include <algorithm>
  38 #include <deque>
  39
  40 #include "table/strings.h"
  41 #include "table/sprites.h"
  42
  43 #include "safeguards.h"
  44
  45 extern const TileTypeProcs
  46         _tile_type_clear_procs,
  47         _tile_type_rail_procs,
  48         _tile_type_road_procs,
  49         _tile_type_town_procs,
  50         _tile_type_trees_procs,
  51         _tile_type_station_procs,
  52         _tile_type_water_procs,
  53         _tile_type_void_procs,
  54         _tile_type_industry_procs,
  55         _tile_type_tunnelbridge_procs,
  56         _tile_type_object_procs;
  57
  58 /**
  59  * Tile callback functions for each type of tile.
  60  * @ingroup TileCallbackGroup
  61  * @see TileType
  62  */
  63 const TileTypeProcs * const _tile_type_procs[16] = {
  64         &_tile_type_clear_procs,        ///< Callback functions for MP_CLEAR tiles
  65         &_tile_type_rail_procs,         ///< Callback functions for MP_RAILWAY tiles
  66         &_tile_type_road_procs,         ///< Callback functions for MP_ROAD tiles
  67         &_tile_type_town_procs,         ///< Callback functions for MP_HOUSE tiles
  68         &_tile_type_trees_procs,        ///< Callback functions for MP_TREES tiles
  69         &_tile_type_station_procs,      ///< Callback functions for MP_STATION tiles
  70         &_tile_type_water_procs,        ///< Callback functions for MP_WATER tiles
  71         &_tile_type_void_procs,         ///< Callback functions for MP_VOID tiles
  72         &_tile_type_industry_procs,     ///< Callback functions for MP_INDUSTRY tiles
  73         &_tile_type_tunnelbridge_procs, ///< Callback functions for MP_TUNNELBRIDGE tiles
  74         &_tile_type_object_procs,       ///< Callback functions for MP_OBJECT tiles
  75 };
  76
  77 /** landscape slope => sprite */
  78 extern const byte _slope_to_sprite_offset[32] = {
  79         0, 1, 2, 3, 4, 5, 6,  7, 8, 9, 10, 11, 12, 13, 14, 0,
  80         0, 0, 0, 0, 0, 0, 0, 16, 0, 0,  0, 17,  0, 15, 18, 0,
  81 };
  82
  83 /**
  84  * Description of the snow line throughout the year.
  85  *
  86  * If it is \c nullptr, a static snowline height is used, as set by \c _settings_game.game_creation.snow_line_height.
  87  * Otherwise it points to a table loaded from a newGRF file that describes the variable snowline.
  88  * @ingroup SnowLineGroup
  89  * @see GetSnowLine() GameCreationSettings
  90  */
  91 static SnowLine *_snow_line = nullptr;
  92
  93 static const int LONG_RIVER_LENGTH = 512;
  94 static TileIndex _current_spring = INVALID_TILE;
  95 static TileIndex _current_estuary = INVALID_TILE;
  96 static bool _is_main_river = false;
  97
  98 /**
  99  * Applies a foundation to a slope.
 100  *
 101  * @pre      Foundation and slope must be valid combined.
 102  * @param f  The #Foundation.
 103  * @param s  The #Slope to modify.
 104  * @return   Increment to the tile Z coordinate.
 105  */
 106 uint ApplyFoundationToSlope(Foundation f, Slope *s)
 107 {
 108         if (!IsFoundation(f)) return 0;
 109
 110         if (IsLeveledFoundation(f)) {
 111                 uint dz = 1 + (IsSteepSlope(*s) ? 1 : 0);
 112                 *s = SLOPE_FLAT;
 113                 return dz;
 114         }
 115
 116         if (f != FOUNDATION_STEEP_BOTH && IsNonContinuousFoundation(f)) {
 117                 *s = HalftileSlope(*s, GetHalftileFoundationCorner(f));
 118                 return 0;
 119         }
 120
 121         if (IsSpecialRailFoundation(f)) {
 122                 *s = SlopeWithThreeCornersRaised(OppositeCorner(GetRailFoundationCorner(f)));
 123                 return 0;
 124         }
 125
 126         uint dz = IsSteepSlope(*s) ? 1 : 0;
 127         Corner highest_corner = GetHighestSlopeCorner(*s);
 128
 129         switch (f) {
 130                 case FOUNDATION_INCLINED_X:
 131                         *s = (((highest_corner == CORNER_W) || (highest_corner == CORNER_S)) ? SLOPE_SW : SLOPE_NE);
 132                         break;
 133
 134                 case FOUNDATION_INCLINED_Y:
 135                         *s = (((highest_corner == CORNER_S) || (highest_corner == CORNER_E)) ? SLOPE_SE : SLOPE_NW);
 136                         break;
 137
 138                 case FOUNDATION_STEEP_LOWER:
 139                         *s = SlopeWithOneCornerRaised(highest_corner);
 140                         break;
 141
 142                 case FOUNDATION_STEEP_BOTH:
 143                         *s = HalftileSlope(SlopeWithOneCornerRaised(highest_corner), highest_corner);
 144                         break;
 145
 146                 default: NOT_REACHED();
 147         }
 148         return dz;
 149 }
 150
 151
 152 /**
 153  * Determines height at given coordinate of a slope
 154  * @param x x coordinate
 155  * @param y y coordinate
 156  * @param corners slope to examine
 157  * @return height of given point of given slope
 158  */
 159 uint GetPartialPixelZ(int x, int y, Slope corners)
 160 {
 161         if (IsHalftileSlope(corners)) {
 162                 switch (GetHalftileSlopeCorner(corners)) {
 163                         case CORNER_W:
 164                                 if (x - y >= 0) return GetSlopeMaxPixelZ(corners);
 165                                 break;
 166
 167                         case CORNER_S:
 168                                 if (x - (y ^ 0xF) >= 0) return GetSlopeMaxPixelZ(corners);
 169                                 break;
 170
 171                         case CORNER_E:
 172                                 if (y - x >= 0) return GetSlopeMaxPixelZ(corners);
 173                                 break;
 174
 175                         case CORNER_N:
 176                                 if ((y ^ 0xF) - x >= 0) return GetSlopeMaxPixelZ(corners);
 177                                 break;
 178
 179                         default: NOT_REACHED();
 180                 }
 181         }
 182
 183         int z = 0;
 184
 185         switch (RemoveHalftileSlope(corners)) {
 186                 case SLOPE_W:
 187                         if (x - y >= 0) {
 188                                 z = (x - y) >> 1;
 189                         }
 190                         break;
 191
 192                 case SLOPE_S:
 193                         y ^= 0xF;
 194                         if ((x - y) >= 0) {
 195                                 z = (x - y) >> 1;
 196                         }
 197                         break;
 198
 199                 case SLOPE_SW:
 200                         z = (x >> 1) + 1;
 201                         break;
 202
 203                 case SLOPE_E:
 204                         if (y - x >= 0) {
 205                                 z = (y - x) >> 1;
 206                         }
 207                         break;
 208
 209                 case SLOPE_EW:
 210                 case SLOPE_NS:
 211                 case SLOPE_ELEVATED:
 212                         z = 4;
 213                         break;
 214
 215                 case SLOPE_SE:
 216                         z = (y >> 1) + 1;
 217                         break;
 218
 219                 case SLOPE_WSE:
 220                         z = 8;
 221                         y ^= 0xF;
 222                         if (x - y < 0) {
 223                                 z += (x - y) >> 1;
 224                         }
 225                         break;
 226
 227                 case SLOPE_N:
 228                         y ^= 0xF;
 229                         if (y - x >= 0) {
 230                                 z = (y - x) >> 1;
 231                         }
 232                         break;
 233
 234                 case SLOPE_NW:
 235                         z = (y ^ 0xF) >> 1;
 236                         break;
 237
 238                 case SLOPE_NWS:
 239                         z = 8;
 240                         if (x - y < 0) {
 241                                 z += (x - y) >> 1;
 242                         }
 243                         break;
 244
 245                 case SLOPE_NE:
 246                         z = (x ^ 0xF) >> 1;
 247                         break;
 248
 249                 case SLOPE_ENW:
 250                         z = 8;
 251                         y ^= 0xF;
 252                         if (y - x < 0) {
 253                                 z += (y - x) >> 1;
 254                         }
 255                         break;
 256
 257                 case SLOPE_SEN:
 258                         z = 8;
 259                         if (y - x < 0) {
 260                                 z += (y - x) >> 1;
 261                         }
 262                         break;
 263
 264                 case SLOPE_STEEP_S:
 265                         z = 1 + ((x + y) >> 1);
 266                         break;
 267
 268                 case SLOPE_STEEP_W:
 269                         z = 1 + ((x + (y ^ 0xF)) >> 1);
 270                         break;
 271
 272                 case SLOPE_STEEP_N:
 273                         z = 1 + (((x ^ 0xF) + (y ^ 0xF)) >> 1);
 274                         break;
 275
 276                 case SLOPE_STEEP_E:
 277                         z = 1 + (((x ^ 0xF) + y) >> 1);
 278                         break;
 279
 280                 default: break;
 281         }
 282
 283         return z;
 284 }
 285
 286 int GetSlopePixelZ(int x, int y)
 287 {
 288         TileIndex tile = TileVirtXY(x, y);
 289
 290         return _tile_type_procs[GetTileType(tile)]->get_slope_z_proc(tile, x, y);
 291 }
 292
 293 /**
 294  * Determine the Z height of a corner relative to TileZ.
 295  *
 296  * @pre The slope must not be a halftile slope.
 297  *
 298  * @param tileh The slope.
 299  * @param corner The corner.
 300  * @return Z position of corner relative to TileZ.
 301  */
 302 int GetSlopeZInCorner(Slope tileh, Corner corner)
 303 {
 304         assert(!IsHalftileSlope(tileh));
 305         return ((tileh & SlopeWithOneCornerRaised(corner)) != 0 ? 1 : 0) + (tileh == SteepSlope(corner) ? 1 : 0);
 306 }
 307
 308 /**
 309  * Determine the Z height of the corners of a specific tile edge
 310  *
 311  * @note If a tile has a non-continuous halftile foundation, a corner can have different heights wrt. its edges.
 312  *
 313  * @pre z1 and z2 must be initialized (typ. with TileZ). The corner heights just get added.
 314  *
 315  * @param tileh The slope of the tile.
 316  * @param edge The edge of interest.
 317  * @param z1 Gets incremented by the height of the first corner of the edge. (near corner wrt. the camera)
 318  * @param z2 Gets incremented by the height of the second corner of the edge. (far corner wrt. the camera)
 319  */
 320 void GetSlopePixelZOnEdge(Slope tileh, DiagDirection edge, int *z1, int *z2)
 321 {
 322         static const Slope corners[4][4] = {
 323                 /*    corner     |          steep slope
 324                  *  z1      z2   |       z1             z2        */
 325                 {SLOPE_E, SLOPE_N, SLOPE_STEEP_E, SLOPE_STEEP_N}, // DIAGDIR_NE, z1 = E, z2 = N
 326                 {SLOPE_S, SLOPE_E, SLOPE_STEEP_S, SLOPE_STEEP_E}, // DIAGDIR_SE, z1 = S, z2 = E
 327                 {SLOPE_S, SLOPE_W, SLOPE_STEEP_S, SLOPE_STEEP_W}, // DIAGDIR_SW, z1 = S, z2 = W
 328                 {SLOPE_W, SLOPE_N, SLOPE_STEEP_W, SLOPE_STEEP_N}, // DIAGDIR_NW, z1 = W, z2 = N
 329         };
 330
 331         int halftile_test = (IsHalftileSlope(tileh) ? SlopeWithOneCornerRaised(GetHalftileSlopeCorner(tileh)) : 0);
 332         if (halftile_test == corners[edge][0]) *z2 += TILE_HEIGHT; // The slope is non-continuous in z2. z2 is on the upper side.
 333         if (halftile_test == corners[edge][1]) *z1 += TILE_HEIGHT; // The slope is non-continuous in z1. z1 is on the upper side.
 334
 335         if ((tileh & corners[edge][0]) != 0) *z1 += TILE_HEIGHT; // z1 is raised
 336         if ((tileh & corners[edge][1]) != 0) *z2 += TILE_HEIGHT; // z2 is raised
 337         if (RemoveHalftileSlope(tileh) == corners[edge][2]) *z1 += TILE_HEIGHT; // z1 is highest corner of a steep slope
 338         if (RemoveHalftileSlope(tileh) == corners[edge][3]) *z2 += TILE_HEIGHT; // z2 is highest corner of a steep slope
 339 }
 340
 341 /**
 342  * Get slope of a tile on top of a (possible) foundation
 343  * If a tile does not have a foundation, the function returns the same as GetTileSlope.
 344  *
 345  * @param tile The tile of interest.
 346  * @param z returns the z of the foundation slope. (Can be nullptr, if not needed)
 347  * @return The slope on top of the foundation.
 348  */
 349 Slope GetFoundationSlope(TileIndex tile, int *z)
 350 {
 351         Slope tileh = GetTileSlope(tile, z);
 352         Foundation f = _tile_type_procs[GetTileType(tile)]->get_foundation_proc(tile, tileh);
 353         uint z_inc = ApplyFoundationToSlope(f, &tileh);
 354         if (z != nullptr) *z += z_inc;
 355         return tileh;
 356 }
 357
 358
 359 bool HasFoundationNW(TileIndex tile, Slope slope_here, uint z_here)
 360 {
 361         if (IsRoadCustomBridgeHeadTile(tile) && GetTunnelBridgeDirection(tile) == DIAGDIR_NW) return false;
 362
 363         int z;
 364
 365         int z_W_here = z_here;
 366         int z_N_here = z_here;
 367         GetSlopePixelZOnEdge(slope_here, DIAGDIR_NW, &z_W_here, &z_N_here);
 368
 369         Slope slope = GetFoundationPixelSlope(TILE_ADDXY(tile, 0, -1), &z);
 370         int z_W = z;
 371         int z_N = z;
 372         GetSlopePixelZOnEdge(slope, DIAGDIR_SE, &z_W, &z_N);
 373
 374         return (z_N_here > z_N) || (z_W_here > z_W);
 375 }
 376
 377
 378 bool HasFoundationNE(TileIndex tile, Slope slope_here, uint z_here)
 379 {
 380         if (IsRoadCustomBridgeHeadTile(tile) && GetTunnelBridgeDirection(tile) == DIAGDIR_NE) return false;
 381
 382         int z;
 383
 384         int z_E_here = z_here;
 385         int z_N_here = z_here;
 386         GetSlopePixelZOnEdge(slope_here, DIAGDIR_NE, &z_E_here, &z_N_here);
 387
 388         Slope slope = GetFoundationPixelSlope(TILE_ADDXY(tile, -1, 0), &z);
 389         int z_E = z;
 390         int z_N = z;
 391         GetSlopePixelZOnEdge(slope, DIAGDIR_SW, &z_E, &z_N);
 392
 393         return (z_N_here > z_N) || (z_E_here > z_E);
 394 }
 395
 396 /**
 397  * Draw foundation \a f at tile \a ti. Updates \a ti.
 398  * @param ti Tile to draw foundation on
 399  * @param f  Foundation to draw
 400  */
 401 void DrawFoundation(TileInfo *ti, Foundation f)
 402 {
 403         if (!IsFoundation(f)) return;
 404
 405         /* Two part foundations must be drawn separately */
 406         assert(f != FOUNDATION_STEEP_BOTH);
 407
 408         uint sprite_block = 0;
 409         int z;
 410         Slope slope = GetFoundationPixelSlope(ti->tile, &z);
 411
 412         /* Select the needed block of foundations sprites
 413          * Block 0: Walls at NW and NE edge
 414          * Block 1: Wall  at        NE edge
 415          * Block 2: Wall  at NW        edge
 416          * Block 3: No walls at NW or NE edge
 417          */
 418         if (!HasFoundationNW(ti->tile, slope, z)) sprite_block += 1;
 419         if (!HasFoundationNE(ti->tile, slope, z)) sprite_block += 2;
 420
 421         /* Use the original slope sprites if NW and NE borders should be visible */
 422         SpriteID leveled_base = (sprite_block == 0 ? (int)SPR_FOUNDATION_BASE : (SPR_SLOPES_VIRTUAL_BASE + sprite_block * SPR_TRKFOUND_BLOCK_SIZE));
 423         SpriteID inclined_base = SPR_SLOPES_VIRTUAL_BASE + SPR_SLOPES_INCLINED_OFFSET + sprite_block * SPR_TRKFOUND_BLOCK_SIZE;
 424         SpriteID halftile_base = SPR_HALFTILE_FOUNDATION_BASE + sprite_block * SPR_HALFTILE_BLOCK_SIZE;
 425
 426         if (IsSteepSlope(ti->tileh)) {
 427                 if (!IsNonContinuousFoundation(f)) {
 428                         /* Lower part of foundation */
 429                         AddSortableSpriteToDraw(
 430                                 leveled_base + (ti->tileh & ~SLOPE_STEEP), PAL_NONE, ti->x, ti->y, 16, 16, 7, ti->z
 431                         );
 432                 }
 433
 434                 Corner highest_corner = GetHighestSlopeCorner(ti->tileh);
 435                 ti->z += ApplyPixelFoundationToSlope(f, &ti->tileh);
 436
 437                 if (IsInclinedFoundation(f)) {
 438                         /* inclined foundation */
 439                         byte inclined = highest_corner * 2 + (f == FOUNDATION_INCLINED_Y ? 1 : 0);
 440
 441                         AddSortableSpriteToDraw(inclined_base + inclined, PAL_NONE, ti->x, ti->y,
 442                                 f == FOUNDATION_INCLINED_X ? 16 : 1,
 443                                 f == FOUNDATION_INCLINED_Y ? 16 : 1,
 444                                 TILE_HEIGHT, ti->z
 445                         );
 446                         OffsetGroundSprite(31, 9);
 447                 } else if (IsLeveledFoundation(f)) {
 448                         AddSortableSpriteToDraw(leveled_base + SlopeWithOneCornerRaised(highest_corner), PAL_NONE, ti->x, ti->y, 16, 16, 7, ti->z - TILE_HEIGHT);
 449                         OffsetGroundSprite(31, 1);
 450                 } else if (f == FOUNDATION_STEEP_LOWER) {
 451                         /* one corner raised */
 452                         OffsetGroundSprite(31, 1);
 453                 } else {
 454                         /* halftile foundation */
 455                         int x_bb = (((highest_corner == CORNER_W) || (highest_corner == CORNER_S)) ? 8 : 0);
 456                         int y_bb = (((highest_corner == CORNER_S) || (highest_corner == CORNER_E)) ? 8 : 0);
 457
 458                         AddSortableSpriteToDraw(halftile_base + highest_corner, PAL_NONE, ti->x + x_bb, ti->y + y_bb, 8, 8, 7, ti->z + TILE_HEIGHT);
 459                         OffsetGroundSprite(31, 9);
 460                 }
 461         } else {
 462                 if (IsLeveledFoundation(f)) {
 463                         /* leveled foundation */
 464                         AddSortableSpriteToDraw(leveled_base + ti->tileh, PAL_NONE, ti->x, ti->y, 16, 16, 7, ti->z);
 465                         OffsetGroundSprite(31, 1);
 466                 } else if (IsNonContinuousFoundation(f)) {
 467                         /* halftile foundation */
 468                         Corner halftile_corner = GetHalftileFoundationCorner(f);
 469                         int x_bb = (((halftile_corner == CORNER_W) || (halftile_corner == CORNER_S)) ? 8 : 0);
 470                         int y_bb = (((halftile_corner == CORNER_S) || (halftile_corner == CORNER_E)) ? 8 : 0);
 471
 472                         AddSortableSpriteToDraw(halftile_base + halftile_corner, PAL_NONE, ti->x + x_bb, ti->y + y_bb, 8, 8, 7, ti->z);
 473                         OffsetGroundSprite(31, 9);
 474                 } else if (IsSpecialRailFoundation(f)) {
 475                         /* anti-zig-zag foundation */
 476                         SpriteID spr;
 477                         if (ti->tileh == SLOPE_NS || ti->tileh == SLOPE_EW) {
 478                                 /* half of leveled foundation under track corner */
 479                                 spr = leveled_base + SlopeWithThreeCornersRaised(GetRailFoundationCorner(f));
 480                         } else {
 481                                 /* tile-slope = sloped along X/Y, foundation-slope = three corners raised */
 482                                 spr = inclined_base + 2 * GetRailFoundationCorner(f) + ((ti->tileh == SLOPE_SW || ti->tileh == SLOPE_NE) ? 1 : 0);
 483                         }
 484                         AddSortableSpriteToDraw(spr, PAL_NONE, ti->x, ti->y, 16, 16, 7, ti->z);
 485                         OffsetGroundSprite(31, 9);
 486                 } else {
 487                         /* inclined foundation */
 488                         byte inclined = GetHighestSlopeCorner(ti->tileh) * 2 + (f == FOUNDATION_INCLINED_Y ? 1 : 0);
 489
 490                         AddSortableSpriteToDraw(inclined_base + inclined, PAL_NONE, ti->x, ti->y,
 491                                 f == FOUNDATION_INCLINED_X ? 16 : 1,
 492                                 f == FOUNDATION_INCLINED_Y ? 16 : 1,
 493                                 TILE_HEIGHT, ti->z
 494                         );
 495                         OffsetGroundSprite(31, 9);
 496                 }
 497                 ti->z += ApplyPixelFoundationToSlope(f, &ti->tileh);
 498         }
 499 }
 500
 501 void DoClearSquare(TileIndex tile)
 502 {
 503         /* If the tile can have animation and we clear it, delete it from the animated tile list. */
 504         if (_tile_type_procs[GetTileType(tile)]->animate_tile_proc != nullptr) DeleteAnimatedTile(tile);
 505
 506         MakeClear(tile, CLEAR_GRASS, _generating_world ? 3 : 0);
 507         MarkTileDirtyByTile(tile);
 508 }
 509
 510 /**
 511  * Returns information about trackdirs and signal states.
 512  * If there is any trackbit at 'side', return all trackdirbits.
 513  * For TRANSPORT_ROAD, return no trackbits if there is no roadbit (of given subtype) at given side.
 514  * @param tile tile to get info about
 515  * @param mode transport type
 516  * @param sub_mode for TRANSPORT_ROAD, roadtypes to check
 517  * @param side side we are entering from, INVALID_DIAGDIR to return all trackbits
 518  * @return trackdirbits and other info depending on 'mode'
 519  */
 520 TrackStatus GetTileTrackStatus(TileIndex tile, TransportType mode, uint sub_mode, DiagDirection side)
 521 {
 522         return _tile_type_procs[GetTileType(tile)]->get_tile_track_status_proc(tile, mode, sub_mode, side);
 523 }
 524
 525 /**
 526  * Change the owner of a tile
 527  * @param tile      Tile to change
 528  * @param old_owner Current owner of the tile
 529  * @param new_owner New owner of the tile
 530  */
 531 void ChangeTileOwner(TileIndex tile, Owner old_owner, Owner new_owner)
 532 {
 533         _tile_type_procs[GetTileType(tile)]->change_tile_owner_proc(tile, old_owner, new_owner);
 534 }
 535
 536 void GetTileDesc(TileIndex tile, TileDesc *td)
 537 {
 538         _tile_type_procs[GetTileType(tile)]->get_tile_desc_proc(tile, td);
 539 }
 540
 541 /**
 542  * Has a snow line table already been loaded.
 543  * @return true if the table has been loaded already.
 544  * @ingroup SnowLineGroup
 545  */
 546 bool IsSnowLineSet()
 547 {
 548         return _snow_line != nullptr;
 549 }
 550
 551 /**
 552  * Set a variable snow line, as loaded from a newgrf file.
 553  * @param table the 12 * 32 byte table containing the snowline for each day
 554  * @ingroup SnowLineGroup
 555  */
 556 void SetSnowLine(byte table[SNOW_LINE_MONTHS][SNOW_LINE_DAYS])
 557 {
 558         _snow_line = CallocT<SnowLine>(1);
 559         _snow_line->lowest_value = 0xFF;
 560         memcpy(_snow_line->table, table, sizeof(_snow_line->table));
 561
 562         for (uint i = 0; i < SNOW_LINE_MONTHS; i++) {
 563                 for (uint j = 0; j < SNOW_LINE_DAYS; j++) {
 564                         _snow_line->highest_value = max(_snow_line->highest_value, table[i][j]);
 565                         _snow_line->lowest_value = min(_snow_line->lowest_value, table[i][j]);
 566                 }
 567         }
 568 }
 569
 570 /**
 571  * Get the current snow line, either variable or static.
 572  * @return the snow line height.
 573  * @ingroup SnowLineGroup
 574  */
 575 uint16 GetSnowLine()
 576 {
 577         if (_snow_line == nullptr) return _settings_game.game_creation.snow_line_height;
 578
 579         return _snow_line->table[_cur_date_ymd.month][_cur_date_ymd.day];
 580 }
 581
 582 /**
 583  * Get the highest possible snow line height, either variable or static.
 584  * @return the highest snow line height.
 585  * @ingroup SnowLineGroup
 586  */
 587 uint16 HighestSnowLine()
 588 {
 589         return _snow_line == nullptr ? _settings_game.game_creation.snow_line_height : _snow_line->highest_value;
 590 }
 591
 592 /**
 593  * Get the lowest possible snow line height, either variable or static.
 594  * @return the lowest snow line height.
 595  * @ingroup SnowLineGroup
 596  */
 597 uint16 LowestSnowLine()
 598 {
 599         return _snow_line == nullptr ? _settings_game.game_creation.snow_line_height : _snow_line->lowest_value;
 600 }
 601
 602 /**
 603  * Clear the variable snow line table and free the memory.
 604  * @ingroup SnowLineGroup
 605  */
 606 void ClearSnowLine()
 607 {
 608         free(_snow_line);
 609         _snow_line = nullptr;
 610 }
 611
 612 /**
 613  * Clear a piece of landscape
 614  * @param tile tile to clear
 615  * @param flags of operation to conduct
 616  * @param p1 unused
 617  * @param p2 unused
 618  * @param text unused
 619  * @return the cost of this operation or an error
 620  */
 621 CommandCost CmdLandscapeClear(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text)
 622 {
 623         CommandCost cost(EXPENSES_CONSTRUCTION);
 624         bool do_clear = false;
 625         /* Test for stuff which results in water when cleared. Then add the cost to also clear the water. */
 626         if ((flags & DC_FORCE_CLEAR_TILE) && HasTileWaterClass(tile) && IsTileOnWater(tile) && !IsWaterTile(tile) && !IsCoastTile(tile)) {
 627                 if ((flags & DC_AUTO) && GetWaterClass(tile) == WATER_CLASS_CANAL) return CommandError(STR_ERROR_MUST_DEMOLISH_CANAL_FIRST);
 628                 do_clear = true;
 629                 cost.AddCost(GetWaterClass(tile) == WATER_CLASS_CANAL ? _price[PR_CLEAR_CANAL] : _price[PR_CLEAR_WATER]);
 630         }
 631
 632         Company *c = (flags & (DC_AUTO | DC_BANKRUPT)) ? nullptr : Company::GetIfValid(_current_company);
 633         if (c != nullptr && (int)GB(c->clear_limit, 16, 16) < 1) {
 634                 return CommandError(STR_ERROR_CLEARING_LIMIT_REACHED);
 635         }
 636
 637         const ClearedObjectArea *coa = FindClearedObject(tile);
 638
 639         /* If this tile was the first tile which caused object destruction, always
 640          * pass it on to the tile_type_proc. That way multiple test runs and the exec run stay consistent. */
 641         if (coa != nullptr && coa->first_tile != tile) {
 642                 /* If this tile belongs to an object which was already cleared via another tile, pretend it has been
 643                  * already removed.
 644                  * However, we need to check stuff, which is not the same for all object tiles. (e.g. being on water or not) */
 645
 646                 /* If a object is removed, it leaves either bare land or water. */
 647                 if ((flags & DC_NO_WATER) && HasTileWaterClass(tile) && IsTileOnWater(tile)) {
 648                         return CommandError(STR_ERROR_CAN_T_BUILD_ON_WATER);
 649                 }
 650         } else {
 651                 cost.AddCost(_tile_type_procs[GetTileType(tile)]->clear_tile_proc(tile, flags));
 652         }
 653
 654         if (flags & DC_EXEC) {
 655                 if (c != nullptr) c->clear_limit -= 1 << 16;
 656                 if (do_clear) DoClearSquare(tile);
 657         }
 658         return cost;
 659 }
 660
 661 /**
 662  * Clear a big piece of landscape
 663  * @param tile end tile of area dragging
 664  * @param flags of operation to conduct
 665  * @param p1 start tile of area dragging
 666  * @param p2 various bitstuffed data.
 667  *  bit      0: Whether to use the Orthogonal (0) or Diagonal (1) iterator.
 668  * @param text unused
 669  * @return the cost of this operation or an error
 670  */
 671 CommandCost CmdClearArea(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text)
 672 {
 673         if (p1 >= MapSize()) return CommandError();
 674
 675         Money money = GetAvailableMoneyForCommand();
 676         CommandCost cost(EXPENSES_CONSTRUCTION);
 677         CommandCost last_error = CommandError();
 678         bool had_success = false;
 679
 680         const Company *c = (flags & (DC_AUTO | DC_BANKRUPT)) ? nullptr : Company::GetIfValid(_current_company);
 681         int limit = (c == nullptr ? INT32_MAX : GB(c->clear_limit, 16, 16));
 682
 683         TileIterator *iter = HasBit(p2, 0) ? (TileIterator *)new DiagonalTileIterator(tile, p1) : new OrthogonalTileIterator(tile, p1);
 684         for (; *iter != INVALID_TILE; ++(*iter)) {
 685                 TileIndex t = *iter;
 686                 CommandCost ret = DoCommand(t, 0, 0, flags & ~DC_EXEC, CMD_LANDSCAPE_CLEAR);
 687                 if (ret.Failed()) {
 688                         last_error = ret;
 689
 690                         /* We may not clear more tiles. */
 691                         if (c != nullptr && GB(c->clear_limit, 16, 16) < 1) break;
 692                         continue;
 693                 }
 694
 695                 had_success = true;
 696                 if (flags & DC_EXEC) {
 697                         money -= ret.GetCost();
 698                         if (ret.GetCost() > 0 && money < 0) {
 699                                 _additional_cash_required = ret.GetCost();
 700                                 delete iter;
 701                                 return cost;
 702                         }
 703                         DoCommand(t, 0, 0, flags, CMD_LANDSCAPE_CLEAR);
 704
 705                         /* draw explosion animation...
 706                          * Disable explosions when game is paused. Looks silly and blocks the view. */
 707                         if ((t == tile || t == p1) && _pause_mode == PM_UNPAUSED) {
 708                                 /* big explosion in two corners, or small explosion for single tiles */
 709                                 CreateEffectVehicleAbove(TileX(t) * TILE_SIZE + TILE_SIZE / 2, TileY(t) * TILE_SIZE + TILE_SIZE / 2, 2,
 710                                         TileX(tile) == TileX(p1) && TileY(tile) == TileY(p1) ? EV_EXPLOSION_SMALL : EV_EXPLOSION_LARGE
 711                                 );
 712                         }
 713                 } else {
 714                         /* When we're at the clearing limit we better bail (unneed) testing as well. */
 715                         if (ret.GetCost() != 0 && --limit <= 0) break;
 716                 }
 717                 cost.AddCost(ret);
 718         }
 719
 720         delete iter;
 721         return had_success ? cost : last_error;
 722 }
 723
 724
 725 TileIndex _cur_tileloop_tile;
 726
 727 /**
 728  * Gradually iterate over all tiles on the map, calling their TileLoopProcs once every 256 ticks.
 729  */
 730 void RunTileLoop()
 731 {
 732         /* The pseudorandom sequence of tiles is generated using a Galois linear feedback
 733          * shift register (LFSR). This allows a deterministic pseudorandom ordering, but
 734          * still with minimal state and fast iteration. */
 735
 736         /* Maximal length LFSR feedback terms, from 12-bit (for 64x64 maps) to 24-bit (for 4096x4096 maps).
 737          * Extracted from http://www.ece.cmu.edu/~koopman/lfsr/ */
 738         static const uint32 feedbacks[] = {
 739                 0xD8F, 0x1296, 0x2496, 0x4357, 0x8679, 0x1030E, 0x206CD, 0x403FE, 0x807B8, 0x1004B2, 0x2006A8, 0x4004B2, 0x800B87
 740         };
 741         assert_compile(lengthof(feedbacks) == 2 * MAX_MAP_SIZE_BITS - 2 * MIN_MAP_SIZE_BITS + 1);
 742         const uint32 feedback = feedbacks[MapLogX() + MapLogY() - 2 * MIN_MAP_SIZE_BITS];
 743
 744         /* We update every tile every 256 ticks, so divide the map size by 2^8 = 256 */
 745         uint count = 1 << (MapLogX() + MapLogY() - 8);
 746
 747         TileIndex tile = _cur_tileloop_tile;
 748         /* The LFSR cannot have a zeroed state. */
 749         assert(tile != 0);
 750
 751         /* Manually update tile 0 every 256 ticks - the LFSR never iterates over it itself.  */
 752         if (_tick_counter % 256 == 0) {
 753                 _tile_type_procs[GetTileType(0)]->tile_loop_proc(0);
 754                 count--;
 755         }
 756
 757         while (count--) {
 758                 _tile_type_procs[GetTileType(tile)]->tile_loop_proc(tile);
 759
 760                 /* Get the next tile in sequence using a Galois LFSR. */
 761                 tile = (tile >> 1) ^ (-(int32)(tile & 1) & feedback);
 762         }
 763
 764         _cur_tileloop_tile = tile;
 765 }
 766
 767 void InitializeLandscape()
 768 {
 769         uint maxx = MapMaxX();
 770         uint maxy = MapMaxY();
 771         uint sizex = MapSizeX();
 772
 773         uint y;
 774         for (y = _settings_game.construction.freeform_edges ? 1 : 0; y < maxy; y++) {
 775                 uint x;
 776                 for (x = _settings_game.construction.freeform_edges ? 1 : 0; x < maxx; x++) {
 777                         MakeClear(sizex * y + x, CLEAR_GRASS, 3);
 778                         SetTileHeight(sizex * y + x, 0);
 779                         SetTropicZone(sizex * y + x, TROPICZONE_NORMAL);
 780                         ClearBridgeMiddle(sizex * y + x);
 781                 }
 782                 MakeVoid(sizex * y + x);
 783         }
 784         for (uint x = 0; x < sizex; x++) MakeVoid(sizex * y + x);
 785 }
 786
 787 static const byte _genterrain_tbl_1[5] = { 10, 22, 33, 37, 4  };
 788 static const byte _genterrain_tbl_2[5] = {  0,  0,  0,  0, 33 };
 789
 790 static void GenerateTerrain(int type, uint flag)
 791 {
 792         uint32 r = Random();
 793
 794         const Sprite *templ = GetSprite((((r >> 24) * _genterrain_tbl_1[type]) >> 8) + _genterrain_tbl_2[type] + 4845, ST_MAPGEN);
 795         if (templ == nullptr) usererror("Map generator sprites could not be loaded");
 796
 797         uint x = r & MapMaxX();
 798         uint y = (r >> MapLogX()) & MapMaxY();
 799
 800         if (x < 2 || y < 2) return;
 801
 802         DiagDirection direction = (DiagDirection)GB(r, 22, 2);
 803         uint w = templ->width;
 804         uint h = templ->height;
 805
 806         if (DiagDirToAxis(direction) == AXIS_Y) Swap(w, h);
 807
 808         const byte *p = templ->data;
 809
 810         if ((flag & 4) != 0) {
 811                 uint xw = x * MapSizeY();
 812                 uint yw = y * MapSizeX();
 813                 uint bias = (MapSizeX() + MapSizeY()) * 16;
 814
 815                 switch (flag & 3) {
 816                         default: NOT_REACHED();
 817                         case 0:
 818                                 if (xw + yw > MapSize() - bias) return;
 819                                 break;
 820
 821                         case 1:
 822                                 if (yw < xw + bias) return;
 823                                 break;
 824
 825                         case 2:
 826                                 if (xw + yw < MapSize() + bias) return;
 827                                 break;
 828
 829                         case 3:
 830                                 if (xw < yw + bias) return;
 831                                 break;
 832                 }
 833         }
 834
 835         if (x + w >= MapMaxX() - 1) return;
 836         if (y + h >= MapMaxY() - 1) return;
 837
 838         TileIndex tile = TileXY(x, y);
 839
 840         switch (direction) {
 841                 default: NOT_REACHED();
 842                 case DIAGDIR_NE:
 843                         do {
 844                                 TileIndex tile_cur = tile;
 845
 846                                 for (uint w_cur = w; w_cur != 0; --w_cur) {
 847                                         if (GB(*p, 0, 4) >= TileHeight(tile_cur)) SetTileHeight(tile_cur, GB(*p, 0, 4));
 848                                         p++;
 849                                         tile_cur++;
 850                                 }
 851                                 tile += TileDiffXY(0, 1);
 852                         } while (--h != 0);
 853                         break;
 854
 855                 case DIAGDIR_SE:
 856                         do {
 857                                 TileIndex tile_cur = tile;
 858
 859                                 for (uint h_cur = h; h_cur != 0; --h_cur) {
 860                                         if (GB(*p, 0, 4) >= TileHeight(tile_cur)) SetTileHeight(tile_cur, GB(*p, 0, 4));
 861                                         p++;
 862                                         tile_cur += TileDiffXY(0, 1);
 863                                 }
 864                                 tile += TileDiffXY(1, 0);
 865                         } while (--w != 0);
 866                         break;
 867
 868                 case DIAGDIR_SW:
 869                         tile += TileDiffXY(w - 1, 0);
 870                         do {
 871                                 TileIndex tile_cur = tile;
 872
 873                                 for (uint w_cur = w; w_cur != 0; --w_cur) {
 874                                         if (GB(*p, 0, 4) >= TileHeight(tile_cur)) SetTileHeight(tile_cur, GB(*p, 0, 4));
 875                                         p++;
 876                                         tile_cur--;
 877                                 }
 878                                 tile += TileDiffXY(0, 1);
 879                         } while (--h != 0);
 880                         break;
 881
 882                 case DIAGDIR_NW:
 883                         tile += TileDiffXY(0, h - 1);
 884                         do {
 885                                 TileIndex tile_cur = tile;
 886
 887                                 for (uint h_cur = h; h_cur != 0; --h_cur) {
 888                                         if (GB(*p, 0, 4) >= TileHeight(tile_cur)) SetTileHeight(tile_cur, GB(*p, 0, 4));
 889                                         p++;
 890                                         tile_cur -= TileDiffXY(0, 1);
 891                                 }
 892                                 tile += TileDiffXY(1, 0);
 893                         } while (--w != 0);
 894                         break;
 895         }
 896 }
 897
 898
 899 #include "table/genland.h"
 900
 901 static void CreateDesertOrRainForest()
 902 {
 903         TileIndex update_freq = MapSize() / 4;
 904         const TileIndexDiffC *data;
 905         uint max_desert_height = CeilDiv(_settings_game.construction.max_heightlevel, 4);
 906
 907         for (TileIndex tile = 0; tile != MapSize(); ++tile) {
 908                 if ((tile % update_freq) == 0) IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
 909
 910                 if (!IsValidTile(tile)) continue;
 911
 912                 /* Amount of tiles that become desert, excluding those too close to watertiles.*/
 913                 for (data = _make_desert_or_rainforest_data;
 914                                 data != endof(_make_desert_or_rainforest_data); ++data) {
 915                         TileIndex t = AddTileIndexDiffCWrap(tile, *data);
 916                         if (t != INVALID_TILE && (TileHeight(t) >= _settings_newgame.game_creation.desert_amount || IsTileType(t, MP_WATER))) break;
 917                 }
 918                 if (data == endof(_make_desert_or_rainforest_data)) {
 919                         SetTropicZone(tile, TROPICZONE_DESERT);
 920                 }
 921         }
 922
 923         for (uint i = 0; i != 256; i++) {
 924                 if ((i % 64) == 0) IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
 925
 926                 RunTileLoop();
 927         }
 928
 929         for (TileIndex tile = 0; tile != MapSize(); ++tile) {
 930                 if ((tile % update_freq) == 0) IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
 931
 932                 if (!IsValidTile(tile)) continue;
 933
 934                 /* All "land" tiles that are not assigned as desert above become rainforest here. */
 935                 for (data = _make_desert_or_rainforest_data;
 936                                 data != endof(_make_desert_or_rainforest_data); ++data) {
 937                         TileIndex t = AddTileIndexDiffCWrap(tile, *data);
 938                         if (t != INVALID_TILE && IsTileType(t, MP_CLEAR) && IsClearGround(t, CLEAR_DESERT)) break;
 939                 }
 940                 if (data == endof(_make_desert_or_rainforest_data)) {
 941                         SetTropicZone(tile, TROPICZONE_RAINFOREST);
 942                 }
 943         }
 944 }
 945
 946 /**
 947  * Find the spring of a river.
 948  * @param tile The tile to consider for being the spring.
 949  * @param user_data Ignored data.
 950  * @return True iff it is suitable as a spring.
 951  */
 952 static bool FindSpring(TileIndex tile, void *user_data)
 953 {
 954         int referenceHeight;
 955         if (!IsTileFlat(tile, &referenceHeight) || IsWaterTile(tile)) return false;
 956
 957         /* In the tropics rivers start in the rainforest. */
 958         if (_settings_game.game_creation.landscape == LT_TROPIC && GetTropicZone(tile) != TROPICZONE_RAINFOREST) return false;
 959
 960         /* Are there enough higher tiles to warrant a 'spring'? */
 961         uint num = 0;
 962         for (int dx = -1; dx <= 1; dx++) {
 963                 for (int dy = -1; dy <= 1; dy++) {
 964                         TileIndex t = TileAddWrap(tile, dx, dy);
 965                         if (t != INVALID_TILE && GetTileMaxZ(t) > referenceHeight) num++;
 966                 }
 967         }
 968
 969         if (num < 4) return false;
 970
 971         /* Are we near the top of a hill? */
 972         for (int dx = -16; dx <= 16; dx++) {
 973                 for (int dy = -16; dy <= 16; dy++) {
 974                         TileIndex t = TileAddWrap(tile, dx, dy);
 975                         if (t != INVALID_TILE && GetTileMaxZ(t) > referenceHeight + 2) return false;
 976                 }
 977         }
 978
 979         return true;
 980 }
 981
 982 /**
 983  * Make a connected lake; fill all tiles in the circular tile search that are connected.
 984  * @param tile The tile to consider for lake making.
 985  * @param user_data The height of the lake.
 986  * @return Always false, so it continues searching.
 987  */
 988 static bool MakeLake(TileIndex tile, void *user_data)
 989 {
 990         uint height = *(uint*)user_data;
 991         if (!IsValidTile(tile) || TileHeight(tile) != height || !IsTileFlat(tile)) return false;
 992         if (_settings_game.game_creation.landscape == LT_TROPIC && GetTropicZone(tile) == TROPICZONE_DESERT) return false;
 993
 994         for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {
 995                 TileIndex t2 = tile + TileOffsByDiagDir(d);
 996                 if (IsWaterTile(t2)) {
 997                         MakeRiver(tile, Random());
 998                         return false;
 999                 }
1000         }
1001
1002         return false;
1003 }
1004
1005 /**
1006  * Check whether a river at begin could (logically) flow down to end.
1007  * @param begin The origin of the flow.
1008  * @param end The destination of the flow.
1009  * @return True iff the water can be flowing down.
1010  */
1011 static bool FlowsDown(TileIndex begin, TileIndex end)
1012 {
1013         assert(DistanceManhattan(begin, end) == 1);
1014
1015         int heightBegin;
1016         int heightEnd;
1017         Slope slopeBegin = GetTileSlope(begin, &heightBegin);
1018         Slope slopeEnd   = GetTileSlope(end, &heightEnd);
1019
1020         return heightEnd <= heightBegin &&
1021                         /* Slope either is inclined or flat; rivers don't support other slopes. */
1022                         (slopeEnd == SLOPE_FLAT || IsInclinedSlope(slopeEnd)) &&
1023                         /* Slope continues, then it must be lower... or either end must be flat. */
1024                         ((slopeEnd == slopeBegin && heightEnd < heightBegin) || slopeEnd == SLOPE_FLAT || slopeBegin == SLOPE_FLAT);
1025 }
1026
1027 /* AyStar callback for checking whether we reached our destination. */
1028 static int32 River_EndNodeCheck(AyStar *aystar, OpenListNode *current)
1029 {
1030         return current->path.node.tile == *(TileIndex*)aystar->user_target ? AYSTAR_FOUND_END_NODE : AYSTAR_DONE;
1031 }
1032
1033 /* AyStar callback for getting the cost of the current node. */
1034 static int32 River_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
1035 {
1036         return 1 + RandomRange(_settings_game.game_creation.river_route_random);
1037 }
1038
1039 /* AyStar callback for getting the estimated cost to the destination. */
1040 static int32 River_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
1041 {
1042         return DistanceManhattan(*(TileIndex*)aystar->user_target, current->tile);
1043 }
1044
1045 /* AyStar callback for getting the neighbouring nodes of the given node. */
1046 static void River_GetNeighbours(AyStar *aystar, OpenListNode *current)
1047 {
1048         TileIndex tile = current->path.node.tile;
1049
1050         aystar->num_neighbours = 0;
1051         for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {
1052                 TileIndex t2 = tile + TileOffsByDiagDir(d);
1053                 if (IsValidTile(t2) && FlowsDown(tile, t2)) {
1054                         aystar->neighbours[aystar->num_neighbours].tile = t2;
1055                         aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
1056                         aystar->num_neighbours++;
1057                 }
1058         }
1059 }
1060
1061 /** Callback to widen a river tile. */
1062 static bool RiverMakeWider(TileIndex tile, void *data)
1063 {
1064         if (IsValidTile(tile) && !IsWaterTile(tile) && GetTileSlope(tile) == GetTileSlope(*(TileIndex *)data)) {
1065                 MakeRiver(tile, Random());
1066                 /* Remove desert directly around the river tile. */
1067                 TileIndex cur_tile = tile;
1068                 CircularTileSearch(&cur_tile, 5, RiverModifyDesertZone, nullptr);
1069         }
1070         return false;
1071 }
1072
1073 /* AyStar callback when an route has been found. */
1074 static void River_FoundEndNode(AyStar *aystar, OpenListNode *current)
1075 {
1076         /* Count river length. */
1077         uint length = 0;
1078
1079         for (PathNode *path = &current->path; path != nullptr; path = path->parent) {
1080                 length++;
1081         }
1082
1083         uint cur_pos = 0;
1084         for (PathNode *path = &current->path; path != nullptr; path = path->parent, cur_pos++) {
1085                 TileIndex tile = path->node.tile;
1086                 if (!IsWaterTile(tile)) {
1087                         MakeRiver(tile, Random());
1088                         /* Widen river depending on how far we are away from the source. */
1089                         uint current_river_length = DistanceManhattan(_current_spring, path->node.tile);
1090                         uint radius = std::min(3u, (current_river_length / (LONG_RIVER_LENGTH / 3u)) + 1u);
1091
1092                         if (_is_main_river && (radius > 1)) {
1093                                 CircularTileSearch(&tile, radius + RandomRange(1), RiverMakeWider, (void *)&path->node.tile);
1094                         } else {
1095                                 /* Remove desert directly around the river tile. */
1096                                 CircularTileSearch(&tile, 5, RiverModifyDesertZone, nullptr);
1097                         }
1098                 }
1099         }
1100 }
1101
1102 static const uint RIVER_HASH_SIZE = 8; ///< The number of bits the hash for river finding should have.
1103
1104 /**
1105  * Simple hash function for river tiles to be used by AyStar.
1106  * @param tile The tile to hash.
1107  * @param dir The unused direction.
1108  * @return The hash for the tile.
1109  */
1110 static uint River_Hash(uint tile, uint dir)
1111 {
1112         return GB(TileHash(TileX(tile), TileY(tile)), 0, RIVER_HASH_SIZE);
1113 }
1114
1115 /**
1116  * Actually build the river between the begin and end tiles using AyStar.
1117  * @param begin The begin of the river.
1118  * @param end The end of the river.
1119  */
1120 static void BuildRiver(TileIndex begin, TileIndex end)
1121 {
1122         AyStar finder;
1123         finder.CalculateG = River_CalculateG;
1124         finder.CalculateH = River_CalculateH;
1125         finder.GetNeighbours = River_GetNeighbours;
1126         finder.EndNodeCheck = River_EndNodeCheck;
1127         finder.FoundEndNode = River_FoundEndNode;
1128         finder.user_target = &end;
1129
1130         finder.Init(River_Hash, 1 << RIVER_HASH_SIZE);
1131
1132         AyStarNode start;
1133         start.tile = begin;
1134         start.direction = INVALID_TRACKDIR;
1135         finder.AddStartNode(&start, 0);
1136         finder.Main();
1137         finder.Free();
1138 }
1139
1140 /**
1141  * Try to flow the river down from a given begin.
1142  * @param spring           The springing point of the river.
1143  * @param begin            The begin point we are looking from; somewhere down hill from the spring.
1144  * @param min_river_length The minimum length for the river.
1145  * @return True iff a river could/has been built, otherwise false.
1146  */
1147 static bool FlowRiver(TileIndex spring, TileIndex begin, uint min_river_length)
1148 {
1149         #define SET_MARK(x) marks.insert(x)
1150         #define IS_MARKED(x) (marks.find(x) != marks.end())
1151
1152         uint height = TileHeight(begin);
1153         if (IsWaterTile(begin))
1154         {
1155                 if (GetTileZ(begin) == 0) {
1156                         _current_estuary = begin;
1157                         _is_main_river = true;
1158                 }
1159
1160                 return DistanceManhattan(spring, begin) > min_river_length;
1161         }
1162
1163         btree::btree_set<TileIndex> marks;
1164         SET_MARK(begin);
1165
1166         /* Breadth first search for the closest tile we can flow down to. */
1167         std::deque<TileIndex> queue;
1168         queue.push_back(begin);
1169
1170         bool found = false;
1171         TileIndex end;
1172         do {
1173                 end = queue.front();
1174                 queue.pop_front();
1175
1176                 uint height2 = TileHeight(end);
1177                 if (IsTileFlat(end) && (height2 < height || (height2 == height && IsWaterTile(end)))) {
1178                         found = true;
1179                         break;
1180                 }
1181
1182                 for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {
1183                         TileIndex t2 = end + TileOffsByDiagDir(d);
1184                         if (IsValidTile(t2) && !IS_MARKED(t2) && FlowsDown(end, t2)) {
1185                                 SET_MARK(t2);
1186                                 queue.push_back(t2);
1187                         }
1188                 }
1189         } while (!queue.empty());
1190
1191         if (found) {
1192                 /* Flow further down hill. */
1193                 found = FlowRiver(spring, end, min_river_length);
1194         }
1195
1196         marks.clear();
1197
1198         if (found) BuildRiver(begin, end);
1199
1200         return found;
1201 }
1202
1203 /**
1204  * Actually (try to) create some rivers.
1205  */
1206 static void CreateRivers()
1207 {
1208         int amount = _settings_game.game_creation.amount_of_rivers;
1209         if (amount == 0) return;
1210
1211         bool has_water_tiles = false;
1212         for (TileIndex t = 0; t < MapSize(); t++) {
1213                 if (IsWaterTile(t))
1214                 {
1215                         has_water_tiles = true;
1216                         break;
1217                 }
1218         }
1219
1220         // No end points for rivers. Bail.
1221         if (!has_water_tiles) return;
1222
1223         uint wells = ScaleByMapSize(1 << _settings_game.game_creation.amount_of_rivers);
1224         uint num_short_rivers = wells - std::max(1u, wells / 10);
1225         SetGeneratingWorldProgress(GWP_RIVER, wells + 256 / 64); // Include the tile loop calls below.
1226
1227         for (; wells > num_short_rivers; wells--) {
1228                 IncreaseGeneratingWorldProgress(GWP_RIVER);
1229                 for (int tries = 0; tries < 2048; tries++) {
1230                         TileIndex t = RandomTile();
1231                         if (!CircularTileSearch(&t, 8, FindSpring, nullptr)) continue;
1232                         _current_spring = t;
1233                         _is_main_river = false;
1234                         if (FlowRiver(t, t, LONG_RIVER_LENGTH)) break;
1235                 }
1236         }
1237
1238         for (; wells != 0; wells--) {
1239                 IncreaseGeneratingWorldProgress(GWP_RIVER);
1240                 for (int tries = 0; tries < 128; tries++) {
1241                         TileIndex t = RandomTile();
1242                         if (!CircularTileSearch(&t, 8, FindSpring, nullptr)) continue;
1243                         _current_spring = t;
1244                         _is_main_river = false;
1245                         if (FlowRiver(t, t, _settings_game.game_creation.min_river_length)) break;
1246                 }
1247         }
1248
1249         /* Run tile loop to update the ground density. */
1250         for (uint i = 0; i != 256; i++) {
1251                 if (i % 64 == 0) IncreaseGeneratingWorldProgress(GWP_RIVER);
1252                 RunTileLoop();
1253         }
1254 }
1255
1256 void GenerateLandscape(byte mode)
1257 {
1258         /** Number of steps of landscape generation */
1259         enum GenLandscapeSteps {
1260                 GLS_HEIGHTMAP    =  3, ///< Loading a heightmap
1261                 GLS_TERRAGENESIS =  5, ///< Terragenesis generator
1262                 GLS_ORIGINAL     =  2, ///< Original generator
1263                 GLS_TROPIC       = 12, ///< Extra steps needed for tropic landscape
1264                 GLS_OTHER        =  0, ///< Extra steps for other landscapes
1265         };
1266         uint steps = (_settings_game.game_creation.landscape == LT_TROPIC) ? GLS_TROPIC : GLS_OTHER;
1267
1268         if (mode == GWM_HEIGHTMAP) {
1269                 SetGeneratingWorldProgress(GWP_LANDSCAPE, steps + GLS_HEIGHTMAP);
1270                 LoadHeightmap(_file_to_saveload.detail_ftype, _file_to_saveload.name);
1271                 IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
1272         } else if (_settings_game.game_creation.land_generator == LG_TERRAGENESIS) {
1273                 SetGeneratingWorldProgress(GWP_LANDSCAPE, steps + GLS_TERRAGENESIS);
1274                 GenerateTerrainPerlin();
1275         } else {
1276                 SetGeneratingWorldProgress(GWP_LANDSCAPE, steps + GLS_ORIGINAL);
1277                 if (_settings_game.construction.freeform_edges) {
1278                         for (uint x = 0; x < MapSizeX(); x++) MakeVoid(TileXY(x, 0));
1279                         for (uint y = 0; y < MapSizeY(); y++) MakeVoid(TileXY(0, y));
1280                 }
1281                 switch (_settings_game.game_creation.landscape) {
1282                         case LT_ARCTIC: {
1283                                 uint32 r = Random();
1284
1285                                 for (uint i = ScaleByMapSize(GB(r, 0, 7) + 950); i != 0; --i) {
1286                                         GenerateTerrain(2, 0);
1287                                 }
1288
1289                                 uint flag = GB(r, 7, 2) | 4;
1290                                 for (uint i = ScaleByMapSize(GB(r, 9, 7) + 450); i != 0; --i) {
1291                                         GenerateTerrain(4, flag);
1292                                 }
1293                                 break;
1294                         }
1295
1296                         case LT_TROPIC: {
1297                                 uint32 r = Random();
1298
1299                                 for (uint i = ScaleByMapSize(GB(r, 0, 7) + 170); i != 0; --i) {
1300                                         GenerateTerrain(0, 0);
1301                                 }
1302
1303                                 uint flag = GB(r, 7, 2) | 4;
1304                                 for (uint i = ScaleByMapSize(GB(r, 9, 8) + 1700); i != 0; --i) {
1305                                         GenerateTerrain(0, flag);
1306                                 }
1307
1308                                 flag ^= 2;
1309
1310                                 for (uint i = ScaleByMapSize(GB(r, 17, 7) + 410); i != 0; --i) {
1311                                         GenerateTerrain(3, flag);
1312                                 }
1313                                 break;
1314                         }
1315
1316                         default: {
1317                                 uint32 r = Random();
1318
1319                                 assert(_settings_game.difficulty.quantity_sea_lakes != CUSTOM_SEA_LEVEL_NUMBER_DIFFICULTY);
1320                                 uint i = ScaleByMapSize(GB(r, 0, 7) + (3 - _settings_game.difficulty.quantity_sea_lakes) * 256 + 100);
1321                                 for (; i != 0; --i) {
1322                                         /* Make sure we do not overflow. */
1323                                         GenerateTerrain(Clamp(_settings_game.difficulty.terrain_type, 0, 3), 0);
1324                                 }
1325                                 break;
1326                         }
1327                 }
1328         }
1329
1330         /* Do not call IncreaseGeneratingWorldProgress() before FixSlopes(),
1331          * it allows screen redraw. Drawing of broken slopes crashes the game */
1332         FixSlopes();
1333         IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
1334         ConvertGroundTilesIntoWaterTiles();
1335         IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
1336
1337         if (_settings_game.game_creation.landscape == LT_TROPIC) CreateDesertOrRainForest();
1338
1339         CreateRivers();
1340 }
1341
1342 void OnTick_Town();
1343 void OnTick_Trees();
1344 void OnTick_Station();
1345 void OnTick_Industry();
1346
1347 void OnTick_Companies();
1348 void OnTick_LinkGraph();
1349
1350 void CallLandscapeTick()
1351 {
1352         OnTick_Town();
1353         OnTick_Trees();
1354         OnTick_Station();
1355         OnTick_Industry();
1356
1357         OnTick_Companies();
1358         OnTick_LinkGraph();
1359 }