WIP heightmap.cpp

/*
 * This file is part of OpenTTD.
 * 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.
 * 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.
 * 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/>.
 */

/** @file heightmap.cpp Creating of maps from heightmaps. */

#include "stdafx.h"
#include "heightmap.h"
#include "clear_map.h"
#include "void_map.h"
#include "error.h"
#include "saveload/saveload.h"
#include "bmp.h"
#include "gfx_func.h"
#include "fios.h"
#include "fileio_func.h"
#include "core/random_func.hpp"

#include "table/strings.h"

#include "safeguards.h"

#include <vector>

namespace openttd
{
    // vector of 8-bit word per pixel linear bitmaps
    using bitmaps8_t = std::vector<std::vector<byte>>;
}

/**
 * Convert RGB colours to Grayscale using 29.9% Red, 58.7% Green, 11.4% Blue
 *  (average luminosity formula, NTSC Colour Space)
 */
static inline byte RGBToGrayscale(byte red, byte green, byte blue)
{
    /* To avoid doubles and stuff, multiply it with a total of 65536 (16bits), then
     *  divide by it to normalize the value to a byte again. */
    return ((red * 19595) + (green * 38470) + (blue * 7471)) / 65536;
}


#ifdef WITH_PNG

#include <png.h>

template <typename T, typename OP>
void copy_bitmap_data_from_rows(openttd::bitmaps8_t &maps, const uint channels,
    const png_uint_32 width, const png_uint_32 height,
    png_bytep *row_pointers, OP &transform_operator)
{
    if (transform_operator.needs_measurement()) {
        for (uint y = 0; y < height; y++) {
            const T *row_ptr = (const T *)row_pointers[y];
            for (uint x = 0; x < width; x++) {
                for (uint i = 0; i < channels; i++) {
                    transform_operator.measure(i, x, y, *row_ptr);
                    row_ptr++;
                }
            }
        }
    }

    uint dest_offset = 0;
    for (uint y = 0; y < height; y++) {
        const T *row_ptr = (const T *)row_pointers[y];
        for (uint x = 0; x < width; x++) {
            for (uint i = 0; i < channels; i++) {
                maps[i][dest_offset] = transform_operator(i, x, y, *row_ptr);
                row_ptr++;
            }
            dest_offset++;
        }
    }
}

// data-type transform operator functor
//
struct toperator_t
{
    // pure overloads, NO VIRTUAL
    toperator_t() {}
    bool needs_measurement() { return false; }
    void measure(uint i, uint x, uint y, byte z) {}
    byte operator()(uint i, uint x, uint y, byte z) { return 0; }
};

// 8-bit input, do nothing (copy)
struct toperator_8bit_copy_t : toperator_t
{
    toperator_8bit_copy_t() : min_z(256), max_z(0) {}
    bool needs_measurement() { return false; }
    void measure(uint i, uint x, uint y, byte z)
    {
        if (i == 0) {
            if (z > max_z) {
                max_z = z;
            } else if (z < min_z) {
                min_z = z;
            }
        }
    }
    byte operator()(uint i, uint x, uint y, byte z)
    {
        if (z > min_z) {
            //float normalized = float(z - min_z) / float(max_z - min_z);
            //int out_z = z;//1 + int(normalized * 254.0f + 0.5f);
            //assert(out_z >= 0 && out_z < 256);
            return z;
        }
        return 0;
    }
    int min_z;
    int max_z;
};

// 8-bit index, translate via palette table
struct toperator_8bit_indexed_t : toperator_t
{
    toperator_8bit_indexed_t(byte *palette_ptr) : palette(palette_ptr) {}
    byte operator()(uint i, uint x, uint y, byte z)
    {
        return palette[z];
    }
    byte *palette;
};

// conditionally limit to inclusive range
template <typename T>
T limit_inclusive(T x, T minimum, T maximum)
{
    return x < minimum ? minimum : x > maximum ? maximum : x;
}

// MSB/LSB first conversion
std::uint16_t flip_endian(std::uint16_t x)
{
    return ((x >> 8) & 0xFF) | ((x << 8) & 0xFF00);
}

struct minmax_t
{
    minmax_t() : min(INT_MAX), max(INT_MIN)
    {
    }
    void operator()(int x)
    {
        if (x > max) {
            max = x;
        }
        if (x < min) {
            min = x;
        }
    }
    int min;
    int max;
};

// 16-bit input, limit range
template <typename T>
struct toperator_16bit_copy_t : toperator_t
{
    toperator_16bit_copy_t() : neg_z(32767) {}
    bool needs_measurement() { return false; }
    void measure(uint i, uint x, uint y, T z)
    {
        // PNG 16-bit is MSB first
        z = flip_endian(z);
        switch (i) {
            case 0:
                if (z < 32768) {
                    mm[i](z);
                }
                if (z < neg_z) {
                    neg_z = z;
                }
                break;

            case 1:
            case 2:
                mm[i](z);
                break;
        }
    }

    byte operator()(uint i, uint x, uint y, T z)
    {
        // PNG 16-bit is MSB first
        z = flip_endian(z);
        if (i == 0) {
            if (z > 0) {
#if _DEBUG && 0
                if (z < 0 || z > 255) {
                    __debugbreak();
                }
#endif
                //float normalized = float(z - min_z) / float(max_z - min_z);
                //int out_z = 1 + int(normalized * 254.0f + 0.5f);
                const int scaled_height = 1 + ((z - 1) * _settings_game.construction.max_heightlevel) / 255;
                return limit_inclusive<T>(scaled_height, 1, 255);

                //return limit_inclusive<T>(z, 0, 255);
            }
            return 0;
        } else {
            return limit_inclusive<T>(z, 0, 255);
        }
    }
    int neg_z;
    minmax_t mm[3];
};

