1

/* $Id$ */

     2

     3

/** @file map.cpp Base functions related to the map and distances on them. */

     4

     5

#include "stdafx.h"

     6

#include "debug.h"

     7

#include "direction_func.h"

     8

#include "core/bitmath_func.hpp"

     9

#include "core/alloc_func.hpp"

    10

#include "core/math_func.hpp"

    11

#include "map_func.h"

    12

    13

#if defined(_MSC_VER) && _MSC_VER >= 1400 /* VStudio 2005 is stupid! */

    14

/* Why the hell is that not in all MSVC headers?? */

    15

extern "C" _CRTIMP void __cdecl _assert(void *, void *, unsigned);

    16

#endif

    17

    18

uint _map_log_x;     ///< 2^_map_log_x == _map_size_x

    19

uint _map_log_y;     ///< 2^_map_log_y == _map_size_y

    20

uint _map_size_x;    ///< Size of the map along the X

    21

uint _map_size_y;    ///< Size of the map along the Y

    22

uint _map_size;      ///< The number of tiles on the map

    23

uint _map_tile_mask; ///< _map_size - 1 (to mask the mapsize)

    24

    25

Tile *_m = NULL;          ///< Tiles of the map

    26

TileExtended *_me = NULL; ///< Extended Tiles of the map

    27

    28

    29

/*!

    30

 * (Re)allocates a map with the given dimension

    31

 * @param size_x the width of the map along the NE/SW edge

    32

 * @param size_y the 'height' of the map along the SE/NW edge

    33

 */

    34

void AllocateMap(uint size_x, uint size_y)

    35

{

    36

	/* Make sure that the map size is within the limits and that

    37

	 * the x axis size is a power of 2. */

    38

	if (size_x < 64 || size_x > 2048 ||

    39

			size_y < 64 || size_y > 2048 ||

    40

			(size_x & (size_x - 1)) != 0 ||

    41

			(size_y & (size_y - 1)) != 0)

    42

		error("Invalid map size");

    43

    44

	DEBUG(map, 1, "Allocating map of size %dx%d", size_x, size_y);

    45

    46

	_map_log_x = FindFirstBit(size_x);

    47

	_map_log_y = FindFirstBit(size_y);

    48

	_map_size_x = size_x;

    49

	_map_size_y = size_y;

    50

	_map_size = size_x * size_y;

    51

	_map_tile_mask = _map_size - 1;

    52

    53

	free(_m);

    54

	free(_me);

    55

    56

	/* XXX @todo handle memory shortage more gracefully

    57

	 * CallocT does the out-of-memory check

    58

	 * Maybe some attemps could be made to try with smaller maps down to 64x64

    59

	 * Maybe check for available memory before doing the calls, after all, we know how big

    60

	 * the map is */

    61

	_m = CallocT<Tile>(_map_size);

    62

	_me = CallocT<TileExtended>(_map_size);

    63

}

    64

    65

    66

#ifdef _DEBUG

    67

TileIndex TileAdd(TileIndex tile, TileIndexDiff add,

    68

	const char *exp, const char *file, int line)

    69

{

    70

	int dx;

    71

	int dy;

    72

	uint x;

    73

	uint y;

    74

    75

	dx = add & MapMaxX();

    76

	if (dx >= (int)MapSizeX() / 2) dx -= MapSizeX();

    77

	dy = (add - dx) / (int)MapSizeX();

    78

    79

	x = TileX(tile) + dx;

    80

	y = TileY(tile) + dy;

    81

    82

	if (x >= MapSizeX() || y >= MapSizeY()) {

    83

		char buf[512];

    84

    85

		snprintf(buf, lengthof(buf), "TILE_ADD(%s) when adding 0x%.4X and 0x%.4X failed",

    86

			exp, tile, add);

    87

#if !defined(_MSC_VER) || defined(WINCE)

    88

		fprintf(stderr, "%s:%d %s\n", file, line, buf);

    89

#else

    90

		_assert(buf, (char*)file, line);

    91

#endif

    92

	}

    93

    94

	assert(TileXY(x, y) == TILE_MASK(tile + add));

    95

    96

	return TileXY(x, y);

    97

}

    98

#endif

    99

   100

/*!

   101

 * Scales the given value by the map size, where the given value is

   102

 * for a 256 by 256 map.

   103

 * @param n the value to scale

   104

 * @return the scaled size

   105

 */

   106

uint ScaleByMapSize(uint n)

   107

