1

/* $Id$ */

     2

     3

#include "stdafx.h"

     4

#include "openttd.h"

     5

#include "debug.h"

     6

#include "functions.h"

     7

#include "macros.h"

     8

#include "map.h"

     9

#include "direction.h"

    10

    11

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

    12

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

    13

_CRTIMP void __cdecl _assert(void *, void *, unsigned);

    14

#endif

    15

    16

uint _map_log_x;

    17

uint _map_size_x;

    18

uint _map_size_y;

    19

uint _map_tile_mask;

    20

uint _map_size;

    21

    22

Tile* _m = NULL;

    23

    24

    25

void AllocateMap(uint size_x, uint size_y)

    26

{

    27

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

    28

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

    29

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

    30

			size_y < 64 || size_y > 2048 ||

    31

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

    32

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

    33

		error("Invalid map size");

    34

    35

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

    36

    37

	_map_log_x = FindFirstBit(size_x);

    38

	_map_size_x = size_x;

    39

	_map_size_y = size_y;

    40

	_map_size = size_x * size_y;

    41

	_map_tile_mask = _map_size - 1;

    42

    43

	free(_m);

    44

	_m = calloc(_map_size, sizeof(*_m));

    45

    46

	// XXX TODO handle memory shortage more gracefully

    47

	if (_m == NULL) error("Failed to allocate memory for the map");

    48

}

    49

    50

    51

#ifdef _DEBUG

    52

TileIndex TileAdd(TileIndex tile, TileIndexDiff add,

    53

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

    54

{

    55

	int dx;

    56

	int dy;

    57

	uint x;

    58

	uint y;

    59

    60

	dx = add & MapMaxX();

    61

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

    62

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

    63

    64

	x = TileX(tile) + dx;

    65

	y = TileY(tile) + dy;

    66

    67

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

    68

		char buf[512];

    69

    70

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

    71

			exp, tile, add);

    72

#if !defined(_MSC_VER)

    73

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

    74

#else

    75

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

    76

#endif

    77

	}

    78

    79

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

    80

    81

	return TileXY(x,y);

    82

}

    83

#endif

    84

    85

    86

uint ScaleByMapSize(uint n)

    87

{

    88

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

    89

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

    90

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

    91

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

    92

}

    93

    94

    95

// Scale relative to the circumference of the map

    96

uint ScaleByMapSize1D(uint n)

    97

{

    98

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

    99

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

   100

	// just half of it.

   101

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

   102

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

   103

}

   104

   105

   106

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

   107

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

   108

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

   109

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

   110

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

   111

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

   112

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

   113

{

   114

	uint x = TileX(tile) + addx;

   115

	uint y = TileY(tile) + addy;

   116

   117

	// Are we about to wrap?

   118

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

   119

		return tile + TileDiffXY(addx, addy);

   120

   121

	return INVALID_TILE;

   122

}

   123

   124

const TileIndexDiffC _tileoffs_by_diagdir[] = {

   125

	{-1,  0}, // DIAGDIR_NE

   126

	{ 0,  1}, // DIAGDIR_SE

   127

	{ 1,  0}, // DIAGDIR_SW

   128

	{ 0, -1}  // DIAGDIR_NW

   129

};

   130

   131

const TileIndexDiffC _tileoffs_by_dir[] = {

   132

	{-1, -1}, // DIR_N

   133

	{-1,  0}, // DIR_NE

   134

	{-1,  1}, // DIR_E

   135

	{ 0,  1}, // DIR_SE

   136

	{ 1,  1}, // DIR_S

   137

	{ 1,  0}, // DIR_SW

   138

	{ 1, -1}, // DIR_W

   139

	{ 0, -1}  // DIR_NW

   140

};

   141

   142

uint DistanceManhattan(TileIndex t0, TileIndex t1)

   143

{

   144

	const uint dx = abs(TileX(t0) - TileX(t1));

   145

	const uint dy = abs(TileY(t0) - TileY(t1));

   146

	return dx + dy;

   147

}

   148

   149

   150

uint DistanceSquare(TileIndex t0, TileIndex t1)

   151

{

   152

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

   153

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

   154

	return dx * dx + dy * dy;

   155

}

   156

   157

   158

uint DistanceMax(TileIndex t0, TileIndex t1)

   159

{

   160

	const uint dx = abs(TileX(t0) - TileX(t1));

   161

	const uint dy = abs(TileY(t0) - TileY(t1));

   162

	return dx > dy ? dx : dy;

   163

}

   164

   165

   166

uint DistanceMaxPlusManhattan(TileIndex t0, TileIndex t1)

   167

{

   168

	const uint dx = abs(TileX(t0) - TileX(t1));

   169

	const uint dy = abs(TileY(t0) - TileY(t1));

   170

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

   171

}

   172

   173

uint DistanceFromEdge(TileIndex tile)

   174

{

   175

	const uint xl = TileX(tile);

   176

	const uint yl = TileY(tile);

   177

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

   178

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

   179

	const uint minl = xl < yl ? xl : yl;

   180

	const uint minh = xh < yh ? xh : yh;

   181

	return minl < minh ? minl : minh;

   182

}

   183

   184

/**

   185

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

   186

 * Although it really is a square search...

   187

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

   188

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

   189

 * @param tile to start the search from

   190

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

   191

 * @param proc: callback testing function pointer.

   192

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

   193

 * @result of the search

   194

 * @pre proc != NULL

   195

 * @pre size > 0

   196

 */

   197

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

   198

{

   199

	uint n, x, y;

   200

	DiagDirection dir;

   201

   202

	assert(proc != NULL);

   203

	assert(size > 0);

   204

   205

	x = TileX(tile);

   206

	y = TileY(tile);

   207

   208

	if (size % 2 == 1) {

   209

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

   210

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

   211

		n = 2;

   212

		if (proc(TileXY(x, y), data)) return true;

   213

   214

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

   215

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

   216

		x += _tileoffs_by_dir[DIR_W].x;

   217

		y += _tileoffs_by_dir[DIR_W].y;

   218

	} else {

   219

		n = 1;

   220

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

   221

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

   222

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

   223

		 * function assume. */

   224

		x++;

   225

	}

   226

   227

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

   228

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

   229

			uint j;

   230

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

   231

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

   232

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

   233

					return true;                        ///< then stop the search

   234

				}

   235

   236

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

   237

				x += _tileoffs_by_diagdir[dir].x;

   238

				y += _tileoffs_by_diagdir[dir].y;

   239

			}

   240

		}

   241

		/* Jump to next circle to test */

   242

		x += _tileoffs_by_dir[DIR_W].x;

   243

		y += _tileoffs_by_dir[DIR_W].y;

   244

	}

   245

	return false;

   246

}