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