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