{

   108

	/* First shift by 12 to prevent integer overflow for large values of n.

   109

	 * >>12 is safe since the min mapsize is 64x64

   110

	 * Add (1<<4)-1 to round upwards. */

   111

	return (n * (MapSize() >> 12) + (1 << 4) - 1) >> 4;

   112

}

   113

   114

   115

/*!

   116

 * Scales the given value by the maps circumference, where the given

   117

 * value is for a 256 by 256 map

   118

 * @param n the value to scale

   119

 * @return the scaled size

   120

 */

   121

uint ScaleByMapSize1D(uint n)

   122

{

   123

	/* Normal circumference for the X+Y is 256+256 = 1<<9

   124

	 * Note, not actually taking the full circumference into account,

   125

	 * just half of it.

   126

	 * (1<<9) - 1 is there to scale upwards. */

   127

	return (n * (MapSizeX() + MapSizeY()) + (1 << 9) - 1) >> 9;

   128

}

   129

   130

   131

/*!

   132

 * This function checks if we add addx/addy to tile, if we

   133

 * do wrap around the edges. For example, tile = (10,2) and

   134

 * addx = +3 and addy = -4. This function will now return

   135

 * INVALID_TILE, because the y is wrapped. This is needed in

   136

 * for example, farmland. When the tile is not wrapped,

   137

 * the result will be tile + TileDiffXY(addx, addy)

   138

 *

   139

 * @param tile the 'starting' point of the adding

   140

 * @param addx the amount of tiles in the X direction to add

   141

 * @param addy the amount of tiles in the Y direction to add

   142

 * @return translated tile, or INVALID_TILE when it would've wrapped.

   143

 */

   144

TileIndex TileAddWrap(TileIndex tile, int addx, int addy)

   145

{

   146

	uint x = TileX(tile) + addx;

   147

	uint y = TileY(tile) + addy;

   148

   149

	/* Are we about to wrap? */

   150

	if (x < MapMaxX() && y < MapMaxY())

   151

		return tile + TileDiffXY(addx, addy);

   152

   153

	return INVALID_TILE;

   154

}

   155

   156

/** 'Lookup table' for tile offsets given a DiagDirection */

   157

extern const TileIndexDiffC _tileoffs_by_diagdir[] = {

   158

	{-1,  0}, ///< DIAGDIR_NE

   159

	{ 0,  1}, ///< DIAGDIR_SE

   160

	{ 1,  0}, ///< DIAGDIR_SW

   161

	{ 0, -1}  ///< DIAGDIR_NW

   162

};

   163

   164

/** 'Lookup table' for tile offsets given a Direction */

   165

extern const TileIndexDiffC _tileoffs_by_dir[] = {

   166

	{-1, -1}, ///< DIR_N

   167

	{-1,  0}, ///< DIR_NE

   168

	{-1,  1}, ///< DIR_E

   169

	{ 0,  1}, ///< DIR_SE

   170

	{ 1,  1}, ///< DIR_S

   171

	{ 1,  0}, ///< DIR_SW

   172

	{ 1, -1}, ///< DIR_W

   173

	{ 0, -1}  ///< DIR_NW

   174

};

   175

   176

/*!

   177

 * Gets the Manhattan distance between the two given tiles.

   178

 * The Manhattan distance is the sum of the delta of both the

   179

 * X and Y component.

   180

 * Also known as L1-Norm

   181

 * @param t0 the start tile

   182

 * @param t1 the end tile

   183

 * @return the distance

   184

 */

   185

uint DistanceManhattan(TileIndex t0, TileIndex t1)

   186

{

   187

	const uint dx = Delta(TileX(t0), TileX(t1));

   188

	const uint dy = Delta(TileY(t0), TileY(t1));

   189

	return dx + dy;

   190

}

   191

   192

   193

/*!

   194

 * Gets the 'Square' distance between the two given tiles.

   195

 * The 'Square' distance is the square of the shortest (straight line)

   196

 * distance between the two tiles.

   197

 * Also known as euclidian- or L2-Norm squared.

   198

 * @param t0 the start tile

   199

 * @param t1 the end tile

   200

 * @return the distance

   201

 */

   202

uint DistanceSquare(TileIndex t0, TileIndex t1)

   203

{

   204

	const int dx = TileX(t0) - TileX(t1);

   205

	const int dy = TileY(t0) - TileY(t1);

   206

	return dx * dx + dy * dy;

   207

}

   208

   209

   210

/*!

   211

 * Gets the biggest distance component (x or y) between the two given tiles.

   212

 * Also known as L-Infinity-Norm.

   213

 * @param t0 the start tile

   214

 * @param t1 the end tile

   215

 * @return the distance

   216

 */

   217

