1

/* $Id$ */

     2

     3

/** @file map.cpp */

     4

     5

#include "stdafx.h"

     6

#include "openttd.h"

     7

#include "debug.h"

     8

#include "functions.h"

     9

#include "macros.h"

    10

#include "map.h"

    11

#include "direction.h"

    12

#include "helpers.hpp"

    13

    14

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

    15

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

    16

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

    17

#endif

    18

    19

uint _map_log_x;

    20

uint _map_size_x;

    21

uint _map_size_y;

    22

uint _map_tile_mask;

    23

uint _map_size;

    24

    25

Tile *_m = NULL;

    26

TileExtended *_me = NULL;

    27

    28

    29

void AllocateMap(uint size_x, uint size_y)

    30

{

    31

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

    32

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

    33

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

    34

			size_y < 64 || size_y > 2048 ||

    35

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

    36

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

    37

		error("Invalid map size");

    38

    39

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

    40

    41

	_map_log_x = FindFirstBit(size_x);

    42

	_map_size_x = size_x;

    43

	_map_size_y = size_y;

    44

	_map_size = size_x * size_y;

    45

	_map_tile_mask = _map_size - 1;

    46

    47

	free(_m);

    48

	free(_me);

    49

    50

	_m = CallocT<Tile>(_map_size);

    52

    57

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

    58

}

    59

    60

    61

#ifdef _DEBUG

    62

TileIndex TileAdd(TileIndex tile, TileIndexDiff add,

    63

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

    64

{

    65

	int dx;

    66

	int dy;

    67

	uint x;

    68

	uint y;

    69

    70

	dx = add & MapMaxX();

    71

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

    72

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

    73

    74

	x = TileX(tile) + dx;

    75

	y = TileY(tile) + dy;

    76

    77

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

    78

		char buf[512];

    79

    80

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

    81

			exp, tile, add);

    82

#if !defined(_MSC_VER)

    83

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

    84

#else

    85

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

    86

#endif

    87

	}

    88

    90

    92

}

    93

#endif

    94

    95

    96

uint ScaleByMapSize(uint n)

    97

{

    98

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

    99

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

   100

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

   102

}

   103

   104

   105

/* Scale relative to the circumference of the map */

   106

uint ScaleByMapSize1D(uint n)

   107

{

   108

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

   109

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

   110

	 * just half of it.

   111

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

   113

}

   114

   115

   116

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

   117

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

   118

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

   119

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

   120

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

   121

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

   122

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

   123

{

   124

	uint x = TileX(tile) + addx;

   125

	uint y = TileY(tile) + addy;

   126

   127

	/* Are we about to wrap? */

   128

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

   129

		return tile + TileDiffXY(addx, addy);

   130

   131

	return INVALID_TILE;

   132

}

   133

   134

extern const TileIndexDiffC _tileoffs_by_diagdir[] = {

   135

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

   136

	{ 0,  1}, ///< DIAGDIR_SE

   137

	{ 1,  0}, ///< DIAGDIR_SW

   138

	{ 0, -1}  ///< DIAGDIR_NW

   139

};

   140

   141

extern const TileIndexDiffC _tileoffs_by_dir[] = {

   142

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

   143

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

   144

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

   145

	{ 0,  1}, ///< DIR_SE

   146

	{ 1,  1}, ///< DIR_S

   147

	{ 1,  0}, ///< DIR_SW

   148

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

   149

	{ 0, -1}  ///< DIR_NW

   150

};

   151

   152

uint DistanceManhattan(TileIndex t0, TileIndex t1)

   153

{

   154

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

   155

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

   156

	return dx + dy;

   157

}

   158

   159

   160

uint DistanceSquare(TileIndex t0, TileIndex t1)

   161

{

   162

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

   163

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

   164

	return dx * dx + dy * dy;

   165

}

   166

   167

   168

uint DistanceMax(TileIndex t0, TileIndex t1)

   169

{

   170

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

   171

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

   172

	return dx > dy ? dx : dy;

   173

}

   174

   175

   176

uint DistanceMaxPlusManhattan(TileIndex t0, TileIndex t1)

   177

{

   178

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

   179

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

   180

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

   181

}

   182

   183

uint DistanceFromEdge(TileIndex tile)

   184

{

   185

	const uint xl = TileX(tile);

   186

	const uint yl = TileY(tile);

   187

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

   188

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

   189

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

   190

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

   191

	return minl < minh ? minl : minh;

   192

}

   193

   194

/**

   195

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

   196

 * Although it really is a square search...

   197

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

   198

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

   199

 * @param tile to start the search from

   200

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

   201

 * @param proc: callback testing function pointer.

   202

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

   203

 * @return result of the search

   204

 * @pre proc != NULL

   205

 * @pre size > 0

   206

 */

   207

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

   208

{

   209

	uint n, x, y;

   210

	DiagDirection dir;

   211

   212

	assert(proc != NULL);

   213

	assert(size > 0);

   214

   215

	x = TileX(tile);

   216

	y = TileY(tile);

   217

   218

	if (size % 2 == 1) {

   219

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

   220

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

   221

		n = 2;

   222

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

   223

   224

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

   225

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

   226

		x += _tileoffs_by_dir[DIR_W].x;

   227

		y += _tileoffs_by_dir[DIR_W].y;

   228

	} else {

   229

		n = 1;

   230

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

   231

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

   232

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

   233

		 * function assume. */

   234

		x++;

   235

	}

   236

   237

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

   238

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

   239

			uint j;

   240

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

   241

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

   242

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

   243

					return true;                        ///< then stop the search

   244

				}

   245

   246

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

   247

				x += _tileoffs_by_diagdir[dir].x;

   248

				y += _tileoffs_by_diagdir[dir].y;

   249

			}

   250

		}

   251

		/* Jump to next circle to test */

   252

		x += _tileoffs_by_dir[DIR_W].x;

   253

		y += _tileoffs_by_dir[DIR_W].y;

   254

	}

   255

	return false;

   256

}