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 */
IsValidHeightmapDimension(size_t width,size_t height)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 */
RGBToGrayscale(byte red,byte green,byte blue)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 */
ReadHeightmapPNGImageData(byte * map,png_structp png_ptr,png_infop info_ptr)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 */
ReadHeightmapPNG(const char * filename,uint * x,uint * y,byte ** map)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 */
ReadHeightmapBMPImageData(byte * map,BmpInfo * info,BmpData * data)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 */
ReadHeightmapBMP(const char * filename,uint * x,uint * y,byte ** map)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 */
GrayscaleToMapHeights(uint img_width,uint img_height,byte * map)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 */
FixSlopes()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 */
ReadHeightMap(DetailedFileType dft,const char * filename,uint * x,uint * y,byte ** map)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 */
GetHeightmapDimensions(DetailedFileType dft,const char * filename,uint * x,uint * y)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 */
LoadHeightmap(DetailedFileType dft,const char * filename)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 */
FlatEmptyWorld(byte tile_height)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 }
556