/**
 * The PNG Heightmap loader.
 */
static void ReadHeightmapPNGImageData(openttd::bitmaps8_t &maps, png_structp png_ptr, png_infop info_ptr)
{
    byte gray_palette[256];
    png_bytep *row_pointers = nullptr;
    bool has_palette = png_get_color_type(png_ptr, info_ptr) == PNG_COLOR_TYPE_PALETTE;
    uint channels = png_get_channels(png_ptr, info_ptr);

    const png_uint_32 width = png_get_image_width(png_ptr, info_ptr);
    const png_uint_32 height = png_get_image_height(png_ptr, info_ptr);

    /* Get palette and convert it to grayscale */
    if (has_palette) {
        int i;
        int palette_size;
        png_color *palette;
        bool all_gray = true;

        png_get_PLTE(png_ptr, info_ptr, &palette, &palette_size);
        for (i = 0; i < palette_size && (palette_size != 16 || all_gray); i++) {
            all_gray &= palette[i].red == palette[i].green && palette[i].red == palette[i].blue;
            gray_palette[i] = RGBToGrayscale(palette[i].red, palette[i].green, palette[i].blue);
        }

        /**
         * For a non-gray palette of size 16 we assume that
         * the order of the palette determines the height;
         * the first entry is the sea (level 0), the second one
         * level 1, etc.
         */
        if (palette_size == 16 && !all_gray) {
            for (i = 0; i < palette_size; i++) {
                gray_palette[i] = 256 * i / palette_size;
            }
        }
    }

    row_pointers = png_get_rows(png_ptr, info_ptr);

    if (has_palette) {
        switch (png_get_bit_depth(png_ptr, info_ptr)) {
            case 8:
                copy_bitmap_data_from_rows<byte>(maps, channels, width, height, row_pointers,
                    toperator_8bit_indexed_t(gray_palette));
                break;

            default:
                // failure, unhandled bit depth
                __debugbreak();
                break;
        }
    } else {
        switch (png_get_bit_depth(png_ptr, info_ptr)) {
            case 16:
                copy_bitmap_data_from_rows<std::uint16_t>(maps, channels, width, height, row_pointers,
                    toperator_16bit_copy_t<std::uint16_t>());
                break;

            case 8:
                copy_bitmap_data_from_rows<byte>(maps, channels, width, height, row_pointers,
                    toperator_8bit_copy_t());
                break;

            default:
                // failure, unhandled bit depth
                __debugbreak();
                break;
        }
    }
}

/**
 * Reads the heightmap and/or size of the heightmap from a PNG file.
 * If map == nullptr only the size of the PNG is read, otherwise a map
 * with grayscale pixels is allocated and assigned to *map.
 */
static bool ReadHeightmapPNG(const char *filename, uint *x, uint *y, openttd::bitmaps8_t *maps_ptr)
{
    FILE *fp;
    png_structp png_ptr = nullptr;
    png_infop info_ptr  = nullptr;

    fp = FioFOpenFile(filename, "rb", HEIGHTMAP_DIR);
    if (fp == nullptr) {
        ShowErrorMessage(STR_ERROR_PNGMAP, STR_ERROR_PNGMAP_FILE_NOT_FOUND, WL_ERROR);
        return false;
    }

    png_ptr = png_create_read_struct(PNG_LIBPNG_VER_STRING, nullptr, nullptr, nullptr);
    if (png_ptr == nullptr) {
        ShowErrorMessage(STR_ERROR_PNGMAP, STR_ERROR_PNGMAP_MISC, WL_ERROR);
        fclose(fp);
        return false;
    }

    info_ptr = png_create_info_struct(png_ptr);
    if (info_ptr == nullptr || setjmp(png_jmpbuf(png_ptr))) {
        ShowErrorMessage(STR_ERROR_PNGMAP, STR_ERROR_PNGMAP_MISC, WL_ERROR);
        fclose(fp);
        png_destroy_read_struct(&png_ptr, &info_ptr, nullptr);
        return false;
    }

    png_init_io(png_ptr, fp);

    /* Allocate memory and read image, without alpha or 16-bit samples
     * (result is either 8-bit indexed/grayscale or 24-bit RGB) */
    png_set_packing(png_ptr);
    png_read_png(png_ptr, info_ptr, PNG_TRANSFORM_PACKING, nullptr);

    const png_byte channels = png_get_channels(png_ptr, info_ptr);

#if 0
    /* Maps of wrong colour-depth are not used.
     * (this should have been taken care of by stripping alpha and 16-bit samples on load) */
    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)) {
        ShowErrorMessage(STR_ERROR_PNGMAP, STR_ERROR_PNGMAP_IMAGE_TYPE, WL_ERROR);
        fclose(fp);
        png_destroy_read_struct(&png_ptr, &info_ptr, nullptr);
        return false;
    }
