Files
@ r10044:a1e2a7856c4e
Branch filter:
Location: cpp/openttd-patchpack/source/src/map.cpp
r10044:a1e2a7856c4e
9.1 KiB
text/x-c
(svn r14204) -Fix (r7475): when determining length of a string with limited size, first check if we are not out of bounds already
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 | /* $Id$ */
/** @file map.cpp Base functions related to the map and distances on them. */
#include "stdafx.h"
#include "debug.h"
#include "direction_func.h"
#include "core/bitmath_func.hpp"
#include "core/alloc_func.hpp"
#include "core/math_func.hpp"
#include "map_func.h"
#if defined(_MSC_VER) && _MSC_VER >= 1400 /* VStudio 2005 is stupid! */
/* 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
* the x axis size is a power of 2. */
if (size_x < 64 || size_x > 2048 ||
size_y < 64 || size_y > 2048 ||
(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);
/* XXX @todo handle memory shortage more gracefully
* CallocT does the out-of-memory check
* Maybe some attemps could be made to try with smaller maps down to 64x64
* Maybe check for available memory before doing the calls, after all, we know how big
* the map is */
_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
/*!
* Scales the given value by the map size, where the given value is
* for a 256 by 256 map.
* @param n the value to scale
* @return the scaled size
*/
uint ScaleByMapSize(uint n)
{
/* First shift by 12 to prevent integer overflow for large values of n.
* >>12 is safe since the min mapsize is 64x64
* Add (1<<4)-1 to round upwards. */
return (n * (MapSize() >> 12) + (1 << 4) - 1) >> 4;
}
/*!
* Scales the given value by the maps circumference, where the given
* value is for a 256 by 256 map
* @param n the value to scale
* @return the scaled size
*/
uint ScaleByMapSize1D(uint n)
{
/* Normal circumference for the X+Y is 256+256 = 1<<9
* Note, not actually taking the full circumference into account,
* just half of it.
* (1<<9) - 1 is there to scale upwards. */
return (n * (MapSizeX() + MapSizeY()) + (1 << 9) - 1) >> 9;
}
/*!
* 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)
{
uint n, x, y;
DiagDirection dir;
assert(proc != NULL);
assert(size > 0);
x = TileX(*tile);
y = TileY(*tile);
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 */
n = 2;
if (proc(TileXY(x, y), user_data)) {
*tile = TileXY(x, y);
return true;
}
/* If tile test is not successful, get one tile down and left,
* ready for a test in first circle around center tile */
x += _tileoffs_by_dir[DIR_W].x;
y += _tileoffs_by_dir[DIR_W].y;
} else {
n = 1;
/* To use _tileoffs_by_diagdir's order, we must relocate to
* another tile, as we now first go 'up', 'right', 'down', 'left'
* instead of 'right', 'down', 'left', 'up', which the calling
* function assume. */
x++;
}
for (; n < size; n += 2) {
for (dir = DIAGDIR_NE; dir < DIAGDIR_END; dir++) {
uint j;
for (j = n; j != 0; j--) {
if (x <= MapMaxX() && y <= MapMaxY() && ///< Is the tile within the map?
proc(TileXY(x, y), user_data)) { ///< Is the callback successful?
*tile = TileXY(x, y);
return true; ///< then stop the search
}
/* 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;
}
|