src/tree_cmd.cpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   6  */
   7
   8 /** @file tree_cmd.cpp Handling of tree tiles. */
   9
  10 #include "stdafx.h"
  11 #include "clear_map.h"
  12 #include "landscape.h"
  13 #include "tree_map.h"
  14 #include "viewport_func.h"
  15 #include "command_func.h"
  16 #include "town.h"
  17 #include "genworld.h"
  18 #include "clear_func.h"
  19 #include "company_func.h"
  20 #include "sound_func.h"
  21 #include "water.h"
  22 #include "company_base.h"
  23 #include "core/random_func.hpp"
  24 #include "newgrf_generic.h"
  25 #include "timer/timer_game_tick.h"
  26 #include "tree_cmd.h"
  27 #include "landscape_cmd.h"
  28
  29 #include "table/strings.h"
  30 #include "table/tree_land.h"
  31 #include "table/clear_land.h"
  32
  33 #include "safeguards.h"
  34
  35 /**
  36  * List of tree placer algorithm.
  37  *
  38  * This enumeration defines all possible tree placer algorithm in the game.
  39  */
  40 enum TreePlacer {
  41         TP_NONE,     ///< No tree placer algorithm
  42         TP_ORIGINAL, ///< The original algorithm
  43         TP_IMPROVED, ///< A 'improved' algorithm
  44 };
  45
  46 /** Where to place trees while in-game? */
  47 enum ExtraTreePlacement {
  48         ETP_NO_SPREAD,           ///< Grow trees on tiles that have them but don't spread to new ones
  49         ETP_SPREAD_RAINFOREST,   ///< Grow trees on tiles that have them, only spread to new ones in rainforests
  50         ETP_SPREAD_ALL,          ///< Grow trees and spread them without restrictions
  51         ETP_NO_GROWTH_NO_SPREAD, ///< Don't grow trees and don't spread them at all
  52 };
  53
  54 /** Determines when to consider building more trees. */
  55 uint8_t _trees_tick_ctr;
  56
  57 static const uint16_t DEFAULT_TREE_STEPS = 1000;             ///< Default number of attempts for placing trees.
  58 static const uint16_t DEFAULT_RAINFOREST_TREE_STEPS = 15000; ///< Default number of attempts for placing extra trees at rainforest in tropic.
  59 static const uint16_t EDITOR_TREE_DIV = 5;                   ///< Game editor tree generation divisor factor.
  60
  61 /**
  62  * Tests if a tile can be converted to MP_TREES
  63  * This is true for clear ground without farms or rocks.
  64  *
  65  * @param tile the tile of interest
  66  * @param allow_desert Allow planting trees on CLEAR_DESERT?
  67  * @return true if trees can be built.
  68  */
  69 static bool CanPlantTreesOnTile(TileIndex tile, bool allow_desert)
  70 {
  71         switch (GetTileType(tile)) {
  72                 case MP_WATER:
  73                         return !IsBridgeAbove(tile) && IsCoast(tile) && !IsSlopeWithOneCornerRaised(GetTileSlope(tile));
  74
  75                 case MP_CLEAR:
  76                         return !IsBridgeAbove(tile) && !IsClearGround(tile, CLEAR_FIELDS) && GetRawClearGround(tile) != CLEAR_ROCKS &&
  77                                (allow_desert || !IsClearGround(tile, CLEAR_DESERT));
  78
  79                 default: return false;
  80         }
  81 }
  82
  83 /**
  84  * Creates a tree tile
  85  * Ground type and density is preserved.
  86  *
  87  * @pre the tile must be suitable for trees.
  88  *
  89  * @param tile where to plant the trees.
  90  * @param treetype The type of the tree
  91  * @param count the number of trees (minus 1)
  92  * @param growth the growth status
  93  */
  94 static void PlantTreesOnTile(TileIndex tile, TreeType treetype, uint count, TreeGrowthStage growth)
  95 {
  96         assert(treetype != TREE_INVALID);
  97         assert(CanPlantTreesOnTile(tile, true));
  98
  99         TreeGround ground;
 100         uint density = 3;
 101
 102         switch (GetTileType(tile)) {
 103                 case MP_WATER:
 104                         ground = TREE_GROUND_SHORE;
 105                         break;
 106
 107                 case MP_CLEAR:
 108                         switch (GetClearGround(tile)) {
 109                                 case CLEAR_GRASS:  ground = TREE_GROUND_GRASS;       break;
 110                                 case CLEAR_ROUGH:  ground = TREE_GROUND_ROUGH;       break;
 111                                 case CLEAR_SNOW:   ground = GetRawClearGround(tile) == CLEAR_ROUGH ? TREE_GROUND_ROUGH_SNOW : TREE_GROUND_SNOW_DESERT; break;
 112                                 default:           ground = TREE_GROUND_SNOW_DESERT; break;
 113                         }
 114                         if (GetClearGround(tile) != CLEAR_ROUGH) density = GetClearDensity(tile);
 115                         break;
 116
 117                 default: NOT_REACHED();
 118         }
 119
 120         MakeTree(tile, treetype, count, growth, ground, density);
 121 }
 122
 123 /**
 124  * Get a random TreeType for the given tile based on a given seed
 125  *
 126  * This function returns a random TreeType which can be placed on the given tile.
 127  * The seed for randomness must be less or equal 256, use #GB on the value of Random()
 128  * to get such a value.
 129  *
 130  * @param tile The tile to get a random TreeType from
 131  * @param seed The seed for randomness, must be less or equal 256
 132  * @return The random tree type
 133  */
 134 static TreeType GetRandomTreeType(TileIndex tile, uint seed)
 135 {
 136         switch (_settings_game.game_creation.landscape) {
 137                 case LT_TEMPERATE:
 138                         return static_cast<TreeType>(seed * TREE_COUNT_TEMPERATE / 256 + TREE_TEMPERATE);
 139
 140                 case LT_ARCTIC:
 141                         return static_cast<TreeType>(seed * TREE_COUNT_SUB_ARCTIC / 256 + TREE_SUB_ARCTIC);
 142
 143                 case LT_TROPIC:
 144                         switch (GetTropicZone(tile)) {
 145                                 case TROPICZONE_NORMAL:  return static_cast<TreeType>(seed * TREE_COUNT_SUB_TROPICAL / 256 + TREE_SUB_TROPICAL);
 146                                 case TROPICZONE_DESERT:  return static_cast<TreeType>((seed > 12) ? TREE_INVALID : TREE_CACTUS);
 147                                 default:                 return static_cast<TreeType>(seed * TREE_COUNT_RAINFOREST / 256 + TREE_RAINFOREST);
 148                         }
 149
 150                 default:
 151                         return static_cast<TreeType>(seed * TREE_COUNT_TOYLAND / 256 + TREE_TOYLAND);
 152         }
 153 }
 154
 155 /**
 156  * Make a random tree tile of the given tile
 157  *
 158  * Create a new tree-tile for the given tile. The second parameter is used for
 159  * randomness like type and number of trees.
 160  *
 161  * @param tile The tile to make a tree-tile from
 162  * @param r The randomness value from a Random() value
 163  */
 164 static void PlaceTree(TileIndex tile, uint32_t r)
 165 {
 166         TreeType tree = GetRandomTreeType(tile, GB(r, 24, 8));
 167
 168         if (tree != TREE_INVALID) {
 169                 PlantTreesOnTile(tile, tree, GB(r, 22, 2), static_cast<TreeGrowthStage>(std::min<uint8_t>(GB(r, 16, 3), 6)));
 170                 MarkTileDirtyByTile(tile);
 171
 172                 /* Rerandomize ground, if neither snow nor shore */
 173                 TreeGround ground = GetTreeGround(tile);
 174                 if (ground != TREE_GROUND_SNOW_DESERT && ground != TREE_GROUND_ROUGH_SNOW && ground != TREE_GROUND_SHORE) {
 175                         SetTreeGroundDensity(tile, (TreeGround)GB(r, 28, 1), 3);
 176                 }
 177         }
 178 }
 179
 180 /**
 181  * Creates a number of tree groups.
 182  * The number of trees in each group depends on how many trees are actually placed around the given tile.
 183  *
 184  * @param num_groups Number of tree groups to place.
 185  */
 186 static void PlaceTreeGroups(uint num_groups)
 187 {
 188         do {
 189                 TileIndex center_tile = RandomTile();
 190
 191                 for (uint i = 0; i < DEFAULT_TREE_STEPS; i++) {
 192                         uint32_t r = Random();
 193                         int x = GB(r, 0, 5) - 16;
 194                         int y = GB(r, 8, 5) - 16;
 195                         uint dist = abs(x) + abs(y);
 196                         TileIndex cur_tile = TileAddWrap(center_tile, x, y);
 197
 198                         IncreaseGeneratingWorldProgress(GWP_TREE);
 199
 200                         if (cur_tile != INVALID_TILE && dist <= 13 && CanPlantTreesOnTile(cur_tile, true)) {
 201                                 PlaceTree(cur_tile, r);
 202                         }
 203                 }
 204
 205         } while (--num_groups);
 206 }
 207
 208 /**
 209  * Place a tree at the same height as an existing tree.
 210  *
 211  * Add a new tree around the given tile which is at the same
 212  * height or at some offset (2 units) of it.
 213  *
 214  * @param tile The base tile to add a new tree somewhere around
 215  * @param height The height (like the one from the tile)
 216  */
 217 static void PlaceTreeAtSameHeight(TileIndex tile, int height)
 218 {
 219         for (uint i = 0; i < DEFAULT_TREE_STEPS; i++) {
 220                 uint32_t r = Random();
 221                 int x = GB(r, 0, 5) - 16;
 222                 int y = GB(r, 8, 5) - 16;
 223                 TileIndex cur_tile = TileAddWrap(tile, x, y);
 224                 if (cur_tile == INVALID_TILE) continue;
 225
 226                 /* Keep in range of the existing tree */
 227                 if (abs(x) + abs(y) > 16) continue;
 228
 229                 /* Clear tile, no farm-tiles or rocks */
 230                 if (!CanPlantTreesOnTile(cur_tile, true)) continue;
 231
 232                 /* Not too much height difference */
 233                 if (Delta(GetTileZ(cur_tile), height) > 2) continue;
 234
 235                 /* Place one tree and quit */
 236                 PlaceTree(cur_tile, r);
 237                 break;
 238         }
 239 }
 240
 241 /**
 242  * Place some trees randomly
 243  *
 244  * This function just place some trees randomly on the map.
 245  */
 246 void PlaceTreesRandomly()
 247 {
 248         int i, j, ht;
 249
 250         i = Map::ScaleBySize(DEFAULT_TREE_STEPS);
 251         if (_game_mode == GM_EDITOR) i /= EDITOR_TREE_DIV;
 252         do {
 253                 uint32_t r = Random();
 254                 TileIndex tile = RandomTileSeed(r);
 255
 256                 IncreaseGeneratingWorldProgress(GWP_TREE);
 257
 258                 if (CanPlantTreesOnTile(tile, true)) {
 259                         PlaceTree(tile, r);
 260                         if (_settings_game.game_creation.tree_placer != TP_IMPROVED) continue;
 261
 262                         /* Place a number of trees based on the tile height.
 263                          *  This gives a cool effect of multiple trees close together.
 264                          *  It is almost real life ;) */
 265                         ht = GetTileZ(tile);
 266                         /* The higher we get, the more trees we plant */
 267                         j = GetTileZ(tile) * 2;
 268                         /* Above snowline more trees! */
 269                         if (_settings_game.game_creation.landscape == LT_ARCTIC && ht > GetSnowLine()) j *= 3;
 270                         while (j--) {
 271                                 PlaceTreeAtSameHeight(tile, ht);
 272                         }
 273                 }
 274         } while (--i);
 275
 276         /* place extra trees at rainforest area */
 277         if (_settings_game.game_creation.landscape == LT_TROPIC) {
 278                 i = Map::ScaleBySize(DEFAULT_RAINFOREST_TREE_STEPS);
 279                 if (_game_mode == GM_EDITOR) i /= EDITOR_TREE_DIV;
 280
 281                 do {
 282                         uint32_t r = Random();
 283                         TileIndex tile = RandomTileSeed(r);
 284
 285                         IncreaseGeneratingWorldProgress(GWP_TREE);
 286
 287                         if (GetTropicZone(tile) == TROPICZONE_RAINFOREST && CanPlantTreesOnTile(tile, false)) {
 288                                 PlaceTree(tile, r);
 289                         }
 290                 } while (--i);
 291         }
 292 }
 293
 294 /**
 295  * Place some trees in a radius around a tile.
 296  * The trees are placed in an quasi-normal distribution around the indicated tile, meaning that while
 297  * the radius does define a square, the distribution inside the square will be roughly circular.
 298  * @note This function the interactive RNG and must only be used in editor and map generation.
 299  * @param tile      Tile to place trees around.
 300  * @param treetype  Type of trees to place. Must be a valid tree type for the climate.
 301  * @param radius    Maximum distance (on each axis) from tile to place trees.
 302  * @param count     Maximum number of trees to place.
 303  * @param set_zone  Whether to create a rainforest zone when placing rainforest trees.
 304  * @return Number of trees actually placed.
 305  */
 306 uint PlaceTreeGroupAroundTile(TileIndex tile, TreeType treetype, uint radius, uint count, bool set_zone)
 307 {
 308         assert(_game_mode == GM_EDITOR); // Due to InteractiveRandom being used in this function
 309         assert(treetype < TREE_TOYLAND + TREE_COUNT_TOYLAND);
 310         const bool allow_desert = treetype == TREE_CACTUS;
 311         uint planted = 0;
 312
 313         for (; count > 0; count--) {
 314                 /* Simple quasi-normal distribution with range [-radius; radius) */
 315                 auto mkcoord = [&]() -> int32_t {
 316                         const uint32_t rand = InteractiveRandom();
 317                         const int32_t dist = GB<int32_t>(rand, 0, 8) + GB<int32_t>(rand, 8, 8) + GB<int32_t>(rand, 16, 8) + GB<int32_t>(rand, 24, 8);
 318                         const int32_t scu = dist * radius / 512;
 319                         return scu - radius;
 320                 };
 321                 const int32_t xofs = mkcoord();
 322                 const int32_t yofs = mkcoord();
 323                 const TileIndex tile_to_plant = TileAddWrap(tile, xofs, yofs);
 324                 if (tile_to_plant != INVALID_TILE) {
 325                         if (IsTileType(tile_to_plant, MP_TREES) && GetTreeCount(tile_to_plant) < 4) {
 326                                 AddTreeCount(tile_to_plant, 1);
 327                                 SetTreeGrowth(tile_to_plant, TreeGrowthStage::Growing1);
 328                                 MarkTileDirtyByTile(tile_to_plant, 0);
 329                                 planted++;
 330                         } else if (CanPlantTreesOnTile(tile_to_plant, allow_desert)) {
 331                                 PlantTreesOnTile(tile_to_plant, treetype, 0, TreeGrowthStage::Grown);
 332                                 MarkTileDirtyByTile(tile_to_plant, 0);
 333                                 planted++;
 334                         }
 335                 }
 336         }
 337
 338         if (set_zone && IsInsideMM(treetype, TREE_RAINFOREST, TREE_CACTUS)) {
 339                 for (TileIndex t : TileArea(tile).Expand(radius)) {
 340                         if (GetTileType(t) != MP_VOID && DistanceSquare(tile, t) < radius * radius) SetTropicZone(t, TROPICZONE_RAINFOREST);
 341                 }
 342         }
 343
 344         return planted;
 345 }
 346
 347 /**
 348  * Place new trees.
 349  *
 350  * This function takes care of the selected tree placer algorithm and
 351  * place randomly the trees for a new game.
 352  */
 353 void GenerateTrees()
 354 {
 355         uint i, total;
 356
 357         if (_settings_game.game_creation.tree_placer == TP_NONE) return;
 358
 359         switch (_settings_game.game_creation.tree_placer) {
 360                 case TP_ORIGINAL: i = _settings_game.game_creation.landscape == LT_ARCTIC ? 15 : 6; break;
 361                 case TP_IMPROVED: i = _settings_game.game_creation.landscape == LT_ARCTIC ?  4 : 2; break;
 362                 default: NOT_REACHED();
 363         }
 364
 365         total = Map::ScaleBySize(DEFAULT_TREE_STEPS);
 366         if (_settings_game.game_creation.landscape == LT_TROPIC) total += Map::ScaleBySize(DEFAULT_RAINFOREST_TREE_STEPS);
 367         total *= i;
 368         uint num_groups = (_settings_game.game_creation.landscape != LT_TOYLAND) ? Map::ScaleBySize(GB(Random(), 0, 5) + 25) : 0;
 369         total += num_groups * DEFAULT_TREE_STEPS;
 370         SetGeneratingWorldProgress(GWP_TREE, total);
 371
 372         if (num_groups != 0) PlaceTreeGroups(num_groups);
 373
 374         for (; i != 0; i--) {
 375                 PlaceTreesRandomly();
 376         }
 377 }
 378
 379 /**
 380  * Plant a tree.
 381  * @param flags type of operation
 382  * @param tile end tile of area-drag
 383  * @param start_tile start tile of area-drag of tree plantation
 384  * @param tree_to_plant tree type, TREE_INVALID means random.
 385  * @param diagonal Whether to use the Orthogonal (false) or Diagonal (true) iterator.
 386  * @return the cost of this operation or an error
 387  */
 388 CommandCost CmdPlantTree(DoCommandFlag flags, TileIndex tile, TileIndex start_tile, uint8_t tree_to_plant, bool diagonal)
 389 {
 390         StringID msg = INVALID_STRING_ID;
 391         CommandCost cost(EXPENSES_OTHER);
 392
 393         if (start_tile >= Map::Size()) return CMD_ERROR;
 394         /* Check the tree type within the current climate */
 395         if (tree_to_plant != TREE_INVALID && !IsInsideBS(tree_to_plant, _tree_base_by_landscape[_settings_game.game_creation.landscape], _tree_count_by_landscape[_settings_game.game_creation.landscape])) return CMD_ERROR;
 396
 397         Company *c = (_game_mode != GM_EDITOR) ? Company::GetIfValid(_current_company) : nullptr;
 398         int limit = (c == nullptr ? INT32_MAX : GB(c->tree_limit, 16, 16));
 399
 400         std::unique_ptr<TileIterator> iter = TileIterator::Create(tile, start_tile, diagonal);
 401         for (; *iter != INVALID_TILE; ++(*iter)) {
 402                 TileIndex current_tile = *iter;
 403                 switch (GetTileType(current_tile)) {
 404                         case MP_TREES:
 405                                 /* no more space for trees? */
 406                                 if (GetTreeCount(current_tile) == 4) {
 407                                         msg = STR_ERROR_TREE_ALREADY_HERE;
 408                                         continue;
 409                                 }
 410
 411                                 /* Test tree limit. */
 412                                 if (--limit < 1) {
 413                                         msg = STR_ERROR_TREE_PLANT_LIMIT_REACHED;
 414                                         break;
 415                                 }
 416
 417                                 if (flags & DC_EXEC) {
 418                                         AddTreeCount(current_tile, 1);
 419                                         MarkTileDirtyByTile(current_tile);
 420                                         if (c != nullptr) c->tree_limit -= 1 << 16;
 421                                 }
 422                                 /* 2x as expensive to add more trees to an existing tile */
 423                                 cost.AddCost(_price[PR_BUILD_TREES] * 2);
 424                                 break;
 425
 426                         case MP_WATER:
 427                                 if (!IsCoast(current_tile) || IsSlopeWithOneCornerRaised(GetTileSlope(current_tile))) {
 428                                         msg = STR_ERROR_CAN_T_BUILD_ON_WATER;
 429                                         continue;
 430                                 }
 431                                 [[fallthrough]];
 432
 433                         case MP_CLEAR: {
 434                                 if (IsBridgeAbove(current_tile)) {
 435                                         msg = STR_ERROR_SITE_UNSUITABLE;
 436                                         continue;
 437                                 }
 438
 439                                 TreeType treetype = (TreeType)tree_to_plant;
 440                                 /* Be a bit picky about which trees go where. */
 441                                 if (_settings_game.game_creation.landscape == LT_TROPIC && treetype != TREE_INVALID && (
 442                                                 /* No cacti outside the desert */
 443                                                 (treetype == TREE_CACTUS && GetTropicZone(current_tile) != TROPICZONE_DESERT) ||
 444                                                 /* No rain forest trees outside the rain forest, except in the editor mode where it makes those tiles rain forest tile */
 445                                                 (IsInsideMM(treetype, TREE_RAINFOREST, TREE_CACTUS) && GetTropicZone(current_tile) != TROPICZONE_RAINFOREST && _game_mode != GM_EDITOR) ||
 446                                                 /* And no subtropical trees in the desert/rain forest */
 447                                                 (IsInsideMM(treetype, TREE_SUB_TROPICAL, TREE_TOYLAND) && GetTropicZone(current_tile) != TROPICZONE_NORMAL))) {
 448                                         msg = STR_ERROR_TREE_WRONG_TERRAIN_FOR_TREE_TYPE;
 449                                         continue;
 450                                 }
 451
 452                                 /* Test tree limit. */
 453                                 if (--limit < 1) {
 454                                         msg = STR_ERROR_TREE_PLANT_LIMIT_REACHED;
 455                                         break;
 456                                 }
 457
 458                                 if (IsTileType(current_tile, MP_CLEAR)) {
 459                                         /* Remove fields or rocks. Note that the ground will get barrened */
 460                                         switch (GetRawClearGround(current_tile)) {
 461                                                 case CLEAR_FIELDS:
 462                                                 case CLEAR_ROCKS: {
 463                                                         CommandCost ret = Command<CMD_LANDSCAPE_CLEAR>::Do(flags, current_tile);
 464                                                         if (ret.Failed()) return ret;
 465                                                         cost.AddCost(ret);
 466                                                         break;
 467                                                 }
 468
 469                                                 default: break;
 470                                         }
 471                                 }
 472
 473                                 if (_game_mode != GM_EDITOR && Company::IsValidID(_current_company)) {
 474                                         Town *t = ClosestTownFromTile(current_tile, _settings_game.economy.dist_local_authority);
 475                                         if (t != nullptr) ChangeTownRating(t, RATING_TREE_UP_STEP, RATING_TREE_MAXIMUM, flags);
 476                                 }
 477
 478                                 if (flags & DC_EXEC) {
 479                                         if (treetype == TREE_INVALID) {
 480                                                 treetype = GetRandomTreeType(current_tile, GB(Random(), 24, 8));
 481                                                 if (treetype == TREE_INVALID) treetype = TREE_CACTUS;
 482                                         }
 483
 484                                         /* Plant full grown trees in scenario editor */
 485                                         PlantTreesOnTile(current_tile, treetype, 0, _game_mode == GM_EDITOR ? TreeGrowthStage::Grown : TreeGrowthStage::Growing1);
 486                                         MarkTileDirtyByTile(current_tile);
 487                                         if (c != nullptr) c->tree_limit -= 1 << 16;
 488
 489                                         /* When planting rainforest-trees, set tropiczone to rainforest in editor. */
 490                                         if (_game_mode == GM_EDITOR && IsInsideMM(treetype, TREE_RAINFOREST, TREE_CACTUS)) {
 491                                                 SetTropicZone(current_tile, TROPICZONE_RAINFOREST);
 492                                         }
 493                                 }
 494                                 cost.AddCost(_price[PR_BUILD_TREES]);
 495                                 break;
 496                         }
 497
 498                         default:
 499                                 msg = STR_ERROR_SITE_UNSUITABLE;
 500                                 break;
 501                 }
 502
 503                 /* Tree limit used up? No need to check more. */
 504                 if (limit < 0) break;
 505         }
 506
 507         if (cost.GetCost() == 0) {
 508                 return_cmd_error(msg);
 509         } else {
 510                 return cost;
 511         }
 512 }
 513
 514 struct TreeListEnt : PalSpriteID {
 515         uint8_t x, y;
 516 };
 517
 518 static void DrawTile_Trees(TileInfo *ti)
 519 {
 520         switch (GetTreeGround(ti->tile)) {
 521                 case TREE_GROUND_SHORE: DrawShoreTile(ti->tileh); break;
 522                 case TREE_GROUND_GRASS: DrawClearLandTile(ti, GetTreeDensity(ti->tile)); break;
 523                 case TREE_GROUND_ROUGH: DrawHillyLandTile(ti); break;
 524                 default: DrawGroundSprite(_clear_land_sprites_snow_desert[GetTreeDensity(ti->tile)] + SlopeToSpriteOffset(ti->tileh), PAL_NONE); break;
 525         }
 526
 527         /* Do not draw trees when the invisible trees setting is set */
 528         if (IsInvisibilitySet(TO_TREES)) return;
 529
 530         uint tmp = CountBits(ti->tile.base() + ti->x + ti->y);
 531         uint index = GB(tmp, 0, 2) + (GetTreeType(ti->tile) << 2);
 532
 533         /* different tree styles above one of the grounds */
 534         if ((GetTreeGround(ti->tile) == TREE_GROUND_SNOW_DESERT || GetTreeGround(ti->tile) == TREE_GROUND_ROUGH_SNOW) &&
 535                         GetTreeDensity(ti->tile) >= 2 &&
 536                         IsInsideMM(index, TREE_SUB_ARCTIC << 2, TREE_RAINFOREST << 2)) {
 537                 index += 164 - (TREE_SUB_ARCTIC << 2);
 538         }
 539
 540         assert(index < lengthof(_tree_layout_sprite));
 541
 542         const PalSpriteID *s = _tree_layout_sprite[index];
 543         const TreePos *d = _tree_layout_xy[GB(tmp, 2, 2)];
 544
 545         /* combine trees into one sprite object */
 546         StartSpriteCombine();
 547
 548         TreeListEnt te[4];
 549
 550         /* put the trees to draw in a list */
 551         uint trees = GetTreeCount(ti->tile);
 552
 553         for (uint i = 0; i < trees; i++) {
 554                 SpriteID sprite = s[0].sprite + (i == trees - 1 ? static_cast<uint>(GetTreeGrowth(ti->tile)) : 3);
 555                 PaletteID pal = s[0].pal;
 556
 557                 te[i].sprite = sprite;
 558                 te[i].pal    = pal;
 559                 te[i].x = d->x;
 560                 te[i].y = d->y;
 561                 s++;
 562                 d++;
 563         }
 564
 565         /* draw them in a sorted way */
 566         int z = ti->z + GetSlopeMaxPixelZ(ti->tileh) / 2;
 567
 568         for (; trees > 0; trees--) {
 569                 uint min = te[0].x + te[0].y;
 570                 uint mi = 0;
 571
 572                 for (uint i = 1; i < trees; i++) {
 573                         if ((uint)(te[i].x + te[i].y) < min) {
 574                                 min = te[i].x + te[i].y;
 575                                 mi = i;
 576                         }
 577                 }
 578
 579                 AddSortableSpriteToDraw(te[mi].sprite, te[mi].pal, ti->x + te[mi].x, ti->y + te[mi].y, 16 - te[mi].x, 16 - te[mi].y, 0x30, z, IsTransparencySet(TO_TREES), -te[mi].x, -te[mi].y);
 580
 581                 /* replace the removed one with the last one */
 582                 te[mi] = te[trees - 1];
 583         }
 584
 585         EndSpriteCombine();
 586 }
 587
 588
 589 static int GetSlopePixelZ_Trees(TileIndex tile, uint x, uint y, bool)
 590 {
 591         auto [tileh, z] = GetTilePixelSlope(tile);
 592
 593         return z + GetPartialPixelZ(x & 0xF, y & 0xF, tileh);
 594 }
 595
 596 static Foundation GetFoundation_Trees(TileIndex, Slope)
 597 {
 598         return FOUNDATION_NONE;
 599 }
 600
 601 static CommandCost ClearTile_Trees(TileIndex tile, DoCommandFlag flags)
 602 {
 603         uint num;
 604
 605         if (Company::IsValidID(_current_company)) {
 606                 Town *t = ClosestTownFromTile(tile, _settings_game.economy.dist_local_authority);
 607                 if (t != nullptr) ChangeTownRating(t, RATING_TREE_DOWN_STEP, RATING_TREE_MINIMUM, flags);
 608         }
 609
 610         num = GetTreeCount(tile);
 611         if (IsInsideMM(GetTreeType(tile), TREE_RAINFOREST, TREE_CACTUS)) num *= 4;
 612
 613         if (flags & DC_EXEC) DoClearSquare(tile);
 614
 615         return CommandCost(EXPENSES_CONSTRUCTION, num * _price[PR_CLEAR_TREES]);
 616 }
 617
 618 static void GetTileDesc_Trees(TileIndex tile, TileDesc *td)
 619 {
 620         TreeType tt = GetTreeType(tile);
 621
 622         if (IsInsideMM(tt, TREE_RAINFOREST, TREE_CACTUS)) {
 623                 td->str = STR_LAI_TREE_NAME_RAINFOREST;
 624         } else {
 625                 td->str = tt == TREE_CACTUS ? STR_LAI_TREE_NAME_CACTUS_PLANTS : STR_LAI_TREE_NAME_TREES;
 626         }
 627
 628         td->owner[0] = GetTileOwner(tile);
 629 }
 630
 631 static void TileLoopTreesDesert(TileIndex tile)
 632 {
 633         switch (GetTropicZone(tile)) {
 634                 case TROPICZONE_DESERT:
 635                         if (GetTreeGround(tile) != TREE_GROUND_SNOW_DESERT) {
 636                                 SetTreeGroundDensity(tile, TREE_GROUND_SNOW_DESERT, 3);
 637                                 MarkTileDirtyByTile(tile);
 638                         }
 639                         break;
 640
 641                 case TROPICZONE_RAINFOREST: {
 642                         static const SoundFx forest_sounds[] = {
 643                                 SND_42_RAINFOREST_1,
 644                                 SND_43_RAINFOREST_2,
 645                                 SND_44_RAINFOREST_3,
 646                                 SND_48_RAINFOREST_4
 647                         };
 648                         uint32_t r = Random();
 649
 650                         if (Chance16I(1, 200, r) && _settings_client.sound.ambient) SndPlayTileFx(forest_sounds[GB(r, 16, 2)], tile);
 651                         break;
 652                 }
 653
 654                 default: break;
 655         }
 656 }
 657
 658 static void TileLoopTreesAlps(TileIndex tile)
 659 {
 660         int k = GetTileZ(tile) - GetSnowLine() + 1;
 661
 662         if (k < 0) {
 663                 switch (GetTreeGround(tile)) {
 664                         case TREE_GROUND_SNOW_DESERT: SetTreeGroundDensity(tile, TREE_GROUND_GRASS, 3); break;
 665                         case TREE_GROUND_ROUGH_SNOW:  SetTreeGroundDensity(tile, TREE_GROUND_ROUGH, 3); break;
 666                         default: return;
 667                 }
 668         } else {
 669                 uint density = std::min<uint>(k, 3);
 670
 671                 if (GetTreeGround(tile) != TREE_GROUND_SNOW_DESERT && GetTreeGround(tile) != TREE_GROUND_ROUGH_SNOW) {
 672                         TreeGround tg = GetTreeGround(tile) == TREE_GROUND_ROUGH ? TREE_GROUND_ROUGH_SNOW : TREE_GROUND_SNOW_DESERT;
 673                         SetTreeGroundDensity(tile, tg, density);
 674                 } else if (GetTreeDensity(tile) != density) {
 675                         SetTreeGroundDensity(tile, GetTreeGround(tile), density);
 676                 } else {
 677                         if (GetTreeDensity(tile) == 3) {
 678                                 uint32_t r = Random();
 679                                 if (Chance16I(1, 200, r) && _settings_client.sound.ambient) {
 680                                         SndPlayTileFx((r & 0x80000000) ? SND_39_ARCTIC_SNOW_2 : SND_34_ARCTIC_SNOW_1, tile);
 681                                 }
 682                         }
 683                         return;
 684                 }
 685         }
 686         MarkTileDirtyByTile(tile);
 687 }
 688
 689 static bool CanPlantExtraTrees(TileIndex tile)
 690 {
 691         return ((_settings_game.game_creation.landscape == LT_TROPIC && GetTropicZone(tile) == TROPICZONE_RAINFOREST) ?
 692                 (_settings_game.construction.extra_tree_placement == ETP_SPREAD_ALL || _settings_game.construction.extra_tree_placement == ETP_SPREAD_RAINFOREST) :
 693                 _settings_game.construction.extra_tree_placement == ETP_SPREAD_ALL);
 694 }
 695
 696 static void TileLoop_Trees(TileIndex tile)
 697 {
 698         if (GetTreeGround(tile) == TREE_GROUND_SHORE) {
 699                 TileLoop_Water(tile);
 700         } else {
 701                 switch (_settings_game.game_creation.landscape) {
 702                         case LT_TROPIC: TileLoopTreesDesert(tile); break;
 703                         case LT_ARCTIC: TileLoopTreesAlps(tile);   break;
 704                 }
 705         }
 706
 707         AmbientSoundEffect(tile);
 708
 709         /* TimerGameTick::counter is incremented by 256 between each call, so ignore lower 8 bits.
 710          * Also, we use a simple hash to spread the updates evenly over the map.
 711          * 11 and 9 are just some co-prime numbers for better spread.
 712          */
 713         uint32_t cycle = 11 * TileX(tile) + 9 * TileY(tile) + (TimerGameTick::counter >> 8);
 714
 715         /* Handle growth of grass (under trees/on MP_TREES tiles) at every 8th processings, like it's done for grass on MP_CLEAR tiles. */
 716         if ((cycle & 7) == 7 && GetTreeGround(tile) == TREE_GROUND_GRASS) {
 717                 uint density = GetTreeDensity(tile);
 718                 if (density < 3) {
 719                         SetTreeGroundDensity(tile, TREE_GROUND_GRASS, density + 1);
 720                         MarkTileDirtyByTile(tile);
 721                 }
 722         }
 723
 724         if (_settings_game.construction.extra_tree_placement == ETP_NO_GROWTH_NO_SPREAD) return;
 725
 726         static const uint32_t TREE_UPDATE_FREQUENCY = 16;  // How many tile updates happen for one tree update
 727         if (cycle % TREE_UPDATE_FREQUENCY != TREE_UPDATE_FREQUENCY - 1) return;
 728
 729         switch (GetTreeGrowth(tile)) {
 730                 case TreeGrowthStage::Grown: // regular sized tree
 731                         if (_settings_game.game_creation.landscape == LT_TROPIC &&
 732                                         GetTreeType(tile) != TREE_CACTUS &&
 733                                         GetTropicZone(tile) == TROPICZONE_DESERT) {
 734                                 AddTreeGrowth(tile, 1);
 735                         } else {
 736                                 switch (GB(Random(), 0, 3)) {
 737                                         case 0: // start destructing
 738                                                 AddTreeGrowth(tile, 1);
 739                                                 break;
 740
 741                                         case 1: // add a tree
 742                                                 if (GetTreeCount(tile) < 4 && CanPlantExtraTrees(tile)) {
 743                                                         AddTreeCount(tile, 1);
 744                                                         SetTreeGrowth(tile, TreeGrowthStage::Growing1);
 745                                                         break;
 746                                                 }
 747                                                 [[fallthrough]];
 748
 749                                         case 2: { // add a neighbouring tree
 750                                                 if (!CanPlantExtraTrees(tile)) break;
 751
 752                                                 TreeType treetype = GetTreeType(tile);
 753
 754                                                 tile += TileOffsByDir(static_cast<Direction>(Random() % DIR_END));
 755
 756                                                 /* Cacti don't spread */
 757                                                 if (!CanPlantTreesOnTile(tile, false)) return;
 758
 759                                                 /* Don't plant trees, if ground was freshly cleared */
 760                                                 if (IsTileType(tile, MP_CLEAR) && GetClearGround(tile) == CLEAR_GRASS && GetClearDensity(tile) != 3) return;
 761
 762                                                 PlantTreesOnTile(tile, treetype, 0, TreeGrowthStage::Growing1);
 763
 764                                                 break;
 765                                         }
 766
 767                                         default:
 768                                                 return;
 769                                 }
 770                         }
 771                         break;
 772
 773                 case TreeGrowthStage::Dead: // final stage of tree destruction
 774                         if (!CanPlantExtraTrees(tile)) {
 775                                 /* if trees can't spread just plant a new one to prevent deforestation */
 776                                 SetTreeGrowth(tile, TreeGrowthStage::Growing1);
 777                         } else if (GetTreeCount(tile) > 1) {
 778                                 /* more than one tree, delete it */
 779                                 AddTreeCount(tile, -1);
 780                                 SetTreeGrowth(tile, TreeGrowthStage::Grown);
 781                         } else {
 782                                 /* just one tree, change type into MP_CLEAR */
 783                                 switch (GetTreeGround(tile)) {
 784                                         case TREE_GROUND_SHORE: MakeShore(tile); break;
 785                                         case TREE_GROUND_GRASS: MakeClear(tile, CLEAR_GRASS, GetTreeDensity(tile)); break;
 786                                         case TREE_GROUND_ROUGH: MakeClear(tile, CLEAR_ROUGH, 3); break;
 787                                         case TREE_GROUND_ROUGH_SNOW: {
 788                                                 uint density = GetTreeDensity(tile);
 789                                                 MakeClear(tile, CLEAR_ROUGH, 3);
 790                                                 MakeSnow(tile, density);
 791                                                 break;
 792                                         }
 793                                         default: // snow or desert
 794                                                 if (_settings_game.game_creation.landscape == LT_TROPIC) {
 795                                                         MakeClear(tile, CLEAR_DESERT, GetTreeDensity(tile));
 796                                                 } else {
 797                                                         uint density = GetTreeDensity(tile);
 798                                                         MakeClear(tile, CLEAR_GRASS, 3);
 799                                                         MakeSnow(tile, density);
 800                                                 }
 801                                                 break;
 802                                 }
 803                         }
 804                         break;
 805
 806                 default:
 807                         AddTreeGrowth(tile, 1);
 808                         break;
 809         }
 810
 811         MarkTileDirtyByTile(tile);
 812 }
 813
 814 /**
 815  * Decrement the tree tick counter.
 816  * The interval is scaled by map size to allow for the same density regardless of size.
 817  * Adjustment for map sizes below the standard 256 * 256 are handled earlier.
 818  * @return true if the counter was decremented past zero
 819  */
 820 bool DecrementTreeCounter()
 821 {
 822         /* Ensure _trees_tick_ctr can be decremented past zero only once for the largest map size. */
 823         static_assert(2 * (MAX_MAP_SIZE_BITS - MIN_MAP_SIZE_BITS) - 4 <= std::numeric_limits<uint8_t>::digits);
 824
 825         /* byte underflow */
 826         uint8_t old_trees_tick_ctr = _trees_tick_ctr;
 827         _trees_tick_ctr -= Map::ScaleBySize(1);
 828         return old_trees_tick_ctr <= _trees_tick_ctr;
 829 }
 830
 831 void OnTick_Trees()
 832 {
 833         /* Don't spread trees if that's not allowed */
 834         if (_settings_game.construction.extra_tree_placement == ETP_NO_SPREAD || _settings_game.construction.extra_tree_placement == ETP_NO_GROWTH_NO_SPREAD) return;
 835
 836         uint32_t r;
 837         TileIndex tile;
 838         TreeType tree;
 839
 840         /* Skip some tree ticks for map sizes below 256 * 256. 64 * 64 is 16 times smaller, so
 841          * this is the maximum number of ticks that are skipped. Number of ticks to skip is
 842          * inversely proportional to map size, so that is handled to create a mask. */
 843         int skip = Map::ScaleBySize(16);
 844         if (skip < 16 && (TimerGameTick::counter & (16 / skip - 1)) != 0) return;
 845
 846         /* place a tree at a random rainforest spot */
 847         if (_settings_game.game_creation.landscape == LT_TROPIC) {
 848                 for (uint c = Map::ScaleBySize(1); c > 0; c--) {
 849                         if ((r = Random(), tile = RandomTileSeed(r), GetTropicZone(tile) == TROPICZONE_RAINFOREST) &&
 850                                 CanPlantTreesOnTile(tile, false) &&
 851                                 (tree = GetRandomTreeType(tile, GB(r, 24, 8))) != TREE_INVALID) {
 852                                 PlantTreesOnTile(tile, tree, 0, TreeGrowthStage::Growing1);
 853                         }
 854                 }
 855         }
 856
 857         if (!DecrementTreeCounter() || _settings_game.construction.extra_tree_placement == ETP_SPREAD_RAINFOREST) return;
 858
 859         /* place a tree at a random spot */
 860         r = Random();
 861         tile = RandomTileSeed(r);
 862         if (CanPlantTreesOnTile(tile, false) && (tree = GetRandomTreeType(tile, GB(r, 24, 8))) != TREE_INVALID) {
 863                 PlantTreesOnTile(tile, tree, 0, TreeGrowthStage::Growing1);
 864         }
 865 }
 866
 867 static TrackStatus GetTileTrackStatus_Trees(TileIndex, TransportType, uint, DiagDirection)
 868 {
 869         return 0;
 870 }
 871
 872 static void ChangeTileOwner_Trees(TileIndex, Owner, Owner)
 873 {
 874         /* not used */
 875 }
 876
 877 void InitializeTrees()
 878 {
 879         _trees_tick_ctr = 0;
 880 }
 881
 882 static CommandCost TerraformTile_Trees(TileIndex tile, DoCommandFlag flags, int, Slope)
 883 {
 884         return Command<CMD_LANDSCAPE_CLEAR>::Do(flags, tile);
 885 }
 886
 887
 888 extern const TileTypeProcs _tile_type_trees_procs = {
 889         DrawTile_Trees,           // draw_tile_proc
 890         GetSlopePixelZ_Trees,     // get_slope_z_proc
 891         ClearTile_Trees,          // clear_tile_proc
 892         nullptr,                     // add_accepted_cargo_proc
 893         GetTileDesc_Trees,        // get_tile_desc_proc
 894         GetTileTrackStatus_Trees, // get_tile_track_status_proc
 895         nullptr,                     // click_tile_proc
 896         nullptr,                     // animate_tile_proc
 897         TileLoop_Trees,           // tile_loop_proc
 898         ChangeTileOwner_Trees,    // change_tile_owner_proc
 899         nullptr,                     // add_produced_cargo_proc
 900         nullptr,                     // vehicle_enter_tile_proc
 901         GetFoundation_Trees,      // get_foundation_proc
 902         TerraformTile_Trees,      // terraform_tile_proc
 903 };