#endif

    uint width = png_get_image_width(png_ptr, info_ptr);
    uint height = png_get_image_height(png_ptr, info_ptr);

    /* Check if image dimensions don't overflow a size_t to avoid memory corruption. */
    if ((uint64)width * height >= (size_t)-1) {
        ShowErrorMessage(STR_ERROR_PNGMAP, STR_ERROR_HEIGHTMAP_TOO_LARGE, WL_ERROR);
        fclose(fp);
        png_destroy_read_struct(&png_ptr, &info_ptr, nullptr);
        return false;
    }

    if (maps_ptr != nullptr) {
        openttd::bitmaps8_t &maps = *maps_ptr;
        maps.reserve(channels);
        maps.resize(channels);
        for (int i = 0; i < maps.size(); i++) {
            maps[i].reserve(width * height);
            maps[i].resize(width * height);
        }
        ReadHeightmapPNGImageData(maps, png_ptr, info_ptr);
    }

    *x = width;
    *y = height;

    fclose(fp);
    png_destroy_read_struct(&png_ptr, &info_ptr, nullptr);
    return true;
}

#endif /* WITH_PNG */


/**
 * The BMP Heightmap loader.
 */
static void ReadHeightmapBMPImageData(openttd::bitmaps8_t &maps, BmpInfo *info, BmpData *data)
{
    uint x, y;
    byte gray_palette[256];

    assert(maps.size() > 0);

    if (data->palette != nullptr) {
        uint i;
        bool all_gray = true;

        if (info->palette_size != 2) {
            for (i = 0; i < info->palette_size && (info->palette_size != 16 || all_gray); i++) {
                all_gray &= data->palette[i].r == data->palette[i].g && data->palette[i].r == data->palette[i].b;
                gray_palette[i] = RGBToGrayscale(data->palette[i].r, data->palette[i].g, data->palette[i].b);
            }

            /**
             * For a non-gray palette of size 16 we assume that
             * the order of the palette determines the height;
             * the first entry is the sea (level 0), the second one
             * level 1, etc.
             */
            if (info->palette_size == 16 && !all_gray) {
                for (i = 0; i < info->palette_size; i++) {
                    gray_palette[i] = 256 * i / info->palette_size;
                }
            }
        } else {
            /**
             * For a palette of size 2 we assume that the order of the palette determines the height;
             * the first entry is the sea (level 0), the second one is the land (level 1)
             */
            gray_palette[0] = 0;
            gray_palette[1] = 16;
        }
    }

    /* Read the raw image data and convert in 8-bit grayscale */
    for (y = 0; y < info->height; y++) {
        byte *pixel = &maps[0][y * info->width];
        byte *bitmap = &data->bitmap[y * info->width * (info->bpp == 24 ? 3 : 1)];

        if (info->bpp == 24) {
            for (x = 0; x < info->width; x++) {
                *pixel = RGBToGrayscale(*bitmap, *(bitmap + 1), *(bitmap + 2));
                pixel++;
                bitmap += 3;
            }
        } else if (info->bpp == 8) {
            for (x = 0; x < info->width; x++) {
                *pixel = gray_palette[*bitmap];
                pixel++;
                bitmap++;
            }
        } else {
            // no implementation for other (4-bit, ...) bitmaps
            assert(false);
        }
    }
}

/**
 * Reads the heightmap and/or size of the heightmap from a BMP file.
 * If maps_array == nullptr only the size of the BMP is read, otherwise a map
 * with grayscale pixels is allocated and assigned to each element of maps_array[maps].
 */
static bool ReadHeightmapBMP(const char *filename, uint *x, uint *y, openttd::bitmaps8_t *maps_ptr)
{
    FILE *f;
    BmpInfo info;
    BmpData data;
    BmpBuffer buffer;

    /* Init BmpData */
    memset(&data, 0, sizeof(data));

    f = FioFOpenFile(filename, "rb", HEIGHTMAP_DIR);
    if (f == nullptr) {
        ShowErrorMessage(STR_ERROR_BMPMAP, STR_ERROR_PNGMAP_FILE_NOT_FOUND, WL_ERROR);
        return false;
    }

    BmpInitializeBuffer(&buffer, f);

    if (!BmpReadHeader(&buffer, &info, &data)) {
        ShowErrorMessage(STR_ERROR_BMPMAP, STR_ERROR_BMPMAP_IMAGE_TYPE, WL_ERROR);
        fclose(f);
        BmpDestroyData(&data);
        return false;
    }

    /* Check if image dimensions don't overflow a size_t to avoid memory corruption. */
    if ((uint64)info.width * info.height >= (size_t)-1 / (info.bpp == 24 ? 3 : 1)) {
        ShowErrorMessage(STR_ERROR_BMPMAP, STR_ERROR_HEIGHTMAP_TOO_LARGE, WL_ERROR);
        fclose(f);
        BmpDestroyData(&data);
        return false;
    }

    if (maps_ptr != nullptr) {
        if (!BmpReadBitmap(&buffer, &info, &data)) {
            ShowErrorMessage(STR_ERROR_BMPMAP, STR_ERROR_BMPMAP_IMAGE_TYPE, WL_ERROR);
            fclose(f);
            BmpDestroyData(&data);
            return false;
        }

        openttd::bitmaps8_t &maps = *maps_ptr;
        // rgb
        maps.reserve(3);
        maps.resize(3);
        for (int i = 0; i < maps.size(); i++) {
            maps[i].reserve(info.width * info.height);
            maps[i].resize(info.width * info.height);
        }
        ReadHeightmapBMPImageData(maps, &info, &data);
    }

    BmpDestroyData(&data);

    *x = info.width;
    *y = info.height;

    fclose(f);
    return true;
}

#include "tree_map.h"

static bool CanPlantTreesOnTile(TileIndex tile, bool allow_desert)
{
    switch (GetTileType(tile)) {
        case MP_WATER:
            return !IsBridgeAbove(tile) && IsCoast(tile) && !IsSlopeWithOneCornerRaised(GetTileSlope(tile));

        case MP_CLEAR:
            return !IsBridgeAbove(tile) && !IsClearGround(tile, CLEAR_FIELDS) && GetRawClearGround(tile) != CLEAR_ROCKS &&
                   (allow_desert || !IsClearGround(tile, CLEAR_DESERT));

        default: return false;
    }
}

