map.cpp

Go to the documentation of this file.

/*
 * 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/>.
 */
 
#include "stdafx.h"
#include "debug.h"
#include "core/alloc_func.hpp"
#include "water_map.h"
#include "error_func.h"
#include "string_func.h"
#include "pathfinder/water_regions.h"
 
#include "safeguards.h"
 
/* static */ uint Map::log_x;     
/* static */ uint Map::log_y;     
/* static */ uint Map::size_x;    
/* static */ uint Map::size_y;    
/* static */ uint Map::size;      
/* static */ uint Map::tile_mask; 
 
/* static */ Tile::TileBase *Tile::base_tiles = nullptr;         
/* static */ Tile::TileExtended *Tile::extended_tiles = nullptr; 
 
 
/* static */ void Map::Allocate(uint size_x, uint size_y)
{
  /* Make sure that the map size is within the limits and that
   * size of both axes is a power of 2. */
  if (!IsInsideMM(size_x, MIN_MAP_SIZE, MAX_MAP_SIZE + 1) ||
      !IsInsideMM(size_y, MIN_MAP_SIZE, MAX_MAP_SIZE + 1) ||
      (size_x & (size_x - 1)) != 0 ||
      (size_y & (size_y - 1)) != 0) {
    FatalError("Invalid map size");
  }
 
  Debug(map, 1, "Allocating map of size {}x{}", size_x, size_y);
 
  Map::log_x = FindFirstBit(size_x);
  Map::log_y = FindFirstBit(size_y);
  Map::size_x = size_x;
  Map::size_y = size_y;
  Map::size = size_x * size_y;
  Map::tile_mask = Map::size - 1;
 
  free(Tile::base_tiles);
  free(Tile::extended_tiles);
 
  Tile::base_tiles = CallocT<Tile::TileBase>(Map::size);
  Tile::extended_tiles = CallocT<Tile::TileExtended>(Map::size);
 
  AllocateWaterRegions();
}
 
 
#ifdef _DEBUG
TileIndex TileAdd(TileIndex tile, TileIndexDiff offset)
{
  int dx = offset & Map::MaxX();
  if (dx >= (int)Map::SizeX() / 2) dx -= Map::SizeX();
  int dy = (offset - dx) / (int)Map::SizeX();
 
  uint32_t x = TileX(tile) + dx;
  uint32_t y = TileY(tile) + dy;
 
  assert(x < Map::SizeX());
  assert(y < Map::SizeY());
  assert(TileXY(x, y) == Map::WrapToMap(tile + offset));
 
  return TileXY(x, y);
}
#endif
 
TileIndex TileAddWrap(TileIndex tile, int addx, int addy)
{
  uint x = TileX(tile) + addx;
  uint y = TileY(tile) + addy;
 
  /* Disallow void tiles at the north border. */
  if ((x == 0 || y == 0) && _settings_game.construction.freeform_edges) return INVALID_TILE;
 
  /* Are we about to wrap? */
  if (x >= Map::MaxX() || y >= Map::MaxY()) return INVALID_TILE;
 
  return TileXY(x, y);
}
 
extern const TileIndexDiffC _tileoffs_by_axis[] = {
  { 1,  0}, 
  { 0,  1}, 
};
 
extern const TileIndexDiffC _tileoffs_by_diagdir[] = {
  {-1,  0}, 
  { 0,  1}, 
  { 1,  0}, 
  { 0, -1}  
};
 
extern const TileIndexDiffC _tileoffs_by_dir[] = {
  {-1, -1}, 
  {-1,  0}, 
  {-1,  1}, 
  { 0,  1}, 
  { 1,  1}, 
  { 1,  0}, 
  { 1, -1}, 
  { 0, -1}  
};
 
uint DistanceManhattan(TileIndex t0, TileIndex t1)
{
  const uint dx = Delta(TileX(t0), TileX(t1));
  const uint dy = Delta(TileY(t0), TileY(t1));
  return dx + dy;
}
 
 
uint DistanceSquare(TileIndex t0, TileIndex t1)
{
  const int dx = TileX(t0) - TileX(t1);
  const int dy = TileY(t0) - TileY(t1);
  return dx * dx + dy * dy;
}
 
 
uint DistanceMax(TileIndex t0, TileIndex t1)
{
  const uint dx = Delta(TileX(t0), TileX(t1));
  const uint dy = Delta(TileY(t0), TileY(t1));
  return std::max(dx, dy);
}
 
 
uint DistanceMaxPlusManhattan(TileIndex t0, TileIndex t1)
{
  const uint dx = Delta(TileX(t0), TileX(t1));
  const uint dy = Delta(TileY(t0), TileY(t1));
  return dx > dy ? 2 * dx + dy : 2 * dy + dx;
}
 
