Bug Summary

File:server/sv_rma.cpp
Location:line 1316, column 3
Description:Value stored to 'ty' is never read

Annotated Source Code

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/*
9All original material Copyright (C) 2002-2011 UFO: Alien Invasion.
10
11Original file from Quake 2 v3.21: quake2-2.31/server/sv_init.c
12
13Copyright (C) 1997-2001 Id Software, Inc.
14
15This program is free software; you can redistribute it and/or
16modify it under the terms of the GNU General Public License
17as published by the Free Software Foundation; either version 2
18of the License, or (at your option) any later version.
19
20This program is distributed in the hope that it will be useful,
21but WITHOUT ANY WARRANTY; without even the implied warranty of
22MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
23
24See the GNU General Public License for more details.
25
26You should have received a copy of the GNU General Public License
27along with this program; if not, write to the Free Software
28Foundation, 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 */
63static 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 */
65static short gapList[MAX_RANDOM_MAP_HEIGHT32][MAX_RANDOM_MAP_HEIGHT32][GAPS25 + 1];
66static SDL_sem *mapSem;
67static SDL_cond *mapCond;
68static threads_mutex_t *mapLock;
69static 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 */
76static 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 */
118static 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
134static 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 */
167static 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
275static 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
288static 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 */
306static 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 */
366static 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 */
451static 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
479static 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 */
507static 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
535static 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 */
603static 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 */
771static 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 */
794static 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 */
815static 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 */
867static 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 */
883static 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 */
922static 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 */
968static 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 */
1020static 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 */
1055static 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 */
1078static int availableTiles[MAX_TILETYPES64][2]; /* the 2nd dimension is index and count */
1079
1080static 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 */
1291static 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 */
1348static 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 */
1393static 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 */
1464static 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 */
1590static 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 */
1701void 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 */
1729static 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 */
1778static 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 */
1858void 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
1928static 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
1938static 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 */
2046mapInfo_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}