154 static const int height_decimal_bits = 4;
158 static const int amplitude_decimal_bits = 10;
163 std::vector<Height> h;
178 return h[x + y * dim_x];
186 #define I2H(i) ((i) << height_decimal_bits)
188 #define H2I(i) ((i) >> height_decimal_bits)
191 #define A2I(i) ((i) >> amplitude_decimal_bits)
194 #define A2H(a) ((a) >> (amplitude_decimal_bits - height_decimal_bits))
229 { 3, 3, 3, 3, 4, 5, 7 },
230 { 5, 7, 8, 9, 14, 19, 31 },
231 { 8, 9, 10, 15, 23, 37, 61 },
232 { 10, 11, 17, 19, 49, 63, 73 },
233 { 12, 19, 25, 31, 67, 75, 87 },
244 return I2H(max_height_from_table);
264 static const Amplitude amplitudes[][7] = {
266 {16000, 5600, 1968, 688, 240, 16, 16},
267 {24000, 12800, 6400, 2700, 1024, 128, 16},
268 {32000, 19200, 12800, 8000, 3200, 256, 64},
269 {48000, 24000, 19200, 16000, 8000, 512, 320},
281 static const double extrapolation_factors[] = { 3.3, 2.8, 2.3, 1.8 };
286 int index = frequency -
MAX_TGP_FREQUENCIES +
static_cast<int>(std::size(amplitudes[smoothness]));
287 Amplitude amplitude = amplitudes[smoothness][std::max(0, index)];
288 if (index >= 0)
return amplitude;
291 double extrapolation_factor = extrapolation_factors[smoothness];
292 int height_range =
I2H(16);
294 amplitude = (
Amplitude)(extrapolation_factor * (
double)amplitude);
370 if (amplitude == 0)
continue;
376 for (
int y = 0; y <=
_height_map.size_y; y += step) {
377 for (
int x = 0; x <=
_height_map.size_x; x += step) {
388 for (
int y = 0; y <=
_height_map.size_y; y += 2 * step) {
389 for (
int x = 0; x <=
_height_map.size_x - 2 * step; x += 2 * step) {
392 Height h01 = (h00 + h02) / 2;
398 for (
int y = 0; y <=
_height_map.size_y - 2 * step; y += 2 * step) {
399 for (
int x = 0; x <=
_height_map.size_x; x += step) {
402 Height h10 = (h00 + h20) / 2;
408 for (
int y = 0; y <=
_height_map.size_y; y += step) {
409 for (
int x = 0; x <=
_height_map.size_x; x += step) {
419 Height h_min, h_max, h_avg;
425 if (h < h_min) h_min = h;
426 if (h > h_max) h_max = h;
434 if (min_ptr !=
nullptr) *min_ptr = h_min;
435 if (max_ptr !=
nullptr) *max_ptr = h_max;
436 if (avg_ptr !=
nullptr) *avg_ptr = h_avg;
442 int *hist = hist_buf - h_min;
459 if (h < h_min)
continue;
462 fheight = (double)(h - h_min) / (double)(h_max - h_min);
468 fheight = 2 * fheight - 1;
470 fheight = sin(fheight * M_PI_2);
472 fheight = 0.5 * (fheight + 1);
479 double sine_upper_limit = 0.75;
480 double linear_compression = 2;
481 if (fheight >= sine_upper_limit) {
483 fheight = 1.0 - (1.0 - fheight) / linear_compression;
485 double m = 1.0 - (1.0 - sine_upper_limit) / linear_compression;
487 fheight = 2.0 * fheight / sine_upper_limit - 1.0;
489 fheight = sin(fheight * M_PI_2);
491 fheight = 0.5 * (fheight + 1.0) * m;
500 double sine_lower_limit = 0.5;
501 double linear_compression = 2;
502 if (fheight <= sine_lower_limit) {
504 fheight = fheight / linear_compression;
506 double m = sine_lower_limit / linear_compression;
508 fheight = 2.0 * ((fheight - sine_lower_limit) / (1.0 - sine_lower_limit)) - 1.0;
510 fheight = sin(fheight * M_PI_2);
512 fheight = 0.5 * ((1.0 - m) * fheight + (1.0 + m));
522 h = (
Height)(fheight * (h_max - h_min) + h_min);
523 if (h < 0) h =
I2H(0);
524 if (h >= h_max) h = h_max - 1;
549 struct ControlPoint {
554 #define F(fraction) ((Height)(fraction * mh))
555 const ControlPoint curve_map_1[] = { { F(0.0), F(0.0) }, { F(0.8), F(0.13) }, { F(1.0), F(0.4) } };
556 const ControlPoint curve_map_2[] = { { F(0.0), F(0.0) }, { F(0.53), F(0.13) }, { F(0.8), F(0.27) }, { F(1.0), F(0.6) } };
557 const ControlPoint curve_map_3[] = { { F(0.0), F(0.0) }, { F(0.53), F(0.27) }, { F(0.8), F(0.57) }, { F(1.0), F(0.8) } };
558 const ControlPoint curve_map_4[] = { { F(0.0), F(0.0) }, { F(0.4), F(0.3) }, { F(0.7), F(0.8) }, { F(0.92), F(0.99) }, { F(1.0), F(0.99) } };
561 const std::span<const ControlPoint> curve_maps[] = { curve_map_1, curve_map_2, curve_map_3, curve_map_4 };
563 std::array<
Height, std::size(curve_maps)> ht{};
567 uint sx =
Clamp((
int)(((1 << level) * factor) + 0.5), 1, 128);
568 uint sy =
Clamp((
int)(((1 << level) / factor) + 0.5), 1, 128);
569 std::vector<uint8_t> c(
static_cast<size_t>(sx) * sy);
571 for (uint i = 0; i < sx * sy; i++) {
572 c[i] =
RandomRange(
static_cast<uint32_t
>(std::size(curve_maps)));
579 float fx = (float)(sx * x) /
_height_map.size_x + 1.0f;
582 float xr = 2.0f * (fx - x1) - 1.0f;
583 xr = sin(xr * M_PI_2);
584 xr = sin(xr * M_PI_2);
585 xr = 0.5f * (xr + 1.0f);
586 float xri = 1.0f - xr;
596 float fy = (float)(sy * y) /
_height_map.size_y + 1.0f;
599 float yr = 2.0f * (fy - y1) - 1.0f;
600 yr = sin(yr * M_PI_2);
601 yr = sin(yr * M_PI_2);
602 yr = 0.5f * (yr + 1.0f);
603 float yri = 1.0f - yr;
610 uint corner_a = c[x1 + sx * y1];
611 uint corner_b = c[x1 + sx * y2];
612 uint corner_c = c[x2 + sx * y1];
613 uint corner_d = c[x2 + sx * y2];
617 uint corner_bits = 0;
618 corner_bits |= 1 << corner_a;
619 corner_bits |= 1 << corner_b;
620 corner_bits |= 1 << corner_c;
621 corner_bits |= 1 << corner_d;
626 if (*h <
I2H(1))
continue;
632 for (
size_t t = 0; t < std::size(curve_maps); t++) {
633 if (!
HasBit(corner_bits,
static_cast<uint8_t
>(t)))
continue;
635 [[maybe_unused]]
bool found =
false;
636 auto &cm = curve_maps[t];
637 for (
size_t i = 0; i < cm.size() - 1; i++) {
638 const ControlPoint &p1 = cm[i];
639 const ControlPoint &p2 = cm[i + 1];
641 if (*h >= p1.x && *h < p2.x) {
642 ht[t] = p1.y + (*h - p1.x) * (p2.y - p1.y) / (p2.x - p1.x);
653 *h = (
Height)((ht[corner_a] * yri + ht[corner_b] * yr) * xri + (ht[corner_c] * yri + ht[corner_d] * yr) * xr);
664 Height h_min, h_max, h_avg, h_water_level;
665 int64_t water_tiles, desired_water_tiles;
671 std::vector<int> hist_buf(h_max - h_min + 1);
679 for (h_water_level = h_min, water_tiles = 0; h_water_level < h_max; h_water_level++) {
680 water_tiles += hist[h_water_level];
681 if (water_tiles >= desired_water_tiles)
break;
692 h = (
Height)(((
int)h_max_new) * (h - h_water_level) / (h_max - h_water_level)) +
I2H(1);
694 if (h < 0) h =
I2H(0);
695 if (h >= h_max_new) h = h_max_new - 1;
699 static double perlin_coast_noise_2D(
const double x,
const double y,
const double p,
const int prime);
724 const int margin = 4;
731 if (
HasBit(water_borders, BORDER_NE)) {
734 max_x = std::max((smallest_size * smallest_size / 64) + max_x, (smallest_size * smallest_size / 64) + margin - max_x);
735 if (smallest_size < 8 && max_x > 5) max_x /= 1.5;
736 for (x = 0; x < max_x; x++) {
741 if (
HasBit(water_borders, BORDER_SW)) {
744 max_x = std::max((smallest_size * smallest_size / 64) + max_x, (smallest_size * smallest_size / 64) + margin - max_x);
745 if (smallest_size < 8 && max_x > 5) max_x /= 1.5;
754 if (
HasBit(water_borders, BORDER_NW)) {
757 max_y = std::max((smallest_size * smallest_size / 64) + max_y, (smallest_size * smallest_size / 64) + margin - max_y);
758 if (smallest_size < 8 && max_y > 5) max_y /= 1.5;
759 for (y = 0; y < max_y; y++) {
764 if (
HasBit(water_borders, BORDER_SE)) {
767 max_y = std::max((smallest_size * smallest_size / 64) + max_y, (smallest_size * smallest_size / 64) + margin - max_y);
768 if (smallest_size < 8 && max_y > 5) max_y /= 1.5;
779 const int max_coast_dist_from_edge = 35;
780 const int max_coast_Smooth_depth = 35;
792 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++) {
805 for (depth = 0;
IsValidXY(x, y) && depth <= max_coast_Smooth_depth; depth++, x += dir_x, y += dir_y) {
807 h =
static_cast<Height>(std::min<uint>(h, h_prev + (4 + depth)));
838 for (
int y = 0; y <= (int)
_height_map.size_y; y++) {
839 for (
int x = 0; x <= (int)
_height_map.size_x; x++) {
869 if (water_borders == BORDERS_RANDOM) water_borders =
GB(Random(), 0, 4);
893 static double int_noise(
const long x,
const long y,
const int prime)
900 return 1.0 - (double)((n * (n * n * 15731 + 789221) + 1376312589) & 0x7fffffff) / 1073741824.0;
909 return a + x * (b - a);
919 const int integer_X = (int)x;
920 const int integer_Y = (int)y;
922 const double fractional_X = x - (double)integer_X;
923 const double fractional_Y = y - (double)integer_Y;
925 const double v1 =
int_noise(integer_X, integer_Y, prime);
926 const double v2 =
int_noise(integer_X + 1, integer_Y, prime);
927 const double v3 =
int_noise(integer_X, integer_Y + 1, prime);
928 const double v4 =
int_noise(integer_X + 1, integer_Y + 1, prime);
947 for (
int i = 0; i < 6; i++) {
948 const double frequency = (double)(1 << i);
949 const double amplitude = pow(p, (
double)i);
951 total +=
interpolated_noise((x * frequency) / 64.0, (y * frequency) / 64.0, prime) * amplitude;
constexpr debug_inline bool HasBit(const T x, const uint8_t y)
Checks if a bit in a value is set.
constexpr static debug_inline uint GB(const T x, const uint8_t s, const uint8_t n)
Fetch n bits from x, started at bit s.
Map accessors for 'clear' tiles.
void MakeClear(Tile t, ClearGround g, uint density)
Make a clear tile.
void GenerateWorldSetAbortCallback(GWAbortProc *proc)
Set here the function, if any, that you want to be called when landscape generation is aborted.
Functions related to world/map generation.
void IncreaseGeneratingWorldProgress(GenWorldProgress cls)
Increases the current stage of the world generation with one.
static const uint CUSTOM_SEA_LEVEL_NUMBER_DIFFICULTY
Value for custom sea level in difficulty settings.
@ GWP_LANDSCAPE
Create the landscape.
static const uint CUSTOM_TERRAIN_TYPE_NUMBER_DIFFICULTY
Value for custom terrain type in difficulty settings.
Types related to the landscape.
static debug_inline TileIndex TileXY(uint x, uint y)
Returns the TileIndex of a coordinate.
static const uint MIN_MAP_SIZE_BITS
Minimal and maximal map width and height.
static const uint MAX_MAP_SIZE_BITS
Maximal size of map is equal to 2 ^ MAX_MAP_SIZE_BITS.
constexpr T abs(const T a)
Returns the absolute value of (scalar) variable.
constexpr T Clamp(const T a, const T min, const T max)
Clamp a value between an interval.
Pseudo random number generator.
uint32_t RandomRange(uint32_t limit, const std::source_location location=std::source_location::current())
Pick a random number between 0 and limit - 1, inclusive.
A number of safeguards to prevent using unsafe methods.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition of base types and functions in a cross-platform compatible way.
bool freeform_edges
allow terraforming the tiles at the map edges
uint8_t map_height_limit
the maximum allowed heightlevel
uint8_t terrain_type
the mountainousness of the landscape
uint8_t quantity_sea_lakes
the amount of seas/lakes
uint8_t custom_sea_level
manually entered percentage of water in the map
uint8_t variety
variety level applied to TGP
uint8_t custom_terrain_type
manually entered height for TGP to aim for
uint8_t map_x
X size of map.
uint8_t landscape
the landscape we're currently in
uint8_t tgen_smoothness
how rough is the terrain from 0-3
uint8_t map_y
Y size of map.
uint32_t generation_seed
noise seed for world generation
uint8_t water_borders
bitset of the borders that are water
ConstructionSettings construction
construction of things in-game
DifficultySettings difficulty
settings related to the difficulty
GameCreationSettings game_creation
settings used during the creation of a game (map)
Height map - allocated array of heights (MapSizeX() + 1) x (MapSizeY() + 1)
Height & height(uint x, uint y)
Height map accessor.
static uint SizeY()
Get the size of the map along the Y.
static debug_inline uint SizeX()
Get the size of the map along the X.
static debug_inline uint LogX()
Logarithm of the map size along the X side.
static uint LogY()
Logarithm of the map size along the y side.
static void HeightMapSmoothCoastInDirection(int org_x, int org_y, int dir_x, int dir_y)
Start at given point, move in given direction, find and Smooth coast in that direction.
static void HeightMapSmoothCoasts(uint8_t water_borders)
Smooth coasts by modulating height of tiles close to map edges with cosine of distance from edge.
static void HeightMapGenerate()
Base Perlin noise generator - fills height map with raw Perlin noise.
static double linear_interpolate(const double a, const double b, const double x)
This routine determines the interpolated value between a and b.
static int * HeightMapMakeHistogram(Height h_min, [[maybe_unused]] Height h_max, int *hist_buf)
Dill histogram and return pointer to its base point - to the count of zero heights.
static void HeightMapAdjustWaterLevel(Amplitude water_percent, Height h_max_new)
Adjusts heights in height map to contain required amount of water tiles.
static Height TGPGetMaxHeight()
Gets the maximum allowed height while generating a map based on mapsize, terraintype,...
static bool AllocHeightMap()
Allocate array of (MapSizeX()+1)*(MapSizeY()+1) heights and init the _height_map structure members.
#define I2H(i)
Conversion: int to Height.
static const Amplitude _water_percent[4]
Desired water percentage (100% == 1024) - indexed by _settings_game.difficulty.quantity_sea_lakes.
static void HeightMapGetMinMaxAvg(Height *min_ptr, Height *max_ptr, Height *avg_ptr)
Returns min, max and average height from height map.
static void HeightMapCoastLines(uint8_t water_borders)
This routine sculpts in from the edge a random amount, again a Perlin sequence, to avoid the rigid fl...
static void HeightMapSmoothSlopes(Height dh_max)
This routine provides the essential cleanup necessary before OTTD can display the terrain.
static Height RandomHeight(Amplitude rMax)
Generates new random height in given amplitude (generated numbers will range from - amplitude to + am...
int16_t Height
Fixed point type for heights.
static Amplitude GetAmplitude(int frequency)
Get the amplitude associated with the currently selected smoothness and maximum height level.
static void FreeHeightMap()
Free height map.
int Amplitude
Fixed point array for amplitudes (and percent values)
uint GetEstimationTGPMapHeight()
Get an overestimation of the highest peak TGP wants to generate.
static void HeightMapSineTransform(Height h_min, Height h_max)
Applies sine wave redistribution onto height map.
static HeightMap _height_map
Global height map instance.
#define A2H(a)
Conversion: Amplitude to Height.
static void HeightMapNormalize()
Height map terraform post processing:
static bool IsValidXY(int x, int y)
Check if a X/Y set are within the map.
static const int MAX_TGP_FREQUENCIES
Maximum number of TGP noise frequencies.
static double perlin_coast_noise_2D(const double x, const double y, const double p, const int prime)
This is a similar function to the main perlin noise calculation, but uses the value p passed as a par...
static void TgenSetTileHeight(TileIndex tile, int height)
A small helper function to initialize the terrain.
void GenerateTerrainPerlin()
The main new land generator using Perlin noise.
#define H2I(i)
Conversion: Height to int.
static double interpolated_noise(const double x, const double y, const int prime)
This routine returns the smoothed interpolated noise for an x and y, using the values from the surrou...
static double int_noise(const long x, const long y, const int prime)
The Perlin Noise calculation using large primes The initial number is adjusted by two values; the gen...
#define A2I(i)
Conversion: Amplitude to int.
static void HeightMapCurves(uint level)
Additional map variety is provided by applying different curve maps to different parts of the map.
bool IsInnerTile(Tile tile)
Check if a tile is within the map (not a border)
void SetTileHeight(Tile tile, uint height)
Sets the height of a tile.
Map accessors for void tiles.
void MakeVoid(Tile t)
Make a nice void tile ;)