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