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