tron@2186: /* $Id$ */
tron@2186: 
rubidium@9111: /** @file map.cpp Base functions related to the map and distances on them. */
belugas@6201: 
tron@679: #include "stdafx.h"
tron@1299: #include "debug.h"
rubidium@8100: #include "direction_func.h"
rubidium@8113: #include "core/bitmath_func.hpp"
rubidium@8130: #include "core/alloc_func.hpp"
rubidium@8131: #include "core/math_func.hpp"
rubidium@8139: #include "map_func.h"
tron@679: 
Darkvater@2482: #if defined(_MSC_VER) && _MSC_VER >= 1400 /* VStudio 2005 is stupid! */
Darkvater@2482: /* Why the hell is that not in all MSVC headers?? */
rubidium@5587: extern "C" _CRTIMP void __cdecl _assert(void *, void *, unsigned);
Darkvater@2482: #endif
Darkvater@2482: 
rubidium@6540: uint _map_log_x;     ///< 2^_map_log_x == _map_size_x
belugas@8391: uint _map_log_y;     ///< 2^_map_log_y == _map_size_y
rubidium@6540: uint _map_size_x;    ///< Size of the map along the X
rubidium@6540: uint _map_size_y;    ///< Size of the map along the Y
rubidium@6540: uint _map_size;      ///< The number of tiles on the map
rubidium@6540: uint _map_tile_mask; ///< _map_size - 1 (to mask the mapsize)
tron@689: 
rubidium@6540: Tile *_m = NULL;          ///< Tiles of the map
rubidium@6540: TileExtended *_me = NULL; ///< Extended Tiles of the map
tron@863: 
tron@1218: 
rubidium@7546: /*!
rubidium@6540:  * (Re)allocates a map with the given dimension
rubidium@6540:  * @param size_x the width of the map along the NE/SW edge
rubidium@6540:  * @param size_y the 'height' of the map along the SE/NW edge
rubidium@6540:  */
ludde@2051: void AllocateMap(uint size_x, uint size_y)
tron@1218: {
belugas@6201: 	/* Make sure that the map size is within the limits and that
belugas@6201: 	 * the x axis size is a power of 2. */
ludde@2051: 	if (size_x < 64 || size_x > 2048 ||
ludde@2051: 			size_y < 64 || size_y > 2048 ||
rubidium@6540: 			(size_x & (size_x - 1)) != 0 ||
rubidium@6540: 			(size_y & (size_y - 1)) != 0)
tron@1244: 		error("Invalid map size");
tron@1218: 
Darkvater@5380: 	DEBUG(map, 1, "Allocating map of size %dx%d", size_x, size_y);
tron@1218: 
ludde@2051: 	_map_log_x = FindFirstBit(size_x);
belugas@8391: 	_map_log_y = FindFirstBit(size_y);
ludde@2051: 	_map_size_x = size_x;
ludde@2051: 	_map_size_y = size_y;
ludde@2051: 	_map_size = size_x * size_y;
ludde@2051: 	_map_tile_mask = _map_size - 1;
tron@1218: 
tron@2049: 	free(_m);
maedhros@6332: 	free(_me);
tron@1218: 
rubidium@6492: 	/* XXX @todo handle memory shortage more gracefully
glx@8040: 	 * CallocT does the out-of-memory check
rubidium@6492: 	 * Maybe some attemps could be made to try with smaller maps down to 64x64
rubidium@6492: 	 * Maybe check for available memory before doing the calls, after all, we know how big
rubidium@6492: 	 * the map is */
glx@8040: 	_m = CallocT<Tile>(_map_size);
glx@8040: 	_me = CallocT<TileExtended>(_map_size);
tron@1218: }
tron@900: 
tron@955: 
tron@955: #ifdef _DEBUG
tron@955: TileIndex TileAdd(TileIndex tile, TileIndexDiff add,
tron@955: 	const char *exp, const char *file, int line)
tron@955: {
tron@955: 	int dx;
tron@955: 	int dy;
tron@955: 	uint x;
tron@955: 	uint y;
tron@955: 
tron@955: 	dx = add & MapMaxX();
darkvater@957: 	if (dx >= (int)MapSizeX() / 2) dx -= MapSizeX();
tron@955: 	dy = (add - dx) / (int)MapSizeX();
tron@955: 
tron@955: 	x = TileX(tile) + dx;
tron@955: 	y = TileY(tile) + dy;
tron@955: 
tron@955: 	if (x >= MapSizeX() || y >= MapSizeY()) {
tron@955: 		char buf[512];
tron@955: 
Darkvater@5170: 		snprintf(buf, lengthof(buf), "TILE_ADD(%s) when adding 0x%.4X and 0x%.4X failed",
tron@955: 			exp, tile, add);
truelight@7405: #if !defined(_MSC_VER) || defined(WINCE)
tron@955: 		fprintf(stderr, "%s:%d %s\n", file, line, buf);
tron@955: #else
tron@955: 		_assert(buf, (char*)file, line);
tron@955: #endif
tron@955: 	}
tron@955: 
rubidium@6491: 	assert(TileXY(x, y) == TILE_MASK(tile + add));
tron@955: 
rubidium@6491: 	return TileXY(x, y);
tron@955: }
tron@955: #endif
tron@955: 
rubidium@7546: /*!
rubidium@6540:  * Scales the given value by the map size, where the given value is
rubidium@7546:  * for a 256 by 256 map.
rubidium@6540:  * @param n the value to scale
rubidium@6540:  * @return the scaled size
rubidium@6540:  */
tron@1202: uint ScaleByMapSize(uint n)
tron@1202: {
belugas@6201: 	/* First shift by 12 to prevent integer overflow for large values of n.
belugas@6201: 	 * >>12 is safe since the min mapsize is 64x64
belugas@6201: 	 * Add (1<<4)-1 to round upwards. */
rubidium@6491: 	return (n * (MapSize() >> 12) + (1 << 4) - 1) >> 4;
tron@1202: }
tron@1202: 
tron@1202: 
rubidium@7546: /*!
rubidium@6540:  * Scales the given value by the maps circumference, where the given
rubidium@6540:  * value is for a 256 by 256 map
rubidium@6540:  * @param n the value to scale
rubidium@6540:  * @return the scaled size
rubidium@6540:  */
tron@1202: uint ScaleByMapSize1D(uint n)
tron@1202: {
belugas@6201: 	/* Normal circumference for the X+Y is 256+256 = 1<<9
belugas@6201: 	 * Note, not actually taking the full circumference into account,
belugas@6201: 	 * just half of it.
belugas@6201: 	 * (1<<9) - 1 is there to scale upwards. */
rubidium@6491: 	return (n * (MapSizeX() + MapSizeY()) + (1 << 9) - 1) >> 9;
tron@1202: }
tron@1202: 
tron@1202: 
rubidium@7546: /*!
rubidium@6540:  * This function checks if we add addx/addy to tile, if we
rubidium@7546:  * do wrap around the edges. For example, tile = (10,2) and
rubidium@7546:  * addx = +3 and addy = -4. This function will now return
rubidium@7546:  * INVALID_TILE, because the y is wrapped. This is needed in
rubidium@7546:  * for example, farmland. When the tile is not wrapped,
rubidium@7546:  * the result will be tile + TileDiffXY(addx, addy)
rubidium@7546:  *
rubidium@6540:  * @param tile the 'starting' point of the adding
rubidium@6540:  * @param addx the amount of tiles in the X direction to add
rubidium@6540:  * @param addy the amount of tiles in the Y direction to add
rubidium@6540:  * @return translated tile, or INVALID_TILE when it would've wrapped.
rubidium@6540:  */
frosch@8331: TileIndex TileAddWrap(TileIndex tile, int addx, int addy)
matthijs@1247: {
tron@2548: 	uint x = TileX(tile) + addx;
tron@2548: 	uint y = TileY(tile) + addy;
matthijs@1247: 
belugas@6201: 	/* Are we about to wrap? */
tron@1981: 	if (x < MapMaxX() && y < MapMaxY())
tron@1981: 		return tile + TileDiffXY(addx, addy);
matthijs@1247: 
matthijs@1247: 	return INVALID_TILE;
matthijs@1247: }
matthijs@1247: 
rubidium@6540: /** 'Lookup table' for tile offsets given a DiagDirection */
rubidium@5587: extern const TileIndexDiffC _tileoffs_by_diagdir[] = {
belugas@6201: 	{-1,  0}, ///< DIAGDIR_NE
belugas@6201: 	{ 0,  1}, ///< DIAGDIR_SE
belugas@6201: 	{ 1,  0}, ///< DIAGDIR_SW
belugas@6201: 	{ 0, -1}  ///< DIAGDIR_NW
Darkvater@4559: };
Darkvater@4559: 
rubidium@6540: /** 'Lookup table' for tile offsets given a Direction */
rubidium@5587: extern const TileIndexDiffC _tileoffs_by_dir[] = {
belugas@6201: 	{-1, -1}, ///< DIR_N
belugas@6201: 	{-1,  0}, ///< DIR_NE
belugas@6201: 	{-1,  1}, ///< DIR_E
belugas@6201: 	{ 0,  1}, ///< DIR_SE
belugas@6201: 	{ 1,  1}, ///< DIR_S
belugas@6201: 	{ 1,  0}, ///< DIR_SW
belugas@6201: 	{ 1, -1}, ///< DIR_W
belugas@6201: 	{ 0, -1}  ///< DIR_NW
matthijs@1247: };
matthijs@1247: 
rubidium@7546: /*!
rubidium@6540:  * Gets the Manhattan distance between the two given tiles.
rubidium@6540:  * The Manhattan distance is the sum of the delta of both the
rubidium@6540:  * X and Y component.
rubidium@6540:  * Also known as L1-Norm
rubidium@6540:  * @param t0 the start tile
rubidium@6540:  * @param t1 the end tile
rubidium@6540:  * @return the distance
rubidium@6540:  */
tron@1245: uint DistanceManhattan(TileIndex t0, TileIndex t1)
tron@1245: {
skidd13@7970: 	const uint dx = Delta(TileX(t0), TileX(t1));
skidd13@7970: 	const uint dy = Delta(TileY(t0), TileY(t1));
matthijs@1677: 	return dx + dy;
tron@1245: }
tron@1245: 
tron@1245: 
rubidium@7546: /*!
rubidium@6540:  * Gets the 'Square' distance between the two given tiles.
rubidium@6540:  * The 'Square' distance is the square of the shortest (straight line)
rubidium@6540:  * distance between the two tiles.
rubidium@6540:  * Also known as euclidian- or L2-Norm squared.
rubidium@6540:  * @param t0 the start tile
rubidium@6540:  * @param t1 the end tile
rubidium@6540:  * @return the distance
rubidium@6540:  */
tron@1245: uint DistanceSquare(TileIndex t0, TileIndex t1)
tron@1245: {
matthijs@1677: 	const int dx = TileX(t0) - TileX(t1);
matthijs@1677: 	const int dy = TileY(t0) - TileY(t1);
matthijs@1677: 	return dx * dx + dy * dy;
tron@1245: }
tron@1245: 
tron@1245: 
rubidium@7546: /*!
rubidium@6540:  * Gets the biggest distance component (x or y) between the two given tiles.
rubidium@6540:  * Also known as L-Infinity-Norm.
rubidium@6540:  * @param t0 the start tile
rubidium@6540:  * @param t1 the end tile
rubidium@6540:  * @return the distance
rubidium@6540:  */
tron@1245: uint DistanceMax(TileIndex t0, TileIndex t1)
tron@1245: {
skidd13@7970: 	const uint dx = Delta(TileX(t0), TileX(t1));
skidd13@7970: 	const uint dy = Delta(TileY(t0), TileY(t1));
skidd13@7930: 	return max(dx, dy);
tron@1245: }
tron@1245: 
tron@1245: 
rubidium@7546: /*!
rubidium@6540:  * Gets the biggest distance component (x or y) between the two given tiles
rubidium@6540:  * plus the Manhattan distance, i.e. two times the biggest distance component
rubidium@6540:  * and once the smallest component.
rubidium@6540:  * @param t0 the start tile
rubidium@6540:  * @param t1 the end tile
rubidium@6540:  * @return the distance
rubidium@6540:  */
tron@1245: uint DistanceMaxPlusManhattan(TileIndex t0, TileIndex t1)
tron@1245: {
skidd13@7970: 	const uint dx = Delta(TileX(t0), TileX(t1));
skidd13@7970: 	const uint dy = Delta(TileY(t0), TileY(t1));
matthijs@1677: 	return dx > dy ? 2 * dx + dy : 2 * dy + dx;
tron@1245: }
tron@1245: 
rubidium@7546: /*!
rubidium@6540:  * Param the minimum distance to an edge
rubidium@6540:  * @param tile the tile to get the distance from
rubidium@6540:  * @return the distance from the edge in tiles
rubidium@6540:  */
tron@1245: uint DistanceFromEdge(TileIndex tile)
tron@1245: {
tron@1245: 	const uint xl = TileX(tile);
tron@1245: 	const uint yl = TileY(tile);
tron@1245: 	const uint xh = MapSizeX() - 1 - xl;
tron@1245: 	const uint yh = MapSizeY() - 1 - yl;
skidd13@7930: 	const uint minl = min(xl, yl);
skidd13@7930: 	const uint minh = min(xh, yh);
skidd13@7930: 	return min(minl, minh);
tron@1245: }
belugas@5118: 
rubidium@7546: /*!
belugas@5118:  * Function performing a search around a center tile and going outward, thus in circle.
belugas@5118:  * Although it really is a square search...
belugas@5118:  * Every tile will be tested by means of the callback function proc,
belugas@5118:  * which will determine if yes or no the given tile meets criteria of search.
belugas@5118:  * @param tile to start the search from
belugas@5118:  * @param size: number of tiles per side of the desired search area
belugas@5118:  * @param proc: callback testing function pointer.
belugas@5118:  * @param data to be passed to the callback function. Depends on the implementation
belugas@6201:  * @return result of the search
belugas@5118:  * @pre proc != NULL
belugas@5118:  * @pre size > 0
belugas@5118:  */
belugas@5118: bool CircularTileSearch(TileIndex tile, uint size, TestTileOnSearchProc proc, uint32 data)
belugas@5118: {
belugas@5118: 	uint n, x, y;
belugas@5118: 	DiagDirection dir;
belugas@5118: 
belugas@5118: 	assert(proc != NULL);
belugas@5118: 	assert(size > 0);
belugas@5118: 
belugas@5118: 	x = TileX(tile);
belugas@5118: 	y = TileY(tile);
belugas@5118: 
belugas@5118: 	if (size % 2 == 1) {
belugas@5118: 		/* If the length of the side is uneven, the center has to be checked
belugas@5118: 		 * separately, as the pattern of uneven sides requires to go around the center */
belugas@5118: 		n = 2;
belugas@5118: 		if (proc(TileXY(x, y), data)) return true;
belugas@5118: 
peter1138@7372: 		/* If tile test is not successful, get one tile down and left,
belugas@5118: 		 * ready for a test in first circle around center tile */
belugas@5118: 		x += _tileoffs_by_dir[DIR_W].x;
belugas@5118: 		y += _tileoffs_by_dir[DIR_W].y;
belugas@5118: 	} else {
belugas@5118: 		n = 1;
belugas@5118: 		/* To use _tileoffs_by_diagdir's order, we must relocate to
belugas@5118: 		 * another tile, as we now first go 'up', 'right', 'down', 'left'
belugas@5118: 		 * instead of 'right', 'down', 'left', 'up', which the calling
belugas@5118: 		 * function assume. */
belugas@5118: 		x++;
belugas@5118: 	}
belugas@5118: 
belugas@5118: 	for (; n < size; n += 2) {
belugas@5118: 		for (dir = DIAGDIR_NE; dir < DIAGDIR_END; dir++) {
belugas@5118: 			uint j;
belugas@5118: 			for (j = n; j != 0; j--) {
belugas@5118: 				if (x <= MapMaxX() && y <= MapMaxY() && ///< Is the tile within the map?
peter1138@7372: 						proc(TileXY(x, y), data)) {     ///< Is the callback successful?
belugas@5118: 					return true;                        ///< then stop the search
belugas@5118: 				}
belugas@5118: 
belugas@5118: 				/* Step to the next 'neighbour' in the circular line */
belugas@5118: 				x += _tileoffs_by_diagdir[dir].x;
belugas@5118: 				y += _tileoffs_by_diagdir[dir].y;
belugas@5118: 			}
belugas@5118: 		}
belugas@5118: 		/* Jump to next circle to test */
belugas@5118: 		x += _tileoffs_by_dir[DIR_W].x;
belugas@5118: 		y += _tileoffs_by_dir[DIR_W].y;
belugas@5118: 	}
belugas@5118: 	return false;
belugas@5118: }