|
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 } |