File: | server/sv_rma.cpp |
Location: | line 1316, column 3 |
Description: | Value stored to 'ty' is never read |
1 | /** |
2 | * @file |
3 | * @brief Random map assembly code |
4 | * More info on map-assembly can be found at: |
5 | * http://ufoai.org/wiki/index.php/Mapping/Random_map_assembly |
6 | */ |
7 | |
8 | /* |
9 | All original material Copyright (C) 2002-2011 UFO: Alien Invasion. |
10 | |
11 | Original file from Quake 2 v3.21: quake2-2.31/server/sv_init.c |
12 | |
13 | Copyright (C) 1997-2001 Id Software, Inc. |
14 | |
15 | This program is free software; you can redistribute it and/or |
16 | modify it under the terms of the GNU General Public License |
17 | as published by the Free Software Foundation; either version 2 |
18 | of the License, or (at your option) any later version. |
19 | |
20 | This program is distributed in the hope that it will be useful, |
21 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
22 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. |
23 | |
24 | See the GNU General Public License for more details. |
25 | |
26 | You should have received a copy of the GNU General Public License |
27 | along with this program; if not, write to the Free Software |
28 | Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
29 | |
30 | */ |
31 | |
32 | #include "server.h" |
33 | #include "sv_rma.h" |
34 | #include "../shared/parse.h" |
35 | #include "../shared/mutex.h" |
36 | |
37 | #define ASSEMBLE_THREADS2 2 |
38 | /** @brief print some debugging info */ |
39 | #define PRINT_RMA_PROGRESS0 0 |
40 | /** @brief place the biggest 'required' tiles first. Helps oriental a lot, but is bad for village. */ |
41 | #define SORT_BY_SIZE1 1 |
42 | |
43 | /** @brief max # of recursions */ |
44 | #define RMA2_MAX_REC64 64 |
45 | /** @brief max # of valid tile/position combinations */ |
46 | /* How to calculate this value: |
47 | * Take he largest map of the project, eg. +farm |
48 | * farm large has a size of 12x12. |
49 | * If we had only 'fits everywhere'-tiles of size 1x1, |
50 | * we'd need 12x12=144 x tiletypes(25) = 3600 (in theory). |
51 | * Larger tiles eg. 2x2 would reduce the positions from 144 to 11x11=121 |
52 | * Required tiles with exactly one instance ie. "1 1" reduce both the # of tiletypes |
53 | * and the # of positions by their size. |
54 | * The neighbouring requirements of required tiles will further reduce the value. |
55 | * => It's best to determine a working value empirically. |
56 | */ |
57 | #define RMA2_MAX_TILEPOS1700 1700 |
58 | /** @brief tile code multiplier. For the various debug printfs we want a number that we can easily divide through (20, 50, 100,...) */ |
59 | #define TCM50 50 |
60 | /** @brief the # of different tiles we can store for a gap */ |
61 | #define GAPS25 25 |
62 | /** @brief array of working random tile positions, 50 recursions */ |
63 | static short posTileList[RMA2_MAX_REC64][RMA2_MAX_TILEPOS1700]; |
64 | /** @brief for every x/y we can store the tiles that can cover that place here */ |
65 | static short gapList[MAX_RANDOM_MAP_HEIGHT32][MAX_RANDOM_MAP_HEIGHT32][GAPS25 + 1]; |
66 | static SDL_sem *mapSem; |
67 | static SDL_cond *mapCond; |
68 | static threads_mutex_t *mapLock; |
69 | static Uint32 threadID; |
70 | |
71 | /** |
72 | * @brief Fills a list with random values between @c 0 and @c n |
73 | * @param[in] n Size of the list |
74 | * @param[out] list The list to fill with random values |
75 | */ |
76 | static void RandomList (const int n, short *list) |
77 | { |
78 | short i; |
79 | |
80 | for (i = 0; i < n; i++) |
81 | list[i] = i; |
82 | |
83 | for (i = 0; i < n; i++) { |
84 | const short r = rand() % (i + (n - i)); |
85 | const short t = list[r]; |
86 | list[r] = list[i]; |
87 | list[i] = t; |
88 | } |
89 | } |
90 | |
91 | #define ALL_TILES(0xfffffffeUL) (0xfffffffeUL) |
92 | #define IS_SOLID(x)((x)&1UL) ((x)&1UL) |
93 | |
94 | /** |
95 | * @brief Convert to tile spec - normalize the characters |
96 | * @sa SV_ParseMapTile |
97 | * @note a tile definition looks like this: |
98 | * @code tile +s02 |
99 | * { |
100 | * 3 3 |
101 | * |
102 | * 0 a 0 |
103 | * b +b b |
104 | * 0 a 0 |
105 | * } |
106 | * @endcode |
107 | * tile +s02 defines the name of the tile which can be refered to from the assembly |
108 | * the first two numbers defines the tile size - if you have a tile with the 'real' |
109 | * size of 1x1 (256x256 in radiant) the definition is 3x3 because you have to |
110 | * define the surroundings, too |
111 | * The field marked with the + is the 'real' mapparts all the others are the |
112 | * surroundings - the letters of the surroundings must have a tile definition with |
113 | * a + and the letter, too - otherwise the placing of the tile may fail |
114 | * |
115 | * @note If you marked a tile with + the mTile_t->spec at that position will be SOLID |
116 | * @note valid tile characters are 0-5 and a-z |
117 | */ |
118 | static unsigned long tileMask (const char chr) |
119 | { |
120 | if (chr == '+') |
121 | return 1UL; |
122 | else if (chr == '0') |
123 | return ALL_TILES(0xfffffffeUL); |
124 | else if (chr >= '1' && chr <= '5') |
125 | return 1UL << (chr - '0'); |
126 | else if (chr >= 'a' && chr <= 'z') |
127 | return 1UL << (chr - 'a' + 6); |
128 | else if (chr >= 'A' && chr <= 'Z') |
129 | return 1UL << (chr - 'A' + 6); |
130 | |
131 | Com_Error(ERR_DROP1, "SV_ParseMapTile: Invalid tile char '%c'", chr); |
132 | } |
133 | |
134 | static void SV_TileMaskToString (unsigned long m, char *str) |
135 | { |
136 | int i; |
137 | int j = 0; /* writepos */ |
138 | |
139 | if (m == ALL_TILES(0xfffffffeUL)) { |
140 | str[0] = '0'; |
141 | str[1] = 0; |
142 | return; |
143 | } |
144 | if (m & 1) { |
145 | str[0] = '+'; |
146 | j = 1; |
147 | } |
148 | for (i = 1; i < 6; i++) { |
149 | if (m >> i & 1) { |
150 | str[j] = '0' + i; |
151 | j++; |
152 | } |
153 | } |
154 | for (i = 6; i < 32; i++) { |
155 | if (m >> i & 1) { |
156 | str[j] = 'a' - 6 + i; |
157 | j++; |
158 | } |
159 | } |
160 | str[j] = 0; |
161 | } |
162 | |
163 | #define ACW6 6 /* ascii cell width */ |
164 | #define ACH3 3 /* ascii cell height */ |
165 | #define MMW13 13 /* map max height 13 means we support 12 */ |
166 | #define MMH13 13 /* map max height */ |
167 | static void SV_RmaPrintMap (const mapInfo_t *map) |
168 | { |
169 | char screen[(MMH13 + 1) * ACH3][(MMW13 + 1) * ACW6]; |
170 | int i, j; |
171 | |
172 | assert(map->mAssembly[map->mAsm].height < MMH)(__builtin_expect(!(map->mAssembly[map->mAsm].height < 13), 0) ? __assert_rtn(__func__, "src/server/sv_rma.cpp", 172 , "map->mAssembly[map->mAsm].height < MMH") : (void) 0); |
173 | assert(map->mAssembly[map->mAsm].width < MMW)(__builtin_expect(!(map->mAssembly[map->mAsm].width < 13), 0) ? __assert_rtn(__func__, "src/server/sv_rma.cpp", 173 , "map->mAssembly[map->mAsm].width < MMW") : (void)0 ); |
174 | |
175 | /* initialize */ |
176 | int rb = (1 + map->mAssembly[map->mAsm].width) * ACW6; /* index of right border */ |
177 | OBJSET(screen, ' ')(memset(&(screen), (' '), sizeof(screen))); |
178 | for (i = 0; i < MMH13 * ACH3 + 1; i++) { |
179 | screen[i][rb + 1] = '|'; |
180 | screen[i][rb + 2] = 0; |
181 | } |
182 | |
183 | /* fill in the data */ |
184 | for (i = 0; i < map->numPlaced; i++) { |
185 | const mPlaced_t *mp = &map->mPlaced[i]; |
186 | const mTile_t *tile = mp->tile; |
187 | int tx, ty; |
188 | const char *tn = tile->id + 1; |
189 | |
190 | if (!strncmp(tn, "craft_", 6)) |
191 | tn += 6; |
192 | for (ty = 0; ty < tile->h; ty++) { |
193 | for (tx = 0; tx < tile->w; tx++) { |
194 | if (IS_SOLID(tile->spec[ty][tx])((tile->spec[ty][tx])&1UL)) { |
195 | int cbX = ACW6 * (mp->x + tx); |
196 | int cbY = ACH3 * (mp->y + ty); |
197 | char flags[33] = {0,}; |
198 | |
199 | /* write the tilename */ |
200 | for (j = 0; j < ACW6 - 1; j++) { |
201 | if (tn[j]) |
202 | screen[cbY + ACH3 - 1][cbX + 1 + j] = tn[j]; |
203 | else |
204 | break; |
205 | } |
206 | |
207 | /* get the properties of that solid */ |
208 | SV_TileMaskToString(tile->spec[ty][tx], flags); |
209 | /* write the flags */ |
210 | for (j = 0; j < ACW6 - 1; j++) { |
211 | if (flags[j]) |
212 | screen[cbY + ACH3 - 2][cbX + 1 + j] = flags[j]; |
213 | else |
214 | break; |
215 | } |
216 | |
217 | |
218 | /* left border of tile */ |
219 | if (tx > 0 && !IS_SOLID(tile->spec[ty][tx - 1])((tile->spec[ty][tx - 1])&1UL)) { |
220 | for (j = 0; j < ACH3; j++) |
221 | screen[cbY + j][cbX] = '!'; |
222 | } |
223 | if (!IS_SOLID(tile->spec[ty][tx + 1])((tile->spec[ty][tx + 1])&1UL)) { |
224 | for (j = 0; j < ACH3; j++) |
225 | screen[cbY + j][cbX + ACW6] = '!'; |
226 | } |
227 | if (ty > 0 && !IS_SOLID(tile->spec[ty - 1][tx])((tile->spec[ty - 1][tx])&1UL)) { |
228 | for (j = 1; j < ACW6; j++) |
229 | screen[cbY][cbX + j] = '-'; |
230 | } |
231 | if (!IS_SOLID(tile->spec[ty + 1][tx])((tile->spec[ty + 1][tx])&1UL)) { |
232 | for (j = 1; j < ACW6; j++) |
233 | screen[cbY + ACH3][cbX + j] = '-'; |
234 | } |
235 | } |
236 | } |
237 | } |
238 | } |
239 | |
240 | /* now add the specs of the gaps */ |
241 | int cx, cy; |
242 | int height = map->mAssembly[map->mAsm].height; |
243 | int width = map->mAssembly[map->mAsm].width; |
244 | for (cy = 0; cy <= height; cy++) { |
245 | for (cx = 0; cx <= width; cx++) { |
246 | if (!IS_SOLID(map->curMap[cy][cx])((map->curMap[cy][cx])&1UL)) { |
247 | const int cbX = ACW6 * (cx); |
248 | const int cbY = ACH3 * (cy); |
249 | char flags2[33] = {0,}; |
250 | |
251 | /* get the requirements of that gap */ |
252 | SV_TileMaskToString(map->curMap[cy][cx], flags2); |
253 | /* write the flags */ |
254 | for (j = 0; j < ACW6 - 1; j++) { |
255 | if (flags2[j]) |
256 | screen[cbY + ACH3 - 2][cbX + 1 + j] = flags2[j]; |
257 | else |
258 | break; |
259 | } |
260 | } |
261 | } |
262 | } |
263 | |
264 | /* print it */ |
265 | const char *underscores = "_________________________________________________________________________\n"; |
266 | Com_Printf("\nCurrent state of the map:\n"); |
267 | int w = ACW6 * (MMW13 - 1 - map->mAssembly[map->mAsm].width); |
268 | Com_Printf("%s", underscores + w); |
269 | int h = ACH3 * (height + 1); |
270 | for (i = h; i >= ACH3; i--) |
271 | Com_Printf("%s\n", screen[i] + ACW6); |
272 | Com_Printf("%s", underscores + w); |
273 | } |
274 | |
275 | static const mTileSet_t *SV_GetMapTileSet (const mapInfo_t *map, const char *tileSetName) |
276 | { |
277 | int i; |
278 | |
279 | for (i = 0; i < map->numTileSets; i++) { |
280 | const mTileSet_t *tileSet = &map->mTileSets[i]; |
281 | if (Q_streq(tileSetName, tileSet->id)(strcmp(tileSetName, tileSet->id) == 0)) |
282 | return tileSet; |
283 | } |
284 | |
285 | return NULL__null; |
286 | } |
287 | |
288 | static inline const mTile_t *SV_GetMapTile (const mapInfo_t *map, const char *tileName) |
289 | { |
290 | int i; |
291 | |
292 | for (i = 0; i < map->numTiles; i++) { |
293 | const mTile_t *tile = &map->mTile[i]; |
294 | if (Q_streq(tileName, tile->id)(strcmp(tileName, tile->id) == 0)) |
295 | return tile; |
296 | } |
297 | |
298 | return NULL__null; |
299 | } |
300 | |
301 | /** |
302 | * @brief Parsed a tileset definition out of the ump-files |
303 | * @sa SV_ParseAssembly |
304 | * @sa SV_AssembleMap |
305 | */ |
306 | static bool SV_ParseMapTileSet (const char *filename, const char **text, mapInfo_t *map, bool inherit) |
307 | { |
308 | const char *errhead = "SV_ParseMapTileSet: Unexpected end of file ("; |
309 | const char *token; |
310 | mTileSet_t *target = &map->mTileSets[map->numTileSets]; |
311 | |
312 | OBJZERO(*target)(memset(&((*target)), (0), sizeof((*target)))); |
313 | |
314 | /* get tileset name */ |
315 | token = Com_EParse(text, errhead, filename); |
316 | if (!*text) |
317 | return false; |
318 | |
319 | Q_strncpyz(target->id, token, sizeof(target->id))Q_strncpyzDebug( target->id, token, sizeof(target->id), "src/server/sv_rma.cpp", 319 ); |
320 | |
321 | /* start parsing the block */ |
322 | token = Com_EParse(text, errhead, filename); |
323 | if (!*text) |
324 | return false; |
325 | if (*token != '{') { |
326 | Com_Printf("SV_ParseMapTileSet: Expected '{' for tileset '%s' (%s)\n", target->id, filename); |
327 | return false; |
328 | } |
329 | |
330 | do { |
331 | token = Com_EParse(text, errhead, filename); |
332 | if (!*text) |
333 | return false; |
334 | if (token[0] != '}') { |
335 | if (target->numTiles >= MAX_TILESETTILES8) |
336 | Com_Error(ERR_DROP1, "Max tileset limit reached for tileset '%s'", target->id); |
337 | else { /* just to get rid of the 'mixed decl and code' warning */ |
338 | char *tileTarget = target->tiles[target->numTiles]; |
339 | const size_t size = sizeof(target->tiles[target->numTiles]); |
340 | if (inherit) { |
341 | if (token[0] == '+') |
342 | token++; |
343 | |
344 | Com_sprintf(tileTarget, size, "%s%s", map->inheritBasePath, token); |
345 | } else { |
346 | Q_strncpyz(tileTarget, token, size)Q_strncpyzDebug( tileTarget, token, size, "src/server/sv_rma.cpp" , 346 ); |
347 | } |
348 | |
349 | if (SV_GetMapTile(map, tileTarget) != NULL__null) |
350 | target->numTiles++; |
351 | else |
352 | Com_Error(ERR_DROP1, "Did not find tile '%s' from tileset '%s'", tileTarget, target->id); |
353 | } |
354 | } |
355 | } while (token[0] != '}'); |
356 | |
357 | map->numTileSets++; |
358 | return false; |
359 | } |
360 | |
361 | /** |
362 | * @brief Parsed a tile definition out of the ump-files |
363 | * @sa SV_ParseAssembly |
364 | * @sa SV_AssembleMap |
365 | */ |
366 | static bool SV_ParseMapTile (const char *filename, const char **text, mapInfo_t *map, bool inherit) |
367 | { |
368 | const char *errhead = "SV_ParseMapTile: Unexpected end of file ("; |
369 | const char *token; |
370 | int x, y, i; |
371 | mTile_t *target = &map->mTile[map->numTiles]; |
372 | target->area = 0; |
373 | |
374 | /* get tile name */ |
375 | token = Com_EParse(text, errhead, filename); |
376 | if (!*text) |
377 | return false; |
378 | |
379 | OBJZERO(*target)(memset(&((*target)), (0), sizeof((*target)))); |
380 | |
381 | if (inherit) { |
382 | if (token[0] == '+') |
383 | token++; |
384 | Com_sprintf(target->id, sizeof(target->id), "%s%s", map->inheritBasePath, token); |
385 | } else { |
386 | Q_strncpyz(target->id, token, sizeof(target->id))Q_strncpyzDebug( target->id, token, sizeof(target->id), "src/server/sv_rma.cpp", 386 ); |
387 | } |
388 | |
389 | /* start parsing the block */ |
390 | token = Com_EParse(text, errhead, filename); |
391 | if (!*text) |
392 | return false; |
393 | if (*token != '{') { |
394 | Com_Printf("SV_ParseMapTile: Expected '{' for tile '%s' (%s)\n", target->id, filename); |
395 | return false; |
396 | } |
397 | |
398 | /* get width and height */ |
399 | token = Com_EParse(text, errhead, filename); |
400 | if (!*text) |
401 | return false; |
402 | target->w = atoi(token); |
403 | |
404 | token = Com_EParse(text, errhead, filename); |
405 | if (!*text) |
406 | return false; |
407 | target->h = atoi(token); |
408 | |
409 | if (target->w > MAX_TILESIZE16 || target->h > MAX_TILESIZE16) { |
410 | Com_Printf("SV_ParseMapTile: Bad tile size [%i %i] (%s) (max. [%i %i])\n", target->w, target->h, filename, MAX_TILESIZE16, MAX_TILESIZE16); |
411 | *text = strchr(*text, '}'); |
412 | return false; |
413 | } |
414 | |
415 | /* get tile specs */ |
416 | for (y = target->h - 1; y >= 0; y--) |
417 | for (x = 0; x < target->w; x++) { |
418 | token = Com_EParse(text, errhead, filename); |
419 | if (!*text || *token == '}') { |
420 | Com_Printf("SV_ParseMapTile: Bad tile desc in '%s' - not enough entries for size\n", target->id); |
421 | *text = strchr(*text, '}') + 1; |
422 | return 0; |
423 | } |
424 | target->spec[y][x] = 0UL; |
425 | for (i = 0; token[i]; i++) { |
426 | target->spec[y][x] |= tileMask(token[i]); |
427 | } |
428 | if (IS_SOLID(target->spec[y][x])((target->spec[y][x])&1UL)) |
429 | target->area++; /* # of solid tiles */ |
430 | } |
431 | |
432 | token = Com_EParse(text, errhead, filename); |
433 | |
434 | /* get connections */ |
435 | if (*token != '}') |
436 | Com_Printf("SV_ParseMapTile: Bad tile desc in '%s' - too many entries for size\n", target->id); |
437 | |
438 | /* successfully parsed - this tile counts */ |
439 | return true; |
440 | } |
441 | |
442 | /** |
443 | * @brief Tries to extract a tile name from a cvar - the cvar value must start with a '+' |
444 | * @param a the assembly |
445 | * @param token The cvar name |
446 | * @param filename The ump filename |
447 | * @param text The text buffer |
448 | * @param errhead Error header |
449 | * @return @c NULL if file has invalid format, @c the tilename of the cvar otherwise. |
450 | */ |
451 | static const char *SV_GetCvarToken (const mAssembly_t *a, const char* token, const char *filename, const char **text, const char *errhead) |
452 | { |
453 | const cvar_t *cvar; |
454 | |
455 | Com_DPrintf(DEBUG_SERVER0x40, "SV_GetCvarToken: cvar replacement: %s\n", token); |
456 | |
457 | cvar = Cvar_FindVar(token); |
458 | |
459 | token = Com_EParse(text, errhead, filename); |
460 | if (!text || token[0] == '}') |
461 | return NULL__null; |
462 | |
463 | if (cvar == NULL__null) |
464 | return token; |
465 | |
466 | Com_DPrintf(DEBUG_SERVER0x40, "SV_ParseAssembly: cvar replacement value: %s\n", cvar->string); |
467 | if (cvar->string[0] != '+') { |
468 | Com_Printf("SV_ParseAssembly: warning - cvar '%s' value doesn't seam to be a valid tile id '%s' - set to default '%s'\n", |
469 | cvar->name, cvar->string, token); |
470 | Cvar_Set(cvar->name, token); |
471 | if (token[0] != '+') |
472 | Com_Error(ERR_DROP1, "SV_ParseAssembly: wrong tile id in assembly '%s'", a->id); |
473 | |
474 | return token; |
475 | } |
476 | return cvar->string; |
477 | } |
478 | |
479 | static const char *SV_GetTileFromTileSet (const mapInfo_t *map, const char *filename, const char **text, const mAssembly_t *a) |
480 | { |
481 | const char *errhead = "SV_GetTileFromTileSet: Unexpected end of file ("; |
482 | const mTileSet_t *tileSet; |
483 | int random; |
484 | const char *token; |
485 | |
486 | /* get tileset id */ |
487 | token = Com_EParse(text, errhead, filename); |
488 | if (!text) |
489 | Com_Error(ERR_DROP1, "SV_GetTileFromTileSet: illegal tileset syntax in assembly '%s' in %s", a->id, filename); |
490 | |
491 | tileSet = SV_GetMapTileSet(map, token); |
492 | if (tileSet == NULL__null) |
493 | Com_Error(ERR_DROP1, "SV_GetTileFromTileSet: Could not find tileset %s in %s (assembly %s)", token, filename, a->id); |
494 | |
495 | random = rand() % tileSet->numTiles; |
496 | return tileSet->tiles[random]; |
497 | } |
498 | |
499 | /** |
500 | * @brief Parses a list of working seeds to assemble this rma assembly |
501 | * @param[in,out] map All we know about the map to assemble |
502 | * @param[in] filename The name of the .UMP file, used in error messages |
503 | * @param[out] a Pointer to the assembly to be initialized, must be allocated. |
504 | * @param[in] text The text of the ump file to parse |
505 | * @return @c true if it was parsed, @c false if not. |
506 | */ |
507 | static bool SV_ParseAssemblySeeds (mapInfo_t *map, const char *filename, const char **text, mAssembly_t *a) |
508 | { |
509 | const char *errhead = "SV_ParseAssemblySeeds: Unexpected end of file ("; |
510 | const char *token; |
511 | |
512 | /* start parsing the block */ |
513 | token = Com_EParse(text, errhead, filename); |
514 | if (!*text) |
515 | return false; |
516 | if (*token != '{') { |
517 | Com_Printf("SV_ParseAssemblySeeds: Expected '{' for seed of assembly '%s' (%s)\n", a->id, filename); |
518 | return false; |
519 | } |
520 | |
521 | for (;;) { |
522 | token = Com_EParse(text, errhead, filename); |
523 | if (!*text || token[0] == '}') |
524 | break; |
525 | |
526 | if (a->numSeeds < lengthof(a->seeds)(sizeof(a->seeds) / sizeof(*(a->seeds)))) { |
527 | a->seeds[a->numSeeds++] = atoi(token); |
528 | } else { |
529 | Com_Printf("too many seeds for %s (%s) - ignore seed %s\n", a->id, filename, token); |
530 | } |
531 | } |
532 | return true; |
533 | } |
534 | |
535 | static void SV_GetTilesFromTileSet (const mapInfo_t *map, const char *filename, const char **text, mAssembly_t *a) |
536 | { |
537 | const char *errhead = "SV_GetTilesFromTileSet: Unexpected end of file ("; |
538 | const mTileSet_t *tileSet; |
539 | const mTile_t *tile; |
540 | int c, x, y, random; |
541 | const char *token; |
542 | |
543 | /* get tileset id */ |
544 | token = Com_EParse(text, errhead, filename); |
545 | if (!text) |
546 | Com_Error(ERR_DROP1, "SV_GetTilesFromTilesSet: illegal tileset syntax in assembly '%s' in %s", a->id, filename); |
547 | tileSet = SV_GetMapTileSet(map, token); |
548 | if (tileSet == NULL__null) |
549 | Com_Error(ERR_DROP1, "SV_GetTilesFromTilesSet: Could not find tileset %s in %s (assembly %s)", token, filename, a->id); |
550 | |
551 | /* get min and max tileset number */ |
552 | token = Com_EParse(text, errhead, filename); |
553 | if (!text || *token == '}') |
554 | Com_Error(ERR_DROP1, "SV_GetTilesFromTilesSet: Error in assembly %s (invalid syntax for tileset %s)", filename, tileSet->id); |
555 | if (!strstr(token, " ")) |
556 | Com_Error(ERR_DROP1, "SV_GetTilesFromTilesSet: Error in assembly %s (min max value of tileset %s)", filename, tileSet->id); |
557 | sscanf(token, "%i %i", &x, &y); |
558 | if (x > y) |
559 | Com_Error(ERR_DROP1, "SV_GetTilesFromTilesSet: Error in assembly %s (min is bigger than max for tileset %s)", filename, tileSet->id); |
560 | if (y <= 0) |
561 | Com_Error(ERR_DROP1, "SV_GetTilesFromTilesSet: Error in assembly %s (max is <= 0 for tileset %s)", filename, tileSet->id); |
562 | /* set max tile numbers (increasing the max of random tiles until the required max is reached)t */ |
563 | for (c = y; c > 0; c--) { |
564 | random = rand() % tileSet->numTiles; |
565 | tile = SV_GetMapTile(map, tileSet->tiles[random]); |
566 | if (tile != NULL__null) { |
567 | const ptrdiff_t i = tile - map->mTile; |
568 | a->max[i]++; |
569 | } else { |
570 | Com_Error(ERR_DROP1, "Could not find tile: '%s' in tileset '%s' (%s)", tileSet->tiles[random], tileSet->id, filename); |
571 | } |
572 | } |
573 | /* set min tile numbers (increasing the min of random tiles until the required min is reached) */ |
574 | c = x; |
575 | while (c > 0) { |
576 | random = rand() % tileSet->numTiles; |
577 | tile = SV_GetMapTile(map, tileSet->tiles[random]); |
578 | if (tile != NULL__null) { |
579 | const ptrdiff_t i = tile - map->mTile; |
580 | if (a->min[i] < a->max[i]) { |
581 | a->min[i]++; |
582 | c--; |
583 | } |
584 | } else { |
585 | Com_Error(ERR_DROP1, "Could not find tile: '%s' in tileset '%s' (%s)", tileSet->tiles[random], tileSet->id, filename); |
586 | } |
587 | } |
588 | } |
589 | |
590 | /** |
591 | * @brief Parses an assembly block |
592 | * @param[in,out] map All we know about the map to assemble |
593 | * @param[in] filename The name of the .UMP file, used in error messages |
594 | * @param[out] a Pointer to the assembly to be initialized, must be allocated. |
595 | * @param[in] text The text of the ump file to parse |
596 | * @sa SV_AssembleMap |
597 | * @sa SV_ParseMapTile |
598 | * @note: format of size: "size x y" |
599 | * @note: format of fix: "fix [tilename] x y" |
600 | * @note: format of tile: "[tilename] min max" |
601 | * @return @c true if it was parsed, @c false if not. |
602 | */ |
603 | static bool SV_ParseAssembly (mapInfo_t *map, const char *filename, const char **text, mAssembly_t *a) |
604 | { |
605 | const char *errhead = "SV_ParseAssembly: Unexpected end of file ("; |
606 | const char *token; |
607 | int x, y; |
608 | const mTile_t *tile; |
609 | |
610 | /* get assembly name */ |
611 | token = Com_EParse(text, errhead, filename); |
612 | if (!*text) |
613 | return false; |
614 | |
615 | /* init */ |
616 | OBJZERO(*a)(memset(&((*a)), (0), sizeof((*a)))); |
617 | Q_strncpyz(a->id, token, sizeof(a->id))Q_strncpyzDebug( a->id, token, sizeof(a->id), "src/server/sv_rma.cpp" , 617 ); |
618 | a->width = 8; |
619 | a->height = 8; |
620 | a->dx = 1; |
621 | a->dy = 1; |
622 | |
623 | token = Com_EParse(text, errhead, filename); |
624 | if (!*text || *token != '{') |
625 | Com_Error(ERR_DROP1, "Invalid assembly definition '%s' - invalid token '%s' (%s)", a->id, token, filename); |
626 | |
627 | do { |
628 | /* get tile name */ |
629 | token = Com_EParse(text, errhead, filename); |
630 | if (!text || *token == '}') |
631 | break; |
632 | |
633 | if (Q_streq(token, "title")(strcmp(token, "title") == 0)) { |
634 | /* get map title */ |
635 | token = Com_EParse(text, errhead, filename); |
636 | if (!text) |
637 | break; |
638 | |
639 | Q_strncpyz(a->title, token, sizeof(a->title))Q_strncpyzDebug( a->title, token, sizeof(a->title), "src/server/sv_rma.cpp" , 639 ); |
640 | continue; |
641 | } else if (Q_streq(token, "multiplayer")(strcmp(token, "multiplayer") == 0)) { |
642 | /* get map title */ |
643 | token = Com_EParse(text, errhead, filename); |
644 | if (!text) |
645 | break; |
646 | |
647 | /* a multiplayer only tile - forced to be exactly once in the map when |
648 | * we are playing a multiplayer match */ |
649 | if (sv_maxclients->integer >= 2) { |
650 | const mTile_t *t = SV_GetMapTile(map, token); |
651 | if (t != NULL__null) { |
652 | const ptrdiff_t i = t - map->mTile; |
653 | a->min[i] = 1; |
654 | a->max[i] = 1; |
655 | } else { |
656 | Com_Error(ERR_DROP1, "Could not find multiplayer tile: '%s' in assembly '%s' (%s)", token, a->id, filename); |
657 | } |
658 | } |
659 | continue; |
660 | } else if (Q_streq(token, "size")(strcmp(token, "size") == 0)) { |
661 | /* get map size */ |
662 | token = Com_EParse(text, errhead, filename); |
663 | if (!text) |
664 | break; |
665 | |
666 | sscanf(token, "%i %i", &a->width, &a->height); |
667 | a->size = a->width * a->height; |
668 | continue; |
669 | } else if (Q_streq(token, "seeds")(strcmp(token, "seeds") == 0)) { |
670 | if (!SV_ParseAssemblySeeds(map, filename, text, a)) |
671 | return false; |
672 | continue; |
673 | } else if (Q_streq(token, "grid")(strcmp(token, "grid") == 0)) { |
674 | /* get map size */ |
675 | token = Com_EParse(text, errhead, filename); |
676 | if (!text) |
677 | break; |
678 | |
679 | sscanf(token, "%i %i", &a->dx, &a->dy); |
680 | continue; |
681 | /* chose a tile from a tileset */ |
682 | } else if (Q_streq(token, "tileset")(strcmp(token, "tileset") == 0)) { |
683 | SV_GetTilesFromTileSet(map, filename, text, a); |
684 | continue; |
685 | /* fix tilename "x y" */ |
686 | } else if (Q_streq(token, "fix")(strcmp(token, "fix") == 0)) { |
687 | const mTile_t *t; |
688 | |
689 | /* get tile */ |
690 | token = Com_EParse(text, errhead, filename); |
691 | if (!text) |
692 | break; |
693 | |
694 | if (token[0] == '*') { |
695 | token = SV_GetCvarToken(a, token + 1, filename, text, errhead); |
696 | if (token == NULL__null) |
697 | break; |
698 | } else if (Q_streq(token, "tileset")(strcmp(token, "tileset") == 0)) { |
699 | token = SV_GetTileFromTileSet(map, filename, text, a); |
700 | } |
701 | |
702 | t = SV_GetMapTile(map, token); |
703 | if (t != NULL__null) { |
704 | const ptrdiff_t i = t - map->mTile; |
705 | if (a->numFixed >= MAX_FIXEDTILES64) |
706 | Com_Error(ERR_DROP1, "SV_ParseAssembly: Too many fixed tiles in assembly '%s' (%s)", a->id, filename); |
707 | |
708 | /* get coordinates */ |
709 | token = Com_EParse(text, errhead, filename); |
710 | if (!text) |
711 | Com_Error(ERR_DROP1, "SV_ParseAssembly: Error in assembly %s - could not get coordinates for fixed tile", filename); |
712 | |
713 | sscanf(token, "%i %i", &x, &y); |
714 | if (x < 0 || x >= MAX_RANDOM_MAP_WIDTH32) { |
715 | Com_Error(ERR_DROP1, "SV_ParseAssembly: Error, invalid fixed coordinates given for x (%i) boundaries are: [0:%i] (%s).", |
716 | x, MAX_RANDOM_MAP_WIDTH32 - 1, filename); |
717 | } else if (y < 0 || y >= MAX_RANDOM_MAP_HEIGHT32) { |
718 | Com_Error(ERR_DROP1, "SV_ParseAssembly: Error, invalid fixed coordinates given for y (%i) - boundaries are: [0:%i] (%s).", |
719 | y, MAX_RANDOM_MAP_HEIGHT32 - 1, filename); |
720 | } |
721 | a->fX[a->numFixed] = x; |
722 | a->fY[a->numFixed] = y; |
723 | a->fT[a->numFixed] = i; |
724 | a->numFixed++; |
725 | } else |
726 | Com_Error(ERR_DROP1, "Could not find fixed tile: '%s' in assembly '%s' (%s)", token, a->id, filename); |
727 | continue; |
728 | /* <format>*cvarname <defaultvalue> "min max"</format> */ |
729 | } else if (token[0] == '*') { |
730 | token = SV_GetCvarToken(a, token + 1, filename, text, errhead); |
731 | if (token == NULL__null) |
732 | break; |
733 | } |
734 | |
735 | tile = SV_GetMapTile(map, token); |
736 | if (tile != NULL__null) { |
737 | const ptrdiff_t i = tile - map->mTile; |
738 | /* get min and max tile number */ |
739 | token = Com_EParse(text, errhead, filename); |
740 | if (!text || *token == '}') |
741 | Com_Error(ERR_DROP1, "SV_ParseAssembly: Error in assembly %s (invalid syntax for tile %s)", filename, tile->id); |
742 | |
743 | if (!strstr(token, " ")) |
744 | Com_Error(ERR_DROP1, "SV_ParseAssembly: Error in assembly %s (min max value of tile %s)", filename, tile->id); |
745 | |
746 | sscanf(token, "%i %i", &x, &y); |
747 | a->min[i] = x; |
748 | a->max[i] = y; |
749 | if (a->min[i] > a->max[i]) |
750 | Com_Error(ERR_DROP1, "SV_ParseAssembly: Error in assembly %s (min is bigger than max for tile %s)", filename, tile->id); |
751 | if (a->max[i] <= 0) |
752 | Com_Error(ERR_DROP1, "SV_ParseAssembly: Error in assembly %s (max is <= 0 for tile %s)", filename, tile->id); |
753 | } else { |
754 | Com_Error(ERR_DROP1, "Could not find tile: '%s' in assembly '%s' (%s)", token, a->id, filename); |
755 | } |
756 | } while (text); |
757 | |
758 | return true; |
759 | } |
760 | |
761 | |
762 | /** |
763 | * @brief Combines the alternatives/connection info of a map with a tile and sets the rating |
764 | * @param[in,out] mapAlts Pointer to the alternatives info field of the map which will be updated. |
765 | * @param[in] tileAlts Pointer to the alternatives info field of the tile. |
766 | * @param[in,out] mapRating Pointer to the rating field of the map. |
767 | * @sa SV_AssembleMap |
768 | * @sa SV_AddRegion |
769 | * @sa SV_FitTile |
770 | */ |
771 | static void SV_CombineAlternatives (unsigned long *mapAlts, const unsigned long tileAlts, char *mapRating) |
772 | { |
773 | /* don't touch solid fields of the map, return if tile has no connection info */ |
774 | if (IS_SOLID(*mapAlts)((*mapAlts)&1UL) || (tileAlts == ALL_TILES(0xfffffffeUL))) |
775 | return; |
776 | |
777 | /* for an empty map tile the rating must be zero */ |
778 | assert((*mapAlts != ALL_TILES) || (*mapRating == 0))(__builtin_expect(!((*mapAlts != (0xfffffffeUL)) || (*mapRating == 0)), 0) ? __assert_rtn(__func__, "src/server/sv_rma.cpp", 778, "(*mapAlts != ALL_TILES) || (*mapRating == 0)") : (void )0); |
779 | |
780 | /* copy if tile is solid */ |
781 | if (IS_SOLID(tileAlts)((tileAlts)&1UL)) { |
782 | *mapAlts = tileAlts; |
783 | *mapRating = 1; |
784 | /* combine otherways */ |
785 | } else { |
786 | *mapAlts &= tileAlts; |
787 | (*mapRating)--; |
788 | } |
789 | } |
790 | |
791 | /** |
792 | * @brief Reset the map to empty state. |
793 | */ |
794 | static void SV_ClearMap (mapInfo_t *map) |
795 | { |
796 | unsigned long *mp = &map->curMap[0][0]; |
797 | const unsigned long *end = &map->curMap[MAX_RANDOM_MAP_HEIGHT32 - 1][MAX_RANDOM_MAP_WIDTH32 - 1]; |
798 | |
799 | OBJZERO(map->curRating)(memset(&((map->curRating)), (0), sizeof((map->curRating )))); |
800 | |
801 | while (mp <= end) |
802 | *(mp++) = ALL_TILES(0xfffffffeUL); |
803 | } |
804 | |
805 | /** |
806 | * @brief Checks if a given map-tile fits into the empty space (in a given location) of a map. |
807 | * @param[in,out] map All we know about the map to assemble |
808 | * @param[in] tile The tile definition that should be fitted into the map. |
809 | * @param[in] x The x position in the map where the tile is supposed to be placed/checked. |
810 | * @param[in] y The y position in the map where the tile is supposed to be placed/checked. |
811 | * @return @c true if the tile fits, @c false if the tile does not fit or an error was encountered. |
812 | * @sa SV_AddMandatoryParts |
813 | * @sa SV_AddRegion |
814 | */ |
815 | static bool SV_FitTile (const mapInfo_t *map, const mTile_t * tile, const int x, const int y) |
816 | { |
817 | int tx, ty; |
818 | const unsigned long *spec = NULL__null; |
819 | const unsigned long *m = NULL__null; |
820 | const mAssembly_t *mAsm = &map->mAssembly[map->mAsm]; |
821 | |
822 | /* check for valid grid positions */ |
823 | assert(x % mAsm->dx == 0)(__builtin_expect(!(x % mAsm->dx == 0), 0) ? __assert_rtn( __func__, "src/server/sv_rma.cpp", 823, "x % mAsm->dx == 0" ) : (void)0); |
824 | assert(y % mAsm->dy == 0)(__builtin_expect(!(y % mAsm->dy == 0), 0) ? __assert_rtn( __func__, "src/server/sv_rma.cpp", 824, "y % mAsm->dy == 0" ) : (void)0); |
825 | assert(tile)(__builtin_expect(!(tile), 0) ? __assert_rtn(__func__, "src/server/sv_rma.cpp" , 825, "tile") : (void)0); |
826 | |
827 | if (x < 0 || y < 0) |
828 | return false; |
829 | |
830 | /* check for map border */ |
831 | if (x + tile->w > mAsm->width + 2 || y + tile->h > mAsm->height + 2) |
832 | return false; |
833 | unsigned long combined; |
834 | #if 0 |
835 | /* shortcut: most tiles are solid at [1][1], so check this first */ |
836 | spec = &tile->spec[1][1]; |
837 | m = &map->curMap[y+1][x+1]; |
838 | combined = (*m) & (*spec); |
839 | if (IS_SOLID(combined)((combined)&1UL) || !combined) |
840 | return false; |
841 | #endif |
842 | /* test for fit */ |
843 | spec = &tile->spec[0][0]; |
844 | m = &map->curMap[y][x]; |
845 | for (ty = 0; ty < tile->h; ty++) { |
846 | for (tx = 0; tx < tile->w; tx++, spec++, m++) { |
847 | combined = (*m) & (*spec); |
848 | |
849 | /* quit if both are solid or no equal connection is found */ |
850 | if (IS_SOLID(combined)((combined)&1UL) || !combined) |
851 | return false; |
852 | } |
853 | spec += (MAX_TILESIZE16 - tile->w); |
854 | m += (MAX_RANDOM_MAP_WIDTH32 - tile->w); |
855 | } |
856 | |
857 | return true; |
858 | } |
859 | |
860 | /** |
861 | * @brief Checks if the map is completely filled. |
862 | * @return @c true if the map is filled, @c false if the map has still empty fields |
863 | * @sa SV_AssembleMap |
864 | * @sa SV_AddRegion |
865 | * @sa SV_FitTile |
866 | */ |
867 | static bool SV_TestFilled (const mapInfo_t *map) |
868 | { |
869 | int x, y; |
870 | const mAssembly_t *mAsm = &map->mAssembly[map->mAsm]; |
871 | |
872 | for (y = 1; y < mAsm->height + 1; y++) |
873 | for (x = 1; x < mAsm->width + 1; x++) |
874 | if (!IS_SOLID(map->curMap[y][x])((map->curMap[y][x])&1UL)) |
875 | return false; |
876 | |
877 | return true; |
878 | } |
879 | |
880 | /** |
881 | * @brief Debug function to dump the map location of a placed tile. |
882 | */ |
883 | static void SV_DumpPlaced (const mapInfo_t *map, int pl) |
884 | { |
885 | int x, y; |
886 | const mAssembly_t *mAsm = &map->mAssembly[map->mAsm]; |
887 | const int h = mAsm->height; |
888 | const int w = mAsm->width; |
889 | const mPlaced_t *placed = &map->mPlaced[pl]; |
890 | |
891 | Com_Printf("Placed tile %s at %d %d\n", placed->tile->id, placed->x, placed->y); |
892 | |
893 | for (y = h; y >= 1; y--) { |
894 | for (x = 1; x < w + 1; x++) { |
895 | const int dx = x - placed->x; |
896 | const int dy = y - placed->y; |
897 | |
898 | if (dx >= 0 && dx < placed->tile->w && dy >= 0 && dy < placed->tile->h && |
899 | IS_SOLID(placed->tile->spec[dy][dx])((placed->tile->spec[dy][dx])&1UL)) |
900 | Com_Printf(" X"); |
901 | else |
902 | Com_Printf(" ."); |
903 | } |
904 | Com_Printf("\n"); |
905 | } |
906 | Com_Printf("\n"); |
907 | } |
908 | |
909 | /** |
910 | * @brief Adds a new map-tile to an assembled map. Also adds the tile to the placed-tiles list. |
911 | * @note The tile must fit at the given position, otherwise an assert will occur! |
912 | * @param[in,out] map The map that will get the tile. Modified in place. |
913 | * @param[in] tile The tile to add to the map. |
914 | * @param[in] x The x position in the map where the tile should be placed. |
915 | * @param[in] y The y position in the map where the tile should be placed. |
916 | * @param[in] idx The index of the placement algorithm. |
917 | * @param[in] pos The position of the placement algorithm. |
918 | * @sa SV_AssembleMap |
919 | * @sa SV_AddRegion |
920 | * @sa SV_FitTile |
921 | */ |
922 | static void SV_AddTile (mapInfo_t *map, const mTile_t *tile, int x, int y, int idx, int pos) |
923 | { |
924 | int tx, ty; |
925 | #ifdef DEBUG1 |
926 | const mAssembly_t *mAsm = &map->mAssembly[map->mAsm]; |
927 | |
928 | /* check vor valid grid positions */ |
929 | assert(x % mAsm->dx == 0)(__builtin_expect(!(x % mAsm->dx == 0), 0) ? __assert_rtn( __func__, "src/server/sv_rma.cpp", 929, "x % mAsm->dx == 0" ) : (void)0); |
930 | assert(y % mAsm->dy == 0)(__builtin_expect(!(y % mAsm->dy == 0), 0) ? __assert_rtn( __func__, "src/server/sv_rma.cpp", 930, "y % mAsm->dy == 0" ) : (void)0); |
931 | #endif |
932 | |
933 | /* add the new tile */ |
934 | for (ty = 0; ty < tile->h; ty++) |
935 | for (tx = 0; tx < tile->w; tx++) { |
936 | assert(y + ty < MAX_RANDOM_MAP_HEIGHT)(__builtin_expect(!(y + ty < 32), 0) ? __assert_rtn(__func__ , "src/server/sv_rma.cpp", 936, "y + ty < MAX_RANDOM_MAP_HEIGHT" ) : (void)0); |
937 | assert(x + tx < MAX_RANDOM_MAP_WIDTH)(__builtin_expect(!(x + tx < 32), 0) ? __assert_rtn(__func__ , "src/server/sv_rma.cpp", 937, "x + tx < MAX_RANDOM_MAP_WIDTH" ) : (void)0); |
938 | |
939 | SV_CombineAlternatives(&map->curMap[y + ty][x + tx], tile->spec[ty][tx], &map->curRating[y + ty][x + tx]); |
940 | } |
941 | |
942 | /* add the tile to the array of placed tiles*/ |
943 | if (map->numPlaced >= MAX_MAPTILES64) |
944 | Com_Error(ERR_DROP1, "SV_AddTile: Too many map tiles"); |
945 | |
946 | map->mPlaced[map->numPlaced].tile = tile; |
947 | map->mPlaced[map->numPlaced].x = x; |
948 | map->mPlaced[map->numPlaced].y = y; |
949 | map->mPlaced[map->numPlaced].idx = idx; |
950 | map->mPlaced[map->numPlaced].pos = pos; |
951 | |
952 | map->numPlaced++; |
953 | |
954 | if (idx >= 0) { |
955 | map->mToPlace[idx].cnt++; |
956 | } |
957 | } |
958 | |
959 | /** |
960 | * @brief Rebuilds a assembled map up to the previous tile. |
961 | * @param[in,out] map All we know about the map to assemble |
962 | * @param[out] idx Pointer to the location to store the index field of the removed tile |
963 | * @param[out] pos Pointer to the location to store the position field of the removed tile |
964 | * @sa SV_AssembleMap |
965 | * @sa SV_AddTile |
966 | * @sa SV_FitTile |
967 | */ |
968 | static void SV_RemoveTile (mapInfo_t *map, int* idx, int* pos) |
969 | { |
970 | int tx, ty; |
971 | int i, index; |
972 | |
973 | SV_ClearMap(map); |
974 | |
975 | if (map->numPlaced == 0) |
976 | return; |
977 | |
978 | map->numPlaced--; |
979 | index = map->mPlaced[map->numPlaced].idx; |
980 | |
981 | if (index >= 0) { |
982 | map->mToPlace[index].cnt--; |
983 | } |
984 | |
985 | for (i = map->numPlaced; i--;) { |
986 | const mTile_t *tile = map->mPlaced[i].tile; |
987 | const int x = map->mPlaced[i].x; |
988 | const int y = map->mPlaced[i].y; |
989 | assert(i >= 0)(__builtin_expect(!(i >= 0), 0) ? __assert_rtn(__func__, "src/server/sv_rma.cpp" , 989, "i >= 0") : (void)0); |
990 | assert(tile)(__builtin_expect(!(tile), 0) ? __assert_rtn(__func__, "src/server/sv_rma.cpp" , 990, "tile") : (void)0); |
991 | |
992 | /* add the tile again*/ |
993 | for (ty = 0; ty < tile->h; ty++) { |
994 | for (tx = 0; tx < tile->w; tx++) { |
995 | assert(y + ty < MAX_RANDOM_MAP_HEIGHT)(__builtin_expect(!(y + ty < 32), 0) ? __assert_rtn(__func__ , "src/server/sv_rma.cpp", 995, "y + ty < MAX_RANDOM_MAP_HEIGHT" ) : (void)0); |
996 | assert(x + tx < MAX_RANDOM_MAP_WIDTH)(__builtin_expect(!(x + tx < 32), 0) ? __assert_rtn(__func__ , "src/server/sv_rma.cpp", 996, "x + tx < MAX_RANDOM_MAP_WIDTH" ) : (void)0); |
997 | |
998 | SV_CombineAlternatives(&map->curMap[y + ty][x + tx], tile->spec[ty][tx], &map->curRating[y + ty][x + tx]); |
999 | } |
1000 | } |
1001 | } |
1002 | |
1003 | if (idx) |
1004 | *idx = index; |
1005 | |
1006 | if (pos) |
1007 | *pos = map->mPlaced[map->numPlaced].pos; |
1008 | } |
1009 | |
1010 | /** |
1011 | * @brief Prints the mapstrings as known from the ufoconsole.log |
1012 | * This can also be used to dump the progress of the RMA process. |
1013 | * @param[in,out] map All we know about the map to assemble |
1014 | * @param[out] asmMap The output string of the random map assembly that contains all the |
1015 | * map tiles that should be assembled. The order is the same as in the @c asmPos string. |
1016 | * Each of the map tiles in this string has a corresponding entry in the pos string, too. |
1017 | * @param[out] asmPos The pos string for the assembly. For each tile from the @c asmMap |
1018 | * string this string contains three coordinates for shifting the given tile names. |
1019 | */ |
1020 | static void SV_PrintMapStrings (mapInfo_t *map, char *asmMap, char *asmPos) |
1021 | { |
1022 | int i; |
1023 | mAssembly_t *mAsm; |
1024 | mAsm = &map->mAssembly[map->mAsm]; |
1025 | |
1026 | for (i = 0; i < map->numPlaced; i++) { |
1027 | const mPlaced_t *pl = &map->mPlaced[i]; |
1028 | |
1029 | if (sv_dumpmapassembly->integer) |
1030 | SV_DumpPlaced(map, i); |
1031 | |
1032 | if (asmMap[0]) |
1033 | Q_strcat(asmMap, " ", MAX_TOKEN_CHARS256 * MAX_TILESTRINGS25); |
1034 | if (asmPos[0]) |
1035 | Q_strcat(asmPos, " ", MAX_TOKEN_CHARS256 * MAX_TILESTRINGS25); |
1036 | |
1037 | Q_strcat(asmMap, va("%s", pl->tile->id), MAX_TOKEN_CHARS256 * MAX_TILESTRINGS25); |
1038 | Q_strcat(asmPos, va("%i %i %i", (pl->x - mAsm->width / 2) * 8, (pl->y - mAsm->height / 2) * 8, 0), MAX_TOKEN_CHARS256 * MAX_TILESTRINGS25); |
1039 | } |
1040 | |
1041 | Com_Printf("tiles: %s\n", asmMap); |
1042 | Com_Printf("pos: %s\n", asmPos); |
1043 | Com_Printf("tiles: %i\n", map->numPlaced); |
1044 | } |
1045 | |
1046 | /** |
1047 | * @brief get the specs of a tile at map-x/y if it was placed where tileCode indicates |
1048 | * @param map All we know about the map to assemble |
1049 | * @param tileCode encoded tile and position |
1050 | * @param mapW width of the map. Needed to decode tileCode |
1051 | * @param mapX x of the gap |
1052 | * @param mapY y of the gap |
1053 | * @return the flags |
1054 | */ |
1055 | static unsigned long SV_GapGetFlagsAtAbsPos (mapInfo_t *map, int tileCode, int mapW, int mapX, int mapY) |
1056 | { |
1057 | const int pos = tileCode / TCM50; |
1058 | const int ti = tileCode % TCM50; |
1059 | const int posX = pos % mapW; |
1060 | const int posY = pos / mapW; |
1061 | const mToPlace_t *mToPlace = map->mToPlace; |
1062 | const mTile_t *tile = mToPlace[ti].tile; |
1063 | |
1064 | return tile->spec[mapY - posY][mapX - posX]; |
1065 | } |
1066 | |
1067 | /** |
1068 | * @brief Select the next tile to place and place it (recursively) |
1069 | * @param map All we know about the map to assemble |
1070 | * @param rec The number of the current recursion |
1071 | * @param posListCnt The number of remaining tile position (=options) |
1072 | * @param myPosList The previous list of remaining tile position (=options) |
1073 | * @param prevTile The tile placed by the previous recursion |
1074 | * @param prevX x where it was placed |
1075 | * @param prevY well, y |
1076 | * @return @c false if the tiles do not fit, @c true if the map could be filled. |
1077 | */ |
1078 | static int availableTiles[MAX_TILETYPES64][2]; /* the 2nd dimension is index and count */ |
1079 | |
1080 | static bool SV_AddMissingTiles_r (mapInfo_t *map, int rec, int posListCnt, short myPosList[], const mTile_t *prevTile, int prevX, int prevY) |
1081 | { |
1082 | static int callCnt = 0; |
1083 | const mAssembly_t *mAsm = &map->mAssembly[map->mAsm]; |
1084 | const int mapW = mAsm->width; |
1085 | const mToPlace_t *mToPlace = map->mToPlace; |
1086 | int i, j = 0; |
1087 | int solids = 0; /* the # of places that the remaining tiles can theoretically cover */ |
1088 | int availableTilesCnt = 0; /* the # of different tiles remaining in posTileList */ |
1089 | |
1090 | assert(rec < RMA2_MAX_REC)(__builtin_expect(!(rec < 64), 0) ? __assert_rtn(__func__, "src/server/sv_rma.cpp", 1090, "rec < RMA2_MAX_REC") : (void )0); |
1091 | callCnt++; |
1092 | |
1093 | /** calculate the area of the tile placed by the previous recursion */ |
1094 | int prevMaxX = 0, prevMaxY = 0; |
1095 | if (rec > 0) { |
1096 | prevMaxX = prevX + prevTile->w - 1; |
1097 | prevMaxY = prevY + prevTile->h - 1; |
1098 | } |
1099 | |
1100 | /** circle through the old list of available tile positions and store the remaining ones in the static array */ |
1101 | for (i = 0; i < posListCnt; i++) { |
1102 | const int pos = myPosList[i] / TCM50; |
1103 | const int ti = myPosList[i] % TCM50; |
1104 | const int x = pos % mapW; |
1105 | const int y = pos / mapW; |
1106 | |
1107 | if (mToPlace[ti].cnt >= mToPlace[ti].max) |
1108 | continue; |
1109 | |
1110 | const mTile_t *cTile = mToPlace[ti].tile; |
1111 | bool ok = false; |
1112 | /** try to reduce the # of calls to SV_FitTile by checking only those gaps affected by the placement of the previous tile */ |
1113 | if (rec > 0) { /* the first recursion doesn't have a previous tile */ |
1114 | if (x > prevMaxX || y > prevMaxY || prevX > x + cTile->w - 1 || prevY > y + cTile->h - 1) |
1115 | ok = true; /* tiles do not overlap, so tile will still fit */ |
1116 | } |
1117 | |
1118 | if (!ok) { |
1119 | ok = SV_FitTile(map, mToPlace[ti].tile, x, y); |
1120 | } |
1121 | if (ok) { |
1122 | /* store the posTile in our new list */ |
1123 | assert(j < RMA2_MAX_TILEPOS)(__builtin_expect(!(j < 1700), 0) ? __assert_rtn(__func__, "src/server/sv_rma.cpp", 1123, "j < RMA2_MAX_TILEPOS") : ( void)0); |
1124 | posTileList[rec][j] = myPosList[i]; |
1125 | j++; |
1126 | /* store the tile index in the list of remaining tile types */ |
1127 | int k; |
1128 | for (k = 0; k < availableTilesCnt; k++) { |
1129 | if (availableTiles[k][0] == ti) { |
1130 | availableTiles[k][1]++; /* inc count */ |
1131 | break; |
1132 | } |
1133 | } |
1134 | if (k >= availableTilesCnt) { /* didn't find it in the list */ |
1135 | availableTiles[availableTilesCnt][0] = ti; /* store the tile index */ |
1136 | availableTiles[availableTilesCnt][1] = 1; /* init counter of places */ |
1137 | availableTilesCnt++; |
1138 | } |
1139 | } |
1140 | } |
1141 | |
1142 | /** initialize the list of gaps */ |
1143 | int x, y; |
1144 | int gapCount = 0; |
1145 | for (y = 1; y < mAsm->height + 1; y++) { |
1146 | for (x = 1; x < mAsm->width + 1; x++) |
1147 | if (IS_SOLID(map->curMap[y][x])((map->curMap[y][x])&1UL)) |
1148 | gapList[x][y][0] = -1; |
1149 | else { |
1150 | gapCount++; |
1151 | gapList[x][y][0] = 0; |
1152 | } |
1153 | } |
1154 | |
1155 | /** if the remaining tiles are simply not enough to cover the gaps, bail */ |
1156 | for (i = 0; i < availableTilesCnt; i++) { |
1157 | const int ti = availableTiles[i][0]; |
1158 | const int allowed = mToPlace[ti].max - mToPlace[ti].cnt; |
1159 | const int possible = availableTiles[i][1]; |
1160 | const int remaining = std::min(allowed, possible); |
1161 | solids += remaining * mToPlace[ti].tile->area; |
1162 | } |
1163 | if (solids < gapCount) { |
1164 | if (sv_rmadisplaythemap->integer) { |
1165 | SV_RmaPrintMap(map); |
1166 | Com_Printf("out of solids\n"); |
1167 | } |
1168 | return false; |
1169 | } |
1170 | |
1171 | /** check how well the remaining tiles can cover the gaps */ |
1172 | for (i = 0; i < j; i++) { |
1173 | const int pos = posTileList[rec][i] / TCM50; |
1174 | const int ti = posTileList[rec][i] % TCM50; |
1175 | const int x = pos % mapW; |
1176 | const int y = pos / mapW; |
1177 | const mTile_t *tile = mToPlace[ti].tile; |
1178 | int tx, ty; |
1179 | for (ty = 0; ty < tile->h; ty++) { |
1180 | for (tx = 0; tx < tile->w; tx++) { |
1181 | if (IS_SOLID(tile->spec[ty][tx])((tile->spec[ty][tx])&1UL)) { |
1182 | gapList[x + tx][y + ty][0] += 1; |
1183 | int cnt = gapList[x + tx][y + ty][0]; /* get the counter */ |
1184 | if (cnt < GAPS25 + 1) |
1185 | gapList[x + tx][y + ty][cnt] = posTileList[rec][i]; /* remember the tilecode */ |
1186 | } |
1187 | } |
1188 | } |
1189 | } |
1190 | |
1191 | /** if we find a gap that NO tile can cover, bail */ |
1192 | for (y = 1; y < mAsm->height + 1; y++) { |
1193 | for (x = 1; x < mAsm->width + 1; x++) { |
1194 | if (gapList[x][y][0] == 0) { |
1195 | if (sv_rmadisplaythemap->integer) { |
1196 | SV_RmaPrintMap(map); |
1197 | Com_Printf("uncovered gap: %i/%i\n", x, y); |
1198 | } |
1199 | return false; |
1200 | } |
1201 | } |
1202 | } |
1203 | |
1204 | #if 0 |
1205 | /** print the gaplist */ |
1206 | for (y = 1; y < mAsm->height + 1; y++) { |
1207 | for (x = 1; x < mAsm->width + 1; x++) { |
1208 | Com_Printf("%2.i ", gapList[x][y][0]); |
1209 | } |
1210 | Com_Printf("\n"); |
1211 | } |
1212 | Com_Printf("\n"); |
1213 | #endif |
1214 | |
1215 | /** if there is a gap that only ONE tile can cover, try that. If it doesn't work out, we're done. */ |
1216 | /** if there is a gap that only TWO tiles can cover, try those two. If it doesn't work out, we're done. Then try with THREE and so on. */ |
1217 | int g, h, line = 0; |
1218 | unsigned lineFlags = map->lineFlags; /* lineforming tiles, eg. water tiles in forest_large */ |
1219 | unsigned nonLineFlags = (~lineFlags) ^ 1L; |
1220 | if (lineFlags) |
1221 | line = 1; |
1222 | for (; line >= 0; line--) { /* if there are lineforming tiles, process them first */ |
1223 | for (g = 1; g <= GAPS25; g++) { /* process the gaps with the least alternatives first */ |
1224 | for (y = 1; y < mAsm->height + 1; y++) { |
1225 | for (x = 1; x < mAsm->width + 1; x++) { |
1226 | if (gapList[x][y][0] == g) { /* if this gap has the right amount of covering tiles */ |
1227 | /* if we are looking for lines but the gap doesn't require a line-tile, skip */ |
1228 | if (line && (map->curMap[y][x] & nonLineFlags)) |
1229 | continue; |
1230 | for (h = 1; h <= g; h++) { /* circle through the alternatives stored for this gap */ |
1231 | const int tc = gapList[x][y][h]; |
1232 | const int pos = tc / TCM50; |
1233 | const int ti = tc % TCM50; |
1234 | const int px = pos % mapW; |
1235 | const int py = pos / mapW; |
1236 | |
1237 | SV_AddTile(map, mToPlace[ti].tile, px, py, ti, pos); |
1238 | #if PRINT_RMA_PROGRESS0 |
1239 | if (rec < 10) |
1240 | Com_Printf("GAPS: %i rec: %i chances: %i calls: %i\n", GAPS25, rec, j, callCnt); |
1241 | #endif |
1242 | if (SV_TestFilled(map)) |
1243 | return true; /* this was the last tile we needed */ |
1244 | if (SV_AddMissingTiles_r(map, rec + 1, j, posTileList[rec], mToPlace[ti].tile, px, py)) |
1245 | return true; /* recursive placement succeeded */ |
1246 | |
1247 | /* tile was a dead end, remove it */ |
1248 | SV_RemoveTile(map, NULL__null, NULL__null); |
1249 | |
1250 | if (h >= g) { |
1251 | #if 0 |
1252 | if (sv_rmadisplaythemap->integer) { |
1253 | SV_RmaPrintMap(map); |
1254 | Com_Printf("no tile works for gap\n"); |
1255 | } |
1256 | #endif |
1257 | return false; |
1258 | } |
1259 | } |
1260 | } |
1261 | } |
1262 | } |
1263 | } |
1264 | } |
1265 | |
1266 | /** now try each of the remaining positions, that is, those that have more than GAPS alternatives. Rarely happens. */ |
1267 | for (i = 0; i < j; i++) { |
1268 | const int pos = posTileList[rec][i] / TCM50; |
1269 | const int ti = posTileList[rec][i] % TCM50; |
1270 | const int x = pos % mapW; |
1271 | const int y = pos / mapW; |
1272 | |
1273 | SV_AddTile(map, mToPlace[ti].tile, x, y, ti, pos); |
1274 | if (SV_TestFilled(map)) |
1275 | return true; |
1276 | if (SV_AddMissingTiles_r(map, rec + 1, j, posTileList[rec], mToPlace[ti].tile, x, y)) |
1277 | return true; |
1278 | else |
1279 | SV_RemoveTile(map, NULL__null, NULL__null); |
1280 | } |
1281 | return false; |
1282 | } |
1283 | |
1284 | /** |
1285 | * @brief Builds a list of map positions (gaps) and the tiles that can cover them. |
1286 | * @note actually it's not a list but a 3D-array |
1287 | * @param map All we know about the map to assemble |
1288 | * @param tilePosListCnt The number of remaining possible tile positions |
1289 | * @return false if we detect a gap that NO tile can cover |
1290 | */ |
1291 | static bool SV_GapListBuild (mapInfo_t *map, int tilePosListCnt) |
1292 | { |
1293 | const mAssembly_t *mAsm = &map->mAssembly[map->mAsm]; |
1294 | const int mapW = mAsm->width; |
1295 | const mToPlace_t *mToPlace = map->mToPlace; |
1296 | |
1297 | /** initialize the list of gaps */ |
1298 | int x, y; |
1299 | for (y = 1; y < mAsm->height + 1; y++) { |
1300 | for (x = 1; x < mAsm->width + 1; x++) |
1301 | if (IS_SOLID(map->curMap[y][x])((map->curMap[y][x])&1UL)) |
1302 | gapList[x][y][0] = -1; /* the gap is solid already, so we don't need a counter. But we might need the info. */ |
1303 | else |
1304 | gapList[x][y][0] = 0; /* the counter for this pos */ |
1305 | } |
1306 | |
1307 | /* check how well the tiles can cover the gaps */ |
1308 | int i; |
1309 | for (i = 0; i < tilePosListCnt; i++) { |
1310 | const int pos = posTileList[0][i] / TCM50; |
1311 | const int ti = posTileList[0][i] % TCM50; |
1312 | x = pos % mapW; |
1313 | y = pos / mapW; |
1314 | mTile_t *tile = mToPlace[ti].tile; |
1315 | int tx, ty; |
1316 | ty = 0; /* for a breakpoint */ |
Value stored to 'ty' is never read | |
1317 | for (ty = 0; ty < tile->h; ty++) { |
1318 | for (tx = 0; tx < tile->w; tx++) { |
1319 | if (IS_SOLID(tile->spec[ty][tx])((tile->spec[ty][tx])&1UL)) { |
1320 | gapList[x + tx][y + ty][0] += 1; |
1321 | const int cnt = gapList[x + tx][y + ty][0]; /* get the counter */ |
1322 | if (cnt < GAPS25 + 1) |
1323 | gapList[x + tx][y + ty][cnt] = posTileList[0][i]; /* remember the tilecode */ |
1324 | } |
1325 | } |
1326 | } |
1327 | } |
1328 | |
1329 | /** if we find a gap that NO tile can cover, bail */ |
1330 | for (y = 1; y < mAsm->height + 1; y++) { |
1331 | for (x = 1; x < mAsm->width + 1; x++) { |
1332 | if (gapList[x][y][0] == 0) |
1333 | return false; |
1334 | } |
1335 | } |
1336 | return true; |
1337 | } |
1338 | |
1339 | /** |
1340 | * @brief Find a tile that meets the requirements of tc1 at a given pos |
1341 | * @param map All we know about the map to assemble |
1342 | * @param tc1 encoded tile and position |
1343 | * @param mapW width of the map. Needed to decode tc1 |
1344 | * @param nx x of the absolute map position to investigate |
1345 | * @param nx y of the absolute map position to investigate |
1346 | * @return @c true if no matching tile was found |
1347 | */ |
1348 | static bool SV_GapCheckNeighbour (mapInfo_t *map, int tc1, int mapW, int nx, int ny) |
1349 | { |
1350 | if (nx < 1) |
1351 | /* map border */ |
1352 | return false; |
1353 | if (ny < 1) |
1354 | return false; |
1355 | if (nx > mapW) |
1356 | return false; |
1357 | if (ny > map->mAssembly[map->mAsm].height) |
1358 | return false; |
1359 | |
1360 | if (gapList[nx][ny][0] < 1) |
1361 | /* no tiles cover this gap, probably map border */ |
1362 | return false; |
1363 | if (gapList[nx][ny][0] >= GAPS25) |
1364 | /* if there are more tiles than we stored the tc's of, |
1365 | * we can not evaluate this neighbour. */ |
1366 | return false; |
1367 | |
1368 | bool flags1 = SV_GapGetFlagsAtAbsPos(map, tc1, mapW, nx, ny); |
1369 | if (IS_SOLID(flags1)((flags1)&1UL)) |
1370 | /* nx/ny is part of tc1 itself */ |
1371 | return false; |
1372 | |
1373 | /** circle through the tiles that cover this gap */ |
1374 | int h; |
1375 | for (h = 1; h <= gapList[nx][ny][0]; h++) { |
1376 | const int tc2 = gapList[nx][ny][h]; |
1377 | const unsigned long flags2 = SV_GapGetFlagsAtAbsPos(map, tc2, mapW, nx, ny); |
1378 | |
1379 | if (flags1 & flags2) { |
1380 | /* found at least one tile that would work */ |
1381 | return false; |
1382 | } |
1383 | } |
1384 | return true; |
1385 | } |
1386 | |
1387 | /** |
1388 | * @brief Tries to find tiles that exclude all of their neighbours |
1389 | * This is called only once, before recursion starts. So we can safely (ab)use the posTileList space for recursion 1 |
1390 | * @param map All we know about the map to assemble |
1391 | * @return the number of tiles that could be eliminated |
1392 | */ |
1393 | static int SV_GapListReduce (mapInfo_t *map) |
1394 | { |
1395 | const mAssembly_t *mAsm = &map->mAssembly[map->mAsm]; |
1396 | const int mapW = mAsm->width; |
1397 | int x, y; |
1398 | int n = 0; /** number of tiles marked for elinimation */ |
1399 | |
1400 | /** if there is a tile that doesn't match ANY of the tiles available for the adjacent gap we can eliminate it. */ |
1401 | for (y = 1; y < mAsm->height + 1; y++) { |
1402 | for (x = 1; x < mAsm->width + 1; x++) { |
1403 | if (gapList[x][y][0] < 1) /* solid ? */ |
1404 | continue; |
1405 | |
1406 | int g; |
1407 | for (g = 1; g <= gapList[x][y][0]; g++) { |
1408 | const int tc1 = gapList[x][y][g]; |
1409 | if (g >= GAPS25) |
1410 | break; /* there are more tiles than we stored the tc's of. */ |
1411 | |
1412 | /* check the neighbour to the right */ |
1413 | if (SV_GapCheckNeighbour(map, tc1, mapW, x+1, y)) { |
1414 | posTileList[1][n] = tc1; |
1415 | n++; |
1416 | continue; |
1417 | } |
1418 | /* check the neighbour to the left */ |
1419 | if (SV_GapCheckNeighbour(map, tc1, mapW, x-1, y)) { |
1420 | posTileList[1][n] = tc1; |
1421 | n++; |
1422 | continue; |
1423 | } |
1424 | /* check the upper neighbour */ |
1425 | if (SV_GapCheckNeighbour(map, tc1, mapW, x, y+1)) { |
1426 | posTileList[1][n] = tc1; |
1427 | n++; |
1428 | continue; |
1429 | } |
1430 | /* check the neighbour below */ |
1431 | if (SV_GapCheckNeighbour(map, tc1, mapW, x, y-1)) { |
1432 | posTileList[1][n] = tc1; |
1433 | n++; |
1434 | continue; |
1435 | } |
1436 | } |
1437 | } |
1438 | } |
1439 | |
1440 | return n; |
1441 | } |
1442 | |
1443 | #if PRINT_RMA_PROGRESS0 |
1444 | char mapStr[10000] = {0}; |
1445 | char posStr[10000] = {0}; |
1446 | #endif |
1447 | /** |
1448 | * @brief Tries to fill the missing tiles of the current map. |
1449 | * While the 2010 algo used a 'by chance'-algo, this algo does a full tree search. |
1450 | * Example: After placing the fixed and required tiles on a 8x8 map, we have say 32 places not yet covered by tiles. |
1451 | * If there are 10 different tiles for each gap, we can have up to have 10^32 constellations to try. |
1452 | * That's about one fantastillion. Impossible. |
1453 | * Fortunately, there are usually many solutions to this puzzle. And we only need to find one working solution. |
1454 | * But on some maps eg. 'forest large' with it's little brook, there are fewer solutions, so the search can take longer. |
1455 | * In order to complete the search in a reasonable time, this algo uses several strategies: |
1456 | * - reduce the number of available options to narrow the tree |
1457 | * - direct the search towards those options that are more likely to fail. This can cut off a whole branch of the tree. |
1458 | * Details will be explained along the call-tree |
1459 | * @param map All we know about the map to assemble |
1460 | * @return @c false if the tiles does not fit, @c true if the map could be filled. |
1461 | * @sa SV_FitTile |
1462 | * @sa SV_AddTile |
1463 | */ |
1464 | static bool SV_AddMissingTiles (mapInfo_t *map) |
1465 | { |
1466 | static int attempts = 0; /* how often this function is called in the RMA process */ |
1467 | const mAssembly_t *mAsm = &map->mAssembly[map->mAsm]; |
1468 | const int mapSize = mAsm->size; /* the # of grid squares in the assembly. A grid suare is usually 8x8 cells. */ |
1469 | const int mapW = mAsm->width; |
1470 | const mToPlace_t *mToPlace = map->mToPlace; |
1471 | short posList[MAX_RANDOM_MAP_HEIGHT32 * MAX_RANDOM_MAP_WIDTH32]; /* array of random positions */ |
1472 | short tilenumList[MAX_TILETYPES64]; /* array of tiles */ |
1473 | |
1474 | /* shuffle only once, the map will be build with that seed */ |
1475 | RandomList(mapSize, posList); |
1476 | RandomList(map->numToPlace, tilenumList); |
1477 | attempts++; |
1478 | |
1479 | /* check if the map is already filled */ |
1480 | if (SV_TestFilled(map)) |
1481 | return true; |
1482 | |
1483 | /** build a list of all positions of the map and all the tiles that fit there */ |
1484 | int i, j, k, offs, num, n = 0; |
1485 | for (i = 0; i < mapSize; i++) { |
1486 | const int x = posList[i] % mapW; |
1487 | const int y = posList[i] / mapW; |
1488 | |
1489 | /* only use positions that are on the grid */ |
1490 | if (x % mAsm->dx != 0 || y % mAsm->dy != 0) { |
1491 | continue; |
1492 | } |
1493 | /* if we simply test the tiles in the same sequence for each pos, we get the 'boring maps' problem */ |
1494 | /* So let's check them from a different starting point in the list each time */ |
1495 | /* Example: if we have say 20 tiles, test eg. 13-20 first, then 1-12 */ |
1496 | num = map->numToPlace; |
1497 | offs = rand() % num; |
1498 | for (k = offs; k < num + offs; k++) { |
1499 | const int ti = tilenumList[k % num]; |
1500 | |
1501 | if (mToPlace[ti].cnt >= mToPlace[ti].max) |
1502 | continue; |
1503 | if (SV_FitTile(map, mToPlace[ti].tile, x, y)) { |
1504 | posTileList[0][n] = posList[i] * TCM50 + ti; |
1505 | assert(n < RMA2_MAX_TILEPOS)(__builtin_expect(!(n < 1700), 0) ? __assert_rtn(__func__, "src/server/sv_rma.cpp", 1505, "n < RMA2_MAX_TILEPOS") : ( void)0); |
1506 | n++; |
1507 | } |
1508 | } |
1509 | } |
1510 | #if PRINT_RMA_PROGRESS0 |
1511 | Com_Printf("\nMapsize: %i tiles: %i chances: %i\n", mapSize, map->numToPlace, n); |
1512 | mapStr[0] = 0; |
1513 | posStr[0] = 0; |
1514 | if (map->numPlaced < 8) |
1515 | SV_PrintMapStrings(map, mapStr, posStr); |
1516 | #endif |
1517 | /** try to reduce the number of available options */ |
1518 | bool eliminated = true; |
1519 | while (eliminated) { /* if we could eliminate one or more tiles, try again */ |
1520 | eliminated = false; |
1521 | #if 0 |
1522 | /* print the posTileList */ |
1523 | for (i = 0; i < n; i++) { |
1524 | Com_Printf("%2.i/%2.i ", posTileList[0][i] / TCM50, posTileList[0][i] % TCM50); |
1525 | if (!(i % 10)) |
1526 | Com_Printf("\n"); |
1527 | } |
1528 | Com_Printf("\n"); |
1529 | #endif |
1530 | bool covered = SV_GapListBuild(map, n); |
1531 | |
1532 | #if 0 |
1533 | /* print the gapList */ |
1534 | int x, y; |
1535 | Com_Printf("\n"); |
1536 | for (x = 0; x < mAsm->width + 1; x++){ |
1537 | for (y = 0; y < mAsm->height + 1; y++){ |
1538 | int cnt = gapList[x][y][0]; |
1539 | Com_Printf("x:%i y:%i cnt:%i ",x,y,cnt); |
1540 | for (j = 0; j <= cnt + 3; j++) { |
1541 | Com_Printf("%i ", gapList[x][y][j]); |
1542 | } |
1543 | Com_Printf("\n"); |
1544 | } |
1545 | } |
1546 | #endif |
1547 | |
1548 | if (!covered) |
1549 | return false; /* creating the gapList left one gap uncovered */ |
1550 | |
1551 | int m = SV_GapListReduce(map); |
1552 | if (m) { /* the number of tilepositions to discard */ |
1553 | eliminated = true; |
1554 | for (j = 0; j < m; j++) { |
1555 | const int tc = posTileList[1][j]; /* SV_GapListReduce abuses the space for rec=1 to return it's result */ |
1556 | int offset = 0; |
1557 | for (i = 0; i < n; i++) { |
1558 | if (posTileList[0][i] == tc) { |
1559 | offset = 1; |
1560 | continue; |
1561 | } |
1562 | posTileList[0][i - offset] = posTileList[0][i]; |
1563 | } |
1564 | if (offset) /* only if we actually removed the tile */ |
1565 | n--; /* reduce the counter of posTileList */ |
1566 | } |
1567 | } |
1568 | } |
1569 | |
1570 | return SV_AddMissingTiles_r(map, 0, n, posTileList[0], NULL__null, 0, 0); |
1571 | } |
1572 | |
1573 | /** |
1574 | * @brief Tries to build the map |
1575 | * There are 3 categories of tiles: |
1576 | * - fixed: the position of the tile is already given in the assembly definition |
1577 | * - required: a given number of such a tile must be placed somewhere on the map |
1578 | * - optional: up to a given number of these tiles may be used in the map |
1579 | * The algorithm works as follows: |
1580 | * The fixed tiles have already been placed in the calling function. |
1581 | * This function here now places the required tiles at random positions. |
1582 | * Then the remaining gaps are filled with the optional tiles. |
1583 | * If that fails, the last required tile is moved to a different place and the filling is tried again. |
1584 | * If no more places are left for the required tile, the previous required tile is relocated and so on. |
1585 | * That is, for the required tiles every possible combination is tried before we give up. |
1586 | * @param map All we know about the map to assemble |
1587 | * @sa SV_FitTile |
1588 | * @sa SV_AddTile |
1589 | */ |
1590 | static bool SV_AddMapTiles (mapInfo_t *map) |
1591 | { |
1592 | int idx; /* index in the array of available tiles */ |
1593 | int pos; /* index in the array of random positions */ |
1594 | const mAssembly_t *mAsm = &map->mAssembly[map->mAsm]; |
1595 | const int mapW = mAsm->width; /* width in x-direction */ |
1596 | const int mapSize = mAsm->size; /* the # of grid squares in the assembly. A grid suare is usually 8x8 cells. */ |
1597 | const int numToPlace = map->numToPlace; |
1598 | const mToPlace_t *mToPlace = map->mToPlace; /* pointer to a tile descriptor */ |
1599 | short prList[MAX_RANDOM_MAP_HEIGHT32 * MAX_RANDOM_MAP_WIDTH32]; /* array of random positions */ |
1600 | const int start = map->numPlaced; |
1601 | #ifdef DEBUG1 |
1602 | const mPlaced_t *mPlaced = map->mPlaced; |
1603 | #endif |
1604 | |
1605 | #if PRINT_RMA_PROGRESS0 |
1606 | char mapStr[10000] = {0}; |
1607 | char posStr[10000] = {0}; |
1608 | #endif |
1609 | |
1610 | /* shuffle only once, the map will be build with that seed */ |
1611 | RandomList(mapSize, prList); |
1612 | |
1613 | pos = 0; |
1614 | idx = 0; |
1615 | while (idx < numToPlace) { /* for all tile-descriptors */ |
1616 | while (mToPlace[idx].cnt < mToPlace[idx].min) { |
1617 | for (; pos < mapSize; pos++) { |
1618 | const int x = prList[pos] % mapW; |
1619 | const int y = prList[pos] / mapW; |
1620 | if (sv_threads->integer && sv_rma->integer == 1) { |
1621 | if (SDL_SemValue(mapSem) != 1) { |
1622 | /* someone else beat me to it */ |
1623 | return true; |
1624 | } |
1625 | } |
1626 | |
1627 | if ((x % mAsm->dx != 0) || (y % mAsm->dy != 0)) |
1628 | continue; |
1629 | |
1630 | if (SV_FitTile(map, mToPlace[idx].tile, x, y)) { |
1631 | /* add tile */ |
1632 | SV_AddTile(map, mToPlace[idx].tile, x, y, idx, pos); |
1633 | #if PRINT_RMA_PROGRESS0 |
1634 | mapStr[0] = 0; |
1635 | posStr[0] = 0; |
1636 | if (map->numPlaced < 6) |
1637 | SV_PrintMapStrings(map, mapStr, posStr); |
1638 | #endif |
1639 | break; |
1640 | } |
1641 | } |
1642 | /* tile fits, try another tile of the same type */ |
1643 | if (pos < mapSize) |
1644 | continue; |
1645 | |
1646 | /* tile doesn't fit and no try left with this tile */ |
1647 | if (!mToPlace[idx].cnt) |
1648 | break; |
1649 | |
1650 | /* tile does not fit, restore last status - replace the last tile */ |
1651 | assert(map->numPlaced > 0)(__builtin_expect(!(map->numPlaced > 0), 0) ? __assert_rtn (__func__, "src/server/sv_rma.cpp", 1651, "map->numPlaced > 0" ) : (void)0); |
1652 | #ifdef DEBUG1 |
1653 | assert(idx == mPlaced[map->numPlaced - 1].idx)(__builtin_expect(!(idx == mPlaced[map->numPlaced - 1].idx ), 0) ? __assert_rtn(__func__, "src/server/sv_rma.cpp", 1653, "idx == mPlaced[map->numPlaced - 1].idx") : (void)0); |
1654 | #endif |
1655 | if (sv_rmadisplaythemap->integer) { |
1656 | SV_RmaPrintMap(map); |
1657 | Com_Printf("required tile doesn't fit\n"); |
1658 | } |
1659 | SV_RemoveTile(map, &idx, &pos); |
1660 | pos++; |
1661 | } |
1662 | |
1663 | /* tile fits, try next tile */ |
1664 | if (pos < mapSize) { |
1665 | pos = 0; /* start at the beginning of the random positions array */ |
1666 | idx++; |
1667 | } else { |
1668 | /* no more retries */ |
1669 | if (start == map->numPlaced) { |
1670 | if (mAsm->numSeeds == 0 || map->retryCnt > 2) { |
1671 | Com_Error(ERR_DROP1, "SV_AddMapTiles: Impossible to assemble map '%s' with assembly '%s'\n", |
1672 | map->name, mAsm->id ? mAsm->id : ""); |
1673 | } else { |
1674 | Com_Printf("SV_AddMapTiles: Impossible to assemble map '%s' with assembly '%s' - retry with another seed\n", |
1675 | map->name, mAsm->id ? mAsm->id : ""); |
1676 | return false; |
1677 | } |
1678 | } |
1679 | SV_RemoveTile(map, &idx, &pos); |
1680 | pos++; |
1681 | } |
1682 | |
1683 | if (idx == numToPlace && !SV_AddMissingTiles(map)) { |
1684 | if (sv_rmadisplaythemap->integer) { |
1685 | SV_RmaPrintMap(map); |
1686 | Com_Printf("couldn't pad\n"); |
1687 | } |
1688 | SV_RemoveTile(map, &idx, &pos); |
1689 | pos++; |
1690 | } |
1691 | } |
1692 | |
1693 | return true; |
1694 | } |
1695 | |
1696 | /** |
1697 | * @brief Prepare the list of tiles to place |
1698 | * @sa SV_AssembleMap |
1699 | * @sa SV_AddTile |
1700 | */ |
1701 | void SV_PrepareTilesToPlace (mapInfo_t *map) |
1702 | { |
1703 | int i; |
1704 | const mAssembly_t *mAsm = &map->mAssembly[map->mAsm]; |
1705 | |
1706 | map->numToPlace = 0; |
1707 | OBJZERO(map->mToPlace)(memset(&((map->mToPlace)), (0), sizeof((map->mToPlace )))); |
1708 | |
1709 | for (i = 0; i < map->numTiles; i++) { |
1710 | if (mAsm->max[i]) { |
1711 | map->mToPlace[map->numToPlace].tile = &map->mTile[i]; |
1712 | map->mToPlace[map->numToPlace].min = mAsm->min[i]; |
1713 | map->mToPlace[map->numToPlace].max = mAsm->max[i]; |
1714 | map->numToPlace++; |
1715 | } |
1716 | } |
1717 | } |
1718 | |
1719 | /** |
1720 | * @brief The main function for the threads that try to create random map assemblies in parallel. |
1721 | * @param data The @c mapInfo_t structure local to this thread. Should be initialized |
1722 | * by memcpy-ing the actual map into new memory. Not thread-safe to read or write, this thread |
1723 | * assumes that nobody else will access the given copy of the map before the thread ends. |
1724 | * It is the responsibility of the caller to free the map, if needed, after the thread has died |
1725 | * and been collected. |
1726 | * @return 0 on success, -1 if it was interrupted via the @c mapSem semaphore, signaling that |
1727 | * someone else has finished first, or timeout occurred. |
1728 | */ |
1729 | static int SV_AssemblyThread (void* data) |
1730 | { |
1731 | mapInfo_t *map = (mapInfo_t*) data; |
1732 | |
1733 | Com_SetRandomSeed(time(NULL__null)); |
1734 | |
1735 | if (!SV_AddMapTiles(map)) { |
1736 | map->retryCnt++; |
1737 | } |
1738 | |
1739 | /* the first thread to reach this point, gets the semaphore */ |
1740 | if (SDL_SemTryWait(mapSem) != 0) |
1741 | return -1; |
1742 | TH_MutexLock(mapLock)_TH_MutexLock((mapLock), "src/server/sv_rma.cpp", 1742); |
1743 | |
1744 | assert(threadID == 0)(__builtin_expect(!(threadID == 0), 0) ? __assert_rtn(__func__ , "src/server/sv_rma.cpp", 1744, "threadID == 0") : (void)0); |
1745 | threadID = SDL_ThreadID(); |
1746 | |
1747 | /* tell main we're done */ |
1748 | SDL_CondSignal(mapCond); |
1749 | TH_MutexUnlock(mapLock)_TH_MutexUnlock((mapLock), "src/server/sv_rma.cpp", 1749); |
1750 | |
1751 | return 0; |
1752 | } |
1753 | |
1754 | /** |
1755 | * @brief Spawn ASSEMBLE_THREADS threads to try and assemble a map. The first map complete gets returned. |
1756 | * Allocates a new copy of the map for each thread, and frees it at the end. |
1757 | * Uses a timeout (initially 5 seconds). If the spawned threads have not completed by the timeout, they |
1758 | * are restarted, with double the timeout. |
1759 | * @note The algorithm main points: |
1760 | * The synchronization of threads happens using a semaphore @c mapSem, a lock @c mapLock, and a condition @c mapCond. |
1761 | * The semaphore is initially 1 (and reset to 1 every time there is a restart). |
1762 | * The first thread that finishes, grabs the semaphore, to tell all other threads to abort. |
1763 | * All threads test the semaphore, if it is 0, they abort. |
1764 | * After the timeout, the main thread grabs the semaphore, to make everybody conclude, and then restarts them. |
1765 | * The lock is used to protect writes to the threadID global variable, that holds the ID of the thread which finished, |
1766 | * if any. It is also used to protect the conditional @c mapCond, used by the finished thread to notify the main() |
1767 | * thread, so it can collect all threads and copy the final map back to the caller. |
1768 | * The lock is locked by main() at all times, unless it is waiting on the conditional (with timeout). |
1769 | * When an assembler thread finishes, it grabs the lock (which means main() is still waiting), writes its ID to |
1770 | * threadID, signals main() and releases the lock. main() gets the signal after the lock is released, since the signal |
1771 | * is protected by the lock, so there can be no race between finishing assembly and signaling main() for the |
1772 | * assembler threads. |
1773 | * When a timeout occurs, main() exits the conditional by grabbing the lock again. This will prevent any thread |
1774 | * from exiting, even if it finishes between the time that main() timed out and the time it tries to get the semaphore. |
1775 | * So, main() checks the semaphore to see if it is taken, and if so doesn't restart, despite the timeout. |
1776 | * @todo Maybe we also need to reduce the timeout value a bit every time it succeeds? |
1777 | */ |
1778 | static int SV_ParallelSearch (mapInfo_t *map) |
1779 | { |
1780 | SDL_Thread *threads[ASSEMBLE_THREADS2]; |
1781 | mapInfo_t *maps[ASSEMBLE_THREADS2]; |
1782 | int i; |
1783 | static int timeout = 5000; /* wait for 5 sec initially, double it every time it times out */ |
1784 | const int threadno = std::min(sv_threads->integer, ASSEMBLE_THREADS2); |
1785 | |
1786 | assert(mapLock == NULL)(__builtin_expect(!(mapLock == __null), 0) ? __assert_rtn(__func__ , "src/server/sv_rma.cpp", 1786, "mapLock == NULL") : (void)0 ); |
1787 | mapLock = TH_MutexCreate("rma"); |
1788 | |
1789 | assert(mapCond == NULL)(__builtin_expect(!(mapCond == __null), 0) ? __assert_rtn(__func__ , "src/server/sv_rma.cpp", 1789, "mapCond == NULL") : (void)0 ); |
1790 | mapCond = SDL_CreateCond(); |
1791 | |
1792 | threadID = 0; |
1793 | assert(mapSem == NULL)(__builtin_expect(!(mapSem == __null), 0) ? __assert_rtn(__func__ , "src/server/sv_rma.cpp", 1793, "mapSem == NULL") : (void)0); |
1794 | mapSem = SDL_CreateSemaphore(1); |
1795 | |
1796 | TH_MutexLock(mapLock)_TH_MutexLock((mapLock), "src/server/sv_rma.cpp", 1796); |
1797 | for (i = 0; i < threadno; i++) { |
1798 | maps[i] = Mem_AllocType(mapInfo_t)((mapInfo_t*)_Mem_Alloc(((sizeof(mapInfo_t))),true,(com_genericPool ),(0),"src/server/sv_rma.cpp",1798)); |
1799 | memcpy(maps[i], map, sizeof(*map)); |
1800 | threads[i] = SDL_CreateThread(SV_AssemblyThread, (void*) maps[i]); |
1801 | } |
1802 | while (threadID == 0) { |
1803 | /* if nobody is done after 5 sec, restart, double the timeout. */ |
1804 | if (TH_MutexCondWaitTimeout(mapLock, mapCond, timeout) != 0) { |
1805 | Com_Printf("SV_ParallelSearch: timeout at %i ms, restarting\n", timeout); |
1806 | timeout += timeout; |
1807 | /* tell them all to die */ |
1808 | if (SDL_SemTryWait(mapSem) != 0) { |
1809 | /* couldn't tell everyone to die, someone must have finished since the last line... */ |
1810 | continue; |
1811 | } |
1812 | /* collect the dead */ |
1813 | for (i = 0; i < threadno; i++) { |
1814 | SDL_WaitThread(threads[i], NULL__null); |
1815 | } |
1816 | /* reset semaphore */ |
1817 | SDL_SemPost(mapSem); |
1818 | /* start'em again */ |
1819 | for (i = 0; i < threadno; i++) { |
1820 | memcpy(maps[i], map, sizeof(*map)); |
1821 | threads[i] = SDL_CreateThread(SV_AssemblyThread, (void*) maps[i]); |
1822 | } |
1823 | } else { |
1824 | /* someone finished */ |
1825 | assert(threadID != 0)(__builtin_expect(!(threadID != 0), 0) ? __assert_rtn(__func__ , "src/server/sv_rma.cpp", 1825, "threadID != 0") : (void)0); |
1826 | } |
1827 | } |
1828 | TH_MutexUnlock(mapLock)_TH_MutexUnlock((mapLock), "src/server/sv_rma.cpp", 1828); |
1829 | for (i = 0; i < threadno; i++) { |
1830 | if (SDL_GetThreadID(threads[i]) == threadID) { |
1831 | memcpy(map, maps[i], sizeof(*map)); |
1832 | } |
1833 | |
1834 | SDL_WaitThread(threads[i], NULL__null); |
1835 | Mem_Free(maps[i])_Mem_Free((maps[i]),"src/server/sv_rma.cpp",1835); |
1836 | } |
1837 | |
1838 | /* cleanup, for possible next time */ |
1839 | SDL_DestroySemaphore(mapSem); |
1840 | SDL_DestroyCond(mapCond); |
1841 | TH_MutexDestroy(mapLock); |
1842 | mapLock = NULL__null; |
1843 | mapSem = NULL__null; |
1844 | mapCond = NULL__null; |
1845 | threadID = 0; |
1846 | timeout = 5000; |
1847 | |
1848 | return 0; |
1849 | } |
1850 | |
1851 | /** |
1852 | * @brief Parses an ump file that contains the random map definition |
1853 | * @param[in] name The basename of the ump file (without extension) |
1854 | * @param[out] map The data structure to store the parsed data in |
1855 | * @param[in] inherit When @c true, this is called to inherit tile definitions |
1856 | * from another ump file (no assemblies) |
1857 | */ |
1858 | void SV_ParseUMP (const char *name, mapInfo_t *map, bool inherit) |
1859 | { |
1860 | char filename[MAX_QPATH64]; |
1861 | byte *buf; |
1862 | const char *text, *token; |
1863 | |
1864 | /* load the map info */ |
1865 | Com_sprintf(filename, sizeof(filename), "maps/%s.ump", name); |
1866 | FS_LoadFile(filename, &buf); |
1867 | if (!buf) |
1868 | Com_Error(ERR_DROP1, "SV_ParseUMP: Map assembly info '%s' not found", filename); |
1869 | |
1870 | /* parse it */ |
1871 | text = (const char*)buf; |
1872 | do { |
1873 | token = Com_Parse(&text); |
1874 | if (!text) |
1875 | break; |
1876 | |
1877 | if (Q_streq(token, "extends")(strcmp(token, "extends") == 0)) { |
1878 | token = Com_Parse(&text); |
1879 | SV_ParseUMP(token, map, true); |
1880 | } else if (Q_streq(token, "base")(strcmp(token, "base") == 0)) { |
1881 | token = Com_Parse(&text); |
1882 | if (inherit) |
1883 | Q_strncpyz(map->inheritBasePath, token, sizeof(map->inheritBasePath))Q_strncpyzDebug( map->inheritBasePath, token, sizeof(map-> inheritBasePath), "src/server/sv_rma.cpp", 1883 ); |
1884 | else |
1885 | Q_strncpyz(map->basePath, token, sizeof(map->basePath))Q_strncpyzDebug( map->basePath, token, sizeof(map->basePath ), "src/server/sv_rma.cpp", 1885 ); |
1886 | } else if (Q_streq(token, "line")(strcmp(token, "line") == 0)) { |
1887 | token = Com_Parse(&text); |
1888 | const char *p = token; |
1889 | map->lineFlags = 0; |
1890 | while (*p) { |
1891 | map->lineFlags |= tileMask(*p); |
1892 | p++; |
1893 | } |
1894 | } else if (Q_streq(token, "tileset")(strcmp(token, "tileset") == 0)) { |
1895 | if (map->numTileSets >= MAX_TILESETS16) |
1896 | Com_Printf("SV_ParseUMP: Too many map tileset found in (%s)\n", filename); |
1897 | else if (SV_ParseMapTileSet(filename, &text, map, inherit)) |
1898 | map->numTileSets++; |
1899 | } else if (Q_streq(token, "tile")(strcmp(token, "tile") == 0)) { |
1900 | if (map->numTiles >= MAX_TILETYPES64) |
1901 | Com_Printf("SV_ParseUMP: Too many map tile types (%s)\n", filename); |
1902 | else if (SV_ParseMapTile(filename, &text, map, inherit)) |
1903 | map->numTiles++; |
1904 | } else if (Q_streq(token, "assembly")(strcmp(token, "assembly") == 0)) { |
1905 | if (inherit) { |
1906 | FS_SkipBlock(&text); |
1907 | } else { |
1908 | if (map->numAssemblies >= MAX_MAPASSEMBLIES32) |
1909 | Com_Printf("SV_ParseUMP: Too many map assemblies (%s)\n", filename); |
1910 | else if (SV_ParseAssembly(map, filename, &text, &map->mAssembly[map->numAssemblies])) |
1911 | map->numAssemblies++; |
1912 | } |
1913 | } else if (token[0] == '{') { |
1914 | Com_Printf("SV_ParseUMP: Skipping unknown block\n"); |
1915 | /* ignore unknown block */ |
1916 | text = strchr(text, '}') + 1; |
1917 | if (!text) |
1918 | break; |
1919 | } else |
1920 | Com_Printf("SV_ParseUMP: Unknown token '%s' (%s)\n", token, filename); |
1921 | } while (text); |
1922 | |
1923 | /* free the file */ |
1924 | FS_FreeFile(buf); |
1925 | } |
1926 | |
1927 | #if SORT_BY_SIZE1 |
1928 | static int cmpTileAreaSize (const void * a, const void * b) |
1929 | { |
1930 | if (((const mToPlace_t *) a)->tile->area > ((const mToPlace_t *) b)->tile->area) |
1931 | return -1; |
1932 | else if (((const mToPlace_t *) a)->tile->area == ((const mToPlace_t *) b)->tile->area) |
1933 | return 0; |
1934 | return 1; |
1935 | } |
1936 | #endif |
1937 | |
1938 | static mapInfo_t* SV_DoMapAssemble (mapInfo_t *map, const char *assembly, char *asmMap, char *asmPos, const unsigned int seed) |
1939 | { |
1940 | int i; |
1941 | mAssembly_t *mAsm = &map->mAssembly[map->mAsm]; |
1942 | |
1943 | Com_DPrintf(DEBUG_SERVER0x40, "Use assembly: '%s'\n", mAsm->id); |
1944 | |
1945 | /* check size */ |
1946 | assert(mAsm->width <= MAX_RANDOM_MAP_WIDTH)(__builtin_expect(!(mAsm->width <= 32), 0) ? __assert_rtn (__func__, "src/server/sv_rma.cpp", 1946, "mAsm->width <= MAX_RANDOM_MAP_WIDTH" ) : (void)0); |
1947 | assert(mAsm->height <= MAX_RANDOM_MAP_HEIGHT)(__builtin_expect(!(mAsm->height <= 32), 0) ? __assert_rtn (__func__, "src/server/sv_rma.cpp", 1947, "mAsm->height <= MAX_RANDOM_MAP_HEIGHT" ) : (void)0); |
1948 | |
1949 | SV_PrepareTilesToPlace(map); |
1950 | |
1951 | #if SORT_BY_SIZE1 |
1952 | /* This is the perfect time to sort them by size, which helps RMA a lot. |
1953 | * This eliminates the need for a seedlist in oriental large completely. |
1954 | * Unfortunately, it doesn't do that for the others. Instead, it can slow down some maps quite a bit. */ |
1955 | qsort(map->mToPlace, map->numToPlace, sizeof(mToPlace_t), cmpTileAreaSize); |
1956 | #endif |
1957 | |
1958 | /* assemble the map */ |
1959 | map->numPlaced = 0; |
1960 | SV_ClearMap(map); |
1961 | |
1962 | /* place fixed parts - defined in ump via fix parameter */ |
1963 | for (i = 0; i < mAsm->numFixed; i++) |
1964 | SV_AddTile(map, &map->mTile[mAsm->fT[i]], mAsm->fX[i], mAsm->fY[i], -1, -1); |
1965 | |
1966 | if (sv_threads->integer && sv_rma->integer == 1) { |
1967 | int oldCount = map->retryCnt; |
1968 | if (SV_ParallelSearch(map) < 0) { |
1969 | if (oldCount < map->retryCnt && mAsm->numSeeds > 0) { |
1970 | /* if we are allowed to restart the search with a fixed seed |
1971 | * from the assembly definition, do so */ |
1972 | Com_SetRandomSeed(mAsm->seeds[rand() % mAsm->numSeeds]); |
1973 | return SV_DoMapAssemble(map, assembly, asmMap, asmPos, seed); |
1974 | } |
1975 | Mem_Free(map)_Mem_Free((map),"src/server/sv_rma.cpp",1975); |
1976 | return NULL__null; |
1977 | } |
1978 | } else { |
1979 | unsigned int seedUsed; |
1980 | |
1981 | if (mAsm->numSeeds > 0) { |
1982 | /* if the map has a seedlist defined, use that */ |
1983 | seedUsed = mAsm->seeds[rand() % mAsm->numSeeds]; |
1984 | if (seed) { |
1985 | /* if a seed was passed, we are in cunit test mode */ |
1986 | if (seed >= mAsm->numSeeds) |
1987 | /* if the given seed is outside the seedlist, assume that we already tested it and pretend that it's ok */ |
1988 | return map; |
1989 | /* use the passed seed as an index into the seedlist */ |
1990 | seedUsed = mAsm->seeds[seed % mAsm->numSeeds]; |
1991 | } |
1992 | Com_Printf("Picked seed: %i for <%s>\n", seedUsed, assembly); |
1993 | } else { |
1994 | /* no seedlist */ |
1995 | if (seed) |
1996 | seedUsed = seed; |
1997 | else |
1998 | seedUsed = rand() % 50; /* limit the possible seeds to (testable) values between 0 and 49 */ |
1999 | } |
2000 | Com_SetRandomSeed(seedUsed); |
2001 | Com_Printf("Using RMA%i seed: %i for <%s>\n", sv_rma->integer, seedUsed, assembly); |
2002 | |
2003 | if (!SV_AddMapTiles(map)) { |
2004 | map->retryCnt++; |
2005 | if (mAsm->numSeeds > 0) { |
2006 | /* if we are allowed to restart the search with a fixed seed |
2007 | * from the assembly definition, do so */ |
2008 | Com_SetRandomSeed(mAsm->seeds[seed % mAsm->numSeeds]); |
2009 | return SV_DoMapAssemble(map, assembly, asmMap, asmPos, seed); |
2010 | } |
2011 | return NULL__null; |
2012 | } |
2013 | } |
2014 | |
2015 | /* prepare map and pos strings */ |
2016 | if (map->basePath[0]) |
2017 | Com_sprintf(asmMap, sizeof(map->basePath) + 1, "-%s", map->basePath); |
2018 | |
2019 | asmPos[0] = 0; |
2020 | |
2021 | /* generate the strings */ |
2022 | SV_PrintMapStrings(map, asmMap, asmPos); |
2023 | |
2024 | return map; |
2025 | } |
2026 | |
2027 | /** |
2028 | * @brief Assembles a "random" map |
2029 | * and parses the *.ump files for assembling the "random" maps and places the 'fixed' tiles. |
2030 | * For a more detailed description of the whole algorithm see SV_AddMapTiles. |
2031 | * @param[in] name The name of the map (ump) file to parse |
2032 | * @param[in] assembly The random map assembly that should be used from the given rma |
2033 | * @param[out] asmMap The output string of the random map assembly that contains all the |
2034 | * map tiles that should be assembled. The order is the same as in the @c asmPos string. |
2035 | * Each of the map tiles in this string has a corresponding entry in the pos string, too. |
2036 | * @param[out] asmPos The pos string for the assembly. For each tile from the @c asmMap |
2037 | * string this string contains three coordinates for shifting the given tile names. |
2038 | * @param[in] seed random seed to use (for cunit tests). If 0, the called functions can use their own seed setting. |
2039 | * @sa B_AssembleMap_f |
2040 | * @sa SV_AddTile |
2041 | * @sa SV_AddMandatoryParts |
2042 | * @sa SV_ParseAssembly |
2043 | * @sa SV_ParseMapTile |
2044 | * @note Make sure to free the returned pointer |
2045 | */ |
2046 | mapInfo_t* SV_AssembleMap (const char *name, const char *assembly, char *asmMap, char *asmPos, const unsigned int seed) |
2047 | { |
2048 | mapInfo_t *map; |
2049 | |
2050 | map = Mem_AllocType(mapInfo_t)((mapInfo_t*)_Mem_Alloc(((sizeof(mapInfo_t))),true,(com_genericPool ),(0),"src/server/sv_rma.cpp",2050)); |
2051 | Q_strncpyz(map->name, name, sizeof(map->name))Q_strncpyzDebug( map->name, name, sizeof(map->name), "src/server/sv_rma.cpp" , 2051 ); |
2052 | |
2053 | SV_ParseUMP(name, map, false); |
2054 | |
2055 | /* check for parsed tiles and assemblies */ |
2056 | if (!map->numTiles) |
2057 | Com_Error(ERR_DROP1, "No map tiles defined (%s)!", map->name); |
2058 | #ifdef DEBUG1 |
2059 | else |
2060 | Com_DPrintf(DEBUG_SERVER0x40, "numTiles: %i\n", map->numTiles); |
2061 | #endif |
2062 | |
2063 | if (!map->numAssemblies) |
2064 | Com_Error(ERR_DROP1, "No map assemblies defined (%s)!", map->name); |
2065 | #ifdef DEBUG1 |
2066 | else |
2067 | Com_DPrintf(DEBUG_SERVER0x40, "numAssemblies: %i\n", map->numAssemblies); |
2068 | #endif |
2069 | |
2070 | /* use random assembly, if no valid one has been specified */ |
2071 | map->mAsm = rand() % map->numAssemblies; |
2072 | |
2073 | /* overwrite with specified, if any */ |
2074 | if (assembly && assembly[0]) { |
2075 | int i; |
2076 | for (i = 0; i < map->numAssemblies; i++) |
2077 | if (Q_streq(assembly, map->mAssembly[i].id)(strcmp(assembly, map->mAssembly[i].id) == 0)) { |
2078 | map->mAsm = i; |
2079 | break; |
2080 | } |
2081 | if (i == map->numAssemblies) { |
2082 | Com_Printf("SV_AssembleMap: Map assembly '%s' not found\n", assembly); |
2083 | } |
2084 | } |
2085 | |
2086 | SV_DoMapAssemble(map, assembly, asmMap, asmPos, seed); |
2087 | |
2088 | return map; |
2089 | } |