uint DistanceMax(TileIndex t0, TileIndex t1)

   218

{

   219

	const uint dx = Delta(TileX(t0), TileX(t1));

   220

	const uint dy = Delta(TileY(t0), TileY(t1));

   221

	return max(dx, dy);

   222

}

   223

   224

   225

/*!

   226

 * Gets the biggest distance component (x or y) between the two given tiles

   227

 * plus the Manhattan distance, i.e. two times the biggest distance component

   228

 * and once the smallest component.

   229

 * @param t0 the start tile

   230

 * @param t1 the end tile

   231

 * @return the distance

   232

 */

   233

uint DistanceMaxPlusManhattan(TileIndex t0, TileIndex t1)

   234

{

   235

	const uint dx = Delta(TileX(t0), TileX(t1));

   236

	const uint dy = Delta(TileY(t0), TileY(t1));

   237

	return dx > dy ? 2 * dx + dy : 2 * dy + dx;

   238

}

   239

   240

/*!

   241

 * Param the minimum distance to an edge

   242

 * @param tile the tile to get the distance from

   243

 * @return the distance from the edge in tiles

   244

 */

   245

uint DistanceFromEdge(TileIndex tile)

   246

{

   247

	const uint xl = TileX(tile);

   248

	const uint yl = TileY(tile);

   249

	const uint xh = MapSizeX() - 1 - xl;

   250

	const uint yh = MapSizeY() - 1 - yl;

   251

	const uint minl = min(xl, yl);

   252

	const uint minh = min(xh, yh);

   253

	return min(minl, minh);

   254

}

   255

   256

/*!

   257

 * Function performing a search around a center tile and going outward, thus in circle.

   258

 * Although it really is a square search...

   259

 * Every tile will be tested by means of the callback function proc,

   260

 * which will determine if yes or no the given tile meets criteria of search.

   261

 * @param tile to start the search from. Upon completion, it will return the tile matching the search

   262

 * @param size: number of tiles per side of the desired search area

   263

 * @param proc: callback testing function pointer.

   264

 * @param data to be passed to the callback function. Depends on the implementation

   265

 * @return result of the search

   266

 * @pre proc != NULL

   267

 * @pre size > 0

   268

 */

   269

bool CircularTileSearch(TileIndex *tile, uint size, TestTileOnSearchProc proc, uint32 data)

   270

{

   271

	uint n, x, y;

   272

	DiagDirection dir;

   273

   274

	assert(proc != NULL);

   275

	assert(size > 0);

   276

   277

	x = TileX(*tile);

   278

	y = TileY(*tile);

   279

   280

	if (size % 2 == 1) {

   281

		/* If the length of the side is uneven, the center has to be checked

   282

		 * separately, as the pattern of uneven sides requires to go around the center */

   283

		n = 2;

   284

		if (proc(TileXY(x, y), data)) {

   285

			*tile = TileXY(x, y);

   286

			return true;

   287

		}

   288

   289

		/* If tile test is not successful, get one tile down and left,

   290

		 * ready for a test in first circle around center tile */

   291

		x += _tileoffs_by_dir[DIR_W].x;

   292

		y += _tileoffs_by_dir[DIR_W].y;

   293

	} else {

   294

		n = 1;

   295

		/* To use _tileoffs_by_diagdir's order, we must relocate to

   296

		 * another tile, as we now first go 'up', 'right', 'down', 'left'

   297

		 * instead of 'right', 'down', 'left', 'up', which the calling

   298

		 * function assume. */

   299

		x++;

   300

	}

   301

   302

	for (; n < size; n += 2) {

   303

		for (dir = DIAGDIR_NE; dir < DIAGDIR_END; dir++) {

   304

			uint j;

   305

			for (j = n; j != 0; j--) {

   306

				if (x <= MapMaxX() && y <= MapMaxY() && ///< Is the tile within the map?

   307

						proc(TileXY(x, y), data)) {     ///< Is the callback successful?

   308

					*tile = TileXY(x, y);

   309

					return true;                        ///< then stop the search

   310

				}

   311

   312

				/* Step to the next 'neighbour' in the circular line */

   313

				x += _tileoffs_by_diagdir[dir].x;

   314

				y += _tileoffs_by_diagdir[dir].y;

   315

			}

   316

		}

   317

		/* Jump to next circle to test */

   318

		x += _tileoffs_by_dir[DIR_W].x;

   319

		y += _tileoffs_by_dir[DIR_W].y;

   320

	}

   321

   322

	*tile = INVALID_TILE;

   323

	return false;

   324

}