uint DistanceFromEdge(TileIndex tile)
{
  const uint xl = TileX(tile);
  const uint yl = TileY(tile);
  const uint xh = Map::SizeX() - 1 - xl;
  const uint yh = Map::SizeY() - 1 - yl;
  const uint minl = std::min(xl, yl);
  const uint minh = std::min(xh, yh);
  return std::min(minl, minh);
}
 
uint DistanceFromEdgeDir(TileIndex tile, DiagDirection dir)
{
  switch (dir) {
    case DIAGDIR_NE: return             TileX(tile) - (_settings_game.construction.freeform_edges ? 1 : 0);
    case DIAGDIR_NW: return             TileY(tile) - (_settings_game.construction.freeform_edges ? 1 : 0);
    case DIAGDIR_SW: return Map::MaxX() - TileX(tile) - 1;
    case DIAGDIR_SE: return Map::MaxY() - TileY(tile) - 1;
    default: NOT_REACHED();
  }
}
 
bool CircularTileSearch(TileIndex *tile, uint size, TestTileOnSearchProc proc, void *user_data)
{
  assert(proc != nullptr);
  assert(size > 0);
 
  if (size % 2 == 1) {
    /* If the length of the side is uneven, the center has to be checked
     * separately, as the pattern of uneven sides requires to go around the center */
    if (proc(*tile, user_data)) return true;
 
    /* If tile test is not successful, get one tile up,
     * ready for a test in first circle around center tile */
    *tile = TileAddByDir(*tile, DIR_N);
    return CircularTileSearch(tile, size / 2, 1, 1, proc, user_data);
  } else {
    return CircularTileSearch(tile, size / 2, 0, 0, proc, user_data);
  }
}
 
bool CircularTileSearch(TileIndex *tile, uint radius, uint w, uint h, TestTileOnSearchProc proc, void *user_data)
{
  assert(proc != nullptr);
  assert(radius > 0);
 
  uint x = TileX(*tile) + w + 1;
  uint y = TileY(*tile);
 
  const uint extent[DIAGDIR_END] = { w, h, w, h };
 
  for (uint n = 0; n < radius; n++) {
    for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
      /* Is the tile within the map? */
      for (uint j = extent[dir] + n * 2 + 1; j != 0; j--) {
        if (x < Map::SizeX() && y < Map::SizeY()) {
          TileIndex t = TileXY(x, y);
          /* Is the callback successful? */
          if (proc(t, user_data)) {
            /* Stop the search */
            *tile = t;
            return true;
          }
        }
 
        /* Step to the next 'neighbour' in the circular line */
        x += _tileoffs_by_diagdir[dir].x;
        y += _tileoffs_by_diagdir[dir].y;
      }
    }
    /* Jump to next circle to test */
    x += _tileoffs_by_dir[DIR_W].x;
    y += _tileoffs_by_dir[DIR_W].y;
  }
 
  *tile = INVALID_TILE;
  return false;
}
 
uint GetClosestWaterDistance(TileIndex tile, bool water)
{
  if (HasTileWaterGround(tile) == water) return 0;
 
  uint max_dist = water ? 0x7F : 0x200;
 
  int x = TileX(tile);
  int y = TileY(tile);
 
  uint max_x = Map::MaxX();
  uint max_y = Map::MaxY();
  uint min_xy = _settings_game.construction.freeform_edges ? 1 : 0;
 
  /* go in a 'spiral' with increasing manhattan distance in each iteration */
  for (uint dist = 1; dist < max_dist; dist++) {
    /* next 'diameter' */
    y--;
 
    /* going counter-clockwise around this square */
    for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
      static const int8_t ddx[DIAGDIR_END] = { -1,  1,  1, -1};
      static const int8_t ddy[DIAGDIR_END] = {  1,  1, -1, -1};
 
      int dx = ddx[dir];
      int dy = ddy[dir];
 
      /* each side of this square has length 'dist' */
      for (uint a = 0; a < dist; a++) {
        /* MP_VOID tiles are not checked (interval is [min; max) for IsInsideMM())*/
        if (IsInsideMM(x, min_xy, max_x) && IsInsideMM(y, min_xy, max_y)) {
          TileIndex t = TileXY(x, y);
          if (HasTileWaterGround(t) == water) return dist;
        }
        x += dx;
        y += dy;
      }
    }
  }
 
  if (!water) {
    /* no land found - is this a water-only map? */
    for (const auto t : Map::Iterate()) {
      if (!IsTileType(t, MP_VOID) && !IsTileType(t, MP_WATER)) return 0x1FF;
    }
  }
 
  return max_dist;
}