// generate number 0 to max_value
std::uint8_t randr(const std::uint8_t max_value)
{
    const std::uint8_t rng = rand() & 255;
    return (rng * max_value + 127) >> 8;
}

static TreeType MakeTreeType(TileIndex tile, uint height, uint moisture)
{
    TreeType type = TREE_INVALID;

    switch (_settings_game.game_creation.landscape) {
        case LT_TEMPERATE:
            type = TreeType(TREE_TEMPERATE + (height * TREE_COUNT_TEMPERATE) / 256);
            break;

        case LT_ARCTIC:
            //type = TreeType(TREE_SUB_ARCTIC + (mapsize.y * TREE_COUNT_SUB_ARCTIC) / 256);
            if (height < 128 && randr(3) == 0) {
                // mixed leafy
                if (moisture >= 192) {
                    // light green
                    type = TreeType(TREE_SUB_ARCTIC + 7);
                } else if (moisture >= 128) {
                    // green
                    type = TreeType(TREE_SUB_ARCTIC + 3);
                } else if (moisture >= 64) {
                    // red
                    type = TreeType(TREE_SUB_ARCTIC + (randr(1) ? 4 : 6));
                } else {
                    // yellow
                    type = TreeType(TREE_SUB_ARCTIC + 5);
                }
            } else {
                // conifer only
                // types 2 and 3
                if (moisture >= 170) {
                    type = TreeType(TREE_SUB_ARCTIC + 0);
                } else if (moisture >= 85) {
                    type = TreeType(TREE_SUB_ARCTIC + 1);
                } else {
                    type = TreeType(TREE_SUB_ARCTIC + 2);
                }
            }
            break;

        case LT_TROPIC:
            switch (GetTropicZone(tile)) {
                case TROPICZONE_NORMAL:
                    type = TreeType(TREE_SUB_TROPICAL + (height * TREE_COUNT_SUB_TROPICAL) / 256);
                    break;
                case TROPICZONE_DESERT:
                    type = TREE_CACTUS;
                    break;
                case TROPICZONE_RAINFOREST:
                    type = TreeType(TREE_RAINFOREST + (height * TREE_COUNT_RAINFOREST) / 256);
                    break;
            }
            break;

        case LT_TOYLAND:
            type = TreeType(TREE_TOYLAND + (height * TREE_COUNT_TOYLAND) / 256);
            break;
    }
    return type;
}

/**
 * This function takes care of the fact that land in OpenTTD can never differ
 * more than 1 in mapsize.y
 */
void FixSlopes()
{
    uint width, height;
    int row, col;
    byte current_tile;

    /* Adjust height difference to maximum one horizontal/vertical change. */
    width   = MapSizeX();
    height  = MapSizeY();

    /* Top and left edge */
    for (row = 0; (uint)row < height; row++) {
        for (col = 0; (uint)col < width; col++) {
            current_tile = MAX_TILE_HEIGHT;
            if (col != 0) {
                /* Find lowest tile; either the top or left one */
                current_tile = TileHeight(TileXY(col - 1, row)); // top edge
            }
            if (row != 0) {
                if (TileHeight(TileXY(col, row - 1)) < current_tile) {
                    current_tile = TileHeight(TileXY(col, row - 1)); // left edge
                }
            }

            /* Does the height differ more than one? */
            if (TileHeight(TileXY(col, row)) >= (uint)current_tile + 2) {
                /* Then change the height to be no more than one */
                SetTileHeight(TileXY(col, row), current_tile + 1);
            }
        }
    }

    /* Bottom and right edge */
    for (row = height - 1; row >= 0; row--) {
        for (col = width - 1; col >= 0; col--) {
            current_tile = MAX_TILE_HEIGHT;
            if ((uint)col != width - 1) {
                /* Find lowest tile; either the bottom and right one */
                current_tile = TileHeight(TileXY(col + 1, row)); // bottom edge
            }

            if ((uint)row != height - 1) {
                if (TileHeight(TileXY(col, row + 1)) < current_tile) {
                    current_tile = TileHeight(TileXY(col, row + 1)); // right edge
                }
            }

            /* Does the height differ more than one? */
            if (TileHeight(TileXY(col, row)) >= (uint)current_tile + 2) {
                /* Then change the height to be no more than one */
                SetTileHeight(TileXY(col, row), current_tile + 1);
            }
        }
    }
}

bool IsTileValidRiverSlope(TileIndex tile)
{
    int z;
    Slope slope = GetTileSlope(tile, &z);
    return slope == SLOPE_FLAT || GetInclinedSlopeDirection(slope) != INVALID_DIAGDIR;
}

int skew(int fract, int div, int range, float x)
{
    return int(std::round(std::pow(float(fract) / float(div), x) * range));
}

template <typename T>
struct point_t
{
    using P = point_t<T>;

    T x;
    T y;

    point_t() {}
    point_t(T _x, T _y) { x = _x; y = _y; }
    point_t(const point_t &p) { x = p.x; y = p.y; }

    template <class I> point_t(I _x, I _y) { x = T(_x); y = T(_y); }
    template <class I> void operator()(I _x, I _y) { x = T(_x); y = T(_y); }
    void operator=(const P &p) { x = p.x; y = p.y; }

