src/landscape.cpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * 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.
   4  * 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.
   5  * 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/>.
   6  */
   7
   8 /** @file landscape.cpp Functions related to the landscape (slopes etc.). */
   9
  10 /** @defgroup SnowLineGroup Snowline functions and data structures */
  11
  12 #include "stdafx.h"
  13 #include "heightmap.h"
  14 #include "clear_map.h"
  15 #include "spritecache.h"
  16 #include "viewport_func.h"
  17 #include "command_func.h"
  18 #include "landscape.h"
  19 #include "void_map.h"
  20 #include "tgp.h"
  21 #include "genworld.h"
  22 #include "fios.h"
  23 #include "date_func.h"
  24 #include "water.h"
  25 #include "effectvehicle_func.h"
  26 #include "landscape_type.h"
  27 #include "animated_tile_func.h"
  28 #include "core/random_func.hpp"
  29 #include "object_base.h"
  30 #include "company_func.h"
  31 #include "pathfinder/npf/aystar.h"
  32 #include "saveload/saveload.h"
  33 #include "framerate_type.h"
  34 #include "landscape_cmd.h"
  35 #include "terraform_cmd.h"
  36 #include "station_func.h"
  37 #include <array>
  38 #include <list>
  39 #include <set>
  40
  41 #include "table/strings.h"
  42 #include "table/sprites.h"
  43
  44 #include "safeguards.h"
  45
  46 extern const TileTypeProcs
  47         _tile_type_clear_procs,
  48         _tile_type_rail_procs,
  49         _tile_type_road_procs,
  50         _tile_type_town_procs,
  51         _tile_type_trees_procs,
  52         _tile_type_station_procs,
  53         _tile_type_water_procs,
  54         _tile_type_void_procs,
  55         _tile_type_industry_procs,
  56         _tile_type_tunnelbridge_procs,
  57         _tile_type_object_procs;
  58
  59 /**
  60  * Tile callback functions for each type of tile.
  61  * @ingroup TileCallbackGroup
  62  * @see TileType
  63  */
  64 const TileTypeProcs * const _tile_type_procs[16] = {
  65         &_tile_type_clear_procs,        ///< Callback functions for MP_CLEAR tiles
  66         &_tile_type_rail_procs,         ///< Callback functions for MP_RAILWAY tiles
  67         &_tile_type_road_procs,         ///< Callback functions for MP_ROAD tiles
  68         &_tile_type_town_procs,         ///< Callback functions for MP_HOUSE tiles
  69         &_tile_type_trees_procs,        ///< Callback functions for MP_TREES tiles
  70         &_tile_type_station_procs,      ///< Callback functions for MP_STATION tiles
  71         &_tile_type_water_procs,        ///< Callback functions for MP_WATER tiles
  72         &_tile_type_void_procs,         ///< Callback functions for MP_VOID tiles
  73         &_tile_type_industry_procs,     ///< Callback functions for MP_INDUSTRY tiles
  74         &_tile_type_tunnelbridge_procs, ///< Callback functions for MP_TUNNELBRIDGE tiles
  75         &_tile_type_object_procs,       ///< Callback functions for MP_OBJECT tiles
  76 };
  77
  78 /** landscape slope => sprite */
  79 extern const byte _slope_to_sprite_offset[32] = {
  80         0, 1, 2, 3, 4, 5, 6,  7, 8, 9, 10, 11, 12, 13, 14, 0,
  81         0, 0, 0, 0, 0, 0, 0, 16, 0, 0,  0, 17,  0, 15, 18, 0,
  82 };
  83
  84 /**
  85  * Description of the snow line throughout the year.
  86  *
  87  * If it is \c nullptr, a static snowline height is used, as set by \c _settings_game.game_creation.snow_line_height.
  88  * Otherwise it points to a table loaded from a newGRF file that describes the variable snowline.
  89  * @ingroup SnowLineGroup
  90  * @see GetSnowLine() GameCreationSettings
  91  */
  92 static SnowLine *_snow_line = nullptr;
  93
  94 /**
  95  * Map 2D viewport or smallmap coordinate to 3D world or tile coordinate.
  96  * Function takes into account height of tiles and foundations.
  97  *
  98  * @param x X viewport 2D coordinate.
  99  * @param y Y viewport 2D coordinate.
 100  * @param clamp_to_map Clamp the coordinate outside of the map to the closest, non-void tile within the map.
 101  * @param[out] clamped Whether coordinates were clamped.
 102  * @return 3D world coordinate of point visible at the given screen coordinate (3D perspective).
 103  *
 104  * @note Inverse of #RemapCoords2 function. Smaller values may get rounded.
 105  * @see InverseRemapCoords
 106  */
 107 Point InverseRemapCoords2(int x, int y, bool clamp_to_map, bool *clamped)
 108 {
 109         if (clamped != nullptr) *clamped = false; // Not clamping yet.
 110
 111         /* Initial x/y world coordinate is like if the landscape
 112          * was completely flat on height 0. */
 113         Point pt = InverseRemapCoords(x, y);
 114
 115         const uint min_coord = _settings_game.construction.freeform_edges ? TILE_SIZE : 0;
 116         const uint max_x = MapMaxX() * TILE_SIZE - 1;
 117         const uint max_y = MapMaxY() * TILE_SIZE - 1;
 118
 119         if (clamp_to_map) {
 120                 /* Bring the coordinates near to a valid range. At the top we allow a number
 121                  * of extra tiles. This is mostly due to the tiles on the north side of
 122                  * the map possibly being drawn higher due to the extra height levels. */
 123                 int extra_tiles = CeilDiv(_settings_game.construction.map_height_limit * TILE_HEIGHT, TILE_PIXELS);
 124                 Point old_pt = pt;
 125                 pt.x = Clamp(pt.x, -extra_tiles * TILE_SIZE, max_x);
 126                 pt.y = Clamp(pt.y, -extra_tiles * TILE_SIZE, max_y);
 127                 if (clamped != nullptr) *clamped = (pt.x != old_pt.x) || (pt.y != old_pt.y);
 128         }
 129
 130         /* Now find the Z-world coordinate by fix point iteration.
 131          * This is a bit tricky because the tile height is non-continuous at foundations.
 132          * The clicked point should be approached from the back, otherwise there are regions that are not clickable.
 133          * (FOUNDATION_HALFTILE_LOWER on SLOPE_STEEP_S hides north halftile completely)
 134          * So give it a z-malus of 4 in the first iterations. */
 135         int z = 0;
 136         if (clamp_to_map) {
 137                 for (int i = 0; i < 5; i++) z = GetSlopePixelZ(Clamp(pt.x + std::max(z, 4) - 4, min_coord, max_x), Clamp(pt.y + std::max(z, 4) - 4, min_coord, max_y)) / 2;
 138                 for (int m = 3; m > 0; m--) z = GetSlopePixelZ(Clamp(pt.x + std::max(z, m) - m, min_coord, max_x), Clamp(pt.y + std::max(z, m) - m, min_coord, max_y)) / 2;
 139                 for (int i = 0; i < 5; i++) z = GetSlopePixelZ(Clamp(pt.x + z,             min_coord, max_x), Clamp(pt.y + z,             min_coord, max_y)) / 2;
 140         } else {
 141                 for (int i = 0; i < 5; i++) z = GetSlopePixelZOutsideMap(pt.x + std::max(z, 4) - 4, pt.y + std::max(z, 4) - 4) / 2;
 142                 for (int m = 3; m > 0; m--) z = GetSlopePixelZOutsideMap(pt.x + std::max(z, m) - m, pt.y + std::max(z, m) - m) / 2;
 143                 for (int i = 0; i < 5; i++) z = GetSlopePixelZOutsideMap(pt.x + z,             pt.y + z            ) / 2;
 144         }
 145
 146         pt.x += z;
 147         pt.y += z;
 148         if (clamp_to_map) {
 149                 Point old_pt = pt;
 150                 pt.x = Clamp(pt.x, min_coord, max_x);
 151                 pt.y = Clamp(pt.y, min_coord, max_y);
 152                 if (clamped != nullptr) *clamped = *clamped || (pt.x != old_pt.x) || (pt.y != old_pt.y);
 153         }
 154
 155         return pt;
 156 }
 157
 158 /**
 159  * Applies a foundation to a slope.
 160  *
 161  * @pre      Foundation and slope must be valid combined.
 162  * @param f  The #Foundation.
 163  * @param s  The #Slope to modify.
 164  * @return   Increment to the tile Z coordinate.
 165  */
 166 uint ApplyFoundationToSlope(Foundation f, Slope *s)
 167 {
 168         if (!IsFoundation(f)) return 0;
 169
 170         if (IsLeveledFoundation(f)) {
 171                 uint dz = 1 + (IsSteepSlope(*s) ? 1 : 0);
 172                 *s = SLOPE_FLAT;
 173                 return dz;
 174         }
 175
 176         if (f != FOUNDATION_STEEP_BOTH && IsNonContinuousFoundation(f)) {
 177                 *s = HalftileSlope(*s, GetHalftileFoundationCorner(f));
 178                 return 0;
 179         }
 180
 181         if (IsSpecialRailFoundation(f)) {
 182                 *s = SlopeWithThreeCornersRaised(OppositeCorner(GetRailFoundationCorner(f)));
 183                 return 0;
 184         }
 185
 186         uint dz = IsSteepSlope(*s) ? 1 : 0;
 187         Corner highest_corner = GetHighestSlopeCorner(*s);
 188
 189         switch (f) {
 190                 case FOUNDATION_INCLINED_X:
 191                         *s = (((highest_corner == CORNER_W) || (highest_corner == CORNER_S)) ? SLOPE_SW : SLOPE_NE);
 192                         break;
 193
 194                 case FOUNDATION_INCLINED_Y:
 195                         *s = (((highest_corner == CORNER_S) || (highest_corner == CORNER_E)) ? SLOPE_SE : SLOPE_NW);
 196                         break;
 197
 198                 case FOUNDATION_STEEP_LOWER:
 199                         *s = SlopeWithOneCornerRaised(highest_corner);
 200                         break;
 201
 202                 case FOUNDATION_STEEP_BOTH:
 203                         *s = HalftileSlope(SlopeWithOneCornerRaised(highest_corner), highest_corner);
 204                         break;
 205
 206                 default: NOT_REACHED();
 207         }
 208         return dz;
 209 }
 210
 211
 212 /**
 213  * Determines height at given coordinate of a slope
 214  * @param x x coordinate
 215  * @param y y coordinate
 216  * @param corners slope to examine
 217  * @return height of given point of given slope
 218  */
 219 uint GetPartialPixelZ(int x, int y, Slope corners)
 220 {
 221         if (IsHalftileSlope(corners)) {
 222                 switch (GetHalftileSlopeCorner(corners)) {
 223                         case CORNER_W:
 224                                 if (x - y >= 0) return GetSlopeMaxPixelZ(corners);
 225                                 break;
 226
 227                         case CORNER_S:
 228                                 if (x - (y ^ 0xF) >= 0) return GetSlopeMaxPixelZ(corners);
 229                                 break;
 230
 231                         case CORNER_E:
 232                                 if (y - x >= 0) return GetSlopeMaxPixelZ(corners);
 233                                 break;
 234
 235                         case CORNER_N:
 236                                 if ((y ^ 0xF) - x >= 0) return GetSlopeMaxPixelZ(corners);
 237                                 break;
 238
 239                         default: NOT_REACHED();
 240                 }
 241         }
 242
 243         int z = 0;
 244
 245         switch (RemoveHalftileSlope(corners)) {
 246                 case SLOPE_W:
 247                         if (x - y >= 0) {
 248                                 z = (x - y) >> 1;
 249                         }
 250                         break;
 251
 252                 case SLOPE_S:
 253                         y ^= 0xF;
 254                         if ((x - y) >= 0) {
 255                                 z = (x - y) >> 1;
 256                         }
 257                         break;
 258
 259                 case SLOPE_SW:
 260                         z = (x >> 1) + 1;
 261                         break;
 262
 263                 case SLOPE_E:
 264                         if (y - x >= 0) {
 265                                 z = (y - x) >> 1;
 266                         }
 267                         break;
 268
 269                 case SLOPE_EW:
 270                 case SLOPE_NS:
 271                 case SLOPE_ELEVATED:
 272                         z = 4;
 273                         break;
 274
 275                 case SLOPE_SE:
 276                         z = (y >> 1) + 1;
 277                         break;
 278
 279                 case SLOPE_WSE:
 280                         z = 8;
 281                         y ^= 0xF;
 282                         if (x - y < 0) {
 283                                 z += (x - y) >> 1;
 284                         }
 285                         break;
 286
 287                 case SLOPE_N:
 288                         y ^= 0xF;
 289                         if (y - x >= 0) {
 290                                 z = (y - x) >> 1;
 291                         }
 292                         break;
 293
 294                 case SLOPE_NW:
 295                         z = (y ^ 0xF) >> 1;
 296                         break;
 297
 298                 case SLOPE_NWS:
 299                         z = 8;
 300                         if (x - y < 0) {
 301                                 z += (x - y) >> 1;
 302                         }
 303                         break;
 304
 305                 case SLOPE_NE:
 306                         z = (x ^ 0xF) >> 1;
 307                         break;
 308
 309                 case SLOPE_ENW:
 310                         z = 8;
 311                         y ^= 0xF;
 312                         if (y - x < 0) {
 313                                 z += (y - x) >> 1;
 314                         }
 315                         break;
 316
 317                 case SLOPE_SEN:
 318                         z = 8;
 319                         if (y - x < 0) {
 320                                 z += (y - x) >> 1;
 321                         }
 322                         break;
 323
 324                 case SLOPE_STEEP_S:
 325                         z = 1 + ((x + y) >> 1);
 326                         break;
 327
 328                 case SLOPE_STEEP_W:
 329                         z = 1 + ((x + (y ^ 0xF)) >> 1);
 330                         break;
 331
 332                 case SLOPE_STEEP_N:
 333                         z = 1 + (((x ^ 0xF) + (y ^ 0xF)) >> 1);
 334                         break;
 335
 336                 case SLOPE_STEEP_E:
 337                         z = 1 + (((x ^ 0xF) + y) >> 1);
 338                         break;
 339
 340                 default: break;
 341         }
 342
 343         return z;
 344 }
 345
 346 int GetSlopePixelZ(int x, int y)
 347 {
 348         TileIndex tile = TileVirtXY(x, y);
 349
 350         return _tile_type_procs[GetTileType(tile)]->get_slope_z_proc(tile, x, y);
 351 }
 352
 353 /**
 354  * Return world \c z coordinate of a given point of a tile,
 355  * also for tiles outside the map (virtual "black" tiles).
 356  *
 357  * @param x World X coordinate in tile "units", may be outside the map.
 358  * @param y World Y coordinate in tile "units", may be outside the map.
 359  * @return World Z coordinate at tile ground level, including slopes and foundations.
 360  */
 361 int GetSlopePixelZOutsideMap(int x, int y)
 362 {
 363         if (IsInsideBS(x, 0, MapSizeX() * TILE_SIZE) && IsInsideBS(y, 0, MapSizeY() * TILE_SIZE)) {
 364                 return GetSlopePixelZ(x, y);
 365         } else {
 366                 return _tile_type_procs[MP_VOID]->get_slope_z_proc(INVALID_TILE, x, y);
 367         }
 368 }
 369
 370 /**
 371  * Determine the Z height of a corner relative to TileZ.
 372  *
 373  * @pre The slope must not be a halftile slope.
 374  *
 375  * @param tileh The slope.
 376  * @param corner The corner.
 377  * @return Z position of corner relative to TileZ.
 378  */
 379 int GetSlopeZInCorner(Slope tileh, Corner corner)
 380 {
 381         assert(!IsHalftileSlope(tileh));
 382         return ((tileh & SlopeWithOneCornerRaised(corner)) != 0 ? 1 : 0) + (tileh == SteepSlope(corner) ? 1 : 0);
 383 }
 384
 385 /**
 386  * Determine the Z height of the corners of a specific tile edge
 387  *
 388  * @note If a tile has a non-continuous halftile foundation, a corner can have different heights wrt. its edges.
 389  *
 390  * @pre z1 and z2 must be initialized (typ. with TileZ). The corner heights just get added.
 391  *
 392  * @param tileh The slope of the tile.
 393  * @param edge The edge of interest.
 394  * @param z1 Gets incremented by the height of the first corner of the edge. (near corner wrt. the camera)
 395  * @param z2 Gets incremented by the height of the second corner of the edge. (far corner wrt. the camera)
 396  */
 397 void GetSlopePixelZOnEdge(Slope tileh, DiagDirection edge, int *z1, int *z2)
 398 {
 399         static const Slope corners[4][4] = {
 400                 /*    corner     |          steep slope
 401                  *  z1      z2   |       z1             z2        */
 402                 {SLOPE_E, SLOPE_N, SLOPE_STEEP_E, SLOPE_STEEP_N}, // DIAGDIR_NE, z1 = E, z2 = N
 403                 {SLOPE_S, SLOPE_E, SLOPE_STEEP_S, SLOPE_STEEP_E}, // DIAGDIR_SE, z1 = S, z2 = E
 404                 {SLOPE_S, SLOPE_W, SLOPE_STEEP_S, SLOPE_STEEP_W}, // DIAGDIR_SW, z1 = S, z2 = W
 405                 {SLOPE_W, SLOPE_N, SLOPE_STEEP_W, SLOPE_STEEP_N}, // DIAGDIR_NW, z1 = W, z2 = N
 406         };
 407
 408         int halftile_test = (IsHalftileSlope(tileh) ? SlopeWithOneCornerRaised(GetHalftileSlopeCorner(tileh)) : 0);
 409         if (halftile_test == corners[edge][0]) *z2 += TILE_HEIGHT; // The slope is non-continuous in z2. z2 is on the upper side.
 410         if (halftile_test == corners[edge][1]) *z1 += TILE_HEIGHT; // The slope is non-continuous in z1. z1 is on the upper side.
 411
 412         if ((tileh & corners[edge][0]) != 0) *z1 += TILE_HEIGHT; // z1 is raised
 413         if ((tileh & corners[edge][1]) != 0) *z2 += TILE_HEIGHT; // z2 is raised
 414         if (RemoveHalftileSlope(tileh) == corners[edge][2]) *z1 += TILE_HEIGHT; // z1 is highest corner of a steep slope
 415         if (RemoveHalftileSlope(tileh) == corners[edge][3]) *z2 += TILE_HEIGHT; // z2 is highest corner of a steep slope
 416 }
 417
 418 /**
 419  * Get slope of a tile on top of a (possible) foundation
 420  * If a tile does not have a foundation, the function returns the same as GetTileSlope.
 421  *
 422  * @param tile The tile of interest.
 423  * @param z returns the z of the foundation slope. (Can be nullptr, if not needed)
 424  * @return The slope on top of the foundation.
 425  */
 426 Slope GetFoundationSlope(TileIndex tile, int *z)
 427 {
 428         Slope tileh = GetTileSlope(tile, z);
 429         Foundation f = _tile_type_procs[GetTileType(tile)]->get_foundation_proc(tile, tileh);
 430         uint z_inc = ApplyFoundationToSlope(f, &tileh);
 431         if (z != nullptr) *z += z_inc;
 432         return tileh;
 433 }
 434
 435
 436 bool HasFoundationNW(TileIndex tile, Slope slope_here, uint z_here)
 437 {
 438         int z;
 439
 440         int z_W_here = z_here;
 441         int z_N_here = z_here;
 442         GetSlopePixelZOnEdge(slope_here, DIAGDIR_NW, &z_W_here, &z_N_here);
 443
 444         Slope slope = GetFoundationPixelSlope(TILE_ADDXY(tile, 0, -1), &z);
 445         int z_W = z;
 446         int z_N = z;
 447         GetSlopePixelZOnEdge(slope, DIAGDIR_SE, &z_W, &z_N);
 448
 449         return (z_N_here > z_N) || (z_W_here > z_W);
 450 }
 451
 452
 453 bool HasFoundationNE(TileIndex tile, Slope slope_here, uint z_here)
 454 {
 455         int z;
 456
 457         int z_E_here = z_here;
 458         int z_N_here = z_here;
 459         GetSlopePixelZOnEdge(slope_here, DIAGDIR_NE, &z_E_here, &z_N_here);
 460
 461         Slope slope = GetFoundationPixelSlope(TILE_ADDXY(tile, -1, 0), &z);
 462         int z_E = z;
 463         int z_N = z;
 464         GetSlopePixelZOnEdge(slope, DIAGDIR_SW, &z_E, &z_N);
 465
 466         return (z_N_here > z_N) || (z_E_here > z_E);
 467 }
 468
 469 /**
 470  * Draw foundation \a f at tile \a ti. Updates \a ti.
 471  * @param ti Tile to draw foundation on
 472  * @param f  Foundation to draw
 473  */
 474 void DrawFoundation(TileInfo *ti, Foundation f)
 475 {
 476         if (!IsFoundation(f)) return;
 477
 478         /* Two part foundations must be drawn separately */
 479         assert(f != FOUNDATION_STEEP_BOTH);
 480
 481         uint sprite_block = 0;
 482         int z;
 483         Slope slope = GetFoundationPixelSlope(ti->tile, &z);
 484
 485         /* Select the needed block of foundations sprites
 486          * Block 0: Walls at NW and NE edge
 487          * Block 1: Wall  at        NE edge
 488          * Block 2: Wall  at NW        edge
 489          * Block 3: No walls at NW or NE edge
 490          */
 491         if (!HasFoundationNW(ti->tile, slope, z)) sprite_block += 1;
 492         if (!HasFoundationNE(ti->tile, slope, z)) sprite_block += 2;
 493
 494         /* Use the original slope sprites if NW and NE borders should be visible */
 495         SpriteID leveled_base = (sprite_block == 0 ? (int)SPR_FOUNDATION_BASE : (SPR_SLOPES_VIRTUAL_BASE + sprite_block * SPR_TRKFOUND_BLOCK_SIZE));
 496         SpriteID inclined_base = SPR_SLOPES_VIRTUAL_BASE + SPR_SLOPES_INCLINED_OFFSET + sprite_block * SPR_TRKFOUND_BLOCK_SIZE;
 497         SpriteID halftile_base = SPR_HALFTILE_FOUNDATION_BASE + sprite_block * SPR_HALFTILE_BLOCK_SIZE;
 498
 499         if (IsSteepSlope(ti->tileh)) {
 500                 if (!IsNonContinuousFoundation(f)) {
 501                         /* Lower part of foundation */
 502                         AddSortableSpriteToDraw(
 503                                 leveled_base + (ti->tileh & ~SLOPE_STEEP), PAL_NONE, ti->x, ti->y, 16, 16, 7, ti->z
 504                         );
 505                 }
 506
 507                 Corner highest_corner = GetHighestSlopeCorner(ti->tileh);
 508                 ti->z += ApplyPixelFoundationToSlope(f, &ti->tileh);
 509
 510                 if (IsInclinedFoundation(f)) {
 511                         /* inclined foundation */
 512                         byte inclined = highest_corner * 2 + (f == FOUNDATION_INCLINED_Y ? 1 : 0);
 513
 514                         AddSortableSpriteToDraw(inclined_base + inclined, PAL_NONE, ti->x, ti->y,
 515                                 f == FOUNDATION_INCLINED_X ? 16 : 1,
 516                                 f == FOUNDATION_INCLINED_Y ? 16 : 1,
 517                                 TILE_HEIGHT, ti->z
 518                         );
 519                         OffsetGroundSprite(31, 9);
 520                 } else if (IsLeveledFoundation(f)) {
 521                         AddSortableSpriteToDraw(leveled_base + SlopeWithOneCornerRaised(highest_corner), PAL_NONE, ti->x, ti->y, 16, 16, 7, ti->z - TILE_HEIGHT);
 522                         OffsetGroundSprite(31, 1);
 523                 } else if (f == FOUNDATION_STEEP_LOWER) {
 524                         /* one corner raised */
 525                         OffsetGroundSprite(31, 1);
 526                 } else {
 527                         /* halftile foundation */
 528                         int x_bb = (((highest_corner == CORNER_W) || (highest_corner == CORNER_S)) ? 8 : 0);
 529                         int y_bb = (((highest_corner == CORNER_S) || (highest_corner == CORNER_E)) ? 8 : 0);
 530
 531                         AddSortableSpriteToDraw(halftile_base + highest_corner, PAL_NONE, ti->x + x_bb, ti->y + y_bb, 8, 8, 7, ti->z + TILE_HEIGHT);
 532                         OffsetGroundSprite(31, 9);
 533                 }
 534         } else {
 535                 if (IsLeveledFoundation(f)) {
 536                         /* leveled foundation */
 537                         AddSortableSpriteToDraw(leveled_base + ti->tileh, PAL_NONE, ti->x, ti->y, 16, 16, 7, ti->z);
 538                         OffsetGroundSprite(31, 1);
 539                 } else if (IsNonContinuousFoundation(f)) {
 540                         /* halftile foundation */
 541                         Corner halftile_corner = GetHalftileFoundationCorner(f);
 542                         int x_bb = (((halftile_corner == CORNER_W) || (halftile_corner == CORNER_S)) ? 8 : 0);
 543                         int y_bb = (((halftile_corner == CORNER_S) || (halftile_corner == CORNER_E)) ? 8 : 0);
 544
 545                         AddSortableSpriteToDraw(halftile_base + halftile_corner, PAL_NONE, ti->x + x_bb, ti->y + y_bb, 8, 8, 7, ti->z);
 546                         OffsetGroundSprite(31, 9);
 547                 } else if (IsSpecialRailFoundation(f)) {
 548                         /* anti-zig-zag foundation */
 549                         SpriteID spr;
 550                         if (ti->tileh == SLOPE_NS || ti->tileh == SLOPE_EW) {
 551                                 /* half of leveled foundation under track corner */
 552                                 spr = leveled_base + SlopeWithThreeCornersRaised(GetRailFoundationCorner(f));
 553                         } else {
 554                                 /* tile-slope = sloped along X/Y, foundation-slope = three corners raised */
 555                                 spr = inclined_base + 2 * GetRailFoundationCorner(f) + ((ti->tileh == SLOPE_SW || ti->tileh == SLOPE_NE) ? 1 : 0);
 556                         }
 557                         AddSortableSpriteToDraw(spr, PAL_NONE, ti->x, ti->y, 16, 16, 7, ti->z);
 558                         OffsetGroundSprite(31, 9);
 559                 } else {
 560                         /* inclined foundation */
 561                         byte inclined = GetHighestSlopeCorner(ti->tileh) * 2 + (f == FOUNDATION_INCLINED_Y ? 1 : 0);
 562
 563                         AddSortableSpriteToDraw(inclined_base + inclined, PAL_NONE, ti->x, ti->y,
 564                                 f == FOUNDATION_INCLINED_X ? 16 : 1,
 565                                 f == FOUNDATION_INCLINED_Y ? 16 : 1,
 566                                 TILE_HEIGHT, ti->z
 567                         );
 568                         OffsetGroundSprite(31, 9);
 569                 }
 570                 ti->z += ApplyPixelFoundationToSlope(f, &ti->tileh);
 571         }
 572 }
 573
 574 void DoClearSquare(TileIndex tile)
 575 {
 576         /* If the tile can have animation and we clear it, delete it from the animated tile list. */
 577         if (_tile_type_procs[GetTileType(tile)]->animate_tile_proc != nullptr) DeleteAnimatedTile(tile);
 578
 579         bool remove = IsDockingTile(tile);
 580         MakeClear(tile, CLEAR_GRASS, _generating_world ? 3 : 0);
 581         MarkTileDirtyByTile(tile);
 582         if (remove) RemoveDockingTile(tile);
 583 }
 584
 585 /**
 586  * Returns information about trackdirs and signal states.
 587  * If there is any trackbit at 'side', return all trackdirbits.
 588  * For TRANSPORT_ROAD, return no trackbits if there is no roadbit (of given subtype) at given side.
 589  * @param tile tile to get info about
 590  * @param mode transport type
 591  * @param sub_mode for TRANSPORT_ROAD, roadtypes to check
 592  * @param side side we are entering from, INVALID_DIAGDIR to return all trackbits
 593  * @return trackdirbits and other info depending on 'mode'
 594  */
 595 TrackStatus GetTileTrackStatus(TileIndex tile, TransportType mode, uint sub_mode, DiagDirection side)
 596 {
 597         return _tile_type_procs[GetTileType(tile)]->get_tile_track_status_proc(tile, mode, sub_mode, side);
 598 }
 599
 600 /**
 601  * Change the owner of a tile
 602  * @param tile      Tile to change
 603  * @param old_owner Current owner of the tile
 604  * @param new_owner New owner of the tile
 605  */
 606 void ChangeTileOwner(TileIndex tile, Owner old_owner, Owner new_owner)
 607 {
 608         _tile_type_procs[GetTileType(tile)]->change_tile_owner_proc(tile, old_owner, new_owner);
 609 }
 610
 611 void GetTileDesc(TileIndex tile, TileDesc *td)
 612 {
 613         _tile_type_procs[GetTileType(tile)]->get_tile_desc_proc(tile, td);
 614 }
 615
 616 /**
 617  * Has a snow line table already been loaded.
 618  * @return true if the table has been loaded already.
 619  * @ingroup SnowLineGroup
 620  */
 621 bool IsSnowLineSet()
 622 {
 623         return _snow_line != nullptr;
 624 }
 625
 626 /**
 627  * Set a variable snow line, as loaded from a newgrf file.
 628  * @param table the 12 * 32 byte table containing the snowline for each day
 629  * @ingroup SnowLineGroup
 630  */
 631 void SetSnowLine(byte table[SNOW_LINE_MONTHS][SNOW_LINE_DAYS])
 632 {
 633         _snow_line = CallocT<SnowLine>(1);
 634         _snow_line->lowest_value = 0xFF;
 635         memcpy(_snow_line->table, table, sizeof(_snow_line->table));
 636
 637         for (uint i = 0; i < SNOW_LINE_MONTHS; i++) {
 638                 for (uint j = 0; j < SNOW_LINE_DAYS; j++) {
 639                         _snow_line->highest_value = std::max(_snow_line->highest_value, table[i][j]);
 640                         _snow_line->lowest_value = std::min(_snow_line->lowest_value, table[i][j]);
 641                 }
 642         }
 643 }
 644
 645 /**
 646  * Get the current snow line, either variable or static.
 647  * @return the snow line height.
 648  * @ingroup SnowLineGroup
 649  */
 650 byte GetSnowLine()
 651 {
 652         if (_snow_line == nullptr) return _settings_game.game_creation.snow_line_height;
 653
 654         YearMonthDay ymd;
 655         ConvertDateToYMD(_date, &ymd);
 656         return _snow_line->table[ymd.month][ymd.day];
 657 }
 658
 659 /**
 660  * Get the highest possible snow line height, either variable or static.
 661  * @return the highest snow line height.
 662  * @ingroup SnowLineGroup
 663  */
 664 byte HighestSnowLine()
 665 {
 666         return _snow_line == nullptr ? _settings_game.game_creation.snow_line_height : _snow_line->highest_value;
 667 }
 668
 669 /**
 670  * Get the lowest possible snow line height, either variable or static.
 671  * @return the lowest snow line height.
 672  * @ingroup SnowLineGroup
 673  */
 674 byte LowestSnowLine()
 675 {
 676         return _snow_line == nullptr ? _settings_game.game_creation.snow_line_height : _snow_line->lowest_value;
 677 }
 678
 679 /**
 680  * Clear the variable snow line table and free the memory.
 681  * @ingroup SnowLineGroup
 682  */
 683 void ClearSnowLine()
 684 {
 685         free(_snow_line);
 686         _snow_line = nullptr;
 687 }
 688
 689 /**
 690  * Clear a piece of landscape
 691  * @param flags of operation to conduct
 692  * @param tile tile to clear
 693  * @return the cost of this operation or an error
 694  */
 695 CommandCost CmdLandscapeClear(DoCommandFlag flags, TileIndex tile)
 696 {
 697         CommandCost cost(EXPENSES_CONSTRUCTION);
 698         bool do_clear = false;
 699         /* Test for stuff which results in water when cleared. Then add the cost to also clear the water. */
 700         if ((flags & DC_FORCE_CLEAR_TILE) && HasTileWaterClass(tile) && IsTileOnWater(tile) && !IsWaterTile(tile) && !IsCoastTile(tile)) {
 701                 if ((flags & DC_AUTO) && GetWaterClass(tile) == WATER_CLASS_CANAL) return_cmd_error(STR_ERROR_MUST_DEMOLISH_CANAL_FIRST);
 702                 do_clear = true;
 703                 cost.AddCost(GetWaterClass(tile) == WATER_CLASS_CANAL ? _price[PR_CLEAR_CANAL] : _price[PR_CLEAR_WATER]);
 704         }
 705
 706         Company *c = (flags & (DC_AUTO | DC_BANKRUPT)) ? nullptr : Company::GetIfValid(_current_company);
 707         if (c != nullptr && (int)GB(c->clear_limit, 16, 16) < 1) {
 708                 return_cmd_error(STR_ERROR_CLEARING_LIMIT_REACHED);
 709         }
 710
 711         const ClearedObjectArea *coa = FindClearedObject(tile);
 712
 713         /* If this tile was the first tile which caused object destruction, always
 714          * pass it on to the tile_type_proc. That way multiple test runs and the exec run stay consistent. */
 715         if (coa != nullptr && coa->first_tile != tile) {
 716                 /* If this tile belongs to an object which was already cleared via another tile, pretend it has been
 717                  * already removed.
 718                  * However, we need to check stuff, which is not the same for all object tiles. (e.g. being on water or not) */
 719
 720                 /* If a object is removed, it leaves either bare land or water. */
 721                 if ((flags & DC_NO_WATER) && HasTileWaterClass(tile) && IsTileOnWater(tile)) {
 722                         return_cmd_error(STR_ERROR_CAN_T_BUILD_ON_WATER);
 723                 }
 724         } else {
 725                 cost.AddCost(_tile_type_procs[GetTileType(tile)]->clear_tile_proc(tile, flags));
 726         }
 727
 728         if (flags & DC_EXEC) {
 729                 if (c != nullptr) c->clear_limit -= 1 << 16;
 730                 if (do_clear) DoClearSquare(tile);
 731         }
 732         return cost;
 733 }
 734
 735 /**
 736  * Clear a big piece of landscape
 737  * @param flags of operation to conduct
 738  * @param tile end tile of area dragging
 739  * @param start_tile start tile of area dragging
 740  * @param diagonal Whether to use the Orthogonal (false) or Diagonal (true) iterator.
 741  * @return the cost of this operation or an error
 742  */
 743 std::tuple<CommandCost, Money> CmdClearArea(DoCommandFlag flags, TileIndex tile, TileIndex start_tile, bool diagonal)
 744 {
 745         if (start_tile >= MapSize()) return { CMD_ERROR, 0 };
 746
 747         Money money = GetAvailableMoneyForCommand();
 748         CommandCost cost(EXPENSES_CONSTRUCTION);
 749         CommandCost last_error = CMD_ERROR;
 750         bool had_success = false;
 751
 752         const Company *c = (flags & (DC_AUTO | DC_BANKRUPT)) ? nullptr : Company::GetIfValid(_current_company);
 753         int limit = (c == nullptr ? INT32_MAX : GB(c->clear_limit, 16, 16));
 754
 755         TileIterator *iter = diagonal ? (TileIterator *)new DiagonalTileIterator(tile, start_tile) : new OrthogonalTileIterator(tile, start_tile);
 756         for (; *iter != INVALID_TILE; ++(*iter)) {
 757                 TileIndex t = *iter;
 758                 CommandCost ret = Command<CMD_LANDSCAPE_CLEAR>::Do(flags & ~DC_EXEC, t);
 759                 if (ret.Failed()) {
 760                         last_error = ret;
 761
 762                         /* We may not clear more tiles. */
 763                         if (c != nullptr && GB(c->clear_limit, 16, 16) < 1) break;
 764                         continue;
 765                 }
 766
 767                 had_success = true;
 768                 if (flags & DC_EXEC) {
 769                         money -= ret.GetCost();
 770                         if (ret.GetCost() > 0 && money < 0) {
 771                                 delete iter;
 772                                 return { cost, ret.GetCost() };
 773                         }
 774                         Command<CMD_LANDSCAPE_CLEAR>::Do(flags, t);
 775
 776                         /* draw explosion animation...
 777                          * Disable explosions when game is paused. Looks silly and blocks the view. */
 778                         if ((t == tile || t == start_tile) && _pause_mode == PM_UNPAUSED) {
 779                                 /* big explosion in two corners, or small explosion for single tiles */
 780                                 CreateEffectVehicleAbove(TileX(t) * TILE_SIZE + TILE_SIZE / 2, TileY(t) * TILE_SIZE + TILE_SIZE / 2, 2,
 781                                         TileX(tile) == TileX(start_tile) && TileY(tile) == TileY(start_tile) ? EV_EXPLOSION_SMALL : EV_EXPLOSION_LARGE
 782                                 );
 783                         }
 784                 } else {
 785                         /* When we're at the clearing limit we better bail (unneed) testing as well. */
 786                         if (ret.GetCost() != 0 && --limit <= 0) break;
 787                 }
 788                 cost.AddCost(ret);
 789         }
 790
 791         delete iter;
 792         return { had_success ? cost : last_error, 0 };
 793 }
 794
 795
 796 TileIndex _cur_tileloop_tile;
 797
 798 /**
 799  * Gradually iterate over all tiles on the map, calling their TileLoopProcs once every 256 ticks.
 800  */
 801 void RunTileLoop()
 802 {
 803         PerformanceAccumulator framerate(PFE_GL_LANDSCAPE);
 804
 805         /* The pseudorandom sequence of tiles is generated using a Galois linear feedback
 806          * shift register (LFSR). This allows a deterministic pseudorandom ordering, but
 807          * still with minimal state and fast iteration. */
 808
 809         /* Maximal length LFSR feedback terms, from 12-bit (for 64x64 maps) to 24-bit (for 4096x4096 maps).
 810          * Extracted from http://www.ece.cmu.edu/~koopman/lfsr/ */
 811         static const uint32 feedbacks[] = {
 812                 0xD8F, 0x1296, 0x2496, 0x4357, 0x8679, 0x1030E, 0x206CD, 0x403FE, 0x807B8, 0x1004B2, 0x2006A8, 0x4004B2, 0x800B87
 813         };
 814         static_assert(lengthof(feedbacks) == 2 * MAX_MAP_SIZE_BITS - 2 * MIN_MAP_SIZE_BITS + 1);
 815         const uint32 feedback = feedbacks[MapLogX() + MapLogY() - 2 * MIN_MAP_SIZE_BITS];
 816
 817         /* We update every tile every 256 ticks, so divide the map size by 2^8 = 256 */
 818         uint count = 1 << (MapLogX() + MapLogY() - 8);
 819
 820         TileIndex tile = _cur_tileloop_tile;
 821         /* The LFSR cannot have a zeroed state. */
 822         assert(tile != 0);
 823
 824         /* Manually update tile 0 every 256 ticks - the LFSR never iterates over it itself.  */
 825         if (_tick_counter % 256 == 0) {
 826                 _tile_type_procs[GetTileType(0)]->tile_loop_proc(0);
 827                 count--;
 828         }
 829
 830         while (count--) {
 831                 _tile_type_procs[GetTileType(tile)]->tile_loop_proc(tile);
 832
 833                 /* Get the next tile in sequence using a Galois LFSR. */
 834                 tile = (tile >> 1) ^ (-(int32)(tile & 1) & feedback);
 835         }
 836
 837         _cur_tileloop_tile = tile;
 838 }
 839
 840 void InitializeLandscape()
 841 {
 842         for (uint y = _settings_game.construction.freeform_edges ? 1 : 0; y < MapMaxY(); y++) {
 843                 for (uint x = _settings_game.construction.freeform_edges ? 1 : 0; x < MapMaxX(); x++) {
 844                         MakeClear(TileXY(x, y), CLEAR_GRASS, 3);
 845                         SetTileHeight(TileXY(x, y), 0);
 846                         SetTropicZone(TileXY(x, y), TROPICZONE_NORMAL);
 847                         ClearBridgeMiddle(TileXY(x, y));
 848                 }
 849         }
 850
 851         for (uint x = 0; x < MapSizeX(); x++) MakeVoid(TileXY(x, MapMaxY()));
 852         for (uint y = 0; y < MapSizeY(); y++) MakeVoid(TileXY(MapMaxX(), y));
 853 }
 854
 855 static const byte _genterrain_tbl_1[5] = { 10, 22, 33, 37, 4  };
 856 static const byte _genterrain_tbl_2[5] = {  0,  0,  0,  0, 33 };
 857
 858 static void GenerateTerrain(int type, uint flag)
 859 {
 860         uint32 r = Random();
 861
 862         const Sprite *templ = GetSprite((((r >> 24) * _genterrain_tbl_1[type]) >> 8) + _genterrain_tbl_2[type] + 4845, ST_MAPGEN);
 863         if (templ == nullptr) usererror("Map generator sprites could not be loaded");
 864
 865         uint x = r & MapMaxX();
 866         uint y = (r >> MapLogX()) & MapMaxY();
 867
 868         uint edge_distance = 1 + (_settings_game.construction.freeform_edges ? 1 : 0);
 869         if (x <= edge_distance || y <= edge_distance) return;
 870
 871         DiagDirection direction = (DiagDirection)GB(r, 22, 2);
 872         uint w = templ->width;
 873         uint h = templ->height;
 874
 875         if (DiagDirToAxis(direction) == AXIS_Y) Swap(w, h);
 876
 877         const byte *p = templ->data;
 878
 879         if ((flag & 4) != 0) {
 880                 uint xw = x * MapSizeY();
 881                 uint yw = y * MapSizeX();
 882                 uint bias = (MapSizeX() + MapSizeY()) * 16;
 883
 884                 switch (flag & 3) {
 885                         default: NOT_REACHED();
 886                         case 0:
 887                                 if (xw + yw > MapSize() - bias) return;
 888                                 break;
 889
 890                         case 1:
 891                                 if (yw < xw + bias) return;
 892                                 break;
 893
 894                         case 2:
 895                                 if (xw + yw < MapSize() + bias) return;
 896                                 break;
 897
 898                         case 3:
 899                                 if (xw < yw + bias) return;
 900                                 break;
 901                 }
 902         }
 903
 904         if (x + w >= MapMaxX()) return;
 905         if (y + h >= MapMaxY()) return;
 906
 907         TileIndex tile = TileXY(x, y);
 908
 909         switch (direction) {
 910                 default: NOT_REACHED();
 911                 case DIAGDIR_NE:
 912                         do {
 913                                 TileIndex tile_cur = tile;
 914
 915                                 for (uint w_cur = w; w_cur != 0; --w_cur) {
 916                                         if (GB(*p, 0, 4) >= TileHeight(tile_cur)) SetTileHeight(tile_cur, GB(*p, 0, 4));
 917                                         p++;
 918                                         tile_cur++;
 919                                 }
 920                                 tile += TileDiffXY(0, 1);
 921                         } while (--h != 0);
 922                         break;
 923
 924                 case DIAGDIR_SE:
 925                         do {
 926                                 TileIndex tile_cur = tile;
 927
 928                                 for (uint h_cur = h; h_cur != 0; --h_cur) {
 929                                         if (GB(*p, 0, 4) >= TileHeight(tile_cur)) SetTileHeight(tile_cur, GB(*p, 0, 4));
 930                                         p++;
 931                                         tile_cur += TileDiffXY(0, 1);
 932                                 }
 933                                 tile += TileDiffXY(1, 0);
 934                         } while (--w != 0);
 935                         break;
 936
 937                 case DIAGDIR_SW:
 938                         tile += TileDiffXY(w - 1, 0);
 939                         do {
 940                                 TileIndex tile_cur = tile;
 941
 942                                 for (uint w_cur = w; w_cur != 0; --w_cur) {
 943                                         if (GB(*p, 0, 4) >= TileHeight(tile_cur)) SetTileHeight(tile_cur, GB(*p, 0, 4));
 944                                         p++;
 945                                         tile_cur--;
 946                                 }
 947                                 tile += TileDiffXY(0, 1);
 948                         } while (--h != 0);
 949                         break;
 950
 951                 case DIAGDIR_NW:
 952                         tile += TileDiffXY(0, h - 1);
 953                         do {
 954                                 TileIndex tile_cur = tile;
 955
 956                                 for (uint h_cur = h; h_cur != 0; --h_cur) {
 957                                         if (GB(*p, 0, 4) >= TileHeight(tile_cur)) SetTileHeight(tile_cur, GB(*p, 0, 4));
 958                                         p++;
 959                                         tile_cur -= TileDiffXY(0, 1);
 960                                 }
 961                                 tile += TileDiffXY(1, 0);
 962                         } while (--w != 0);
 963                         break;
 964         }
 965 }
 966
 967
 968 #include "table/genland.h"
 969
 970 static void CreateDesertOrRainForest(uint desert_tropic_line)
 971 {
 972         TileIndex update_freq = MapSize() / 4;
 973         const TileIndexDiffC *data;
 974
 975         for (TileIndex tile = 0; tile != MapSize(); ++tile) {
 976                 if ((tile % update_freq) == 0) IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
 977
 978                 if (!IsValidTile(tile)) continue;
 979
 980                 for (data = _make_desert_or_rainforest_data;
 981                                 data != endof(_make_desert_or_rainforest_data); ++data) {
 982                         TileIndex t = AddTileIndexDiffCWrap(tile, *data);
 983                         if (t != INVALID_TILE && (TileHeight(t) >= desert_tropic_line || IsTileType(t, MP_WATER))) break;
 984                 }
 985                 if (data == endof(_make_desert_or_rainforest_data)) {
 986                         SetTropicZone(tile, TROPICZONE_DESERT);
 987                 }
 988         }
 989
 990         for (uint i = 0; i != 256; i++) {
 991                 if ((i % 64) == 0) IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
 992
 993                 RunTileLoop();
 994         }
 995
 996         for (TileIndex tile = 0; tile != MapSize(); ++tile) {
 997                 if ((tile % update_freq) == 0) IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
 998
 999                 if (!IsValidTile(tile)) continue;
1000
1001                 for (data = _make_desert_or_rainforest_data;
1002                                 data != endof(_make_desert_or_rainforest_data); ++data) {
1003                         TileIndex t = AddTileIndexDiffCWrap(tile, *data);
1004                         if (t != INVALID_TILE && IsTileType(t, MP_CLEAR) && IsClearGround(t, CLEAR_DESERT)) break;
1005                 }
1006                 if (data == endof(_make_desert_or_rainforest_data)) {
1007                         SetTropicZone(tile, TROPICZONE_RAINFOREST);
1008                 }
1009         }
1010 }
1011
1012 /**
1013  * Find the spring of a river.
1014  * @param tile The tile to consider for being the spring.
1015  * @param user_data Ignored data.
1016  * @return True iff it is suitable as a spring.
1017  */
1018 static bool FindSpring(TileIndex tile, void *user_data)
1019 {
1020         int referenceHeight;
1021         if (!IsTileFlat(tile, &referenceHeight) || IsWaterTile(tile)) return false;
1022
1023         /* In the tropics rivers start in the rainforest. */
1024         if (_settings_game.game_creation.landscape == LT_TROPIC && GetTropicZone(tile) != TROPICZONE_RAINFOREST) return false;
1025
1026         /* Are there enough higher tiles to warrant a 'spring'? */
1027         uint num = 0;
1028         for (int dx = -1; dx <= 1; dx++) {
1029                 for (int dy = -1; dy <= 1; dy++) {
1030                         TileIndex t = TileAddWrap(tile, dx, dy);
1031                         if (t != INVALID_TILE && GetTileMaxZ(t) > referenceHeight) num++;
1032                 }
1033         }
1034
1035         if (num < 4) return false;
1036
1037         /* Are we near the top of a hill? */
1038         for (int dx = -16; dx <= 16; dx++) {
1039                 for (int dy = -16; dy <= 16; dy++) {
1040                         TileIndex t = TileAddWrap(tile, dx, dy);
1041                         if (t != INVALID_TILE && GetTileMaxZ(t) > referenceHeight + 2) return false;
1042                 }
1043         }
1044
1045         return true;
1046 }
1047
1048 /**
1049  * Make a connected lake; fill all tiles in the circular tile search that are connected.
1050  * @param tile The tile to consider for lake making.
1051  * @param user_data The height of the lake.
1052  * @return Always false, so it continues searching.
1053  */
1054 static bool MakeLake(TileIndex tile, void *user_data)
1055 {
1056         uint height = *(uint*)user_data;
1057         if (!IsValidTile(tile) || TileHeight(tile) != height || !IsTileFlat(tile)) return false;
1058         if (_settings_game.game_creation.landscape == LT_TROPIC && GetTropicZone(tile) == TROPICZONE_DESERT) return false;
1059
1060         for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {
1061                 TileIndex t2 = tile + TileOffsByDiagDir(d);
1062                 if (IsWaterTile(t2)) {
1063                         MakeRiver(tile, Random());
1064                         MarkTileDirtyByTile(tile);
1065                         /* Remove desert directly around the river tile. */
1066                         TileIndex t = tile;
1067                         CircularTileSearch(&t, RIVER_OFFSET_DESERT_DISTANCE, RiverModifyDesertZone, nullptr);
1068                         return false;
1069                 }
1070         }
1071
1072         return false;
1073 }
1074
1075 /**
1076  * Widen a river by expanding into adjacent tiles via circular tile search.
1077  * @param tile The tile to try expanding the river into.
1078  * @param data The tile to try surrounding the river around.
1079  * @return Always false, so it continues searching.
1080  */
1081 static bool RiverMakeWider(TileIndex tile, void *data)
1082 {
1083         /* Don't expand into void tiles. */
1084         if (!IsValidTile(tile)) return false;
1085
1086         /* If the tile is already sea or river, don't expand. */
1087         if (IsWaterTile(tile)) return false;
1088
1089         /* If the tile is at height 0 after terraforming but the ocean hasn't flooded yet, don't build river. */
1090         if (GetTileMaxZ(tile) == 0) return false;
1091
1092         TileIndex origin_tile = *(TileIndex *)data;;
1093         Slope cur_slope = GetTileSlope(tile);
1094         Slope desired_slope = GetTileSlope(origin_tile); // Initialize matching the origin tile as a shortcut if no terraforming is needed.
1095
1096         /* Never flow uphill. */
1097         if (GetTileMaxZ(tile) > GetTileMaxZ(origin_tile)) return false;
1098
1099         /* If the new tile can't hold a river tile, try terraforming. */
1100         if (!IsTileFlat(tile) && !IsInclinedSlope(cur_slope)) {
1101                 /* Don't try to terraform steep slopes. */
1102                 if (IsSteepSlope(cur_slope)) return false;
1103
1104                 bool flat_river_found = false;
1105                 bool sloped_river_found = false;
1106
1107                 /* There are two common possibilities:
1108                  * 1. River flat, adjacent tile has one corner lowered.
1109                  * 2. River descending, adjacent tile has either one or three corners raised.
1110                  */
1111
1112                 /* First, determine the desired slope based on adjacent river tiles. This doesn't necessarily match the origin tile for the CircularTileSearch. */
1113                 for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {
1114                         TileIndex other_tile = TileAddByDiagDir(tile, d);
1115                         Slope other_slope = GetTileSlope(other_tile);
1116
1117                         /* Only consider river tiles. */
1118                         if (IsWaterTile(other_tile) && IsRiver(other_tile)) {
1119                                 /* If the adjacent river tile flows downhill, we need to check where we are relative to the slope. */
1120                                 if (IsInclinedSlope(other_slope) && GetTileMaxZ(tile) == GetTileMaxZ(other_tile)) {
1121                                         /* Check for a parallel slope. If we don't find one, we're above or below the slope instead. */
1122                                         if (GetInclinedSlopeDirection(other_slope) == ChangeDiagDir(d, DIAGDIRDIFF_90RIGHT) ||
1123                                                         GetInclinedSlopeDirection(other_slope) == ChangeDiagDir(d, DIAGDIRDIFF_90LEFT)) {
1124                                                 desired_slope = other_slope;
1125                                                 sloped_river_found = true;
1126                                                 break;
1127                                         }
1128                                 }
1129                                 /* If we find an adjacent river tile, remember it. We'll terraform to match it later if we don't find a slope. */
1130                                 if (IsTileFlat(tile)) flat_river_found = true;
1131                         }
1132                 }
1133                 /* We didn't find either an inclined or flat river, so we're climbing the wrong slope. Bail out. */
1134                 if (!sloped_river_found && !flat_river_found) return false;
1135
1136                 /* We didn't find an inclined river, but there is a flat river. */
1137                 if (!sloped_river_found && flat_river_found) desired_slope = SLOPE_FLAT;
1138
1139                 /* Now that we know the desired slope, it's time to terraform! */
1140
1141                 /* If the river is flat and the adjacent tile has one corner lowered, we want to raise it. */
1142                 if (desired_slope == SLOPE_FLAT && IsSlopeWithThreeCornersRaised(cur_slope)) {
1143                         /* Make sure we're not affecting an existing river slope tile. */
1144                         for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {
1145                                 TileIndex other_tile = TileAddByDiagDir(tile, d);
1146                                 if (IsInclinedSlope(GetTileSlope(other_tile)) && IsWaterTile(other_tile)) return false;
1147                         }
1148                         Command<CMD_TERRAFORM_LAND>::Do(DC_EXEC | DC_AUTO, tile, ComplementSlope(cur_slope), true);
1149
1150                 /* If the river is descending and the adjacent tile has either one or three corners raised, we want to make it match the slope. */
1151                 } else if (IsInclinedSlope(desired_slope)) {
1152                         /* Don't break existing flat river tiles by terraforming under them. */
1153                         DiagDirection river_direction = ReverseDiagDir(GetInclinedSlopeDirection(desired_slope));
1154
1155                         for (DiagDirDiff d = DIAGDIRDIFF_BEGIN; d < DIAGDIRDIFF_END; d++) {
1156                                 /* We don't care about downstream or upstream tiles, just the riverbanks. */
1157                                 if (d == DIAGDIRDIFF_SAME || d == DIAGDIRDIFF_REVERSE) continue;
1158
1159                                 TileIndex other_tile = (TileAddByDiagDir(tile, ChangeDiagDir(river_direction, d)));
1160                                 if (IsWaterTile(other_tile) && IsRiver(other_tile) && IsTileFlat(other_tile)) return false;
1161                         }
1162
1163                         /* Get the corners which are different between the current and desired slope. */
1164                         Slope to_change = cur_slope ^ desired_slope;
1165
1166                         /* Lower unwanted corners first. If only one corner is raised, no corners need lowering. */
1167                         if (!IsSlopeWithOneCornerRaised(cur_slope)) {
1168                                 to_change = to_change & ComplementSlope(desired_slope);
1169                                 Command<CMD_TERRAFORM_LAND>::Do(DC_EXEC | DC_AUTO, tile, to_change, false);
1170                         }
1171
1172                         /* Now check the match and raise any corners needed. */
1173                         cur_slope = GetTileSlope(tile);
1174                         if (cur_slope != desired_slope && IsSlopeWithOneCornerRaised(cur_slope)) {
1175                                 to_change = cur_slope ^ desired_slope;
1176                                 Command<CMD_TERRAFORM_LAND>::Do(DC_EXEC | DC_AUTO, tile, to_change, true);
1177                         }
1178                 }
1179         }
1180         /* Update cur_slope after possibly terraforming. */
1181         cur_slope = GetTileSlope(tile);
1182
1183         /* If the tile slope matches the desired slope, add a river tile. */
1184         if (cur_slope == desired_slope) {
1185                 MakeRiver(tile, Random());
1186
1187                 /* Remove desert directly around the river tile. */
1188                 TileIndex cur_tile = tile;
1189                 MarkTileDirtyByTile(cur_tile);
1190                 CircularTileSearch(&cur_tile, RIVER_OFFSET_DESERT_DISTANCE, RiverModifyDesertZone, nullptr);
1191         }
1192
1193         /* Always return false to keep searching. */
1194         return false;
1195 }
1196
1197 /**
1198  * Check whether a river at begin could (logically) flow down to end.
1199  * @param begin The origin of the flow.
1200  * @param end The destination of the flow.
1201  * @return True iff the water can be flowing down.
1202  */
1203 static bool FlowsDown(TileIndex begin, TileIndex end)
1204 {
1205         assert(DistanceManhattan(begin, end) == 1);
1206
1207         int heightBegin;
1208         int heightEnd;
1209         Slope slopeBegin = GetTileSlope(begin, &heightBegin);
1210         Slope slopeEnd   = GetTileSlope(end, &heightEnd);
1211
1212         return heightEnd <= heightBegin &&
1213                         /* Slope either is inclined or flat; rivers don't support other slopes. */
1214                         (slopeEnd == SLOPE_FLAT || IsInclinedSlope(slopeEnd)) &&
1215                         /* Slope continues, then it must be lower... or either end must be flat. */
1216                         ((slopeEnd == slopeBegin && heightEnd < heightBegin) || slopeEnd == SLOPE_FLAT || slopeBegin == SLOPE_FLAT);
1217 }
1218
1219 /** Parameters for river generation to pass as AyStar user data. */
1220 struct River_UserData {
1221         TileIndex spring; ///< The current spring during river generation.
1222         bool main_river;  ///< Whether the current river is a big river that others flow into.
1223 };
1224
1225 /* AyStar callback for checking whether we reached our destination. */
1226 static int32 River_EndNodeCheck(const AyStar *aystar, const OpenListNode *current)
1227 {
1228         return current->path.node.tile == *(TileIndex*)aystar->user_target ? AYSTAR_FOUND_END_NODE : AYSTAR_DONE;
1229 }
1230
1231 /* AyStar callback for getting the cost of the current node. */
1232 static int32 River_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
1233 {
1234         return 1 + RandomRange(_settings_game.game_creation.river_route_random);
1235 }
1236
1237 /* AyStar callback for getting the estimated cost to the destination. */
1238 static int32 River_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
1239 {
1240         return DistanceManhattan(*(TileIndex*)aystar->user_target, current->tile);
1241 }
1242
1243 /* AyStar callback for getting the neighbouring nodes of the given node. */
1244 static void River_GetNeighbours(AyStar *aystar, OpenListNode *current)
1245 {
1246         TileIndex tile = current->path.node.tile;
1247
1248         aystar->num_neighbours = 0;
1249         for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {
1250                 TileIndex t2 = tile + TileOffsByDiagDir(d);
1251                 if (IsValidTile(t2) && FlowsDown(tile, t2)) {
1252                         aystar->neighbours[aystar->num_neighbours].tile = t2;
1253                         aystar->neighbours[aystar->num_neighbours].direction = INVALID_TRACKDIR;
1254                         aystar->num_neighbours++;
1255                 }
1256         }
1257 }
1258
1259 /* AyStar callback when an route has been found. */
1260 static void River_FoundEndNode(AyStar *aystar, OpenListNode *current)
1261 {
1262         River_UserData *data = (River_UserData *)aystar->user_data;
1263
1264         /* First, build the river without worrying about its width. */
1265         uint cur_pos = 0;
1266         for (PathNode *path = &current->path; path != nullptr; path = path->parent, cur_pos++) {
1267                 TileIndex tile = path->node.tile;
1268                 if (!IsWaterTile(tile)) {
1269                         MakeRiver(tile, Random());
1270                         MarkTileDirtyByTile(tile);
1271                         /* Remove desert directly around the river tile. */
1272                         CircularTileSearch(&tile, RIVER_OFFSET_DESERT_DISTANCE, RiverModifyDesertZone, nullptr);
1273                 }
1274         }
1275
1276         /* If the river is a main river, go back along the path to widen it.
1277          * Don't make wide rivers if we're using the original landscape generator.
1278          */
1279         if (_settings_game.game_creation.land_generator != LG_ORIGINAL && data->main_river) {
1280                 const uint long_river_length = _settings_game.game_creation.min_river_length * 4;
1281                 uint current_river_length;
1282                 uint radius;
1283
1284                 cur_pos = 0;
1285                 for (PathNode *path = &current->path; path != nullptr; path = path->parent, cur_pos++) {
1286                         TileIndex tile = path->node.tile;
1287
1288                         /* Check if we should widen river depending on how far we are away from the source. */
1289                         current_river_length = DistanceManhattan(data->spring, tile);
1290                         radius = std::min(3u, (current_river_length / (long_river_length / 3u)) + 1u);
1291
1292                         if (radius > 1) CircularTileSearch(&tile, radius + RandomRange(1), RiverMakeWider, (void *)&path->node.tile);
1293                 }
1294         }
1295 }
1296
1297 static const uint RIVER_HASH_SIZE = 8; ///< The number of bits the hash for river finding should have.
1298
1299 /**
1300  * Simple hash function for river tiles to be used by AyStar.
1301  * @param tile The tile to hash.
1302  * @param dir The unused direction.
1303  * @return The hash for the tile.
1304  */
1305 static uint River_Hash(uint tile, uint dir)
1306 {
1307         return GB(TileHash(TileX(tile), TileY(tile)), 0, RIVER_HASH_SIZE);
1308 }
1309
1310 /**
1311  * Actually build the river between the begin and end tiles using AyStar.
1312  * @param begin The begin of the river.
1313  * @param end The end of the river.
1314  * @param spring The springing point of the river.
1315  * @param main_river Whether the current river is a big river that others flow into.
1316  */
1317 static void BuildRiver(TileIndex begin, TileIndex end, TileIndex spring, bool main_river)
1318 {
1319         River_UserData user_data = { spring, main_river };
1320
1321         AyStar finder = {};
1322         finder.CalculateG = River_CalculateG;
1323         finder.CalculateH = River_CalculateH;
1324         finder.GetNeighbours = River_GetNeighbours;
1325         finder.EndNodeCheck = River_EndNodeCheck;
1326         finder.FoundEndNode = River_FoundEndNode;
1327         finder.user_target = &end;
1328         finder.user_data = &user_data;
1329
1330         finder.Init(River_Hash, 1 << RIVER_HASH_SIZE);
1331
1332         AyStarNode start;
1333         start.tile = begin;
1334         start.direction = INVALID_TRACKDIR;
1335         finder.AddStartNode(&start, 0);
1336         finder.Main();
1337         finder.Free();
1338 }
1339
1340 /**
1341  * Try to flow the river down from a given begin.
1342  * @param spring The springing point of the river.
1343  * @param begin  The begin point we are looking from; somewhere down hill from the spring.
1344  * @param min_river_length The minimum length for the river.
1345  * @return First element: True iff a river could/has been built, otherwise false; second element: River ends at sea.
1346  */
1347 static std::tuple<bool, bool> FlowRiver(TileIndex spring, TileIndex begin, uint min_river_length)
1348 {
1349 #       define SET_MARK(x) marks.insert(x)
1350 #       define IS_MARKED(x) (marks.find(x) != marks.end())
1351
1352         uint height = TileHeight(begin);
1353
1354         if (IsWaterTile(begin)) {
1355                 return { DistanceManhattan(spring, begin) > min_river_length, GetTileZ(begin) == 0 };
1356         }
1357
1358         std::set<TileIndex> marks;
1359         SET_MARK(begin);
1360
1361         /* Breadth first search for the closest tile we can flow down to. */
1362         std::list<TileIndex> queue;
1363         queue.push_back(begin);
1364
1365         bool found = false;
1366         uint count = 0; // Number of tiles considered; to be used for lake location guessing.
1367         TileIndex end;
1368         do {
1369                 end = queue.front();
1370                 queue.pop_front();
1371
1372                 uint height2 = TileHeight(end);
1373                 if (IsTileFlat(end) && (height2 < height || (height2 == height && IsWaterTile(end)))) {
1374                         found = true;
1375                         break;
1376                 }
1377
1378                 for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) {
1379                         TileIndex t2 = end + TileOffsByDiagDir(d);
1380                         if (IsValidTile(t2) && !IS_MARKED(t2) && FlowsDown(end, t2)) {
1381                                 SET_MARK(t2);
1382                                 count++;
1383                                 queue.push_back(t2);
1384                         }
1385                 }
1386         } while (!queue.empty());
1387
1388         bool main_river = false;
1389         if (found) {
1390                 /* Flow further down hill. */
1391                 std::tie(found, main_river) = FlowRiver(spring, end, min_river_length);
1392         } else if (count > 32) {
1393                 /* Maybe we can make a lake. Find the Nth of the considered tiles. */
1394                 TileIndex lakeCenter = 0;
1395                 int i = RandomRange(count - 1) + 1;
1396                 std::set<TileIndex>::const_iterator cit = marks.begin();
1397                 while (--i) cit++;
1398                 lakeCenter = *cit;
1399
1400                 if (IsValidTile(lakeCenter) &&
1401                                 /* A river, or lake, can only be built on flat slopes. */
1402                                 IsTileFlat(lakeCenter) &&
1403                                 /* We want the lake to be built at the height of the river. */
1404                                 TileHeight(begin) == TileHeight(lakeCenter) &&
1405                                 /* We don't want the lake at the entry of the valley. */
1406                                 lakeCenter != begin &&
1407                                 /* We don't want lakes in the desert. */
1408                                 (_settings_game.game_creation.landscape != LT_TROPIC || GetTropicZone(lakeCenter) != TROPICZONE_DESERT) &&
1409                                 /* We only want a lake if the river is long enough. */
1410                                 DistanceManhattan(spring, lakeCenter) > min_river_length) {
1411                         end = lakeCenter;
1412                         MakeRiver(lakeCenter, Random());
1413                         MarkTileDirtyByTile(lakeCenter);
1414                         /* Remove desert directly around the river tile. */
1415                         CircularTileSearch(&lakeCenter, RIVER_OFFSET_DESERT_DISTANCE, RiverModifyDesertZone, nullptr);
1416                         lakeCenter = end;
1417                         uint range = RandomRange(8) + 3;
1418                         CircularTileSearch(&lakeCenter, range, MakeLake, &height);
1419                         /* Call the search a second time so artefacts from going circular in one direction get (mostly) hidden. */
1420                         lakeCenter = end;
1421                         CircularTileSearch(&lakeCenter, range, MakeLake, &height);
1422                         found = true;
1423                 }
1424         }
1425
1426         marks.clear();
1427         if (found) BuildRiver(begin, end, spring, main_river);
1428         return { found, main_river };
1429 }
1430
1431 /**
1432  * Actually (try to) create some rivers.
1433  */
1434 static void CreateRivers()
1435 {
1436         int amount = _settings_game.game_creation.amount_of_rivers;
1437         if (amount == 0) return;
1438
1439         uint wells = ScaleByMapSize(4 << _settings_game.game_creation.amount_of_rivers);
1440         const uint num_short_rivers = wells - std::max(1u, wells / 10);
1441         SetGeneratingWorldProgress(GWP_RIVER, wells + 256 / 64); // Include the tile loop calls below.
1442
1443         /* Try to create long rivers. */
1444         for (; wells > num_short_rivers; wells--) {
1445                 IncreaseGeneratingWorldProgress(GWP_RIVER);
1446                 for (int tries = 0; tries < 512; tries++) {
1447                         TileIndex t = RandomTile();
1448                         if (!CircularTileSearch(&t, 8, FindSpring, nullptr)) continue;
1449                         if (std::get<0>(FlowRiver(t, t, _settings_game.game_creation.min_river_length * 4))) break;
1450                 }
1451         }
1452
1453         /* Try to create short rivers. */
1454         for (; wells != 0; wells--) {
1455                 IncreaseGeneratingWorldProgress(GWP_RIVER);
1456                 for (int tries = 0; tries < 128; tries++) {
1457                         TileIndex t = RandomTile();
1458                         if (!CircularTileSearch(&t, 8, FindSpring, nullptr)) continue;
1459                         if (std::get<0>(FlowRiver(t, t, _settings_game.game_creation.min_river_length))) break;
1460                 }
1461         }
1462
1463         /* Run tile loop to update the ground density. */
1464         for (uint i = 0; i != 256; i++) {
1465                 if (i % 64 == 0) IncreaseGeneratingWorldProgress(GWP_RIVER);
1466                 RunTileLoop();
1467         }
1468 }
1469
1470 /**
1471  * Calculate what height would be needed to cover N% of the landmass.
1472  *
1473  * The function allows both snow and desert/tropic line to be calculated. It
1474  * tries to find the closests height which covers N% of the landmass; it can
1475  * be below or above it.
1476  *
1477  * Tropic has a mechanism where water and tropic tiles in mountains grow
1478  * inside the desert. To better approximate the requested coverage, this is
1479  * taken into account via an edge histogram, which tells how many neighbouring
1480  * tiles are lower than the tiles of that height. The multiplier indicates how
1481  * severe this has to be taken into account.
1482  *
1483  * @param coverage A value between 0 and 100 indicating a percentage of landmass that should be covered.
1484  * @param edge_multiplier How much effect neighbouring tiles that are of a lower height level have on the score.
1485  * @return The estimated best height to use to cover N% of the landmass.
1486  */
1487 static uint CalculateCoverageLine(uint coverage, uint edge_multiplier)
1488 {
1489         const DiagDirection neighbour_dir[] = {
1490                 DIAGDIR_NE,
1491                 DIAGDIR_SE,
1492                 DIAGDIR_SW,
1493                 DIAGDIR_NW,
1494         };
1495
1496         /* Histogram of how many tiles per height level exist. */
1497         std::array<int, MAX_TILE_HEIGHT + 1> histogram = {};
1498         /* Histogram of how many neighbour tiles are lower than the tiles of the height level. */
1499         std::array<int, MAX_TILE_HEIGHT + 1> edge_histogram = {};
1500
1501         /* Build a histogram of the map height. */
1502         for (TileIndex tile = 0; tile < MapSize(); tile++) {
1503                 uint h = TileHeight(tile);
1504                 histogram[h]++;
1505
1506                 if (edge_multiplier != 0) {
1507                         /* Check if any of our neighbours is below us. */
1508                         for (auto dir : neighbour_dir) {
1509                                 TileIndex neighbour_tile = AddTileIndexDiffCWrap(tile, TileIndexDiffCByDiagDir(dir));
1510                                 if (IsValidTile(neighbour_tile) && TileHeight(neighbour_tile) < h) {
1511                                         edge_histogram[h]++;
1512                                 }
1513                         }
1514                 }
1515         }
1516
1517         /* The amount of land we have is the map size minus the first (sea) layer. */
1518         uint land_tiles = MapSizeX() * MapSizeY() - histogram[0];
1519         int best_score = land_tiles;
1520
1521         /* Our goal is the coverage amount of the land-mass. */
1522         int goal_tiles = land_tiles * coverage / 100;
1523
1524         /* We scan from top to bottom. */
1525         uint h = MAX_TILE_HEIGHT;
1526         uint best_h = h;
1527
1528         int current_tiles = 0;
1529         for (; h > 0; h--) {
1530                 current_tiles += histogram[h];
1531                 int current_score = goal_tiles - current_tiles;
1532
1533                 /* Tropic grows from water and mountains into the desert. This is a
1534                  * great visual, but it also means we* need to take into account how
1535                  * much less desert tiles are being created if we are on this
1536                  * height-level. We estimate this based on how many neighbouring
1537                  * tiles are below us for a given length, assuming that is where
1538                  * tropic is growing from.
1539                  */
1540                 if (edge_multiplier != 0 && h > 1) {
1541                         /* From water tropic tiles grow for a few tiles land inward. */
1542                         current_score -= edge_histogram[1] * edge_multiplier;
1543                         /* Tropic tiles grow into the desert for a few tiles. */
1544                         current_score -= edge_histogram[h] * edge_multiplier;
1545                 }
1546
1547                 if (std::abs(current_score) < std::abs(best_score)) {
1548                         best_score = current_score;
1549                         best_h = h;
1550                 }
1551
1552                 /* Always scan all height-levels, as h == 1 might give a better
1553                  * score than any before. This is true for example with 0% desert
1554                  * coverage. */
1555         }
1556
1557         return best_h;
1558 }
1559
1560 /**
1561  * Calculate the line from which snow begins.
1562  */
1563 static void CalculateSnowLine()
1564 {
1565         /* We do not have snow sprites on coastal tiles, so never allow "1" as height. */
1566         _settings_game.game_creation.snow_line_height = std::max(CalculateCoverageLine(_settings_game.game_creation.snow_coverage, 0), 2u);
1567 }
1568
1569 /**
1570  * Calculate the line (in height) between desert and tropic.
1571  * @return The height of the line between desert and tropic.
1572  */
1573 static uint8 CalculateDesertLine()
1574 {
1575         /* CalculateCoverageLine() runs from top to bottom, so we need to invert the coverage. */
1576         return CalculateCoverageLine(100 - _settings_game.game_creation.desert_coverage, 4);
1577 }
1578
1579 void GenerateLandscape(byte mode)
1580 {
1581         /** Number of steps of landscape generation */
1582         enum GenLandscapeSteps {
1583                 GLS_HEIGHTMAP    =  3, ///< Loading a heightmap
1584                 GLS_TERRAGENESIS =  5, ///< Terragenesis generator
1585                 GLS_ORIGINAL     =  2, ///< Original generator
1586                 GLS_TROPIC       = 12, ///< Extra steps needed for tropic landscape
1587                 GLS_OTHER        =  0, ///< Extra steps for other landscapes
1588         };
1589         uint steps = (_settings_game.game_creation.landscape == LT_TROPIC) ? GLS_TROPIC : GLS_OTHER;
1590
1591         if (mode == GWM_HEIGHTMAP) {
1592                 SetGeneratingWorldProgress(GWP_LANDSCAPE, steps + GLS_HEIGHTMAP);
1593                 LoadHeightmap(_file_to_saveload.detail_ftype, _file_to_saveload.name.c_str());
1594                 IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
1595         } else if (_settings_game.game_creation.land_generator == LG_TERRAGENESIS) {
1596                 SetGeneratingWorldProgress(GWP_LANDSCAPE, steps + GLS_TERRAGENESIS);
1597                 GenerateTerrainPerlin();
1598         } else {
1599                 SetGeneratingWorldProgress(GWP_LANDSCAPE, steps + GLS_ORIGINAL);
1600                 if (_settings_game.construction.freeform_edges) {
1601                         for (uint x = 0; x < MapSizeX(); x++) MakeVoid(TileXY(x, 0));
1602                         for (uint y = 0; y < MapSizeY(); y++) MakeVoid(TileXY(0, y));
1603                 }
1604                 switch (_settings_game.game_creation.landscape) {
1605                         case LT_ARCTIC: {
1606                                 uint32 r = Random();
1607
1608                                 for (uint i = ScaleByMapSize(GB(r, 0, 7) + 950); i != 0; --i) {
1609                                         GenerateTerrain(2, 0);
1610                                 }
1611
1612                                 uint flag = GB(r, 7, 2) | 4;
1613                                 for (uint i = ScaleByMapSize(GB(r, 9, 7) + 450); i != 0; --i) {
1614                                         GenerateTerrain(4, flag);
1615                                 }
1616                                 break;
1617                         }
1618
1619                         case LT_TROPIC: {
1620                                 uint32 r = Random();
1621
1622                                 for (uint i = ScaleByMapSize(GB(r, 0, 7) + 170); i != 0; --i) {
1623                                         GenerateTerrain(0, 0);
1624                                 }
1625
1626                                 uint flag = GB(r, 7, 2) | 4;
1627                                 for (uint i = ScaleByMapSize(GB(r, 9, 8) + 1700); i != 0; --i) {
1628                                         GenerateTerrain(0, flag);
1629                                 }
1630
1631                                 flag ^= 2;
1632
1633                                 for (uint i = ScaleByMapSize(GB(r, 17, 7) + 410); i != 0; --i) {
1634                                         GenerateTerrain(3, flag);
1635                                 }
1636                                 break;
1637                         }
1638
1639                         default: {
1640                                 uint32 r = Random();
1641
1642                                 assert(_settings_game.difficulty.quantity_sea_lakes != CUSTOM_SEA_LEVEL_NUMBER_DIFFICULTY);
1643                                 uint i = ScaleByMapSize(GB(r, 0, 7) + (3 - _settings_game.difficulty.quantity_sea_lakes) * 256 + 100);
1644                                 for (; i != 0; --i) {
1645                                         /* Make sure we do not overflow. */
1646                                         GenerateTerrain(Clamp(_settings_game.difficulty.terrain_type, 0, 3), 0);
1647                                 }
1648                                 break;
1649                         }
1650                 }
1651         }
1652
1653         /* Do not call IncreaseGeneratingWorldProgress() before FixSlopes(),
1654          * it allows screen redraw. Drawing of broken slopes crashes the game */
1655         FixSlopes();
1656         MarkWholeScreenDirty();
1657         IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
1658
1659         ConvertGroundTilesIntoWaterTiles();
1660         MarkWholeScreenDirty();
1661         IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
1662
1663         switch (_settings_game.game_creation.landscape) {
1664                 case LT_ARCTIC:
1665                         CalculateSnowLine();
1666                         break;
1667
1668                 case LT_TROPIC: {
1669                         uint desert_tropic_line = CalculateDesertLine();
1670                         CreateDesertOrRainForest(desert_tropic_line);
1671                         break;
1672                 }
1673
1674                 default:
1675                         break;
1676         }
1677
1678         CreateRivers();
1679 }
1680
1681 void OnTick_Town();
1682 void OnTick_Trees();
1683 void OnTick_Station();
1684 void OnTick_Industry();
1685
1686 void OnTick_Companies();
1687 void OnTick_LinkGraph();
1688
1689 void CallLandscapeTick()
1690 {
1691         {
1692                 PerformanceAccumulator framerate(PFE_GL_LANDSCAPE);
1693
1694                 OnTick_Town();
1695                 OnTick_Trees();
1696                 OnTick_Station();
1697                 OnTick_Industry();
1698         }
1699
1700         OnTick_Companies();
1701         OnTick_LinkGraph();
1702 }