Files
@ r14312:be27b5f00b31
Branch filter:
Location: cpp/openttd-patchpack/source/src/map.cpp
r14312:be27b5f00b31
11.3 KiB
text/x-c
(svn r18875) -Codechange: remove some unneeded bits from the network protocol and improve the naming of some variables
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 | /* $Id$ */
/*
* 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 map.cpp Base functions related to the map and distances on them. */
#include "stdafx.h"
#include "debug.h"
#include "core/alloc_func.hpp"
#include "core/math_func.hpp"
#include "tile_map.h"
#if defined(_MSC_VER)
/* Why the hell is that not in all MSVC headers?? */
extern "C" _CRTIMP void __cdecl _assert(void *, void *, unsigned);
#endif
uint _map_log_x; ///< 2^_map_log_x == _map_size_x
uint _map_log_y; ///< 2^_map_log_y == _map_size_y
uint _map_size_x; ///< Size of the map along the X
uint _map_size_y; ///< Size of the map along the Y
uint _map_size; ///< The number of tiles on the map
uint _map_tile_mask; ///< _map_size - 1 (to mask the mapsize)
Tile *_m = NULL; ///< Tiles of the map
TileExtended *_me = NULL; ///< Extended Tiles of the map
/*!
* (Re)allocates a map with the given dimension
* @param size_x the width of the map along the NE/SW edge
* @param size_y the 'height' of the map along the SE/NW edge
*/
void AllocateMap(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)
error("Invalid map size");
DEBUG(map, 1, "Allocating map of size %dx%d", 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(_m);
free(_me);
_m = CallocT<Tile>(_map_size);
_me = CallocT<TileExtended>(_map_size);
}
#ifdef _DEBUG
TileIndex TileAdd(TileIndex tile, TileIndexDiff add,
const char *exp, const char *file, int line)
{
int dx;
int dy;
uint x;
uint y;
dx = add & MapMaxX();
if (dx >= (int)MapSizeX() / 2) dx -= MapSizeX();
dy = (add - dx) / (int)MapSizeX();
x = TileX(tile) + dx;
y = TileY(tile) + dy;
if (x >= MapSizeX() || y >= MapSizeY()) {
char buf[512];
snprintf(buf, lengthof(buf), "TILE_ADD(%s) when adding 0x%.4X and 0x%.4X failed",
exp, tile, add);
#if !defined(_MSC_VER) || defined(WINCE)
fprintf(stderr, "%s:%d %s\n", file, line, buf);
#else
_assert(buf, (char*)file, line);
#endif
}
assert(TileXY(x, y) == TILE_MASK(tile + add));
return TileXY(x, y);
}
#endif
/*!
* This function checks if we add addx/addy to tile, if we
* do wrap around the edges. For example, tile = (10,2) and
* addx = +3 and addy = -4. This function will now return
* INVALID_TILE, because the y is wrapped. This is needed in
* for example, farmland. When the tile is not wrapped,
* the result will be tile + TileDiffXY(addx, addy)
*
* @param tile the 'starting' point of the adding
* @param addx the amount of tiles in the X direction to add
* @param addy the amount of tiles in the Y direction to add
* @return translated tile, or INVALID_TILE when it would've wrapped.
*/
TileIndex TileAddWrap(TileIndex tile, int addx, int addy)
{
uint x = TileX(tile) + addx;
uint y = TileY(tile) + addy;
/* Are we about to wrap? */
if (x < MapMaxX() && y < MapMaxY())
return tile + TileDiffXY(addx, addy);
return INVALID_TILE;
}
/** 'Lookup table' for tile offsets given a DiagDirection */
extern const TileIndexDiffC _tileoffs_by_diagdir[] = {
{-1, 0}, ///< DIAGDIR_NE
{ 0, 1}, ///< DIAGDIR_SE
{ 1, 0}, ///< DIAGDIR_SW
{ 0, -1} ///< DIAGDIR_NW
};
/** 'Lookup table' for tile offsets given a Direction */
extern const TileIndexDiffC _tileoffs_by_dir[] = {
{-1, -1}, ///< DIR_N
{-1, 0}, ///< DIR_NE
{-1, 1}, ///< DIR_E
{ 0, 1}, ///< DIR_SE
{ 1, 1}, ///< DIR_S
{ 1, 0}, ///< DIR_SW
{ 1, -1}, ///< DIR_W
{ 0, -1} ///< DIR_NW
};
/*!
* Gets the Manhattan distance between the two given tiles.
* The Manhattan distance is the sum of the delta of both the
* X and Y component.
* Also known as L1-Norm
* @param t0 the start tile
* @param t1 the end tile
* @return the distance
*/
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;
}
/*!
* Gets the 'Square' distance between the two given tiles.
* The 'Square' distance is the square of the shortest (straight line)
* distance between the two tiles.
* Also known as euclidian- or L2-Norm squared.
* @param t0 the start tile
* @param t1 the end tile
* @return the distance
*/
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;
}
/*!
* Gets the biggest distance component (x or y) between the two given tiles.
* Also known as L-Infinity-Norm.
* @param t0 the start tile
* @param t1 the end tile
* @return the distance
*/
uint DistanceMax(TileIndex t0, TileIndex t1)
{
const uint dx = Delta(TileX(t0), TileX(t1));
const uint dy = Delta(TileY(t0), TileY(t1));
return max(dx, dy);
}
/*!
* Gets the biggest distance component (x or y) between the two given tiles
* plus the Manhattan distance, i.e. two times the biggest distance component
* and once the smallest component.
* @param t0 the start tile
* @param t1 the end tile
* @return the distance
*/
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;
}
/*!
* Param the minimum distance to an edge
* @param tile the tile to get the distance from
* @return the distance from the edge in tiles
*/
uint DistanceFromEdge(TileIndex tile)
{
const uint xl = TileX(tile);
const uint yl = TileY(tile);
const uint xh = MapSizeX() - 1 - xl;
const uint yh = MapSizeY() - 1 - yl;
const uint minl = min(xl, yl);
const uint minh = min(xh, yh);
return min(minl, minh);
}
/*!
* Function performing a search around a center tile and going outward, thus in circle.
* Although it really is a square search...
* Every tile will be tested by means of the callback function proc,
* which will determine if yes or no the given tile meets criteria of search.
* @param tile to start the search from. Upon completion, it will return the tile matching the search
* @param size: number of tiles per side of the desired search area
* @param proc: callback testing function pointer.
* @param user_data to be passed to the callback function. Depends on the implementation
* @return result of the search
* @pre proc != NULL
* @pre size > 0
*/
bool CircularTileSearch(TileIndex *tile, uint size, TestTileOnSearchProc proc, void *user_data)
{
assert(proc != NULL);
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 = TILE_ADD(*tile, TileOffsByDir(DIR_N));
return CircularTileSearch(tile, size / 2, 1, 1, proc, user_data);
} else {
return CircularTileSearch(tile, size / 2, 0, 0, proc, user_data);
}
}
/*!
* Generalized circular search allowing for rectangles and a hole.
* Function performing a search around a center rectangle and going outward.
* The center rectangle is left out from the search. To do a rectangular search
* without a hole, set either h or w to zero.
* Every tile will be tested by means of the callback function proc,
* which will determine if yes or no the given tile meets criteria of search.
* @param tile to start the search from. Upon completion, it will return the tile matching the search.
* This tile should be directly north of the hole (if any).
* @param radius How many tiles to search outwards. Note: This is a radius and thus different
* from the size parameter of the other CircularTileSearch function, which is a diameter.
* @param w the width of the inner rectangle
* @param h the height of the inner rectangle
* @param proc callback testing function pointer.
* @param user_data to be passed to the callback function. Depends on the implementation
* @return result of the search
* @pre proc != NULL
* @pre radius > 0
*/
bool CircularTileSearch(TileIndex *tile, uint radius, uint w, uint h, TestTileOnSearchProc proc, void *user_data)
{
assert(proc != NULL);
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 < MapSizeX() && y < MapSizeY()) {
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;
}
/*!
* Finds the distance for the closest tile with water/land given a tile
* @param tile the tile to find the distance too
* @param water whether to find water or land
* @return distance to nearest water (max 0x7F) / land (max 0x1FF; 0x200 if there is no land)
* @note FAILS when an industry should be seen as water
*/
uint GetClosestWaterDistance(TileIndex tile, bool water)
{
if (IsTileType(tile, MP_WATER) == water) return 0;
uint max_dist = water ? 0x7F : 0x200;
int x = TileX(tile);
int y = TileY(tile);
uint max_x = MapMaxX();
uint max_y = MapMaxY();
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 ddx[DIAGDIR_END] = { -1, 1, 1, -1};
static const int8 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 (IsTileType(t, MP_WATER) == water) return dist;
}
x += dx;
y += dy;
}
}
}
if (!water) {
/* no land found - is this a water-only map? */
for (TileIndex t = 0; t < MapSize(); t++) {
if (!IsTileType(t, MP_VOID) && !IsTileType(t, MP_WATER)) return 0x1FF;
}
}
return max_dist;
}
|