    // basic operators
    bool operator!=(const P &p) const { return (x != p.x || y != p.y); }
    bool operator==(const P &p) const { return (x == p.x && y == p.y); }
    template <class I> bool operator>(const point_t<I> &p) const { return (x > p.x && y > p.y); }
    template <class I> bool operator<(const point_t<I> &p) const { return (x < p.x && y < p.y); }
    template <class I> bool operator>=(const point_t<I> &p) const { return (x >= p.x && y >= p.y); }
    template <class I> bool operator<=(const point_t<I> &p) const { return (x <= p.x && y <= p.y); }
    P operator-() const { return P(-x, -y); }

    // point<I> operators
    template <class I> P operator+(const point_t<I> &p) const { return P(x + p.x, y + p.y); }
    template <class I> P operator-(const point_t<I> &p) const { return P(x - p.x, y - p.y); }
    template <class I> P operator*(const point_t<I> &p) const { return P(x * p.x, y * p.y); }
    template <class I> P operator/(const point_t<I> &p) const { return P(x / p.x, y / p.y); }

    template <class I> P &operator+=(const point_t<I> &p) { x += p.x; y += p.y; return *this; }
    template <class I> P &operator-=(const point_t<I> &p) { x -= p.x; y -= p.y; return *this; }
    template <class I> P &operator*=(const point_t<I> &p) { x *= p.x; y *= p.y; return *this; }
    template <class I> P &operator/=(const point_t<I> &p) { x /= p.x; y /= p.y; return *this; }

    // scalar<I> operators
    template <class I> P operator+(const I &v) const { return P(x + v, y + v); }
    template <class I> P operator-(const I &v) const { return P(x - v, y - v); }
    template <class I> P operator*(const I &v) const { return P(x * v, y * v); }
    template <class I> P operator/(const I &v) const { return P(x / v, y / v); }

    template <class I> void operator+=(const I &v) { x += v; y += v; }
    template <class I> void operator-=(const I &v) { x -= v; y -= v; }
    template <class I> void operator*=(const I &v) { x *= v; y *= v; }
    template <class I> void operator/=(const I &v) { x /= v; y /= v; }

    //
    bool is_zero() const { return (x == T(0) && y == T(0)); }
};

// points on a rectangle
// 1 2 3
// 4 5 6
// 7 8 9
enum class rect_origin_t
{
    left_top,
    top,
    right_top,

    left,
    center,
    right,

    left_bottom,
    bottom,
    right_bottom,
};

template <typename T>
struct rect_t
{
    T left;
    T top;
    T right;
    T bottom;

    rect_t() {}
    rect_t(T width, T height) : left(0), top(0), right(width), bottom(height) {}
    rect_t(const point_t<T> &p) : left(0), top(0), right(p.x), bottom(p.y) {}
    rect_t(T _left, T _top, T _right, T _bottom) : left(_left), top(_top), right(_right), bottom(_bottom) {}
    rect_t(const rect_t<T> &r) { copy_rect(r); }

    void copy_rect(const rect_t<T> &r)
    {
        left = r.left;
        top = r.top;
        right = r.right;
        bottom = r.bottom;
    }

    bool operator!=(const rect_t<T> &r) const { return (left != r.left || right != r.right || top != r.top || bottom != r.bottom); }
    bool operator==(const rect_t<T> &r) const { return (left == r.left && right == r.right && top == r.top && bottom == r.bottom); }
    void operator()(const T &l, const T &t, const T &r, const T &b) { (*this) = rect_t<T>(l,t,r,b); }
    void operator()(const rect_t<T> &r) { (*this) = r; }

    const rect_t<T> &get_rect() { return *this; }

    T width() const { return right - left; }
    T height() const { return bottom - top; }

    point_t<T> size() const { return point_t<T>(width(), height()); }

    point_t<T> lefttop() const { return point_t<T>(left,top); }
    point_t<T> righttop() const { return point_t<T>(right,top); }
    point_t<T> leftbottom() const { return point_t<T>(left,bottom); }
    point_t<T> rightbottom() const { return point_t<T>(right,bottom); }

    point_t<T> lt() const { return point_t<T>(left,top); }
    point_t<T> rt() const { return point_t<T>(right,top); }
    point_t<T> lb() const { return point_t<T>(left,bottom); }
    point_t<T> rb() const { return point_t<T>(right,bottom); }

    point_t<T> middle() const { return point_t<T>((left+right)/2, (top+bottom)/2); }

    // add offset required to "virtually" center where origin = (0, 0)
    rect_t<T> centerh(const rect_t<T> &r) const { return rect_t<T>(r) + point((width() - r.width()) / 2, 0); }
    rect_t<T> centerv(const rect_t<T> &r) const { return rect_t<T>(r) + point(0, (height() - r.height()) / 2); }
    rect_t<T> center(const rect_t<T> &r) const { return rect_t<T>(r) + (size() - r.size()) / 2; }

    // center plus offset to real coordinates
    rect_t<T> centero(const rect_t<T> &r) const { return rect_t<T>(r) + (size() - r.size()) / 2 + lefttop(); }

    rect_t<T> operator+(const point_t<T> &p) const { return rect_t<T>(left + p.x, top + p.y, right + p.x, bottom + p.y); }
    rect_t<T> operator-(const point_t<T> &p) const { return rect_t<T>(left - p.x, top - p.y, right - p.x, bottom - p.y); }

    rect_t<T> operator+(const rect_t<T> &p) const { return rect_t<T>(left + p.left, top + p.top, right + p.right, bottom + p.bottom); }
    rect_t<T> operator-(const rect_t<T> &p) const { return rect_t<T>(left - p.left, top - p.top, right - p.right, bottom - p.bottom); }

