1 /*
2 * This file is part of OpenTTD.
3 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
4 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
5 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
6 */
7
8 /** @file map.cpp Base functions related to the map and distances on them. */
9
10 #include "stdafx.h"
11 #include "debug.h"
12 #include "core/alloc_func.hpp"
13 #include "water_map.h"
14 #include "string_func.h"
15
16 #include "safeguards.h"
17
18 #if defined(_MSC_VER)
19 /* Why the hell is that not in all MSVC headers?? */
20 extern "C" _CRTIMP void __cdecl _assert(void *, void *, unsigned);
21 #endif
22
23 uint _map_log_x; ///< 2^_map_log_x == _map_size_x
24 uint _map_log_y; ///< 2^_map_log_y == _map_size_y
25 uint _map_size_x; ///< Size of the map along the X
26 uint _map_size_y; ///< Size of the map along the Y
27 uint _map_size; ///< The number of tiles on the map
28 uint _map_tile_mask; ///< _map_size - 1 (to mask the mapsize)
29
30 Tile *_m = nullptr; ///< Tiles of the map
31 TileExtended *_me = nullptr; ///< Extended Tiles of the map
32
33
34 /**
35 * (Re)allocates a map with the given dimension
36 * @param size_x the width of the map along the NE/SW edge
37 * @param size_y the 'height' of the map along the SE/NW edge
38 */
AllocateMap(uint size_x,uint size_y)39 void AllocateMap(uint size_x, uint size_y)
40 {
41 /* Make sure that the map size is within the limits and that
42 * size of both axes is a power of 2. */
43 if (!IsInsideMM(size_x, MIN_MAP_SIZE, MAX_MAP_SIZE + 1) ||
44 !IsInsideMM(size_y, MIN_MAP_SIZE, MAX_MAP_SIZE + 1) ||
45 (size_x & (size_x - 1)) != 0 ||
46 (size_y & (size_y - 1)) != 0) {
47 error("Invalid map size");
48 }
49
50 Debug(map, 1, "Allocating map of size {}x{}", size_x, size_y);
51
52 _map_log_x = FindFirstBit(size_x);
53 _map_log_y = FindFirstBit(size_y);
54 _map_size_x = size_x;
55 _map_size_y = size_y;
56 _map_size = size_x * size_y;
57 _map_tile_mask = _map_size - 1;
58
59 free(_m);
60 free(_me);
61
62 _m = CallocT<Tile>(_map_size);
63 _me = CallocT<TileExtended>(_map_size);
64 }
65
66
67 #ifdef _DEBUG
TileAdd(TileIndex tile,TileIndexDiff add,const char * exp,const char * file,int line)68 TileIndex TileAdd(TileIndex tile, TileIndexDiff add,
69 const char *exp, const char *file, int line)
70 {
71 int dx;
72 int dy;
73 uint x;
74 uint y;
75
76 dx = add & MapMaxX();
77 if (dx >= (int)MapSizeX() / 2) dx -= MapSizeX();
78 dy = (add - dx) / (int)MapSizeX();
79
80 x = TileX(tile) + dx;
81 y = TileY(tile) + dy;
82
83 if (x >= MapSizeX() || y >= MapSizeY()) {
84 char buf[512];
85
86 seprintf(buf, lastof(buf), "TILE_ADD(%s) when adding 0x%.4X and 0x%.4X failed",
87 exp, tile, add);
88 #if !defined(_MSC_VER)
89 fprintf(stderr, "%s:%d %s\n", file, line, buf);
90 #else
91 _assert(buf, (char*)file, line);
92 #endif
93 }
94
95 assert(TileXY(x, y) == TILE_MASK(tile + add));
96
97 return TileXY(x, y);
98 }
99 #endif
100
101 /**
102 * This function checks if we add addx/addy to tile, if we
103 * do wrap around the edges. For example, tile = (10,2) and
104 * addx = +3 and addy = -4. This function will now return
105 * INVALID_TILE, because the y is wrapped. This is needed in
106 * for example, farmland. When the tile is not wrapped,
107 * the result will be tile + TileDiffXY(addx, addy)
108 *
109 * @param tile the 'starting' point of the adding
110 * @param addx the amount of tiles in the X direction to add
111 * @param addy the amount of tiles in the Y direction to add
112 * @return translated tile, or INVALID_TILE when it would've wrapped.
113 */
TileAddWrap(TileIndex tile,int addx,int addy)114 TileIndex TileAddWrap(TileIndex tile, int addx, int addy)
115 {
116 uint x = TileX(tile) + addx;
117 uint y = TileY(tile) + addy;
118
119 /* Disallow void tiles at the north border. */
120 if ((x == 0 || y == 0) && _settings_game.construction.freeform_edges) return INVALID_TILE;
121
122 /* Are we about to wrap? */
123 if (x >= MapMaxX() || y >= MapMaxY()) return INVALID_TILE;
124
125 return TileXY(x, y);
126 }
127
128 /** 'Lookup table' for tile offsets given a DiagDirection */
129 extern const TileIndexDiffC _tileoffs_by_diagdir[] = {
130 {-1, 0}, ///< DIAGDIR_NE
131 { 0, 1}, ///< DIAGDIR_SE
132 { 1, 0}, ///< DIAGDIR_SW
133 { 0, -1} ///< DIAGDIR_NW
134 };
135
136 /** 'Lookup table' for tile offsets given a Direction */
137 extern const TileIndexDiffC _tileoffs_by_dir[] = {
138 {-1, -1}, ///< DIR_N
139 {-1, 0}, ///< DIR_NE
140 {-1, 1}, ///< DIR_E
141 { 0, 1}, ///< DIR_SE
142 { 1, 1}, ///< DIR_S
143 { 1, 0}, ///< DIR_SW
144 { 1, -1}, ///< DIR_W
145 { 0, -1} ///< DIR_NW
146 };
147
148 /**
149 * Gets the Manhattan distance between the two given tiles.
150 * The Manhattan distance is the sum of the delta of both the
151 * X and Y component.
152 * Also known as L1-Norm
153 * @param t0 the start tile
154 * @param t1 the end tile
155 * @return the distance
156 */
DistanceManhattan(TileIndex t0,TileIndex t1)157 uint DistanceManhattan(TileIndex t0, TileIndex t1)
158 {
159 const uint dx = Delta(TileX(t0), TileX(t1));
160 const uint dy = Delta(TileY(t0), TileY(t1));
161 return dx + dy;
162 }
163
164
165 /**
166 * Gets the 'Square' distance between the two given tiles.
167 * The 'Square' distance is the square of the shortest (straight line)
168 * distance between the two tiles.
169 * Also known as euclidian- or L2-Norm squared.
170 * @param t0 the start tile
171 * @param t1 the end tile
172 * @return the distance
173 */
DistanceSquare(TileIndex t0,TileIndex t1)174 uint DistanceSquare(TileIndex t0, TileIndex t1)
175 {
176 const int dx = TileX(t0) - TileX(t1);
177 const int dy = TileY(t0) - TileY(t1);
178 return dx * dx + dy * dy;
179 }
180
181
182 /**
183 * Gets the biggest distance component (x or y) between the two given tiles.
184 * Also known as L-Infinity-Norm.
185 * @param t0 the start tile
186 * @param t1 the end tile
187 * @return the distance
188 */
DistanceMax(TileIndex t0,TileIndex t1)189 uint DistanceMax(TileIndex t0, TileIndex t1)
190 {
191 const uint dx = Delta(TileX(t0), TileX(t1));
192 const uint dy = Delta(TileY(t0), TileY(t1));
193 return std::max(dx, dy);
194 }
195
196
197 /**
198 * Gets the biggest distance component (x or y) between the two given tiles
199 * plus the Manhattan distance, i.e. two times the biggest distance component
200 * and once the smallest component.
201 * @param t0 the start tile
202 * @param t1 the end tile
203 * @return the distance
204 */
DistanceMaxPlusManhattan(TileIndex t0,TileIndex t1)205 uint DistanceMaxPlusManhattan(TileIndex t0, TileIndex t1)
206 {
207 const uint dx = Delta(TileX(t0), TileX(t1));
208 const uint dy = Delta(TileY(t0), TileY(t1));
209 return dx > dy ? 2 * dx + dy : 2 * dy + dx;
210 }
211
212 /**
213 * Param the minimum distance to an edge
214 * @param tile the tile to get the distance from
215 * @return the distance from the edge in tiles
216 */
DistanceFromEdge(TileIndex tile)217 uint DistanceFromEdge(TileIndex tile)
218 {
219 const uint xl = TileX(tile);
220 const uint yl = TileY(tile);
221 const uint xh = MapSizeX() - 1 - xl;
222 const uint yh = MapSizeY() - 1 - yl;
223 const uint minl = std::min(xl, yl);
224 const uint minh = std::min(xh, yh);
225 return std::min(minl, minh);
226 }
227
228 /**
229 * Gets the distance to the edge of the map in given direction.
230 * @param tile the tile to get the distance from
231 * @param dir the direction of interest
232 * @return the distance from the edge in tiles
233 */
DistanceFromEdgeDir(TileIndex tile,DiagDirection dir)234 uint DistanceFromEdgeDir(TileIndex tile, DiagDirection dir)
235 {
236 switch (dir) {
237 case DIAGDIR_NE: return TileX(tile) - (_settings_game.construction.freeform_edges ? 1 : 0);
238 case DIAGDIR_NW: return TileY(tile) - (_settings_game.construction.freeform_edges ? 1 : 0);
239 case DIAGDIR_SW: return MapMaxX() - TileX(tile) - 1;
240 case DIAGDIR_SE: return MapMaxY() - TileY(tile) - 1;
241 default: NOT_REACHED();
242 }
243 }
244
245 /**
246 * Function performing a search around a center tile and going outward, thus in circle.
247 * Although it really is a square search...
248 * Every tile will be tested by means of the callback function proc,
249 * which will determine if yes or no the given tile meets criteria of search.
250 * @param tile to start the search from. Upon completion, it will return the tile matching the search
251 * @param size: number of tiles per side of the desired search area
252 * @param proc: callback testing function pointer.
253 * @param user_data to be passed to the callback function. Depends on the implementation
254 * @return result of the search
255 * @pre proc != nullptr
256 * @pre size > 0
257 */
CircularTileSearch(TileIndex * tile,uint size,TestTileOnSearchProc proc,void * user_data)258 bool CircularTileSearch(TileIndex *tile, uint size, TestTileOnSearchProc proc, void *user_data)
259 {
260 assert(proc != nullptr);
261 assert(size > 0);
262
263 if (size % 2 == 1) {
264 /* If the length of the side is uneven, the center has to be checked
265 * separately, as the pattern of uneven sides requires to go around the center */
266 if (proc(*tile, user_data)) return true;
267
268 /* If tile test is not successful, get one tile up,
269 * ready for a test in first circle around center tile */
270 *tile = TileAddByDir(*tile, DIR_N);
271 return CircularTileSearch(tile, size / 2, 1, 1, proc, user_data);
272 } else {
273 return CircularTileSearch(tile, size / 2, 0, 0, proc, user_data);
274 }
275 }
276
277 /**
278 * Generalized circular search allowing for rectangles and a hole.
279 * Function performing a search around a center rectangle and going outward.
280 * The center rectangle is left out from the search. To do a rectangular search
281 * without a hole, set either h or w to zero.
282 * Every tile will be tested by means of the callback function proc,
283 * which will determine if yes or no the given tile meets criteria of search.
284 * @param tile to start the search from. Upon completion, it will return the tile matching the search.
285 * This tile should be directly north of the hole (if any).
286 * @param radius How many tiles to search outwards. Note: This is a radius and thus different
287 * from the size parameter of the other CircularTileSearch function, which is a diameter.
288 * @param w the width of the inner rectangle
289 * @param h the height of the inner rectangle
290 * @param proc callback testing function pointer.
291 * @param user_data to be passed to the callback function. Depends on the implementation
292 * @return result of the search
293 * @pre proc != nullptr
294 * @pre radius > 0
295 */
CircularTileSearch(TileIndex * tile,uint radius,uint w,uint h,TestTileOnSearchProc proc,void * user_data)296 bool CircularTileSearch(TileIndex *tile, uint radius, uint w, uint h, TestTileOnSearchProc proc, void *user_data)
297 {
298 assert(proc != nullptr);
299 assert(radius > 0);
300
301 uint x = TileX(*tile) + w + 1;
302 uint y = TileY(*tile);
303
304 const uint extent[DIAGDIR_END] = { w, h, w, h };
305
306 for (uint n = 0; n < radius; n++) {
307 for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
308 /* Is the tile within the map? */
309 for (uint j = extent[dir] + n * 2 + 1; j != 0; j--) {
310 if (x < MapSizeX() && y < MapSizeY()) {
311 TileIndex t = TileXY(x, y);
312 /* Is the callback successful? */
313 if (proc(t, user_data)) {
314 /* Stop the search */
315 *tile = t;
316 return true;
317 }
318 }
319
320 /* Step to the next 'neighbour' in the circular line */
321 x += _tileoffs_by_diagdir[dir].x;
322 y += _tileoffs_by_diagdir[dir].y;
323 }
324 }
325 /* Jump to next circle to test */
326 x += _tileoffs_by_dir[DIR_W].x;
327 y += _tileoffs_by_dir[DIR_W].y;
328 }
329
330 *tile = INVALID_TILE;
331 return false;
332 }
333
334 /**
335 * Finds the distance for the closest tile with water/land given a tile
336 * @param tile the tile to find the distance too
337 * @param water whether to find water or land
338 * @return distance to nearest water (max 0x7F) / land (max 0x1FF; 0x200 if there is no land)
339 */
GetClosestWaterDistance(TileIndex tile,bool water)340 uint GetClosestWaterDistance(TileIndex tile, bool water)
341 {
342 if (HasTileWaterGround(tile) == water) return 0;
343
344 uint max_dist = water ? 0x7F : 0x200;
345
346 int x = TileX(tile);
347 int y = TileY(tile);
348
349 uint max_x = MapMaxX();
350 uint max_y = MapMaxY();
351 uint min_xy = _settings_game.construction.freeform_edges ? 1 : 0;
352
353 /* go in a 'spiral' with increasing manhattan distance in each iteration */
354 for (uint dist = 1; dist < max_dist; dist++) {
355 /* next 'diameter' */
356 y--;
357
358 /* going counter-clockwise around this square */
359 for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
360 static const int8 ddx[DIAGDIR_END] = { -1, 1, 1, -1};
361 static const int8 ddy[DIAGDIR_END] = { 1, 1, -1, -1};
362
363 int dx = ddx[dir];
364 int dy = ddy[dir];
365
366 /* each side of this square has length 'dist' */
367 for (uint a = 0; a < dist; a++) {
368 /* MP_VOID tiles are not checked (interval is [min; max) for IsInsideMM())*/
369 if (IsInsideMM(x, min_xy, max_x) && IsInsideMM(y, min_xy, max_y)) {
370 TileIndex t = TileXY(x, y);
371 if (HasTileWaterGround(t) == water) return dist;
372 }
373 x += dx;
374 y += dy;
375 }
376 }
377 }
378
379 if (!water) {
380 /* no land found - is this a water-only map? */
381 for (TileIndex t = 0; t < MapSize(); t++) {
382 if (!IsTileType(t, MP_VOID) && !IsTileType(t, MP_WATER)) return 0x1FF;
383 }
384 }
385
386 return max_dist;
387 }
388