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_func.h Functions related to maps. */
9
10 #ifndef MAP_FUNC_H
11 #define MAP_FUNC_H
12
13 #include "core/math_func.hpp"
14 #include "tile_type.h"
15 #include "map_type.h"
16 #include "direction_func.h"
17
18 extern uint _map_tile_mask;
19
20 /**
21 * 'Wraps' the given tile to it is within the map. It does
22 * this by masking the 'high' bits of.
23 * @param x the tile to 'wrap'
24 */
25
26 #define TILE_MASK(x) ((x) & _map_tile_mask)
27
28 /**
29 * Pointer to the tile-array.
30 *
31 * This variable points to the tile-array which contains the tiles of
32 * the map.
33 */
34 extern Tile *_m;
35
36 /**
37 * Pointer to the extended tile-array.
38 *
39 * This variable points to the extended tile-array which contains the tiles
40 * of the map.
41 */
42 extern TileExtended *_me;
43
44 void AllocateMap(uint size_x, uint size_y);
45
46 /**
47 * Logarithm of the map size along the X side.
48 * @note try to avoid using this one
49 * @return 2^"return value" == MapSizeX()
50 */
MapLogX()51 static inline uint MapLogX()
52 {
53 extern uint _map_log_x;
54 return _map_log_x;
55 }
56
57 /**
58 * Logarithm of the map size along the y side.
59 * @note try to avoid using this one
60 * @return 2^"return value" == MapSizeY()
61 */
MapLogY()62 static inline uint MapLogY()
63 {
64 extern uint _map_log_y;
65 return _map_log_y;
66 }
67
68 /**
69 * Get the size of the map along the X
70 * @return the number of tiles along the X of the map
71 */
MapSizeX()72 static inline uint MapSizeX()
73 {
74 extern uint _map_size_x;
75 return _map_size_x;
76 }
77
78 /**
79 * Get the size of the map along the Y
80 * @return the number of tiles along the Y of the map
81 */
MapSizeY()82 static inline uint MapSizeY()
83 {
84 extern uint _map_size_y;
85 return _map_size_y;
86 }
87
88 /**
89 * Get the size of the map
90 * @return the number of tiles of the map
91 */
MapSize()92 static inline uint MapSize()
93 {
94 extern uint _map_size;
95 return _map_size;
96 }
97
98 /**
99 * Gets the maximum X coordinate within the map, including MP_VOID
100 * @return the maximum X coordinate
101 */
MapMaxX()102 static inline uint MapMaxX()
103 {
104 return MapSizeX() - 1;
105 }
106
107 /**
108 * Gets the maximum Y coordinate within the map, including MP_VOID
109 * @return the maximum Y coordinate
110 */
MapMaxY()111 static inline uint MapMaxY()
112 {
113 return MapSizeY() - 1;
114 }
115
116 /**
117 * Scales the given value by the map size, where the given value is
118 * for a 256 by 256 map.
119 * @param n the value to scale
120 * @return the scaled size
121 */
ScaleByMapSize(uint n)122 static inline uint ScaleByMapSize(uint n)
123 {
124 /* Subtract 12 from shift in order to prevent integer overflow
125 * for large values of n. It's safe since the min mapsize is 64x64. */
126 return CeilDiv(n << (MapLogX() + MapLogY() - 12), 1 << 4);
127 }
128
129
130 /**
131 * Scales the given value by the maps circumference, where the given
132 * value is for a 256 by 256 map
133 * @param n the value to scale
134 * @return the scaled size
135 */
ScaleByMapSize1D(uint n)136 static inline uint ScaleByMapSize1D(uint n)
137 {
138 /* Normal circumference for the X+Y is 256+256 = 1<<9
139 * Note, not actually taking the full circumference into account,
140 * just half of it. */
141 return CeilDiv((n << MapLogX()) + (n << MapLogY()), 1 << 9);
142 }
143
144 /**
145 * An offset value between to tiles.
146 *
147 * This value is used for the difference between
148 * two tiles. It can be added to a tileindex to get
149 * the resulting tileindex of the start tile applied
150 * with this saved difference.
151 *
152 * @see TileDiffXY(int, int)
153 */
154 typedef int32 TileIndexDiff;
155
156 /**
157 * Returns the TileIndex of a coordinate.
158 *
159 * @param x The x coordinate of the tile
160 * @param y The y coordinate of the tile
161 * @return The TileIndex calculated by the coordinate
162 */
TileXY(uint x,uint y)163 static inline TileIndex TileXY(uint x, uint y)
164 {
165 return (y << MapLogX()) + x;
166 }
167
168 /**
169 * Calculates an offset for the given coordinate(-offset).
170 *
171 * This function calculate an offset value which can be added to an
172 * #TileIndex. The coordinates can be negative.
173 *
174 * @param x The offset in x direction
175 * @param y The offset in y direction
176 * @return The resulting offset value of the given coordinate
177 * @see ToTileIndexDiff(TileIndexDiffC)
178 */
TileDiffXY(int x,int y)179 static inline TileIndexDiff TileDiffXY(int x, int y)
180 {
181 /* Multiplication gives much better optimization on MSVC than shifting.
182 * 0 << shift isn't optimized to 0 properly.
183 * Typically x and y are constants, and then this doesn't result
184 * in any actual multiplication in the assembly code.. */
185 return (y * MapSizeX()) + x;
186 }
187
188 /**
189 * Get a tile from the virtual XY-coordinate.
190 * @param x The virtual x coordinate of the tile.
191 * @param y The virtual y coordinate of the tile.
192 * @return The TileIndex calculated by the coordinate.
193 */
TileVirtXY(uint x,uint y)194 static inline TileIndex TileVirtXY(uint x, uint y)
195 {
196 return (y >> 4 << MapLogX()) + (x >> 4);
197 }
198
199
200 /**
201 * Get the X component of a tile
202 * @param tile the tile to get the X component of
203 * @return the X component
204 */
TileX(TileIndex tile)205 static inline uint TileX(TileIndex tile)
206 {
207 return tile & MapMaxX();
208 }
209
210 /**
211 * Get the Y component of a tile
212 * @param tile the tile to get the Y component of
213 * @return the Y component
214 */
TileY(TileIndex tile)215 static inline uint TileY(TileIndex tile)
216 {
217 return tile >> MapLogX();
218 }
219
220 /**
221 * Return the offset between to tiles from a TileIndexDiffC struct.
222 *
223 * This function works like #TileDiffXY(int, int) and returns the
224 * difference between two tiles.
225 *
226 * @param tidc The coordinate of the offset as TileIndexDiffC
227 * @return The difference between two tiles.
228 * @see TileDiffXY(int, int)
229 */
ToTileIndexDiff(TileIndexDiffC tidc)230 static inline TileIndexDiff ToTileIndexDiff(TileIndexDiffC tidc)
231 {
232 return (tidc.y << MapLogX()) + tidc.x;
233 }
234
235
236 #ifndef _DEBUG
237 /**
238 * Adds to tiles together.
239 *
240 * @param x One tile
241 * @param y Another tile to add
242 * @return The resulting tile(index)
243 */
244 # define TILE_ADD(x, y) ((x) + (y))
245 #else
246 extern TileIndex TileAdd(TileIndex tile, TileIndexDiff add,
247 const char *exp, const char *file, int line);
248 # define TILE_ADD(x, y) (TileAdd((x), (y), #x " + " #y, __FILE__, __LINE__))
249 #endif
250
251 /**
252 * Adds a given offset to a tile.
253 *
254 * @param tile The tile to add an offset on it
255 * @param x The x offset to add to the tile
256 * @param y The y offset to add to the tile
257 */
258 #define TILE_ADDXY(tile, x, y) TILE_ADD(tile, TileDiffXY(x, y))
259
260 TileIndex TileAddWrap(TileIndex tile, int addx, int addy);
261
262 /**
263 * Returns the TileIndexDiffC offset from a DiagDirection.
264 *
265 * @param dir The given direction
266 * @return The offset as TileIndexDiffC value
267 */
TileIndexDiffCByDiagDir(DiagDirection dir)268 static inline TileIndexDiffC TileIndexDiffCByDiagDir(DiagDirection dir)
269 {
270 extern const TileIndexDiffC _tileoffs_by_diagdir[DIAGDIR_END];
271
272 assert(IsValidDiagDirection(dir));
273 return _tileoffs_by_diagdir[dir];
274 }
275
276 /**
277 * Returns the TileIndexDiffC offset from a Direction.
278 *
279 * @param dir The given direction
280 * @return The offset as TileIndexDiffC value
281 */
TileIndexDiffCByDir(Direction dir)282 static inline TileIndexDiffC TileIndexDiffCByDir(Direction dir)
283 {
284 extern const TileIndexDiffC _tileoffs_by_dir[DIR_END];
285
286 assert(IsValidDirection(dir));
287 return _tileoffs_by_dir[dir];
288 }
289
290 /**
291 * Add a TileIndexDiffC to a TileIndex and returns the new one.
292 *
293 * Returns tile + the diff given in diff. If the result tile would end up
294 * outside of the map, INVALID_TILE is returned instead.
295 *
296 * @param tile The base tile to add the offset on
297 * @param diff The offset to add on the tile
298 * @return The resulting TileIndex
299 */
AddTileIndexDiffCWrap(TileIndex tile,TileIndexDiffC diff)300 static inline TileIndex AddTileIndexDiffCWrap(TileIndex tile, TileIndexDiffC diff)
301 {
302 int x = TileX(tile) + diff.x;
303 int y = TileY(tile) + diff.y;
304 /* Negative value will become big positive value after cast */
305 if ((uint)x >= MapSizeX() || (uint)y >= MapSizeY()) return INVALID_TILE;
306 return TileXY(x, y);
307 }
308
309 /**
310 * Returns the diff between two tiles
311 *
312 * @param tile_a from tile
313 * @param tile_b to tile
314 * @return the difference between tila_a and tile_b
315 */
TileIndexToTileIndexDiffC(TileIndex tile_a,TileIndex tile_b)316 static inline TileIndexDiffC TileIndexToTileIndexDiffC(TileIndex tile_a, TileIndex tile_b)
317 {
318 TileIndexDiffC difference;
319
320 difference.x = TileX(tile_a) - TileX(tile_b);
321 difference.y = TileY(tile_a) - TileY(tile_b);
322
323 return difference;
324 }
325
326 /* Functions to calculate distances */
327 uint DistanceManhattan(TileIndex, TileIndex); ///< also known as L1-Norm. Is the shortest distance one could go over diagonal tracks (or roads)
328 uint DistanceSquare(TileIndex, TileIndex); ///< euclidian- or L2-Norm squared
329 uint DistanceMax(TileIndex, TileIndex); ///< also known as L-Infinity-Norm
330 uint DistanceMaxPlusManhattan(TileIndex, TileIndex); ///< Max + Manhattan
331 uint DistanceFromEdge(TileIndex); ///< shortest distance from any edge of the map
332 uint DistanceFromEdgeDir(TileIndex, DiagDirection); ///< distance from the map edge in given direction
333
334 /**
335 * Convert a DiagDirection to a TileIndexDiff
336 *
337 * @param dir The DiagDirection
338 * @return The resulting TileIndexDiff
339 * @see TileIndexDiffCByDiagDir
340 */
TileOffsByDiagDir(DiagDirection dir)341 static inline TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
342 {
343 extern const TileIndexDiffC _tileoffs_by_diagdir[DIAGDIR_END];
344
345 assert(IsValidDiagDirection(dir));
346 return ToTileIndexDiff(_tileoffs_by_diagdir[dir]);
347 }
348
349 /**
350 * Convert a Direction to a TileIndexDiff.
351 *
352 * @param dir The direction to convert from
353 * @return The resulting TileIndexDiff
354 */
TileOffsByDir(Direction dir)355 static inline TileIndexDiff TileOffsByDir(Direction dir)
356 {
357 extern const TileIndexDiffC _tileoffs_by_dir[DIR_END];
358
359 assert(IsValidDirection(dir));
360 return ToTileIndexDiff(_tileoffs_by_dir[dir]);
361 }
362
363 /**
364 * Adds a Direction to a tile.
365 *
366 * @param tile The current tile
367 * @param dir The direction in which we want to step
368 * @return the moved tile
369 */
TileAddByDir(TileIndex tile,Direction dir)370 static inline TileIndex TileAddByDir(TileIndex tile, Direction dir)
371 {
372 return TILE_ADD(tile, TileOffsByDir(dir));
373 }
374
375 /**
376 * Adds a DiagDir to a tile.
377 *
378 * @param tile The current tile
379 * @param dir The direction in which we want to step
380 * @return the moved tile
381 */
TileAddByDiagDir(TileIndex tile,DiagDirection dir)382 static inline TileIndex TileAddByDiagDir(TileIndex tile, DiagDirection dir)
383 {
384 return TILE_ADD(tile, TileOffsByDiagDir(dir));
385 }
386
387 /**
388 * Determines the DiagDirection to get from one tile to another.
389 * The tiles do not necessarily have to be adjacent.
390 * @param tile_from Origin tile
391 * @param tile_to Destination tile
392 * @return DiagDirection from tile_from towards tile_to, or INVALID_DIAGDIR if the tiles are not on an axis
393 */
DiagdirBetweenTiles(TileIndex tile_from,TileIndex tile_to)394 static inline DiagDirection DiagdirBetweenTiles(TileIndex tile_from, TileIndex tile_to)
395 {
396 int dx = (int)TileX(tile_to) - (int)TileX(tile_from);
397 int dy = (int)TileY(tile_to) - (int)TileY(tile_from);
398 if (dx == 0) {
399 if (dy == 0) return INVALID_DIAGDIR;
400 return (dy < 0 ? DIAGDIR_NW : DIAGDIR_SE);
401 } else {
402 if (dy != 0) return INVALID_DIAGDIR;
403 return (dx < 0 ? DIAGDIR_NE : DIAGDIR_SW);
404 }
405 }
406
407 /**
408 * A callback function type for searching tiles.
409 *
410 * @param tile The tile to test
411 * @param user_data additional data for the callback function to use
412 * @return A boolean value, depend on the definition of the function.
413 */
414 typedef bool TestTileOnSearchProc(TileIndex tile, void *user_data);
415
416 bool CircularTileSearch(TileIndex *tile, uint size, TestTileOnSearchProc proc, void *user_data);
417 bool CircularTileSearch(TileIndex *tile, uint radius, uint w, uint h, TestTileOnSearchProc proc, void *user_data);
418
419 /**
420 * Get a random tile out of a given seed.
421 * @param r the random 'seed'
422 * @return a valid tile
423 */
RandomTileSeed(uint32 r)424 static inline TileIndex RandomTileSeed(uint32 r)
425 {
426 return TILE_MASK(r);
427 }
428
429 /**
430 * Get a valid random tile.
431 * @note a define so 'random' gets inserted in the place where it is actually
432 * called, thus making the random traces more explicit.
433 * @return a valid tile
434 */
435 #define RandomTile() RandomTileSeed(Random())
436
437 uint GetClosestWaterDistance(TileIndex tile, bool water);
438
439 #endif /* MAP_FUNC_H */
440