    rect_t<T> operator*(const int &n) const { return rect_t<T>(left * n, top * n, right * n, bottom * n); }
    rect_t<T> operator/(const int &n) const { return rect_t<T>(left / n, top / n, right / n, bottom / n); }

    rect_t<T> operator/(const point_t<T> &p) const { return rect_t<T>(left / p.x, top / p.y, right / p.x, bottom / p.y); }

    rect_t<T> operator*(const float &n) const { return rect_t<T>(T(left * n), T(top * n), T(right * n), T(bottom * n)); }
    rect_t<T> operator/(const float &n) const { return rect_t<T>(T(left / n), T(top / n), T(right / n), T(bottom / n)); }

    void move(T x, T y) { (*this) += point_t<T>(x - left, y - top); }

    bool is_valid_exclusive() const { return (left < right && top < bottom); }
    bool is_valid_inclusive() const { return (left <= right && top <= bottom); }

    bool is_empty() const { return (right <= left || bottom <= top); }

    bool overlaps(const rect_t<T> &r) const { return (right >= r.left && left <= r.right && bottom >= r.top && top <= r.bottom); }
    bool overlaps_exclusive(const rect_t<T> &r) const { return  (right >= r.left && left < r.right && bottom >= r.top && top < r.bottom); }

    bool contains(const rect_t<T> &r) const { return (contains(r.lt()) && contains(r.rb())); }
    bool contains(const point_t<T> &p) const { return (p.x >= left && p.x <= right && p.y >= top && p.y <= bottom); }
    bool contains_exclusive(const point_t<T> &p) const { return (p.x >= left && p.x < right && p.y >= top && p.y < bottom); }

    void operator+=(const point_t<T> &p)
    {
        left += p.x;
        top += p.y;
        right += p.x;
        bottom += p.y;
    }

    void operator-=(const point_t<T> &p)
    {
        left -= p.x;
        top -= p.y;
        right -= p.x;
        bottom -= p.y;
    }

    void operator+=(const rect_t<T> &r)
    {
        left   += r.left;
        top    += r.top;
        right  += r.right;
        bottom += r.bottom;
    }

    void operator-=(const rect_t<T> &r)
    {
        left   -= r.left;
        top    -= r.top;
        right  -= r.right;
        bottom -= r.bottom;
    }

    rect_t<T> inclusive_intersect(const rect_t<T> &r) const
    {
        return rect_t<T>((left > r.left ? left : r.left),
            (top > r.top ? top : r.top),
            (right < r.right ? right : r.right),
            (bottom < r.bottom ? bottom : r.bottom));
    }

    rect_t<T> exclusive_intersect(const rect_t<T> &r) const
    {
        return rect_t<T>((left > r.left ? left : r.left),
            (top > r.top ? top : r.top),
            (right < r.right ? right : r.right-1),
            (bottom < r.bottom ? bottom : r.bottom-1));
    }

    void clip_inclusive(const rect_t<T> &r)
    {
        left = _Mlimit(left, r.left, r.right);
        top = _Mlimit(top, r.top, r.bottom);
        right = _Mlimit(right, r.left, r.right);
        bottom = _Mlimit(bottom, r.top, r.bottom);
    }

    void clip_exclusive(const rect_t<T> &r)
    {
        left = _Mlimit(left, r.left, r.right-1);
        top = _Mlimit(top, r.top, r.bottom-1);
        right = _Mlimit(right, r.left, r.right-1);
        bottom = _Mlimit(bottom, r.top, r.bottom-1);
    }

    void expand(const rect_t<T> &r)
    {
        if (r.is_empty()) return;
        if (left > r.left) left = r.left;
        if (top > r.top) top = r.top;
        if (right < r.right) right = r.right;
        if (bottom < r.bottom) bottom = r.bottom;
    }

    point_t<T> constrain(const rect_t<T> &r)
    {
        point_t<T> p(0,0);
        if (left < r.left) p.x = r.left - left;
        else if (right > r.right) p.x = r.right - right;
        if (top < r.top) p.y = r.top - top;
        else if (bottom > r.bottom) p.y = r.bottom - bottom;
        return p;
    }
};

// height-mapping variables and coordinate scaling and translation
struct map_t
{
    using P = point_t<uint>;

    map_t(const P &img) : num_div(16384), scale(0)
    {
        size.x = 0;
        size.y = 0;

        // Get map size and calculate scale and padding values
        switch (_settings_game.game_creation.heightmap_rotation) {
            default: NOT_REACHED();
            case HM_COUNTER_CLOCKWISE:
                size.x = MapSizeX();
                size.y = MapSizeY();
                break;
            case HM_CLOCKWISE:
                size.x = MapSizeY();
                size.y = MapSizeX();
                break;
        }

        padding.x = 0;
        padding.y = 0;

        const P &diff = img - size;

        if ((img.x * num_div) / img.y > ((size.x * num_div) / size.y)) {
            // Image is wider than map - center vertically
            padding.x = (1 + size.y - ((img.y * scale) / num_div)) / 2;
        }

        if ((img.y * num_div) / img.x > ((size.y * num_div) / size.x)) {
            // Image is taller than map - center horizontally
            padding.y = (1 + size.x - ((img.x * scale) / num_div)) / 2;
        }

        // select a scale and padding to fit the map rectangle within the source heightmap
        if (img.x < img.y) {
            scale = (size.x * num_div) / img.x;
        } else {
            scale = (size.y * num_div) / img.y;
        }

        printf("size(%i, %i) img(%i, %i) padding(%i, %i) scale(%i)\n", size.x, size.y, img.x, img.y, padding.x, padding.y, scale);
    }

