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