173
167
uint total_size; //< height map total size
174
168
uint size_x; //< MapSizeX()
175
169
uint size_y; //< MapSizeY()
172
* Height map accessor
173
* @param x X position
174
* @param y Y position
175
* @return height as fixed point number
177
inline height_t &height(uint x, uint y) {
178
return h[x + y * dim_x];
178
182
/** Global height map instance */
179
183
static HeightMap _height_map = {NULL, 0, 0, 0, 0};
181
/** Height map accessors */
182
#define HeightMapXY(x, y) _height_map.h[(x) + (y) * _height_map.dim_x]
184
185
/** Conversion: int to height_t */
185
186
#define I2H(i) ((i) << height_decimal_bits)
186
187
/** Conversion: height_t to int */
198
199
/** Walk through all items of _height_map.h */
199
200
#define FOR_ALL_TILES_IN_HEIGHT(h) for (h = _height_map.h; h < &_height_map.h[_height_map.total_size]; h++)
202
/** Maximum index into array of noise amplitudes */
203
static const int TGP_FREQUENCY_MAX = 6;
201
205
/** Noise amplitudes (multiplied by 1024)
202
206
* - indexed by "smoothness setting" and log2(frequency) */
203
static const amplitude_t _amplitudes_by_smoothness_and_frequency[4][12] = {
207
static const amplitude_t _amplitudes_by_smoothness_and_frequency[4][TGP_FREQUENCY_MAX + 1] = {
208
/* lowest frequncy.... ...highest (every corner) */
204
209
/* Very smooth */
205
{1000, 350, 123, 43, 15, 1, 1, 0, 0, 0, 0, 0},
210
{16000, 5600, 1968, 688, 240, 16, 16},
207
{1000, 1000, 403, 200, 64, 8, 1, 0, 0, 0, 0, 0},
212
{16000, 16000, 6448, 3200, 1024, 128, 16},
209
{1000, 1200, 800, 500, 200, 16, 4, 0, 0, 0, 0, 0},
214
{16000, 19200, 12800, 8000, 3200, 256, 64},
211
{1500, 1000, 1200, 1000, 500, 32, 20, 0, 0, 0, 0, 0},
216
{24000, 16000, 19200, 16000, 8000, 512, 320},
214
/** Desired water percentage (100% == 1024) - indexed by _opt.diff.quantity_sea_lakes */
219
/** Desired water percentage (100% == 1024) - indexed by _settings_game.difficulty.quantity_sea_lakes */
215
220
static const amplitude_t _water_percent[4] = {20, 80, 250, 400};
217
/** Desired maximum height - indexed by _opt.diff.terrain_type */
222
/** Desired maximum height - indexed by _settings_game.difficulty.terrain_type */
218
223
static const int8 _max_height[4] = {
219
224
6, ///< Very flat
261
268
_height_map.h = NULL;
264
/** RandomHeight() generator */
272
* Generates new random height in given amplitude (generated numbers will range from - amplitude to + amplitude)
273
* @param rMax Limit of result
274
* @return generated height
265
276
static inline height_t RandomHeight(amplitude_t rMax)
267
278
amplitude_t ra = (Random() << 16) | (Random() & 0x0000FFFF);
269
/* Scale the amplitude for better resolution */
271
280
/* Spread height into range -rMax..+rMax */
272
281
rh = A2H(ra % (2 * rMax + 1) - rMax);
276
/** One interpolation and noise round */
286
* One interpolation and noise round
288
* The heights on the map are generated in an iterative process.
289
* We start off with a frequency of 1 (log_frequency == 0), and generate heights only for corners on the most coarsly mesh
290
* (i.e. only for x/y coordinates which are multiples of the minimum edge length).
292
* After this initial step the frequency is doubled (log_frequency incremented) each iteration to generate corners on the next finer mesh.
293
* The heights of the newly added corners are first set by interpolating the heights from the previous iteration.
294
* Finally noise with the given amplitude is applied to all corners of the new mesh.
296
* Generation terminates, when the frequency has reached the map size. I.e. the mesh is as fine as the map, and every corner height
299
* @param log_frequency frequency (logarithmic) to apply noise for
300
* @param amplitude Amplitude for the noise
301
* @return false if we are finished (reached the minimal step size / highest frequency)
277
303
static bool ApplyNoise(uint log_frequency, amplitude_t amplitude)
279
305
uint size_min = min(_height_map.size_x, _height_map.size_y);
280
306
uint step = size_min >> log_frequency;
309
/* Trying to apply noise to uninitialized height map */
283
310
assert(_height_map.h != NULL);
285
312
/* Are we finished? */
300
327
* Interpolate height values at odd x, even y tiles */
301
328
for (y = 0; y <= _height_map.size_y; y += 2 * step) {
302
329
for (x = 0; x < _height_map.size_x; x += 2 * step) {
303
height_t h00 = HeightMapXY(x + 0 * step, y);
304
height_t h02 = HeightMapXY(x + 2 * step, y);
330
height_t h00 = _height_map.height(x + 0 * step, y);
331
height_t h02 = _height_map.height(x + 2 * step, y);
305
332
height_t h01 = (h00 + h02) / 2;
306
HeightMapXY(x + 1 * step, y) = h01;
333
_height_map.height(x + 1 * step, y) = h01;
310
337
/* Interpolate height values at odd y tiles */
311
338
for (y = 0; y < _height_map.size_y; y += 2 * step) {
312
339
for (x = 0; x <= _height_map.size_x; x += step) {
313
height_t h00 = HeightMapXY(x, y + 0 * step);
314
height_t h20 = HeightMapXY(x, y + 2 * step);
340
height_t h00 = _height_map.height(x, y + 0 * step);
341
height_t h20 = _height_map.height(x, y + 2 * step);
315
342
height_t h10 = (h00 + h20) / 2;
316
HeightMapXY(x, y + 1 * step) = h10;
343
_height_map.height(x, y + 1 * step) = h10;
347
/* Add noise for next higher frequency (smaller steps) */
320
348
for (y = 0; y <= _height_map.size_y; y += step) {
321
349
for (x = 0; x <= _height_map.size_x; x += step) {
322
HeightMapXY(x, y) += RandomHeight(amplitude);
350
_height_map.height(x, y) += RandomHeight(amplitude);
325
354
return (step > 1);
332
361
uint iteration_round = 0;
333
362
amplitude_t amplitude;
334
363
bool continue_iteration;
335
uint log_size_min, log_frequency_min;
364
int log_size_min, log_frequency_min;
336
365
int log_frequency;
338
/* Find first power of two that fits */
339
for (log_size_min = 6; (1U << log_size_min) < size_min; log_size_min++) { }
340
log_frequency_min = log_size_min - 6;
367
/* Find first power of two that fits, so that later log_frequency == TGP_FREQUENCY_MAX in the last iteration */
368
for (log_size_min = TGP_FREQUENCY_MAX; (1U << log_size_min) < size_min; log_size_min++) { }
369
log_frequency_min = log_size_min - TGP_FREQUENCY_MAX;
371
/* Zero must be part of the iteration, else initialization will fail. */
372
assert(log_frequency_min >= 0);
374
/* Keep increasing the frequency until we reach the step size equal to one tile */
343
376
log_frequency = iteration_round - log_frequency_min;
344
377
if (log_frequency >= 0) {
345
amplitude = _amplitudes_by_smoothness_and_frequency[_patches.tgen_smoothness][log_frequency];
378
/* Apply noise for the next frequency */
379
assert(log_frequency <= TGP_FREQUENCY_MAX);
380
amplitude = _amplitudes_by_smoothness_and_frequency[_settings_game.game_creation.tgen_smoothness][log_frequency];
382
/* Amplitude for the low frequencies on big maps is 0, i.e. initialise with zero height */
349
385
continue_iteration = ApplyNoise(iteration_round, amplitude);
350
386
iteration_round++;
351
} while(continue_iteration);
387
} while (continue_iteration);
388
assert(log_frequency == TGP_FREQUENCY_MAX);
354
391
/** Returns min, max and average height from height map */
540
577
/* Lower to sea level */
541
578
for (y = 0; y <= _height_map.size_y; y++) {
543
max_x = abs((perlin_coast_noise_2D(_height_map.size_y - y, y, 0.9, 53) + 0.25) * 5 + (perlin_coast_noise_2D(y, y, 0.35, 179) + 1) * 12);
544
max_x = max((smallest_size * smallest_size / 16) + max_x, (smallest_size * smallest_size / 16) + margin - max_x);
545
if (smallest_size < 8 && max_x > 5) max_x /= 1.5;
546
for (x = 0; x < max_x; x++) {
547
HeightMapXY(x, y) = 0;
579
if (HasBit(water_borders, BORDER_NE)) {
581
max_x = abs((perlin_coast_noise_2D(_height_map.size_y - y, y, 0.9, 53) + 0.25) * 5 + (perlin_coast_noise_2D(y, y, 0.35, 179) + 1) * 12);
582
max_x = max((smallest_size * smallest_size / 16) + max_x, (smallest_size * smallest_size / 16) + margin - max_x);
583
if (smallest_size < 8 && max_x > 5) max_x /= 1.5;
584
for (x = 0; x < max_x; x++) {
585
_height_map.height(x, y) = 0;
551
max_x = abs((perlin_coast_noise_2D(_height_map.size_y - y, y, 0.85, 101) + 0.3) * 6 + (perlin_coast_noise_2D(y, y, 0.45, 67) + 0.75) * 8);
552
max_x = max((smallest_size * smallest_size / 16) + max_x, (smallest_size * smallest_size / 16) + margin - max_x);
553
if (smallest_size < 8 && max_x > 5) max_x /= 1.5;
554
for (x = _height_map.size_x; x > (_height_map.size_x - 1 - max_x); x--) {
555
HeightMapXY(x, y) = 0;
589
if (HasBit(water_borders, BORDER_SW)) {
591
max_x = abs((perlin_coast_noise_2D(_height_map.size_y - y, y, 0.85, 101) + 0.3) * 6 + (perlin_coast_noise_2D(y, y, 0.45, 67) + 0.75) * 8);
592
max_x = max((smallest_size * smallest_size / 16) + max_x, (smallest_size * smallest_size / 16) + margin - max_x);
593
if (smallest_size < 8 && max_x > 5) max_x /= 1.5;
594
for (x = _height_map.size_x; x > (_height_map.size_x - 1 - max_x); x--) {
595
_height_map.height(x, y) = 0;
559
600
/* Lower to sea level */
560
601
for (x = 0; x <= _height_map.size_x; x++) {
562
max_y = abs((perlin_coast_noise_2D(x, _height_map.size_y / 2, 0.9, 167) + 0.4) * 5 + (perlin_coast_noise_2D(x, _height_map.size_y / 3, 0.4, 211) + 0.7) * 9);
563
max_y = max((smallest_size * smallest_size / 16) + max_y, (smallest_size * smallest_size / 16) + margin - max_y);
564
if (smallest_size < 8 && max_y > 5) max_y /= 1.5;
565
for (y = 0; y < max_y; y++) {
566
HeightMapXY(x, y) = 0;
602
if (HasBit(water_borders, BORDER_NW)) {
604
max_y = abs((perlin_coast_noise_2D(x, _height_map.size_y / 2, 0.9, 167) + 0.4) * 5 + (perlin_coast_noise_2D(x, _height_map.size_y / 3, 0.4, 211) + 0.7) * 9);
605
max_y = max((smallest_size * smallest_size / 16) + max_y, (smallest_size * smallest_size / 16) + margin - max_y);
606
if (smallest_size < 8 && max_y > 5) max_y /= 1.5;
607
for (y = 0; y < max_y; y++) {
608
_height_map.height(x, y) = 0;
571
max_y = abs((perlin_coast_noise_2D(x, _height_map.size_y / 3, 0.85, 71) + 0.25) * 6 + (perlin_coast_noise_2D(x, _height_map.size_y / 3, 0.35, 193) + 0.75) * 12);
572
max_y = max((smallest_size * smallest_size / 16) + max_y, (smallest_size * smallest_size / 16) + margin - max_y);
573
if (smallest_size < 8 && max_y > 5) max_y /= 1.5;
574
for (y = _height_map.size_y; y > (_height_map.size_y - 1 - max_y); y--) {
575
HeightMapXY(x, y) = 0;
612
if (HasBit(water_borders, BORDER_SE)) {
614
max_y = abs((perlin_coast_noise_2D(x, _height_map.size_y / 3, 0.85, 71) + 0.25) * 6 + (perlin_coast_noise_2D(x, _height_map.size_y / 3, 0.35, 193) + 0.75) * 12);
615
max_y = max((smallest_size * smallest_size / 16) + max_y, (smallest_size * smallest_size / 16) + margin - max_y);
616
if (smallest_size < 8 && max_y > 5) max_y /= 1.5;
617
for (y = _height_map.size_y; y > (_height_map.size_y - 1 - max_y); y--) {
618
_height_map.height(x, y) = 0;
595
639
/* Search for the coast (first non-water tile) */
596
640
for (x = org_x, y = org_y, ed = 0; IsValidXY(x, y) && ed < max_coast_dist_from_edge; x += dir_x, y += dir_y, ed++) {
597
641
/* Coast found? */
598
if (HeightMapXY(x, y) > 15) break;
642
if (_height_map.height(x, y) > 15) break;
600
644
/* Coast found in the neighborhood? */
601
if (IsValidXY(x + dir_y, y + dir_x) && HeightMapXY(x + dir_y, y + dir_x) > 0) break;
645
if (IsValidXY(x + dir_y, y + dir_x) && _height_map.height(x + dir_y, y + dir_x) > 0) break;
603
647
/* Coast found in the neighborhood on the other side */
604
if (IsValidXY(x - dir_y, y - dir_x) && HeightMapXY(x - dir_y, y - dir_x) > 0) break;
648
if (IsValidXY(x - dir_y, y - dir_x) && _height_map.height(x - dir_y, y - dir_x) > 0) break;
607
651
/* Coast found or max_coast_dist_from_edge has been reached.
608
652
* Soften the coast slope */
609
653
for (depth = 0; IsValidXY(x, y) && depth <= max_coast_Smooth_depth; depth++, x += dir_x, y += dir_y) {
610
h = HeightMapXY(x, y);
654
h = _height_map.height(x, y);
611
655
h = min(h, h_prev + (4 + depth)); // coast softening formula
612
HeightMapXY(x, y) = h;
656
_height_map.height(x, y) = h;
617
661
/** Smooth coasts by modulating height of tiles close to map edges with cosine of distance from edge */
618
static void HeightMapSmoothCoasts()
662
static void HeightMapSmoothCoasts(uint8 water_borders)
621
665
/* First Smooth NW and SE coasts (y close to 0 and y close to size_y) */
622
666
for (x = 0; x < _height_map.size_x; x++) {
623
HeightMapSmoothCoastInDirection(x, 0, 0, 1);
624
HeightMapSmoothCoastInDirection(x, _height_map.size_y - 1, 0, -1);
667
if (HasBit(water_borders, BORDER_NW)) HeightMapSmoothCoastInDirection(x, 0, 0, 1);
668
if (HasBit(water_borders, BORDER_SE)) HeightMapSmoothCoastInDirection(x, _height_map.size_y - 1, 0, -1);
626
670
/* First Smooth NE and SW coasts (x close to 0 and x close to size_x) */
627
671
for (y = 0; y < _height_map.size_y; y++) {
628
HeightMapSmoothCoastInDirection(0, y, 1, 0);
629
HeightMapSmoothCoastInDirection(_height_map.size_x - 1, y, -1, 0);
672
if (HasBit(water_borders, BORDER_NE)) HeightMapSmoothCoastInDirection(0, y, 1, 0);
673
if (HasBit(water_borders, BORDER_SW)) HeightMapSmoothCoastInDirection(_height_map.size_x - 1, y, -1, 0);
640
684
static void HeightMapSmoothSlopes(height_t dh_max)
643
for (y = 1; y <= (int)_height_map.size_y; y++) {
644
for (x = 1; x <= (int)_height_map.size_x; x++) {
645
height_t h_max = min(HeightMapXY(x - 1, y), HeightMapXY(x, y - 1)) + dh_max;
646
if (HeightMapXY(x, y) > h_max) HeightMapXY(x, y) = h_max;
687
for (y = 0; y <= (int)_height_map.size_y; y++) {
688
for (x = 0; x <= (int)_height_map.size_x; x++) {
689
height_t h_max = min(_height_map.height(x > 0 ? x - 1 : x, y), _height_map.height(x, y > 0 ? y - 1 : y)) + dh_max;
690
if (_height_map.height(x, y) > h_max) _height_map.height(x, y) = h_max;
649
for (y = _height_map.size_y - 1; y >= 0; y--) {
650
for (x = _height_map.size_x - 1; x >= 0; x--) {
651
height_t h_max = min(HeightMapXY(x + 1, y), HeightMapXY(x, y + 1)) + dh_max;
652
if (HeightMapXY(x, y) > h_max) HeightMapXY(x, y) = h_max;
693
for (y = _height_map.size_y; y >= 0; y--) {
694
for (x = _height_map.size_x; x >= 0; x--) {
695
height_t h_max = min(_height_map.height((uint)x < _height_map.size_x ? x + 1 : x, y), _height_map.height(x, (uint)y < _height_map.size_y ? y + 1 : y)) + dh_max;
696
if (_height_map.height(x, y) > h_max) _height_map.height(x, y) = h_max;
661
705
* - height histogram redistribution by sine wave transform */
662
706
static void HeightMapNormalize()
664
const amplitude_t water_percent = _water_percent[_opt.diff.quantity_sea_lakes];
665
const height_t h_max_new = I2H(_max_height[_opt.diff.terrain_type]);
666
const height_t roughness = 7 + 3 * _patches.tgen_smoothness;
708
const amplitude_t water_percent = _water_percent[_settings_game.difficulty.quantity_sea_lakes];
709
const height_t h_max_new = I2H(_max_height[_settings_game.difficulty.terrain_type]);
710
const height_t roughness = 7 + 3 * _settings_game.game_creation.tgen_smoothness;
668
712
HeightMapAdjustWaterLevel(water_percent, h_max_new);
670
HeightMapCoastLines();
714
byte water_borders = _settings_game.construction.freeform_edges ? _settings_game.game_creation.water_borders : 0xF;
715
if (water_borders == BORDERS_RANDOM) water_borders = GB(Random(), 0, 4);
717
HeightMapCoastLines(water_borders);
671
718
HeightMapSmoothSlopes(roughness);
673
HeightMapSmoothCoasts();
720
HeightMapSmoothCoasts(water_borders);
674
721
HeightMapSmoothSlopes(roughness);
676
723
HeightMapSineTransform(12, h_max_new);
677
724
HeightMapSmoothSlopes(16);
680
static inline int perlin_landXY(uint x, uint y)
682
return HeightMapXY(x, y);
686
/* The following decimals are the octave power modifiers for the Perlin noise */
687
static const double _perlin_p_values[][7] = { // perlin frequency per power
688
{ 0.35, 0.35, 0.35, 0.35, 0.35, 0.25, 0.539 }, ///< Very smooth
689
{ 0.45, 0.55, 0.45, 0.45, 0.35, 0.25, 0.89 }, ///< Smooth
690
{ 0.85, 0.80, 0.70, 0.45, 0.45, 0.35, 1.825 }, ///< Rough 1.825
691
{ 0.95, 0.85, 0.80, 0.55, 0.55, 0.45, 2.245 } //< Very Rough 2.25
695
728
* The Perlin Noise calculation using large primes
696
729
* The initial number is adjusted by two values; the generation_seed, and the
787
/** A small helper function */
820
/** A small helper function to initialize the terrain */
788
821
static void TgenSetTileHeight(TileIndex tile, int height)
790
823
SetTileHeight(tile, height);
791
MakeClear(tile, CLEAR_GRASS, 3);
825
/* Only clear the tiles within the map area. */
826
if (TileX(tile) != MapMaxX() && TileY(tile) != MapMaxY() &&
827
(!_settings_game.construction.freeform_edges || (TileX(tile) != 0 && TileY(tile) != 0))) {
828
MakeClear(tile, CLEAR_GRASS, 3);
814
852
IncreaseGeneratingWorldProgress(GWP_LANDSCAPE);
854
/* First make sure the tiles at the north border are void tiles if needed. */
855
if (_settings_game.construction.freeform_edges) {
856
for (y = 0; y < _height_map.size_y - 1; y++) MakeVoid(_height_map.size_x * y);
857
for (x = 0; x < _height_map.size_x; x++) MakeVoid(x);
816
860
/* Transfer height map into OTTD map */
817
for (y = 2; y < _height_map.size_y - 2; y++) {
818
for (x = 2; x < _height_map.size_x - 2; x++) {
819
int height = H2I(HeightMapXY(x, y));
861
for (y = 0; y < _height_map.size_y; y++) {
862
for (x = 0; x < _height_map.size_x; x++) {
863
int height = H2I(_height_map.height(x, y));
820
864
if (height < 0) height = 0;
821
865
if (height > 15) height = 15;
822
866
TgenSetTileHeight(TileXY(x, y), height);