    bool is_padding(const P &p)
    {
        const uint add_pad = _settings_game.construction.freeform_edges ? 0 : 1;
        return
            p.x < padding.x || p.x >= (size.y - padding.x - add_pad) ||
            p.y < padding.y || p.y >= (size.x  - padding.y - add_pad);
    }

    // scale a point on the map to get source image coordinates
    P get_image_offset(const P &map) const noexcept
    {
        P img;
        // Use nearest neighbour resizing to scale map data
        // rotate the map 45 degrees (counter)clockwise
        img.x = (((map.x - padding.x) * num_div) / scale);
        switch (_settings_game.game_creation.heightmap_rotation) {
            default: NOT_REACHED();
            case HM_COUNTER_CLOCKWISE: img.y = (((size.x - 1 - map.y - padding.y) * num_div) / scale); break;
            case HM_CLOCKWISE: img.y = (((map.y - padding.y) * num_div) / scale); break;
        }

        return img;
    }

    TileIndex get_map_tile_index(const P &map) const noexcept
    {
        switch (_settings_game.game_creation.heightmap_rotation) {
            default: NOT_REACHED();
            case HM_COUNTER_CLOCKWISE: return TileXY(map.y, map.x);
            case HM_CLOCKWISE:         return TileXY(map.x, map.y);
        }

        return -1;
    }

    // fixed point divisor
    // Defines the precision of the aspect ratio (to avoid floating point)
    const uint num_div = 16384;
    uint scale;
    P size;
    P padding;
};

/**
 * Converts a given grayscale map to something that fits in OTTD map system
 * and create a map of that data.
 * @param img_width  the with of the image in pixels/tiles
 * @param img_height the mapsize.y of the image in pixels/tiles
 * @param maps       the input maps
 */
static void GrayscaleToMapHeights(uint img_width, uint img_height, openttd::bitmaps8_t &maps)
{
    using P = map_t::P;
    map_t map(P(img_width, img_height));

    if (_settings_game.construction.freeform_edges) {
        for (uint x = 0; x < MapSizeX(); x++) MakeVoid(TileXY(x, 0));
        for (uint y = 0; y < MapSizeY(); y++) MakeVoid(TileXY(0, y));
    }

    /* Form the landscape */
    if (maps.size() >= 1)
    for (uint x = 0; x < map.size.y; x++) {
        for (uint y = 0; y < map.size.x; y++) {
            TileIndex tile = map.get_map_tile_index(P(x, y));

            /* Check if current tile is within the 1-pixel map edge or padding regions */
            if (map.is_padding(P(x, y)) ||
                (!_settings_game.construction.freeform_edges && DistanceFromEdge(tile) <= 1)) {
                SetTileHeight(tile, 0);
                /* Only clear the tiles within the map area. */
                if (IsInnerTile(tile)) {
                    MakeClear(tile, CLEAR_GRASS, 3);
                }
            } else {
                P img = map.get_image_offset(P(x, y));
                assert(img.x >= 0 && img.x < img_height && img.y >= 0 && img.y < img_width);

                // red = surface mapsize.y
                const uint8 z = maps[0][img.x * img_width + img.y];
                //if (z == 0) {
                    //SetTileHeight(tile, 0);
                //} else {
                    // 0 is sea level.
                    // Other grey scales are scaled evenly to the available height levels > 0.
                    // (The coastline is independent from the number of height levels)
                    //const int scaled_height = 1 + (z - 1) * _settings_game.construction.max_heightlevel / 255;
                    //SetTileHeight(tile, limit_inclusive<uint8>(scaled_height, 1, _settings_game.construction.max_heightlevel));
                    SetTileHeight(tile, z);
                //}

                /* Only clear the tiles within the map area. */
                if (IsInnerTile(tile)) {
                    MakeClear(tile, CLEAR_GRASS, 3);
                }
            }
        }
    }

    if (maps.size() >= 2)
    for (uint x = 0; x < map.size.y; x++) {
        for (uint y = 0; y < map.size.x; y++) {
            TileIndex tile = map.get_map_tile_index(P(x, y));

            /* Check if current tile is within the 1-pixel map edge or padding regions */
            if (map.is_padding(P(x, y)) ||
                (!_settings_game.construction.freeform_edges && DistanceFromEdge(tile) <= 1)) {
                continue;
            } else {
                P img = map.get_image_offset(P(x, y));
                assert(img.x >= 0 && img.x < img_height && img.y >= 0 && img.y < img_width);

                const uint32 rng = Random();
                // green = water availability
                // forest or surface type and density
                const int z = maps[0][img.x * img_width + img.y];
                const int moisture = maps[1][img.x * img_width + img.y];
                if (z == 0) {
                    // trees don't grow in the sea
                    continue;
                }

                // plant trees proportionate to moisture level
                struct forest_density_t
                {
                    // minimum moisture level
                    int moisture;
                    // odds the tile is filled
                    int odds;
                    // minimum number of trees
                    int trees;
                    // additional trees to add
                    int add_trees;
                };

                // power to skew distribution
                const float sk = 3.0f;

                const forest_density_t fmap[] =
                {
                    // dry       = stone, desert, sand & gravel bars
                    {0, 0, 0, 0},
                    // arid      = dry grass and scrubland, sparse arid shrubs
                    {skew(1, 8, 256, sk), 4, 1, 0},
                    // semi-arid = grassland, bushes and few trees
                    {skew(2, 8, 256, sk), 3, 1, 0},
                    // semi-damp = light semi-arid underbrush, sparse forest (1 tree)
                    {skew(3, 8, 256, sk), 2, 1, 0},
                    // damp      = dense underbrush, forest (1 to 2 trees)
                    {skew(4, 8, 256, sk), 1, 1, 1},
                    // moist     = mixed wetland, medium forest (2 to 4 trees)
                    {skew(5, 8, 256, sk), 0, 2, 2},
                    // full      = mixed wetland, dense forest (3 to 4 trees)
                    {skew(6, 8, 256, sk), 0, 3, 1},
                    // max       = mixed wetland, dense forest (4 trees)
                    {skew(7, 8, 256, sk), 0, 4, 0},
                    // end marker
                    {256, 0, 0, 0},
                };

                for (int i = 0; fmap[i].moisture < 256; i++)    {
                    if (moisture >= fmap[i].moisture && moisture < fmap[i + 1].moisture) {
                        const int trees = fmap[i].trees + randr(fmap[i].add_trees);
                        if (trees > 0 && randr(fmap[i].odds) == 0) {
                            if (!IsTileType(tile, MP_TREES) && CanPlantTreesOnTile(tile, true)) {
                                MakeTree(tile, MakeTreeType(tile, z, moisture), trees - 1, randr(7),
                                    TreeGround::TREE_GROUND_GRASS, 3);
                            }
                        }
                        break;
                    }
                }
            }
        }
    }

    if (maps.size() >= 3)
    for (uint x = 0; x < map.size.y; x++) {
        for (uint y = 0; y < map.size.x; y++) {
            TileIndex tile = map.get_map_tile_index(P(x, y));

            /* Check if current tile is within the 1-pixel map edge or padding regions */
            if (map.is_padding(P(x, y)) ||
                (!_settings_game.construction.freeform_edges && DistanceFromEdge(tile) <= 1)) {
                continue;
            } else {
                P img = map.get_image_offset(P(x, y));
                assert(img.x >= 0 && img.x < img_height && img.y >= 0 && img.y < img_width);

                if (IsInnerTile(tile)) {
                    // blue = presence of dense surface water
                    // surface obstructions such as: wetlands, pools, lakes, rivers
                    uint surface_water = maps[2][img.x * img_width + img.y];

                    if (surface_water == 20) {
                        // ocean
                        // z should be 0 for all these tiles,
                        // but due to hight-mapping and slope-fixing routines
                        // this may not be true... so do nothing
                    } else {
                        // if not ocean, limit tile Z >= 1
                        // (since 0 = ocean, a zero height non-ocean tile is not possible)
                        SetTileHeight(tile, limit_inclusive<uint8>(TileHeight(tile), 1, _settings_game.construction.max_heightlevel));

                        if (surface_water == 40) {
                            // rivers
                            if (IsTileValidRiverSlope(tile)) {
                                MakeRiver(tile, Random());
                            }
                        } else if (surface_water == 60) {
                            // lakes
                            // only apply to flat tiles, never slopes
                            if (IsTileFlat(tile)) {
                                MakeRiver(tile, Random());
                            }
                        }
                    }
                }
            }
        }
    }

    FixSlopes();
    MarkWholeScreenDirty();
}

