src/heightmap.cpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   6  */
   7
   8 /** @file heightmap.cpp Creating of maps from heightmaps. */
   9
  10 #include "stdafx.h"
  11 #include "heightmap.h"
  12 #include "clear_map.h"
  13 #include "void_map.h"
  14 #include "error.h"
  15 #include "saveload/saveload.h"
  16 #include "bmp.h"
  17 #include "gfx_func.h"
  18 #include "fios.h"
  19 #include "fileio_func.h"
  20
  21 #include "table/strings.h"
  22
  23 #include "safeguards.h"
  24
  25 /**
  26  * Maximum number of pixels for one dimension of a heightmap image.
  27  * Do not allow images for which the longest side is twice the maximum number of
  28  * tiles along the longest side of the (tile) map.
  29  */
  30 static const uint MAX_HEIGHTMAP_SIDE_LENGTH_IN_PIXELS = 2 * MAX_MAP_SIZE;
  31
  32 /*
  33  * Maximum size in pixels of the heightmap image.
  34  */
  35 static const uint MAX_HEIGHTMAP_SIZE_PIXELS = 256 << 20; // ~256 million
  36 /*
  37  * When loading a PNG or BMP the 24 bpp variant requires at least 4 bytes per pixel
  38  * of memory to load the data. Make sure the "reasonable" limit is well within the
  39  * maximum amount of memory allocatable on 32 bit platforms.
  40  */
  41 static_assert(MAX_HEIGHTMAP_SIZE_PIXELS < UINT32_MAX / 8);
  42
  43 /**
  44  * Check whether the loaded dimension of the heightmap image are considered valid enough
  45  * to attempt to load the image. In other words, the width and height are not beyond the
  46  * #MAX_HEIGHTMAP_SIDE_LENGTH_IN_PIXELS limit and the total number of pixels does not
  47  * exceed #MAX_HEIGHTMAP_SIZE_PIXELS. A width or height less than 1 are disallowed too.
  48  * @param width The width of the to be loaded height map.
  49  * @param height The height of the to be loaded height map.
  50  * @return True iff the dimensions are within the limits.
  51  */
  52 static inline bool IsValidHeightmapDimension(size_t width, size_t height)
  53 {
  54         return (uint64)width * height <= MAX_HEIGHTMAP_SIZE_PIXELS &&
  55                 width > 0 && width <= MAX_HEIGHTMAP_SIDE_LENGTH_IN_PIXELS &&
  56                 height > 0 && height <= MAX_HEIGHTMAP_SIDE_LENGTH_IN_PIXELS;
  57 }
  58
  59 /**
  60  * Convert RGB colours to Grayscale using 29.9% Red, 58.7% Green, 11.4% Blue
  61  *  (average luminosity formula, NTSC Colour Space)
  62  */
  63 static inline byte RGBToGrayscale(byte red, byte green, byte blue)
  64 {
  65         /* To avoid doubles and stuff, multiply it with a total of 65536 (16bits), then
  66          *  divide by it to normalize the value to a byte again. */
  67         return ((red * 19595) + (green * 38470) + (blue * 7471)) / 65536;
  68 }
  69
  70
  71 #ifdef WITH_PNG
  72
  73 #include <png.h>
  74
  75 /**
  76  * The PNG Heightmap loader.
  77  */
  78 static void ReadHeightmapPNGImageData(byte *map, png_structp png_ptr, png_infop info_ptr)
  79 {
  80         uint x, y;
  81         byte gray_palette[256];
  82         png_bytep *row_pointers = nullptr;
  83         bool has_palette = png_get_color_type(png_ptr, info_ptr) == PNG_COLOR_TYPE_PALETTE;
  84         uint channels = png_get_channels(png_ptr, info_ptr);
  85
  86         /* Get palette and convert it to grayscale */
  87         if (has_palette) {
  88                 int i;
  89                 int palette_size;
  90                 png_color *palette;
  91                 bool all_gray = true;
  92
  93                 png_get_PLTE(png_ptr, info_ptr, &palette, &palette_size);
  94                 for (i = 0; i < palette_size && (palette_size != 16 || all_gray); i++) {
  95                         all_gray &= palette[i].red == palette[i].green && palette[i].red == palette[i].blue;
  96                         gray_palette[i] = RGBToGrayscale(palette[i].red, palette[i].green, palette[i].blue);
  97                 }
  98
  99                 /**
 100                  * For a non-gray palette of size 16 we assume that
 101                  * the order of the palette determines the height;
 102                  * the first entry is the sea (level 0), the second one
 103                  * level 1, etc.
 104                  */
 105                 if (palette_size == 16 && !all_gray) {
 106                         for (i = 0; i < palette_size; i++) {
 107                                 gray_palette[i] = 256 * i / palette_size;
 108                         }
 109                 }
 110         }
 111
 112         row_pointers = png_get_rows(png_ptr, info_ptr);
 113
 114         /* Read the raw image data and convert in 8-bit grayscale */
 115         for (x = 0; x < png_get_image_width(png_ptr, info_ptr); x++) {
 116                 for (y = 0; y < png_get_image_height(png_ptr, info_ptr); y++) {
 117                         byte *pixel = &map[y * png_get_image_width(png_ptr, info_ptr) + x];
 118                         uint x_offset = x * channels;
 119
 120                         if (has_palette) {
 121                                 *pixel = gray_palette[row_pointers[y][x_offset]];
 122                         } else if (channels == 3) {
 123                                 *pixel = RGBToGrayscale(row_pointers[y][x_offset + 0],
 124                                                 row_pointers[y][x_offset + 1], row_pointers[y][x_offset + 2]);
 125                         } else {
 126                                 *pixel = row_pointers[y][x_offset];
 127                         }
 128                 }
 129         }
 130 }
 131
 132 /**
 133  * Reads the heightmap and/or size of the heightmap from a PNG file.
 134  * If map == nullptr only the size of the PNG is read, otherwise a map
 135  * with grayscale pixels is allocated and assigned to *map.
 136  */
 137 static bool ReadHeightmapPNG(const char *filename, uint *x, uint *y, byte **map)
 138 {
 139         FILE *fp;
 140         png_structp png_ptr = nullptr;
 141         png_infop info_ptr  = nullptr;
 142
 143         fp = FioFOpenFile(filename, "rb", HEIGHTMAP_DIR);
 144         if (fp == nullptr) {
 145                 ShowErrorMessage(STR_ERROR_PNGMAP, STR_ERROR_PNGMAP_FILE_NOT_FOUND, WL_ERROR);
 146                 return false;
 147         }
 148
 149         png_ptr = png_create_read_struct(PNG_LIBPNG_VER_STRING, nullptr, nullptr, nullptr);
 150         if (png_ptr == nullptr) {
 151                 ShowErrorMessage(STR_ERROR_PNGMAP, STR_ERROR_PNGMAP_MISC, WL_ERROR);
 152                 fclose(fp);
 153                 return false;
 154         }
 155
 156         info_ptr = png_create_info_struct(png_ptr);
 157         if (info_ptr == nullptr || setjmp(png_jmpbuf(png_ptr))) {
 158                 ShowErrorMessage(STR_ERROR_PNGMAP, STR_ERROR_PNGMAP_MISC, WL_ERROR);
 159                 fclose(fp);
 160                 png_destroy_read_struct(&png_ptr, &info_ptr, nullptr);
 161                 return false;
 162         }
 163
 164         png_init_io(png_ptr, fp);
 165
 166         /* Allocate memory and read image, without alpha or 16-bit samples
 167          * (result is either 8-bit indexed/grayscale or 24-bit RGB) */
 168         png_set_packing(png_ptr);
 169         png_read_png(png_ptr, info_ptr, PNG_TRANSFORM_PACKING | PNG_TRANSFORM_STRIP_ALPHA | PNG_TRANSFORM_STRIP_16, nullptr);
 170
 171         /* Maps of wrong colour-depth are not used.
 172          * (this should have been taken care of by stripping alpha and 16-bit samples on load) */
 173         if ((png_get_channels(png_ptr, info_ptr) != 1) && (png_get_channels(png_ptr, info_ptr) != 3) && (png_get_bit_depth(png_ptr, info_ptr) != 8)) {
 174                 ShowErrorMessage(STR_ERROR_PNGMAP, STR_ERROR_PNGMAP_IMAGE_TYPE, WL_ERROR);
 175                 fclose(fp);
 176                 png_destroy_read_struct(&png_ptr, &info_ptr, nullptr);
 177                 return false;
 178         }
 179
 180         uint width = png_get_image_width(png_ptr, info_ptr);
 181         uint height = png_get_image_height(png_ptr, info_ptr);
 182
 183         if (!IsValidHeightmapDimension(width, height)) {
 184                 ShowErrorMessage(STR_ERROR_PNGMAP, STR_ERROR_HEIGHTMAP_TOO_LARGE, WL_ERROR);
 185                 fclose(fp);
 186                 png_destroy_read_struct(&png_ptr, &info_ptr, nullptr);
 187                 return false;
 188         }
 189
 190         if (map != nullptr) {
 191                 *map = MallocT<byte>(width * height);
 192                 ReadHeightmapPNGImageData(*map, png_ptr, info_ptr);
 193         }
 194
 195         *x = width;
 196         *y = height;
 197
 198         fclose(fp);
 199         png_destroy_read_struct(&png_ptr, &info_ptr, nullptr);
 200         return true;
 201 }
 202
 203 #endif /* WITH_PNG */
 204
 205
 206 /**
 207  * The BMP Heightmap loader.
 208  */
 209 static void ReadHeightmapBMPImageData(byte *map, BmpInfo *info, BmpData *data)
 210 {
 211         uint x, y;
 212         byte gray_palette[256];
 213
 214         if (data->palette != nullptr) {
 215                 uint i;
 216                 bool all_gray = true;
 217
 218                 if (info->palette_size != 2) {
 219                         for (i = 0; i < info->palette_size && (info->palette_size != 16 || all_gray); i++) {
 220                                 all_gray &= data->palette[i].r == data->palette[i].g && data->palette[i].r == data->palette[i].b;
 221                                 gray_palette[i] = RGBToGrayscale(data->palette[i].r, data->palette[i].g, data->palette[i].b);
 222                         }
 223
 224                         /**
 225                          * For a non-gray palette of size 16 we assume that
 226                          * the order of the palette determines the height;
 227                          * the first entry is the sea (level 0), the second one
 228                          * level 1, etc.
 229                          */
 230                         if (info->palette_size == 16 && !all_gray) {
 231                                 for (i = 0; i < info->palette_size; i++) {
 232                                         gray_palette[i] = 256 * i / info->palette_size;
 233                                 }
 234                         }
 235                 } else {
 236                         /**
 237                          * For a palette of size 2 we assume that the order of the palette determines the height;
 238                          * the first entry is the sea (level 0), the second one is the land (level 1)
 239                          */
 240                         gray_palette[0] = 0;
 241                         gray_palette[1] = 16;
 242                 }
 243         }
 244
 245         /* Read the raw image data and convert in 8-bit grayscale */
 246         for (y = 0; y < info->height; y++) {
 247                 byte *pixel = &map[y * info->width];
 248                 byte *bitmap = &data->bitmap[y * info->width * (info->bpp == 24 ? 3 : 1)];
 249
 250                 for (x = 0; x < info->width; x++) {
 251                         if (info->bpp != 24) {
 252                                 *pixel++ = gray_palette[*bitmap++];
 253                         } else {
 254                                 *pixel++ = RGBToGrayscale(*bitmap, *(bitmap + 1), *(bitmap + 2));
 255                                 bitmap += 3;
 256                         }
 257                 }
 258         }
 259 }
 260
 261 /**
 262  * Reads the heightmap and/or size of the heightmap from a BMP file.
 263  * If map == nullptr only the size of the BMP is read, otherwise a map
 264  * with grayscale pixels is allocated and assigned to *map.
 265  */
 266 static bool ReadHeightmapBMP(const char *filename, uint *x, uint *y, byte **map)
 267 {
 268         FILE *f;
 269         BmpInfo info;
 270         BmpData data;
 271         BmpBuffer buffer;
 272
 273         /* Init BmpData */
 274         memset(&data, 0, sizeof(data));
 275
 276         f = FioFOpenFile(filename, "rb", HEIGHTMAP_DIR);
 277         if (f == nullptr) {
 278                 ShowErrorMessage(STR_ERROR_BMPMAP, STR_ERROR_PNGMAP_FILE_NOT_FOUND, WL_ERROR);
 279                 return false;
 280         }
 281
 282         BmpInitializeBuffer(&buffer, f);
 283
 284         if (!BmpReadHeader(&buffer, &info, &data)) {
 285                 ShowErrorMessage(STR_ERROR_BMPMAP, STR_ERROR_BMPMAP_IMAGE_TYPE, WL_ERROR);
 286                 fclose(f);
 287                 BmpDestroyData(&data);
 288                 return false;
 289         }
 290
 291         if (!IsValidHeightmapDimension(info.width, info.height)) {
 292                 ShowErrorMessage(STR_ERROR_BMPMAP, STR_ERROR_HEIGHTMAP_TOO_LARGE, WL_ERROR);
 293                 fclose(f);
 294                 BmpDestroyData(&data);
 295                 return false;
 296         }
 297
 298         if (map != nullptr) {
 299                 if (!BmpReadBitmap(&buffer, &info, &data)) {
 300                         ShowErrorMessage(STR_ERROR_BMPMAP, STR_ERROR_BMPMAP_IMAGE_TYPE, WL_ERROR);
 301                         fclose(f);
 302                         BmpDestroyData(&data);
 303                         return false;
 304                 }
 305
 306                 *map = MallocT<byte>(info.width * info.height);
 307                 ReadHeightmapBMPImageData(*map, &info, &data);
 308         }
 309
 310         BmpDestroyData(&data);
 311
 312         *x = info.width;
 313         *y = info.height;
 314
 315         fclose(f);
 316         return true;
 317 }
 318
 319 /**
 320  * Converts a given grayscale map to something that fits in OTTD map system
 321  * and create a map of that data.
 322  * @param img_width  the with of the image in pixels/tiles
 323  * @param img_height the height of the image in pixels/tiles
 324  * @param map        the input map
 325  */
 326 static void GrayscaleToMapHeights(uint img_width, uint img_height, byte *map)
 327 {
 328         /* Defines the detail of the aspect ratio (to avoid doubles) */
 329         const uint num_div = 16384;
 330         /* Ensure multiplication with num_div does not cause overflows. */
 331         static_assert(num_div <= std::numeric_limits<uint>::max() / MAX_HEIGHTMAP_SIDE_LENGTH_IN_PIXELS);
 332
 333         uint width, height;
 334         uint row, col;
 335         uint row_pad = 0, col_pad = 0;
 336         uint img_scale;
 337         uint img_row, img_col;
 338         TileIndex tile;
 339
 340         /* Get map size and calculate scale and padding values */
 341         switch (_settings_game.game_creation.heightmap_rotation) {
 342                 default: NOT_REACHED();
 343                 case HM_COUNTER_CLOCKWISE:
 344                         width   = MapSizeX();
 345                         height  = MapSizeY();
 346                         break;
 347                 case HM_CLOCKWISE:
 348                         width   = MapSizeY();
 349                         height  = MapSizeX();
 350                         break;
 351         }
 352
 353         if ((img_width * num_div) / img_height > ((width * num_div) / height)) {
 354                 /* Image is wider than map - center vertically */
 355                 img_scale = (width * num_div) / img_width;
 356                 row_pad = (1 + height - ((img_height * img_scale) / num_div)) / 2;
 357         } else {
 358                 /* Image is taller than map - center horizontally */
 359                 img_scale = (height * num_div) / img_height;
 360                 col_pad = (1 + width - ((img_width * img_scale) / num_div)) / 2;
 361         }
 362
 363         if (_settings_game.construction.freeform_edges) {
 364                 for (uint x = 0; x < MapSizeX(); x++) MakeVoid(TileXY(x, 0));
 365                 for (uint y = 0; y < MapSizeY(); y++) MakeVoid(TileXY(0, y));
 366         }
 367
 368         /* Form the landscape */
 369         for (row = 0; row < height; row++) {
 370                 for (col = 0; col < width; col++) {
 371                         switch (_settings_game.game_creation.heightmap_rotation) {
 372                                 default: NOT_REACHED();
 373                                 case HM_COUNTER_CLOCKWISE: tile = TileXY(col, row); break;
 374                                 case HM_CLOCKWISE:         tile = TileXY(row, col); break;
 375                         }
 376
 377                         /* Check if current tile is within the 1-pixel map edge or padding regions */
 378                         if ((!_settings_game.construction.freeform_edges && DistanceFromEdge(tile) <= 1) ||
 379                                         (row < row_pad) || (row >= (height - row_pad - (_settings_game.construction.freeform_edges ? 0 : 1))) ||
 380                                         (col < col_pad) || (col >= (width  - col_pad - (_settings_game.construction.freeform_edges ? 0 : 1)))) {
 381                                 SetTileHeight(tile, 0);
 382                         } else {
 383                                 /* Use nearest neighbour resizing to scale map data.
 384                                  *  We rotate the map 45 degrees (counter)clockwise */
 385                                 img_row = (((row - row_pad) * num_div) / img_scale);
 386                                 switch (_settings_game.game_creation.heightmap_rotation) {
 387                                         default: NOT_REACHED();
 388                                         case HM_COUNTER_CLOCKWISE:
 389                                                 img_col = (((width - 1 - col - col_pad) * num_div) / img_scale);
 390                                                 break;
 391                                         case HM_CLOCKWISE:
 392                                                 img_col = (((col - col_pad) * num_div) / img_scale);
 393                                                 break;
 394                                 }
 395
 396                                 assert(img_row < img_height);
 397                                 assert(img_col < img_width);
 398
 399                                 uint heightmap_height = map[img_row * img_width + img_col];
 400
 401                                 if (heightmap_height > 0) {
 402                                         /* 0 is sea level.
 403                                          * Other grey scales are scaled evenly to the available height levels > 0.
 404                                          * (The coastline is independent from the number of height levels) */
 405                                         heightmap_height = 1 + (heightmap_height - 1) * _settings_game.game_creation.heightmap_height / 255;
 406                                 }
 407
 408                                 SetTileHeight(tile, heightmap_height);
 409                         }
 410                         /* Only clear the tiles within the map area. */
 411                         if (IsInnerTile(tile)) {
 412                                 MakeClear(tile, CLEAR_GRASS, 3);
 413                         }
 414                 }
 415         }
 416 }
 417
 418 /**
 419  * This function takes care of the fact that land in OpenTTD can never differ
 420  * more than 1 in height
 421  */
 422 void FixSlopes()
 423 {
 424         uint width, height;
 425         int row, col;
 426         byte current_tile;
 427
 428         /* Adjust height difference to maximum one horizontal/vertical change. */
 429         width   = MapSizeX();
 430         height  = MapSizeY();
 431
 432         /* Top and left edge */
 433         for (row = 0; (uint)row < height; row++) {
 434                 for (col = 0; (uint)col < width; col++) {
 435                         current_tile = MAX_TILE_HEIGHT;
 436                         if (col != 0) {
 437                                 /* Find lowest tile; either the top or left one */
 438                                 current_tile = TileHeight(TileXY(col - 1, row)); // top edge
 439                         }
 440                         if (row != 0) {
 441                                 if (TileHeight(TileXY(col, row - 1)) < current_tile) {
 442                                         current_tile = TileHeight(TileXY(col, row - 1)); // left edge
 443                                 }
 444                         }
 445
 446                         /* Does the height differ more than one? */
 447                         if (TileHeight(TileXY(col, row)) >= (uint)current_tile + 2) {
 448                                 /* Then change the height to be no more than one */
 449                                 SetTileHeight(TileXY(col, row), current_tile + 1);
 450                         }
 451                 }
 452         }
 453
 454         /* Bottom and right edge */
 455         for (row = height - 1; row >= 0; row--) {
 456                 for (col = width - 1; col >= 0; col--) {
 457                         current_tile = MAX_TILE_HEIGHT;
 458                         if ((uint)col != width - 1) {
 459                                 /* Find lowest tile; either the bottom and right one */
 460                                 current_tile = TileHeight(TileXY(col + 1, row)); // bottom edge
 461                         }
 462
 463                         if ((uint)row != height - 1) {
 464                                 if (TileHeight(TileXY(col, row + 1)) < current_tile) {
 465                                         current_tile = TileHeight(TileXY(col, row + 1)); // right edge
 466                                 }
 467                         }
 468
 469                         /* Does the height differ more than one? */
 470                         if (TileHeight(TileXY(col, row)) >= (uint)current_tile + 2) {
 471                                 /* Then change the height to be no more than one */
 472                                 SetTileHeight(TileXY(col, row), current_tile + 1);
 473                         }
 474                 }
 475         }
 476 }
 477
 478 /**
 479  * Reads the heightmap with the correct file reader.
 480  * @param dft Type of image file.
 481  * @param filename Name of the file to load.
 482  * @param[out] x Length of the image.
 483  * @param[out] y Height of the image.
 484  * @param[in,out] map If not \c nullptr, destination to store the loaded block of image data.
 485  * @return Whether loading was successful.
 486  */
 487 static bool ReadHeightMap(DetailedFileType dft, const char *filename, uint *x, uint *y, byte **map)
 488 {
 489         switch (dft) {
 490                 default:
 491                         NOT_REACHED();
 492
 493 #ifdef WITH_PNG
 494                 case DFT_HEIGHTMAP_PNG:
 495                         return ReadHeightmapPNG(filename, x, y, map);
 496 #endif /* WITH_PNG */
 497
 498                 case DFT_HEIGHTMAP_BMP:
 499                         return ReadHeightmapBMP(filename, x, y, map);
 500         }
 501 }
 502
 503 /**
 504  * Get the dimensions of a heightmap.
 505  * @param dft Type of image file.
 506  * @param filename to query
 507  * @param x dimension x
 508  * @param y dimension y
 509  * @return Returns false if loading of the image failed.
 510  */
 511 bool GetHeightmapDimensions(DetailedFileType dft, const char *filename, uint *x, uint *y)
 512 {
 513         return ReadHeightMap(dft, filename, x, y, nullptr);
 514 }
 515
 516 /**
 517  * Load a heightmap from file and change the map in its current dimensions
 518  *  to a landscape representing the heightmap.
 519  * It converts pixels to height. The brighter, the higher.
 520  * @param dft Type of image file.
 521  * @param filename of the heightmap file to be imported
 522  */
 523 void LoadHeightmap(DetailedFileType dft, const char *filename)
 524 {
 525         uint x, y;
 526         byte *map = nullptr;
 527
 528         if (!ReadHeightMap(dft, filename, &x, &y, &map)) {
 529                 free(map);
 530                 return;
 531         }
 532
 533         GrayscaleToMapHeights(x, y, map);
 534         free(map);
 535
 536         FixSlopes();
 537         MarkWholeScreenDirty();
 538 }
 539
 540 /**
 541  * Make an empty world where all tiles are of height 'tile_height'.
 542  * @param tile_height of the desired new empty world
 543  */
 544 void FlatEmptyWorld(byte tile_height)
 545 {
 546         int edge_distance = _settings_game.construction.freeform_edges ? 0 : 2;
 547         for (uint row = edge_distance; row < MapSizeY() - edge_distance; row++) {
 548                 for (uint col = edge_distance; col < MapSizeX() - edge_distance; col++) {
 549                         SetTileHeight(TileXY(col, row), tile_height);
 550                 }
 551         }
 552
 553         FixSlopes();
 554         MarkWholeScreenDirty();
 555 }