/**
 * Reads the heightmap with the correct file reader.
 * @param dft Type of image file.
 * @param filename Name of the file to load.
 * @param[out] x Length of the image.
 * @param[out] y mapsize.y of the image.
 * @param[in,out] map If not \c nullptr, destination to store the loaded block of image data.
 * @return Whether loading was successful.
 */
static bool ReadHeightMap(DetailedFileType dft, const char *filename, uint *x, uint *y, openttd::bitmaps8_t *maps)
{
    switch (dft) {
        default:
            NOT_REACHED();

#ifdef WITH_PNG
        case DFT_HEIGHTMAP_PNG:
            return ReadHeightmapPNG(filename, x, y, maps);
#endif /* WITH_PNG */

        case DFT_HEIGHTMAP_BMP:
            return ReadHeightmapBMP(filename, x, y, maps);
    }
}

/**
 * Get the dimensions of a heightmap.
 * @param dft Type of image file.
 * @param filename to query
 * @param x dimension x
 * @param y dimension y
 * @return Returns false if loading of the image failed.
 */
bool GetHeightmapDimensions(DetailedFileType dft, const char *filename, uint *x, uint *y)
{
    return ReadHeightMap(dft, filename, x, y, nullptr);
}

/**
 * Load a heightmap from file and change the map in his current dimensions
 *  to a landscape representing the heightmap.
 * It converts pixels to mapsize.y. The brighter, the higher.
 * @param dft Type of image file.
 * @param filename of the heightmap file to be imported
 */
void LoadHeightmap(DetailedFileType dft, const char *filename)
{
    uint x, y;
    openttd::bitmaps8_t maps;

    if (!ReadHeightMap(dft, filename, &x, &y, &maps)) {
        return;
    }
    GrayscaleToMapHeights(x, y, maps);
    maps.clear();
}

/**
 * Make an empty world where all tiles are of mapsize.y 'tile_height'.
 * @param tile_height of the desired new empty world
 */
void FlatEmptyWorld(byte tile_height)
{
    int edge_distance = _settings_game.construction.freeform_edges ? 0 : 2;
    for (uint row = edge_distance; row < MapSizeY() - edge_distance; row++) {
        for (uint col = edge_distance; col < MapSizeX() - edge_distance; col++) {
            SetTileHeight(TileXY(col, row), tile_height);
        }
    }

    FixSlopes();
    MarkWholeScreenDirty();
}