1 /***********************************************************************
2 Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; either version 2, or (at your option)
6 any later version.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12 ***********************************************************************/
13
14 #ifdef HAVE_CONFIG_H
15 #include <fc_config.h>
16 #endif
17 #include <string.h> /* strlen */
18
19 /* utility */
20 #include "fcintl.h"
21 #include "iterator.h"
22 #include "log.h"
23 #include "mem.h"
24 #include "rand.h"
25 #include "shared.h"
26 #include "support.h"
27
28 /* common */
29 #include "city.h"
30 #include "game.h"
31 #include "movement.h"
32 #include "nation.h"
33 #include "packets.h"
34 #include "road.h"
35 #include "unit.h"
36 #include "unitlist.h"
37
38 #include "map.h"
39
40 struct startpos {
41 struct tile *location;
42 bool exclude;
43 struct nation_hash *nations;
44 };
45
46 static struct startpos *startpos_new(struct tile *ptile);
47 static void startpos_destroy(struct startpos *psp);
48
49 /* struct startpos_hash and related functions. */
50 #define SPECHASH_TAG startpos
51 #define SPECHASH_IKEY_TYPE struct tile *
52 #define SPECHASH_IDATA_TYPE struct startpos *
53 #define SPECHASH_IDATA_FREE startpos_destroy
54 #include "spechash.h"
55
56 /* Srart position iterator. */
57 struct startpos_iter {
58 struct iterator vtable;
59 const struct startpos *psp;
60 /* 'struct nation_iter' really. See startpos_iter_sizeof(). */
61 struct iterator nation_iter;
62 };
63
64 #define STARTPOS_ITER(p) ((struct startpos_iter *) (p))
65
66
67 /* these are initialized from the terrain ruleset */
68 struct terrain_misc terrain_control;
69
70 /* used to compute neighboring tiles.
71 *
72 * using
73 * x1 = x + DIR_DX[dir];
74 * y1 = y + DIR_DY[dir];
75 * will give you the tile as shown below.
76 * -------
77 * |0|1|2|
78 * |-+-+-|
79 * |3| |4|
80 * |-+-+-|
81 * |5|6|7|
82 * -------
83 * Note that you must normalize x1 and y1 yourself.
84 */
85 const int DIR_DX[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
86 const int DIR_DY[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
87
88 static bool dir_cardinality[9]; /* Including invalid one */
89 static bool dir_validity[9]; /* Including invalid one */
90
91 static bool is_valid_dir_calculate(enum direction8 dir);
92 static bool is_cardinal_dir_calculate(enum direction8 dir);
93
94 static bool restrict_infra(const struct player *pplayer, const struct tile *t1,
95 const struct tile *t2);
96
97 /****************************************************************************
98 Return a bitfield of the extras on the tile that are infrastructure.
99 ****************************************************************************/
get_tile_infrastructure_set(const struct tile * ptile,int * pcount)100 bv_extras get_tile_infrastructure_set(const struct tile *ptile,
101 int *pcount)
102 {
103 bv_extras pspresent;
104 int count = 0;
105
106 BV_CLR_ALL(pspresent);
107
108 extra_type_iterate(pextra) {
109 if (is_extra_removed_by(pextra, ERM_PILLAGE) && tile_has_extra(ptile, pextra)) {
110 struct tile *missingset = tile_virtual_new(ptile);
111 bool dependency = FALSE;
112
113 tile_remove_extra(missingset, pextra);
114 extra_type_iterate(pdependant) {
115 if (tile_has_extra(ptile, pdependant)) {
116 if (!are_reqs_active(NULL, NULL, NULL, NULL, missingset,
117 NULL, NULL, NULL, NULL,
118 &pdependant->reqs, RPT_POSSIBLE)) {
119 dependency = TRUE;
120 break;
121 }
122 }
123 } extra_type_iterate_end;
124
125 tile_virtual_destroy(missingset);
126
127 if (!dependency) {
128 BV_SET(pspresent, extra_index(pextra));
129 count++;
130 }
131 }
132 } extra_type_iterate_end;
133
134 if (pcount) {
135 *pcount = count;
136 }
137
138 return pspresent;
139 }
140
141 /***************************************************************
142 Returns 1 if we are at a stage of the game where the map
143 has not yet been generated/loaded.
144 (To be precise, returns 1 if map_allocate() has not yet been
145 called.)
146 ***************************************************************/
map_is_empty(void)147 bool map_is_empty(void)
148 {
149 return !game.map.tiles;
150 }
151
152 /***************************************************************
153 put some sensible values into the map structure
154 ***************************************************************/
map_init(void)155 void map_init(void)
156 {
157 game.map.topology_id = MAP_DEFAULT_TOPO;
158 game.map.num_continents = 0;
159 game.map.num_oceans = 0;
160 game.map.tiles = NULL;
161 game.map.startpos_table = NULL;
162 game.map.iterate_outwards_indices = NULL;
163
164 /* The [xy]size values are set in map_init_topology. It is initialized
165 * to a non-zero value because some places erronously use these values
166 * before they're initialized. */
167 game.map.xsize = MAP_DEFAULT_LINEAR_SIZE;
168 game.map.ysize = MAP_DEFAULT_LINEAR_SIZE;
169
170 if (is_server()) {
171 game.map.server.mapsize = MAP_DEFAULT_MAPSIZE;
172 game.map.server.size = MAP_DEFAULT_SIZE;
173 game.map.server.tilesperplayer = MAP_DEFAULT_TILESPERPLAYER;
174 game.map.server.seed_setting = MAP_DEFAULT_SEED;
175 game.map.server.seed = MAP_DEFAULT_SEED;
176 game.map.server.riches = MAP_DEFAULT_RICHES;
177 game.map.server.huts = MAP_DEFAULT_HUTS;
178 game.map.server.huts_absolute = -1;
179 game.map.server.animals = MAP_DEFAULT_ANIMALS;
180 game.map.server.landpercent = MAP_DEFAULT_LANDMASS;
181 game.map.server.wetness = MAP_DEFAULT_WETNESS;
182 game.map.server.steepness = MAP_DEFAULT_STEEPNESS;
183 game.map.server.generator = MAP_DEFAULT_GENERATOR;
184 game.map.server.startpos = MAP_DEFAULT_STARTPOS;
185 game.map.server.tinyisles = MAP_DEFAULT_TINYISLES;
186 game.map.server.separatepoles = MAP_DEFAULT_SEPARATE_POLES;
187 game.map.server.single_pole = MAP_DEFAULT_SINGLE_POLE;
188 game.map.server.alltemperate = MAP_DEFAULT_ALLTEMPERATE;
189 game.map.server.temperature = MAP_DEFAULT_TEMPERATURE;
190 game.map.server.have_huts = FALSE;
191 game.map.server.have_resources = FALSE;
192 game.map.server.team_placement = MAP_DEFAULT_TEAM_PLACEMENT;
193 }
194 }
195
196 /**************************************************************************
197 Fill the iterate_outwards_indices array. This may depend on the topology.
198 ***************************************************************************/
generate_map_indices(void)199 static void generate_map_indices(void)
200 {
201 int i = 0, nat_x, nat_y, tiles;
202 int nat_center_x, nat_center_y, nat_min_x, nat_min_y, nat_max_x, nat_max_y;
203 int map_center_x, map_center_y;
204
205 /* These caluclations are done via tricky native math. We need to make
206 * sure that when "exploring" positions in the iterate_outward we hit each
207 * position within the distance exactly once.
208 *
209 * To do this we pick a center position (at the center of the map, for
210 * convenience). Then we iterate over all of the positions around it,
211 * accounting for wrapping, in native coordinates. Note that some of the
212 * positions iterated over before will not even be real; the point is to
213 * use the native math so as to get the right behavior under different
214 * wrapping conditions.
215 *
216 * Thus the "center" position below is just an arbitrary point. We choose
217 * the center of the map to make the min/max values (below) simpler. */
218 nat_center_x = game.map.xsize / 2;
219 nat_center_y = game.map.ysize / 2;
220 NATIVE_TO_MAP_POS(&map_center_x, &map_center_y,
221 nat_center_x, nat_center_y);
222
223 /* If we wrap in a particular direction (X or Y) we only need to explore a
224 * half of a map-width in that direction before we hit the wrap point. If
225 * not we need to explore the full width since we have to account for the
226 * worst-case where we start at one edge of the map. Of course if we try
227 * to explore too far the extra steps will just be skipped by the
228 * normalize check later on. So the purpose at this point is just to
229 * get the right set of positions, relative to the start position, that
230 * may be needed for the iteration.
231 *
232 * If the map does wrap, we go map.Nsize / 2 in each direction. This
233 * gives a min value of 0 and a max value of Nsize-1, because of the
234 * center position chosen above. This also avoids any off-by-one errors.
235 *
236 * If the map doesn't wrap, we go map.Nsize-1 in each direction. In this
237 * case we're not concerned with going too far and wrapping around, so we
238 * just have to make sure we go far enough if we're at one edge of the
239 * map. */
240 nat_min_x = (current_topo_has_flag(TF_WRAPX) ? 0 : (nat_center_x - game.map.xsize + 1));
241 nat_min_y = (current_topo_has_flag(TF_WRAPY) ? 0 : (nat_center_y - game.map.ysize + 1));
242
243 nat_max_x = (current_topo_has_flag(TF_WRAPX)
244 ? (game.map.xsize - 1)
245 : (nat_center_x + game.map.xsize - 1));
246 nat_max_y = (current_topo_has_flag(TF_WRAPY)
247 ? (game.map.ysize - 1)
248 : (nat_center_y + game.map.ysize - 1));
249 tiles = (nat_max_x - nat_min_x + 1) * (nat_max_y - nat_min_y + 1);
250
251 fc_assert(NULL == game.map.iterate_outwards_indices);
252 game.map.iterate_outwards_indices =
253 fc_malloc(tiles * sizeof(*game.map.iterate_outwards_indices));
254
255 for (nat_x = nat_min_x; nat_x <= nat_max_x; nat_x++) {
256 for (nat_y = nat_min_y; nat_y <= nat_max_y; nat_y++) {
257 int map_x, map_y, dx, dy;
258
259 /* Now for each position, we find the vector (in map coordinates) from
260 * the center position to that position. Then we calculate the
261 * distance between the two points. Wrapping is ignored at this
262 * point since the use of native positions means we should always have
263 * the shortest vector. */
264 NATIVE_TO_MAP_POS(&map_x, &map_y, nat_x, nat_y);
265 dx = map_x - map_center_x;
266 dy = map_y - map_center_y;
267
268 game.map.iterate_outwards_indices[i].dx = dx;
269 game.map.iterate_outwards_indices[i].dy = dy;
270 game.map.iterate_outwards_indices[i].dist =
271 map_vector_to_real_distance(dx, dy);
272 i++;
273 }
274 }
275 fc_assert(i == tiles);
276
277 qsort(game.map.iterate_outwards_indices, tiles,
278 sizeof(*game.map.iterate_outwards_indices), compare_iter_index);
279
280 #if 0
281 for (i = 0; i < tiles; i++) {
282 log_debug("%5d : (%3d,%3d) : %d", i,
283 game.map.iterate_outwards_indices[i].dx,
284 game.map.iterate_outwards_indices[i].dy,
285 game.map.iterate_outwards_indices[i].dist);
286 }
287 #endif
288
289 game.map.num_iterate_outwards_indices = tiles;
290 }
291
292 /****************************************************************************
293 map_init_topology needs to be called after map.topology_id is changed.
294
295 map.xsize and map.ysize must be set before calling map_init_topology().
296 This is done by the map generator code (server), when loading a savegame
297 or a scenario with map (server), and packhand code (client).
298 ****************************************************************************/
map_init_topology(void)299 void map_init_topology(void)
300 {
301 enum direction8 dir;
302
303 /* sanity check for iso topologies*/
304 fc_assert(!MAP_IS_ISOMETRIC || (game.map.ysize % 2) == 0);
305
306 /* The size and ratio must satisfy the minimum and maximum *linear*
307 * restrictions on width */
308 fc_assert(game.map.xsize >= MAP_MIN_LINEAR_SIZE);
309 fc_assert(game.map.ysize >= MAP_MIN_LINEAR_SIZE);
310 fc_assert(game.map.xsize <= MAP_MAX_LINEAR_SIZE);
311 fc_assert(game.map.ysize <= MAP_MAX_LINEAR_SIZE);
312 fc_assert(map_num_tiles() >= MAP_MIN_SIZE * 1000);
313 fc_assert(map_num_tiles() <= MAP_MAX_SIZE * 1000);
314
315 game.map.num_valid_dirs = game.map.num_cardinal_dirs = 0;
316
317 /* Values for direction8_invalid() */
318 fc_assert(direction8_invalid() == 8);
319 dir_validity[8] = FALSE;
320 dir_cardinality[8] = FALSE;
321
322 /* Values for actual directions */
323 for (dir = 0; dir < 8; dir++) {
324 if (is_valid_dir_calculate(dir)) {
325 game.map.valid_dirs[game.map.num_valid_dirs] = dir;
326 game.map.num_valid_dirs++;
327 dir_validity[dir] = TRUE;
328 } else {
329 dir_validity[dir] = FALSE;
330 }
331 if (is_cardinal_dir_calculate(dir)) {
332 game.map.cardinal_dirs[game.map.num_cardinal_dirs] = dir;
333 game.map.num_cardinal_dirs++;
334 dir_cardinality[dir] = TRUE;
335 } else {
336 dir_cardinality[dir] = FALSE;
337 }
338 }
339 fc_assert(game.map.num_valid_dirs > 0 && game.map.num_valid_dirs <= 8);
340 fc_assert(game.map.num_cardinal_dirs > 0
341 && game.map.num_cardinal_dirs <= game.map.num_valid_dirs);
342 }
343
344 /***************************************************************
345 Initialize tile structure
346 ***************************************************************/
tile_init(struct tile * ptile)347 static void tile_init(struct tile *ptile)
348 {
349 ptile->continent = 0;
350
351 BV_CLR_ALL(ptile->extras);
352 ptile->resource_valid = FALSE;
353 ptile->resource = NULL;
354 ptile->terrain = T_UNKNOWN;
355 ptile->units = unit_list_new();
356 ptile->owner = NULL; /* Not claimed by any player. */
357 ptile->extras_owner = NULL;
358 ptile->claimer = NULL;
359 ptile->worked = NULL; /* No city working here. */
360 ptile->spec_sprite = NULL;
361 }
362
363 /****************************************************************************
364 Step from the given tile in the given direction. The new tile is returned,
365 or NULL if the direction is invalid or leads off the map.
366 ****************************************************************************/
mapstep(const struct tile * ptile,enum direction8 dir)367 struct tile *mapstep(const struct tile *ptile, enum direction8 dir)
368 {
369 int dx, dy, tile_x, tile_y;
370
371 if (!is_valid_dir(dir)) {
372 return NULL;
373 }
374
375 index_to_map_pos(&tile_x, &tile_y, tile_index(ptile));
376 DIRSTEP(dx, dy, dir);
377
378 tile_x += dx;
379 tile_y += dy;
380
381 return map_pos_to_tile(tile_x, tile_y);
382 }
383
384 /****************************************************************************
385 Return the tile for the given native position, with wrapping.
386
387 This is a backend function used by map_pos_to_tile and native_pos_to_tile.
388 It is called extremely often so it is made inline.
389 ****************************************************************************/
base_native_pos_to_tile(int nat_x,int nat_y)390 static inline struct tile *base_native_pos_to_tile(int nat_x, int nat_y)
391 {
392 /* Wrap in X and Y directions, as needed. */
393 /* If the position is out of range in a non-wrapping direction, it is
394 * unreal. */
395 if (current_topo_has_flag(TF_WRAPX)) {
396 nat_x = FC_WRAP(nat_x, game.map.xsize);
397 } else if (nat_x < 0 || nat_x >= game.map.xsize) {
398 return NULL;
399 }
400 if (current_topo_has_flag(TF_WRAPY)) {
401 nat_y = FC_WRAP(nat_y, game.map.ysize);
402 } else if (nat_y < 0 || nat_y >= game.map.ysize) {
403 return NULL;
404 }
405
406 /* We already checked legality of native pos above, don't repeat */
407 return game.map.tiles + native_pos_to_index_nocheck(nat_x, nat_y);
408 }
409
410 /****************************************************************************
411 Return the tile for the given cartesian (map) position.
412 ****************************************************************************/
map_pos_to_tile(int map_x,int map_y)413 struct tile *map_pos_to_tile(int map_x, int map_y)
414 {
415 /* Instead of introducing new variables for native coordinates,
416 * update the map coordinate variables = registers already in use.
417 * This is one of the most performance-critical functions we have,
418 * so taking measures like this makes sense. */
419 #define nat_x map_x
420 #define nat_y map_y
421
422 if (!game.map.tiles) {
423 return NULL;
424 }
425
426 /* Normalization is best done in native coordinates. */
427 MAP_TO_NATIVE_POS(&nat_x, &nat_y, map_x, map_y);
428 return base_native_pos_to_tile(nat_x, nat_y);
429
430 #undef nat_x
431 #undef nat_y
432 }
433
434 /****************************************************************************
435 Return the tile for the given native position.
436 ****************************************************************************/
native_pos_to_tile(int nat_x,int nat_y)437 struct tile *native_pos_to_tile(int nat_x, int nat_y)
438 {
439 if (!game.map.tiles) {
440 return NULL;
441 }
442
443 return base_native_pos_to_tile(nat_x, nat_y);
444 }
445
446 /****************************************************************************
447 Return the tile for the given index position.
448 ****************************************************************************/
index_to_tile(int mindex)449 struct tile *index_to_tile(int mindex)
450 {
451 if (!game.map.tiles) {
452 return NULL;
453 }
454
455 if (mindex >= 0 && mindex < MAP_INDEX_SIZE) {
456 return game.map.tiles + mindex;
457 } else {
458 /* Unwrapped index coordinates are impossible, so the best we can do is
459 * return NULL. */
460 return NULL;
461 }
462 }
463
464 /***************************************************************
465 Free memory associated with one tile.
466 ***************************************************************/
tile_free(struct tile * ptile)467 static void tile_free(struct tile *ptile)
468 {
469 unit_list_destroy(ptile->units);
470
471 if (ptile->spec_sprite) {
472 free(ptile->spec_sprite);
473 ptile->spec_sprite = NULL;
474 }
475
476 if (ptile->label) {
477 FC_FREE(ptile->label);
478 ptile->label = NULL;
479 }
480 }
481
482 /**************************************************************************
483 Allocate space for map, and initialise the tiles.
484 Uses current map.xsize and map.ysize.
485 **************************************************************************/
map_allocate(void)486 void map_allocate(void)
487 {
488 log_debug("map_allocate (was %p) (%d,%d)",
489 (void *) game.map.tiles, game.map.xsize, game.map.ysize);
490
491 fc_assert_ret(NULL == game.map.tiles);
492 game.map.tiles = fc_calloc(MAP_INDEX_SIZE, sizeof(*game.map.tiles));
493
494 /* Note this use of whole_map_iterate may be a bit sketchy, since the
495 * tile values (ptile->index, etc.) haven't been set yet. It might be
496 * better to do a manual loop here. */
497 whole_map_iterate(ptile) {
498 ptile->index = ptile - game.map.tiles;
499 CHECK_INDEX(tile_index(ptile));
500 tile_init(ptile);
501 } whole_map_iterate_end;
502
503 generate_city_map_indices();
504 generate_map_indices();
505
506 if (game.map.startpos_table != NULL) {
507 startpos_hash_destroy(game.map.startpos_table);
508 }
509 game.map.startpos_table = startpos_hash_new();
510 }
511
512 /***************************************************************
513 Frees the allocated memory of the map.
514 ***************************************************************/
map_free(void)515 void map_free(void)
516 {
517 if (game.map.tiles) {
518 /* it is possible that map_init was called but not map_allocate */
519
520 whole_map_iterate(ptile) {
521 tile_free(ptile);
522 } whole_map_iterate_end;
523
524 free(game.map.tiles);
525 game.map.tiles = NULL;
526
527 if (game.map.startpos_table) {
528 startpos_hash_destroy(game.map.startpos_table);
529 game.map.startpos_table = NULL;
530 }
531
532 FC_FREE(game.map.iterate_outwards_indices);
533 free_city_map_index();
534 }
535 }
536
537 /****************************************************************************
538 Return the "distance" (which is really the Manhattan distance, and should
539 rarely be used) for a given vector.
540 ****************************************************************************/
map_vector_to_distance(int dx,int dy)541 static int map_vector_to_distance(int dx, int dy)
542 {
543 if (current_topo_has_flag(TF_HEX)) {
544 /* Hex: all directions are cardinal so the distance is equivalent to
545 * the real distance. */
546 return map_vector_to_real_distance(dx, dy);
547 } else {
548 return abs(dx) + abs(dy);
549 }
550 }
551
552 /****************************************************************************
553 Return the "real" distance for a given vector.
554 ****************************************************************************/
map_vector_to_real_distance(int dx,int dy)555 int map_vector_to_real_distance(int dx, int dy)
556 {
557 const int absdx = abs(dx), absdy = abs(dy);
558
559 if (current_topo_has_flag(TF_HEX)) {
560 if (current_topo_has_flag(TF_ISO)) {
561 /* Iso-hex: you can't move NE or SW. */
562 if ((dx < 0 && dy > 0)
563 || (dx > 0 && dy < 0)) {
564 /* Diagonal moves in this direction aren't allowed, so it will take
565 * the full number of moves. */
566 return absdx + absdy;
567 } else {
568 /* Diagonal moves in this direction *are* allowed. */
569 return MAX(absdx, absdy);
570 }
571 } else {
572 /* Hex: you can't move SE or NW. */
573 if ((dx > 0 && dy > 0)
574 || (dx < 0 && dy < 0)) {
575 /* Diagonal moves in this direction aren't allowed, so it will take
576 * the full number of moves. */
577 return absdx + absdy;
578 } else {
579 /* Diagonal moves in this direction *are* allowed. */
580 return MAX(absdx, absdy);
581 }
582 }
583 } else {
584 return MAX(absdx, absdy);
585 }
586 }
587
588 /****************************************************************************
589 Return the sq_distance for a given vector.
590 ****************************************************************************/
map_vector_to_sq_distance(int dx,int dy)591 int map_vector_to_sq_distance(int dx, int dy)
592 {
593 if (current_topo_has_flag(TF_HEX)) {
594 /* Hex: The square distance is just the square of the real distance; we
595 * don't worry about pythagorean calculations. */
596 int dist = map_vector_to_real_distance(dx, dy);
597
598 return dist * dist;
599 } else {
600 return dx * dx + dy * dy;
601 }
602 }
603
604 /***************************************************************
605 Return real distance between two tiles.
606 ***************************************************************/
real_map_distance(const struct tile * tile0,const struct tile * tile1)607 int real_map_distance(const struct tile *tile0, const struct tile *tile1)
608 {
609 int dx, dy;
610
611 map_distance_vector(&dx, &dy, tile0, tile1);
612 return map_vector_to_real_distance(dx, dy);
613 }
614
615 /***************************************************************
616 Return squared distance between two tiles.
617 ***************************************************************/
sq_map_distance(const struct tile * tile0,const struct tile * tile1)618 int sq_map_distance(const struct tile *tile0, const struct tile *tile1)
619 {
620 /* We assume map_distance_vector gives us the vector with the
621 minimum squared distance. Right now this is true. */
622 int dx, dy;
623
624 map_distance_vector(&dx, &dy, tile0, tile1);
625 return map_vector_to_sq_distance(dx, dy);
626 }
627
628 /***************************************************************
629 Return Manhattan distance between two tiles.
630 ***************************************************************/
map_distance(const struct tile * tile0,const struct tile * tile1)631 int map_distance(const struct tile *tile0, const struct tile *tile1)
632 {
633 /* We assume map_distance_vector gives us the vector with the
634 minimum map distance. Right now this is true. */
635 int dx, dy;
636
637 map_distance_vector(&dx, &dy, tile0, tile1);
638 return map_vector_to_distance(dx, dy);
639 }
640
641 /****************************************************************************
642 Return TRUE if this ocean terrain is adjacent to a safe coastline.
643 ****************************************************************************/
is_safe_ocean(const struct tile * ptile)644 bool is_safe_ocean(const struct tile *ptile)
645 {
646 adjc_iterate(ptile, adjc_tile) {
647 if (tile_terrain(adjc_tile) != T_UNKNOWN
648 && !terrain_has_flag(tile_terrain(adjc_tile), TER_UNSAFE_COAST)) {
649 return TRUE;
650 }
651 } adjc_iterate_end;
652 return FALSE;
653 }
654
655 /***************************************************************
656 Can tile be irrigated by given unit? Unit can be NULL to check if
657 any settler type unit of any player can irrigate.
658 ***************************************************************/
can_be_irrigated(const struct tile * ptile,const struct unit * punit)659 bool can_be_irrigated(const struct tile *ptile,
660 const struct unit *punit)
661 {
662 struct terrain* pterrain = tile_terrain(ptile);
663
664 if (T_UNKNOWN == pterrain) {
665 return FALSE;
666 }
667
668 return get_tile_bonus(ptile, punit, EFT_IRRIG_POSSIBLE) > 0;
669 }
670
671 /**************************************************************************
672 This function returns true if the tile at the given location can be
673 "reclaimed" from ocean into land. This is the case only when there are
674 a sufficient number of adjacent tiles that are not ocean.
675 **************************************************************************/
can_reclaim_ocean(const struct tile * ptile)676 bool can_reclaim_ocean(const struct tile *ptile)
677 {
678 int land_tiles = 100 - count_terrain_class_near_tile(ptile, FALSE, TRUE,
679 TC_OCEAN);
680
681 return land_tiles >= terrain_control.ocean_reclaim_requirement_pct;
682 }
683
684 /**************************************************************************
685 This function returns true if the tile at the given location can be
686 "channeled" from land into ocean. This is the case only when there are
687 a sufficient number of adjacent tiles that are ocean.
688 **************************************************************************/
can_channel_land(const struct tile * ptile)689 bool can_channel_land(const struct tile *ptile)
690 {
691 int ocean_tiles = count_terrain_class_near_tile(ptile, FALSE, TRUE, TC_OCEAN);
692
693 return ocean_tiles >= terrain_control.land_channel_requirement_pct;
694 }
695
696 /**************************************************************************
697 Returns true if the tile at the given location can be thawed from
698 terrain with a 'Frozen' flag to terrain without. This requires a
699 sufficient number of adjacent unfrozen tiles.
700 **************************************************************************/
can_thaw_terrain(const struct tile * ptile)701 bool can_thaw_terrain(const struct tile *ptile)
702 {
703 int unfrozen_tiles = 100 - count_terrain_flag_near_tile(ptile, FALSE, TRUE,
704 TER_FROZEN);
705
706 return unfrozen_tiles >= terrain_control.terrain_thaw_requirement_pct;
707 }
708
709 /**************************************************************************
710 Returns true if the tile at the given location can be turned from
711 terrain without a 'Frozen' flag to terrain with. This requires a
712 sufficient number of adjacent frozen tiles.
713 **************************************************************************/
can_freeze_terrain(const struct tile * ptile)714 bool can_freeze_terrain(const struct tile *ptile)
715 {
716 int frozen_tiles = count_terrain_flag_near_tile(ptile, FALSE, TRUE,
717 TER_FROZEN);
718
719 return frozen_tiles >= terrain_control.terrain_freeze_requirement_pct;
720 }
721
722 /**************************************************************************
723 Returns FALSE if a terrain change to 'pterrain' would be prevented by not
724 having enough similar terrain surrounding ptile.
725 **************************************************************************/
terrain_surroundings_allow_change(const struct tile * ptile,const struct terrain * pterrain)726 bool terrain_surroundings_allow_change(const struct tile *ptile,
727 const struct terrain *pterrain)
728 {
729 bool ret = TRUE;
730
731 if (is_ocean(tile_terrain(ptile))
732 && !is_ocean(pterrain) && !can_reclaim_ocean(ptile)) {
733 ret = FALSE;
734 } else if (!is_ocean(tile_terrain(ptile))
735 && is_ocean(pterrain) && !can_channel_land(ptile)) {
736 ret = FALSE;
737 }
738
739 if (ret) {
740 if (terrain_has_flag(tile_terrain(ptile), TER_FROZEN)
741 && !terrain_has_flag(pterrain, TER_FROZEN)
742 && !can_thaw_terrain(ptile)) {
743 ret = FALSE;
744 } else if (!terrain_has_flag(tile_terrain(ptile), TER_FROZEN)
745 && terrain_has_flag(pterrain, TER_FROZEN)
746 && !can_freeze_terrain(ptile)) {
747 ret = FALSE;
748 }
749 }
750
751 return ret;
752 }
753
754 /***************************************************************
755 The basic cost to move punit from tile t1 to tile t2.
756 That is, tile_move_cost(), with pre-calculated tile pointers;
757 the tiles are assumed to be adjacent, and the (x,y)
758 values are used only to get the river bonus correct.
759
760 May also be used with punit == NULL, in which case punit
761 tests are not done (for unit-independent results).
762 ***************************************************************/
tile_move_cost_ptrs(const struct unit * punit,const struct unit_type * punittype,const struct player * pplayer,const struct tile * t1,const struct tile * t2)763 int tile_move_cost_ptrs(const struct unit *punit,
764 const struct unit_type *punittype,
765 const struct player *pplayer,
766 const struct tile *t1, const struct tile *t2)
767 {
768 const struct unit_class *pclass = utype_class(punittype);
769 int cost;
770 bool cardinality_checked = FALSE;
771 bool cardinal_move BAD_HEURISTIC_INIT(FALSE);
772 bool ri;
773
774 /* Try to exit early for detectable conditions */
775 if (!uclass_has_flag(pclass, UCF_TERRAIN_SPEED)) {
776 /* units without UCF_TERRAIN_SPEED have a constant cost. */
777 return SINGLE_MOVE;
778
779 } else if (!is_native_tile_to_class(pclass, t2)) {
780 /* Loading to transport or entering port.
781 * UTYF_IGTER units get move benefit. */
782 return (utype_has_flag(punittype, UTYF_IGTER)
783 ? MOVE_COST_IGTER : SINGLE_MOVE);
784
785 } else if (!is_native_tile_to_class(pclass, t1)) {
786 if (game.info.slow_invasions
787 && tile_city(t1) == NULL) {
788 /* If "slowinvasions" option is turned on, units moving from
789 * non-native terrain (from transport) to native terrain lose all
790 * their movement.
791 * e.g. ground units moving from sea to land */
792 if (punit != NULL) {
793 return punit->moves_left;
794 } else {
795 /* Needs to be bigger than SINGLE_MOVE * move_rate * MAX(1, fuel)
796 * for the most mobile unit possible. */
797 return FC_INFINITY;
798 }
799 } else {
800 /* Disembarking from transport or leaving port.
801 * UTYF_IGTER units get move benefit. */
802 return (utype_has_flag(punittype, UTYF_IGTER)
803 ? MOVE_COST_IGTER : SINGLE_MOVE);
804 }
805 }
806
807 cost = tile_terrain(t2)->movement_cost * SINGLE_MOVE;
808 ri = restrict_infra(pplayer, t1, t2);
809
810 extra_type_list_iterate(pclass->cache.bonus_roads, pextra) {
811 struct road_type *proad = extra_road_get(pextra);
812
813 /* We check the destination tile first, as that's
814 * the end of move that determines the cost.
815 * If can avoid inner loop about integrating roads
816 * completely if the destination road has too high cost. */
817
818 if (cost > proad->move_cost
819 && (!ri || road_has_flag(proad, RF_UNRESTRICTED_INFRA))
820 && tile_has_extra(t2, pextra)) {
821 extra_type_list_iterate(proad->integrators, iextra) {
822 /* We have no unrestricted infra related check here,
823 * destination road is the one that counts. */
824 if (tile_has_extra(t1, iextra)
825 && is_native_extra_to_uclass(iextra, pclass)) {
826 if (proad->move_mode == RMM_FAST_ALWAYS) {
827 cost = proad->move_cost;
828 } else {
829 if (!cardinality_checked) {
830 cardinal_move = (ALL_DIRECTIONS_CARDINAL() || is_move_cardinal(t1, t2));
831 cardinality_checked = TRUE;
832 }
833 if (cardinal_move) {
834 cost = proad->move_cost;
835 } else {
836 switch (proad->move_mode) {
837 case RMM_CARDINAL:
838 break;
839 case RMM_RELAXED:
840 if (cost > proad->move_cost * 2) {
841 cardinal_between_iterate(t1, t2, between) {
842 if (tile_has_extra(between, pextra)
843 || (pextra != iextra && tile_has_extra(between, iextra))) {
844 /* 'pextra != iextra' is there just to avoid tile_has_extra()
845 * in by far more common case that 'pextra == iextra' */
846 /* TODO: Should we restrict this more?
847 * Should we check against enemy cities on between tile?
848 * Should we check against non-native terrain on between tile?
849 */
850 cost = proad->move_cost * 2;
851 }
852 } cardinal_between_iterate_end;
853 }
854 break;
855 case RMM_FAST_ALWAYS:
856 fc_assert(proad->move_mode != RMM_FAST_ALWAYS); /* Already handled above */
857 cost = proad->move_cost;
858 break;
859 }
860 }
861 }
862 }
863 } extra_type_list_iterate_end;
864 }
865 } extra_type_list_iterate_end;
866
867 /* UTYF_IGTER units have a maximum move cost per step. */
868 if (utype_has_flag(punittype, UTYF_IGTER) && MOVE_COST_IGTER < cost) {
869 cost = MOVE_COST_IGTER;
870 }
871
872 if (terrain_control.pythagorean_diagonal) {
873 if (!cardinality_checked) {
874 cardinal_move = (ALL_DIRECTIONS_CARDINAL() || is_move_cardinal(t1, t2));
875 }
876 if (!cardinal_move) {
877 return (int) (cost * 1.41421356f);
878 }
879 }
880
881 return cost;
882 }
883
884 /****************************************************************************
885 Returns TRUE if there is a restriction with regard to the infrastructure,
886 i.e. at least one of the tiles t1 and t2 is claimed by a unfriendly
887 nation. This means that one can not use of the infrastructure (road,
888 railroad) on this tile.
889 ****************************************************************************/
restrict_infra(const struct player * pplayer,const struct tile * t1,const struct tile * t2)890 static bool restrict_infra(const struct player *pplayer, const struct tile *t1,
891 const struct tile *t2)
892 {
893 struct player *plr1 = tile_owner(t1), *plr2 = tile_owner(t2);
894
895 if (!pplayer || !game.info.restrictinfra) {
896 return FALSE;
897 }
898
899 if ((plr1 && pplayers_at_war(plr1, pplayer))
900 || (plr2 && pplayers_at_war(plr2, pplayer))) {
901 return TRUE;
902 }
903
904 return FALSE;
905 }
906
907 /***************************************************************
908 Are two tiles adjacent to each other.
909 ***************************************************************/
is_tiles_adjacent(const struct tile * tile0,const struct tile * tile1)910 bool is_tiles_adjacent(const struct tile *tile0, const struct tile *tile1)
911 {
912 return real_map_distance(tile0, tile1) == 1;
913 }
914
915 /***************************************************************
916 Are (x1,y1) and (x2,y2) really the same when adjusted?
917 This function might be necessary ALOT of places...
918 ***************************************************************/
same_pos(const struct tile * tile1,const struct tile * tile2)919 bool same_pos(const struct tile *tile1, const struct tile *tile2)
920 {
921 fc_assert_ret_val(tile1 != NULL && tile2 != NULL, FALSE);
922
923 /* In case of virtual tile, tile1 can be different from tile2,
924 * but they have same index */
925 return (tile1->index == tile2->index);
926 }
927
928 /***************************************************************
929 Is given position real position
930 ***************************************************************/
is_real_map_pos(int x,int y)931 bool is_real_map_pos(int x, int y)
932 {
933 return normalize_map_pos(&x, &y);
934 }
935
936 /**************************************************************************
937 Returns TRUE iff the map position is normal. "Normal" here means that
938 it is both a real/valid coordinate set and that the coordinates are in
939 their canonical/proper form. In plain English: the coordinates must be
940 on the map.
941 **************************************************************************/
is_normal_map_pos(int x,int y)942 bool is_normal_map_pos(int x, int y)
943 {
944 int nat_x, nat_y;
945
946 MAP_TO_NATIVE_POS(&nat_x, &nat_y, x, y);
947 return nat_x >= 0 && nat_x < game.map.xsize && nat_y >= 0 && nat_y < game.map.ysize;
948 }
949
950 /**************************************************************************
951 If the position is real, it will be normalized and TRUE will be returned.
952 If the position is unreal, it will be left unchanged and FALSE will be
953 returned.
954
955 Note, we need to leave x and y with sane values even in the unreal case.
956 Some callers may for instance call nearest_real_pos on these values.
957 **************************************************************************/
normalize_map_pos(int * x,int * y)958 bool normalize_map_pos(int *x, int *y)
959 {
960 struct tile *ptile = map_pos_to_tile(*x, *y);
961
962 if (ptile) {
963 index_to_map_pos(x, y, tile_index(ptile));
964 return TRUE;
965 } else {
966 return FALSE;
967 }
968 }
969
970 /**************************************************************************
971 Twiddle *x and *y to point the the nearest real tile, and ensure that the
972 position is normalized.
973 **************************************************************************/
nearest_real_tile(int x,int y)974 struct tile *nearest_real_tile(int x, int y)
975 {
976 int nat_x, nat_y;
977
978 MAP_TO_NATIVE_POS(&nat_x, &nat_y, x, y);
979 if (!current_topo_has_flag(TF_WRAPX)) {
980 nat_x = CLIP(0, nat_x, game.map.xsize - 1);
981 }
982 if (!current_topo_has_flag(TF_WRAPY)) {
983 nat_y = CLIP(0, nat_y, game.map.ysize - 1);
984 }
985 NATIVE_TO_MAP_POS(&x, &y, nat_x, nat_y);
986
987 return map_pos_to_tile(x, y);
988 }
989
990 /**************************************************************************
991 Returns the total number of (real) positions (or tiles) on the map.
992 **************************************************************************/
map_num_tiles(void)993 int map_num_tiles(void)
994 {
995 return game.map.xsize * game.map.ysize;
996 }
997
998 /****************************************************************************
999 Finds the difference between the two (unnormalized) positions, in
1000 cartesian (map) coordinates. Most callers should use map_distance_vector
1001 instead.
1002 ****************************************************************************/
base_map_distance_vector(int * dx,int * dy,int x0dv,int y0dv,int x1dv,int y1dv)1003 void base_map_distance_vector(int *dx, int *dy,
1004 int x0dv, int y0dv, int x1dv, int y1dv)
1005 {
1006 if (current_topo_has_flag(TF_WRAPX) || current_topo_has_flag(TF_WRAPY)) {
1007 /* Wrapping is done in native coordinates. */
1008 MAP_TO_NATIVE_POS(&x0dv, &y0dv, x0dv, y0dv);
1009 MAP_TO_NATIVE_POS(&x1dv, &y1dv, x1dv, y1dv);
1010
1011 /* Find the "native" distance vector. This corresponds closely to the
1012 * map distance vector but is easier to wrap. */
1013 *dx = x1dv - x0dv;
1014 *dy = y1dv - y0dv;
1015 if (current_topo_has_flag(TF_WRAPX)) {
1016 /* Wrap dx to be in [-map.xsize/2, map.xsize/2). */
1017 *dx = FC_WRAP(*dx + game.map.xsize / 2, game.map.xsize) - game.map.xsize / 2;
1018 }
1019 if (current_topo_has_flag(TF_WRAPY)) {
1020 /* Wrap dy to be in [-map.ysize/2, map.ysize/2). */
1021 *dy = FC_WRAP(*dy + game.map.ysize / 2, game.map.ysize) - game.map.ysize / 2;
1022 }
1023
1024 /* Convert the native delta vector back to a pair of map positions. */
1025 x1dv = x0dv + *dx;
1026 y1dv = y0dv + *dy;
1027 NATIVE_TO_MAP_POS(&x0dv, &y0dv, x0dv, y0dv);
1028 NATIVE_TO_MAP_POS(&x1dv, &y1dv, x1dv, y1dv);
1029 }
1030
1031 /* Find the final (map) vector. */
1032 *dx = x1dv - x0dv;
1033 *dy = y1dv - y0dv;
1034 }
1035
1036 /****************************************************************************
1037 Topology function to find the vector which has the minimum "real"
1038 distance between the map positions (x0, y0) and (x1, y1). If there is
1039 more than one vector with equal distance, no guarantee is made about
1040 which is found.
1041
1042 Real distance is defined as the larger of the distances in the x and y
1043 direction; since units can travel diagonally this is the "real" distance
1044 a unit has to travel to get from point to point.
1045
1046 (See also: real_map_distance, map_distance, and sq_map_distance.)
1047
1048 With the standard topology the ranges of the return value are:
1049 -map.xsize/2 <= dx <= map.xsize/2
1050 -map.ysize < dy < map.ysize
1051 ****************************************************************************/
map_distance_vector(int * dx,int * dy,const struct tile * tile0,const struct tile * tile1)1052 void map_distance_vector(int *dx, int *dy,
1053 const struct tile *tile0,
1054 const struct tile *tile1)
1055 {
1056 int tx0, ty0, tx1, ty1;
1057
1058 index_to_map_pos(&tx0, &ty0, tile_index(tile0));
1059 index_to_map_pos(&tx1, &ty1, tile_index(tile1));
1060 base_map_distance_vector(dx, dy, tx0, ty0, tx1, ty1);
1061 }
1062
1063 /**************************************************************************
1064 Random neighbouring square.
1065 **************************************************************************/
rand_neighbour(const struct tile * ptile)1066 struct tile *rand_neighbour(const struct tile *ptile)
1067 {
1068 int n;
1069 struct tile *tile1;
1070
1071 /*
1072 * list of all 8 directions
1073 */
1074 enum direction8 dirs[8] = {
1075 DIR8_NORTHWEST, DIR8_NORTH, DIR8_NORTHEAST, DIR8_WEST, DIR8_EAST,
1076 DIR8_SOUTHWEST, DIR8_SOUTH, DIR8_SOUTHEAST
1077 };
1078
1079 /* This clever loop by Trent Piepho will take no more than
1080 * 8 tries to find a valid direction. */
1081 for (n = 8; n > 0; n--) {
1082 enum direction8 choice = (enum direction8) fc_rand(n);
1083
1084 /* this neighbour's OK */
1085 tile1 = mapstep(ptile, dirs[choice]);
1086 if (tile1) {
1087 return tile1;
1088 }
1089
1090 /* Choice was bad, so replace it with the last direction in the list.
1091 * On the next iteration, one fewer choices will remain. */
1092 dirs[choice] = dirs[n - 1];
1093 }
1094
1095 fc_assert(FALSE); /* Are we on a 1x1 map with no wrapping??? */
1096 return NULL;
1097 }
1098
1099 /**************************************************************************
1100 Random square anywhere on the map. Only normal positions (for which
1101 is_normal_map_pos returns true) will be found.
1102 **************************************************************************/
rand_map_pos(void)1103 struct tile *rand_map_pos(void)
1104 {
1105 int nat_x = fc_rand(game.map.xsize), nat_y = fc_rand(game.map.ysize);
1106
1107 return native_pos_to_tile(nat_x, nat_y);
1108 }
1109
1110 /**************************************************************************
1111 Give a random tile anywhere on the map for which the 'filter' function
1112 returns TRUE. Return FALSE if none can be found. The filter may be
1113 NULL if any position is okay; if non-NULL it shouldn't have any side
1114 effects.
1115 **************************************************************************/
rand_map_pos_filtered(void * data,bool (* filter)(const struct tile * ptile,const void * data))1116 struct tile *rand_map_pos_filtered(void *data,
1117 bool (*filter)(const struct tile *ptile,
1118 const void *data))
1119 {
1120 struct tile *ptile;
1121 int tries = 0;
1122 const int max_tries = MAP_INDEX_SIZE / ACTIVITY_FACTOR;
1123
1124 /* First do a few quick checks to find a spot. The limit on number of
1125 * tries could use some tweaking. */
1126 do {
1127 ptile = game.map.tiles + fc_rand(MAP_INDEX_SIZE);
1128 } while (filter && !filter(ptile, data) && ++tries < max_tries);
1129
1130 /* If that fails, count all available spots and pick one.
1131 * Slow but reliable. */
1132 if (tries == max_tries) {
1133 int count = 0, *positions;
1134
1135 positions = fc_calloc(MAP_INDEX_SIZE, sizeof(*positions));
1136
1137 whole_map_iterate(check_tile) {
1138 if (filter(check_tile, data)) {
1139 positions[count] = tile_index(check_tile);
1140 count++;
1141 }
1142 } whole_map_iterate_end;
1143
1144 if (count == 0) {
1145 ptile = NULL;
1146 } else {
1147 ptile = game.map.tiles + positions[fc_rand(count)];
1148 }
1149
1150 FC_FREE(positions);
1151 }
1152 return ptile;
1153 }
1154
1155 /**************************************************************************
1156 Return the debugging name of the direction.
1157 **************************************************************************/
dir_get_name(enum direction8 dir)1158 const char *dir_get_name(enum direction8 dir)
1159 {
1160 /* a switch statement is used so the ordering can be changed easily */
1161 switch (dir) {
1162 case DIR8_NORTH:
1163 return "N";
1164 case DIR8_NORTHEAST:
1165 return "NE";
1166 case DIR8_EAST:
1167 return "E";
1168 case DIR8_SOUTHEAST:
1169 return "SE";
1170 case DIR8_SOUTH:
1171 return "S";
1172 case DIR8_SOUTHWEST:
1173 return "SW";
1174 case DIR8_WEST:
1175 return "W";
1176 case DIR8_NORTHWEST:
1177 return "NW";
1178 default:
1179 return "[Undef]";
1180 }
1181 }
1182
1183 /**************************************************************************
1184 Returns the next direction clock-wise.
1185 **************************************************************************/
dir_cw(enum direction8 dir)1186 enum direction8 dir_cw(enum direction8 dir)
1187 {
1188 /* a switch statement is used so the ordering can be changed easily */
1189 switch (dir) {
1190 case DIR8_NORTH:
1191 return DIR8_NORTHEAST;
1192 case DIR8_NORTHEAST:
1193 return DIR8_EAST;
1194 case DIR8_EAST:
1195 return DIR8_SOUTHEAST;
1196 case DIR8_SOUTHEAST:
1197 return DIR8_SOUTH;
1198 case DIR8_SOUTH:
1199 return DIR8_SOUTHWEST;
1200 case DIR8_SOUTHWEST:
1201 return DIR8_WEST;
1202 case DIR8_WEST:
1203 return DIR8_NORTHWEST;
1204 case DIR8_NORTHWEST:
1205 return DIR8_NORTH;
1206 default:
1207 fc_assert(FALSE);
1208 return -1;
1209 }
1210 }
1211
1212 /**************************************************************************
1213 Returns the next direction counter-clock-wise.
1214 **************************************************************************/
dir_ccw(enum direction8 dir)1215 enum direction8 dir_ccw(enum direction8 dir)
1216 {
1217 /* a switch statement is used so the ordering can be changed easily */
1218 switch (dir) {
1219 case DIR8_NORTH:
1220 return DIR8_NORTHWEST;
1221 case DIR8_NORTHEAST:
1222 return DIR8_NORTH;
1223 case DIR8_EAST:
1224 return DIR8_NORTHEAST;
1225 case DIR8_SOUTHEAST:
1226 return DIR8_EAST;
1227 case DIR8_SOUTH:
1228 return DIR8_SOUTHEAST;
1229 case DIR8_SOUTHWEST:
1230 return DIR8_SOUTH;
1231 case DIR8_WEST:
1232 return DIR8_SOUTHWEST;
1233 case DIR8_NORTHWEST:
1234 return DIR8_WEST;
1235 default:
1236 fc_assert(FALSE);
1237 return -1;
1238 }
1239 }
1240
1241 /**************************************************************************
1242 Returns TRUE iff the given direction is a valid one. Does not use
1243 value from the cache, but can be used to calculate the cache.
1244 **************************************************************************/
is_valid_dir_calculate(enum direction8 dir)1245 static bool is_valid_dir_calculate(enum direction8 dir)
1246 {
1247 switch (dir) {
1248 case DIR8_SOUTHEAST:
1249 case DIR8_NORTHWEST:
1250 /* These directions are invalid in hex topologies. */
1251 return !(current_topo_has_flag(TF_HEX) && !current_topo_has_flag(TF_ISO));
1252 case DIR8_NORTHEAST:
1253 case DIR8_SOUTHWEST:
1254 /* These directions are invalid in iso-hex topologies. */
1255 return !(current_topo_has_flag(TF_HEX) && current_topo_has_flag(TF_ISO));
1256 case DIR8_NORTH:
1257 case DIR8_EAST:
1258 case DIR8_SOUTH:
1259 case DIR8_WEST:
1260 return TRUE;
1261 default:
1262 return FALSE;
1263 }
1264 }
1265
1266 /**************************************************************************
1267 Returns TRUE iff the given direction is a valid one.
1268
1269 If the direction could be out of range you should use
1270 map_untrusted_dir_is_valid() in stead.
1271 **************************************************************************/
is_valid_dir(enum direction8 dir)1272 bool is_valid_dir(enum direction8 dir)
1273 {
1274 fc_assert_ret_val(dir <= direction8_invalid(), FALSE);
1275
1276 return dir_validity[dir];
1277 }
1278
1279 /**************************************************************************
1280 Returns TRUE iff the given direction is a valid one.
1281
1282 Doesn't trust the input. Can be used to validate a direction from an
1283 untrusted source.
1284 **************************************************************************/
map_untrusted_dir_is_valid(enum direction8 dir)1285 bool map_untrusted_dir_is_valid(enum direction8 dir)
1286 {
1287 if (!direction8_is_valid(dir)) {
1288 /* Isn't even in range of direction8. */
1289 return FALSE;
1290 }
1291
1292 return is_valid_dir(dir);
1293 }
1294
1295 /**************************************************************************
1296 Returns TRUE iff the given direction is a cardinal one. Does not use
1297 value from the cache, but can be used to calculate the cache.
1298
1299 Cardinal directions are those in which adjacent tiles share an edge not
1300 just a vertex.
1301 **************************************************************************/
is_cardinal_dir_calculate(enum direction8 dir)1302 static bool is_cardinal_dir_calculate(enum direction8 dir)
1303 {
1304 switch (dir) {
1305 case DIR8_NORTH:
1306 case DIR8_SOUTH:
1307 case DIR8_EAST:
1308 case DIR8_WEST:
1309 return TRUE;
1310 case DIR8_SOUTHEAST:
1311 case DIR8_NORTHWEST:
1312 /* These directions are cardinal in iso-hex topologies. */
1313 return current_topo_has_flag(TF_HEX) && current_topo_has_flag(TF_ISO);
1314 case DIR8_NORTHEAST:
1315 case DIR8_SOUTHWEST:
1316 /* These directions are cardinal in hexagonal topologies. */
1317 return current_topo_has_flag(TF_HEX) && !current_topo_has_flag(TF_ISO);
1318 }
1319 return FALSE;
1320 }
1321
1322 /**************************************************************************
1323 Returns TRUE iff the given direction is a cardinal one.
1324
1325 Cardinal directions are those in which adjacent tiles share an edge not
1326 just a vertex.
1327 **************************************************************************/
is_cardinal_dir(enum direction8 dir)1328 bool is_cardinal_dir(enum direction8 dir)
1329 {
1330 fc_assert_ret_val(dir <= direction8_invalid(), FALSE);
1331
1332 return dir_cardinality[dir];
1333 }
1334
1335 /**************************************************************************
1336 Return true and sets dir to the direction of the step if (end_x,
1337 end_y) can be reached from (start_x, start_y) in one step. Return
1338 false otherwise (value of dir is unchanged in this case).
1339 **************************************************************************/
base_get_direction_for_step(const struct tile * start_tile,const struct tile * end_tile,enum direction8 * dir)1340 bool base_get_direction_for_step(const struct tile *start_tile,
1341 const struct tile *end_tile,
1342 enum direction8 *dir)
1343 {
1344 adjc_dir_iterate(start_tile, test_tile, test_dir) {
1345 if (same_pos(end_tile, test_tile)) {
1346 *dir = test_dir;
1347 return TRUE;
1348 }
1349 } adjc_dir_iterate_end;
1350
1351 return FALSE;
1352 }
1353
1354 /**************************************************************************
1355 Return the direction which is needed for a step on the map from
1356 (start_x, start_y) to (end_x, end_y).
1357 **************************************************************************/
get_direction_for_step(const struct tile * start_tile,const struct tile * end_tile)1358 int get_direction_for_step(const struct tile *start_tile,
1359 const struct tile *end_tile)
1360 {
1361 enum direction8 dir;
1362
1363 if (base_get_direction_for_step(start_tile, end_tile, &dir)) {
1364 return dir;
1365 }
1366
1367 fc_assert(FALSE);
1368 return -1;
1369 }
1370
1371 /**************************************************************************
1372 Returns TRUE iff the move from the position (start_x,start_y) to
1373 (end_x,end_y) is a cardinal one.
1374 **************************************************************************/
is_move_cardinal(const struct tile * start_tile,const struct tile * end_tile)1375 bool is_move_cardinal(const struct tile *start_tile,
1376 const struct tile *end_tile)
1377 {
1378 cardinal_adjc_dir_iterate(start_tile, test_tile, test_dir) {
1379 if (same_pos(end_tile, test_tile)) {
1380 return TRUE;
1381 }
1382 } cardinal_adjc_dir_iterate_end;
1383
1384 return FALSE;
1385 }
1386
1387 /****************************************************************************
1388 A "SINGULAR" position is any map position that has an abnormal number of
1389 tiles in the radius of dist.
1390
1391 (map_x, map_y) must be normalized.
1392
1393 dist is the "real" map distance.
1394 ****************************************************************************/
is_singular_tile(const struct tile * ptile,int dist)1395 bool is_singular_tile(const struct tile *ptile, int dist)
1396 {
1397 int tile_x, tile_y;
1398
1399 index_to_map_pos(&tile_x, &tile_y, tile_index(ptile));
1400 do_in_natural_pos(ntl_x, ntl_y, tile_x, tile_y) {
1401 /* Iso-natural coordinates are doubled in scale. */
1402 dist *= MAP_IS_ISOMETRIC ? 2 : 1;
1403
1404 return ((!current_topo_has_flag(TF_WRAPX)
1405 && (ntl_x < dist || ntl_x >= NATURAL_WIDTH - dist))
1406 || (!current_topo_has_flag(TF_WRAPY)
1407 && (ntl_y < dist || ntl_y >= NATURAL_HEIGHT - dist)));
1408 } do_in_natural_pos_end;
1409 }
1410
1411
1412 /****************************************************************************
1413 Create a new, empty start position.
1414 ****************************************************************************/
startpos_new(struct tile * ptile)1415 static struct startpos *startpos_new(struct tile *ptile)
1416 {
1417 struct startpos *psp = fc_malloc(sizeof(*psp));
1418
1419 psp->location = ptile;
1420 psp->exclude = FALSE;
1421 psp->nations = nation_hash_new();
1422
1423 return psp;
1424 }
1425
1426 /****************************************************************************
1427 Free all memory allocated by the start position.
1428 ****************************************************************************/
startpos_destroy(struct startpos * psp)1429 static void startpos_destroy(struct startpos *psp)
1430 {
1431 fc_assert_ret(NULL != psp);
1432 nation_hash_destroy(psp->nations);
1433 free(psp);
1434 }
1435
1436 /****************************************************************************
1437 Returns the start position associated to the given ID.
1438 ****************************************************************************/
map_startpos_by_number(int id)1439 struct startpos *map_startpos_by_number(int id)
1440 {
1441 return map_startpos_get(index_to_tile(id));
1442 }
1443
1444 /****************************************************************************
1445 Returns the unique ID number for this start position. This is just the
1446 tile index of the tile where this start position is located.
1447 ****************************************************************************/
startpos_number(const struct startpos * psp)1448 int startpos_number(const struct startpos *psp)
1449 {
1450 fc_assert_ret_val(NULL != psp, -1);
1451 return tile_index(psp->location);
1452 }
1453
1454 /****************************************************************************
1455 Allow the nation to start at the start position.
1456 NB: in "excluding" mode, this remove the nation from the excluded list.
1457 ****************************************************************************/
startpos_allow(struct startpos * psp,struct nation_type * pnation)1458 bool startpos_allow(struct startpos *psp, struct nation_type *pnation)
1459 {
1460 fc_assert_ret_val(NULL != psp, FALSE);
1461 fc_assert_ret_val(NULL != pnation, FALSE);
1462
1463 if (0 == nation_hash_size(psp->nations) || !psp->exclude) {
1464 psp->exclude = FALSE; /* Disable "excluding" mode. */
1465 return nation_hash_insert(psp->nations, pnation, NULL);
1466 } else {
1467 return nation_hash_remove(psp->nations, pnation);
1468 }
1469 }
1470
1471 /****************************************************************************
1472 Disallow the nation to start at the start position.
1473 NB: in "excluding" mode, this add the nation to the excluded list.
1474 ****************************************************************************/
startpos_disallow(struct startpos * psp,struct nation_type * pnation)1475 bool startpos_disallow(struct startpos *psp, struct nation_type *pnation)
1476 {
1477 fc_assert_ret_val(NULL != psp, FALSE);
1478 fc_assert_ret_val(NULL != pnation, FALSE);
1479
1480 if (0 == nation_hash_size(psp->nations) || psp->exclude) {
1481 psp->exclude = TRUE; /* Enable "excluding" mode. */
1482 return nation_hash_remove(psp->nations, pnation);
1483 } else {
1484 return nation_hash_insert(psp->nations, pnation, NULL);
1485 }
1486 }
1487
1488 /****************************************************************************
1489 Returns the tile where this start position is located.
1490 ****************************************************************************/
startpos_tile(const struct startpos * psp)1491 struct tile *startpos_tile(const struct startpos *psp)
1492 {
1493 fc_assert_ret_val(NULL != psp, NULL);
1494 return psp->location;
1495 }
1496
1497 /****************************************************************************
1498 Returns TRUE if the given nation can start here.
1499 ****************************************************************************/
startpos_nation_allowed(const struct startpos * psp,const struct nation_type * pnation)1500 bool startpos_nation_allowed(const struct startpos *psp,
1501 const struct nation_type *pnation)
1502 {
1503 fc_assert_ret_val(NULL != psp, FALSE);
1504 fc_assert_ret_val(NULL != pnation, FALSE);
1505 return XOR(psp->exclude, nation_hash_lookup(psp->nations, pnation, NULL));
1506 }
1507
1508 /****************************************************************************
1509 Returns TRUE if any nation can start here.
1510 ****************************************************************************/
startpos_allows_all(const struct startpos * psp)1511 bool startpos_allows_all(const struct startpos *psp)
1512 {
1513 fc_assert_ret_val(NULL != psp, FALSE);
1514 return (0 == nation_hash_size(psp->nations));
1515 }
1516
1517 /****************************************************************************
1518 Fills the packet with all of the information at this start position.
1519 Returns TRUE if the packet can be sent.
1520 ****************************************************************************/
startpos_pack(const struct startpos * psp,struct packet_edit_startpos_full * packet)1521 bool startpos_pack(const struct startpos *psp,
1522 struct packet_edit_startpos_full *packet)
1523 {
1524 fc_assert_ret_val(NULL != psp, FALSE);
1525 fc_assert_ret_val(NULL != packet, FALSE);
1526
1527 packet->id = startpos_number(psp);
1528 packet->exclude = psp->exclude;
1529 BV_CLR_ALL(packet->nations);
1530
1531 nation_hash_iterate(psp->nations, pnation) {
1532 BV_SET(packet->nations, nation_number(pnation));
1533 } nation_hash_iterate_end;
1534 return TRUE;
1535 }
1536
1537 /****************************************************************************
1538 Fills the start position with the nation information in the packet.
1539 Returns TRUE if the start position was changed.
1540 ****************************************************************************/
startpos_unpack(struct startpos * psp,const struct packet_edit_startpos_full * packet)1541 bool startpos_unpack(struct startpos *psp,
1542 const struct packet_edit_startpos_full *packet)
1543 {
1544 fc_assert_ret_val(NULL != psp, FALSE);
1545 fc_assert_ret_val(NULL != packet, FALSE);
1546
1547 psp->exclude = packet->exclude;
1548
1549 nation_hash_clear(psp->nations);
1550 if (!BV_ISSET_ANY(packet->nations)) {
1551 return TRUE;
1552 }
1553 nations_iterate(pnation) {
1554 if (BV_ISSET(packet->nations, nation_number(pnation))) {
1555 nation_hash_insert(psp->nations, pnation, NULL);
1556 }
1557 } nations_iterate_end;
1558 return TRUE;
1559 }
1560
1561 /****************************************************************************
1562 Returns TRUE if the nations returned by startpos_raw_nations()
1563 are actually excluded from the nations allowed to start at this position.
1564
1565 FIXME: This function exposes the internal implementation and should be
1566 removed when no longer needed by the property editor system.
1567 ****************************************************************************/
startpos_is_excluding(const struct startpos * psp)1568 bool startpos_is_excluding(const struct startpos *psp)
1569 {
1570 fc_assert_ret_val(NULL != psp, FALSE);
1571 return psp->exclude;
1572 }
1573
1574 /****************************************************************************
1575 Return a the nations hash, used for the property editor.
1576
1577 FIXME: This function exposes the internal implementation and should be
1578 removed when no longer needed by the property editor system.
1579 ****************************************************************************/
startpos_raw_nations(const struct startpos * psp)1580 const struct nation_hash *startpos_raw_nations(const struct startpos *psp)
1581 {
1582 fc_assert_ret_val(NULL != psp, FALSE);
1583 return psp->nations;
1584 }
1585
1586 /****************************************************************************
1587 Implementation of iterator 'sizeof' function.
1588
1589 struct startpos_iter can be either a 'struct nation_hash_iter', a 'struct
1590 nation_iter' or 'struct startpos_iter'.
1591 ****************************************************************************/
startpos_iter_sizeof(void)1592 size_t startpos_iter_sizeof(void)
1593 {
1594 return MAX(sizeof(struct startpos_iter) + nation_iter_sizeof()
1595 - sizeof(struct iterator), nation_hash_iter_sizeof());
1596 }
1597
1598 /****************************************************************************
1599 Implementation of iterator 'next' function.
1600
1601 NB: This is only used for the case where 'exclude' is set in the start
1602 position.
1603 ****************************************************************************/
startpos_exclude_iter_next(struct iterator * startpos_iter)1604 static void startpos_exclude_iter_next(struct iterator *startpos_iter)
1605 {
1606 struct startpos_iter *iter = STARTPOS_ITER(startpos_iter);
1607
1608 do {
1609 iterator_next(&iter->nation_iter);
1610 } while (iterator_valid(&iter->nation_iter)
1611 || !nation_hash_lookup(iter->psp->nations,
1612 iterator_get(&iter->nation_iter), NULL));
1613 }
1614
1615 /****************************************************************************
1616 Implementation of iterator 'get' function. Returns a struct nation_type
1617 pointer.
1618
1619 NB: This is only used for the case where 'exclude' is set in the start
1620 position.
1621 ****************************************************************************/
startpos_exclude_iter_get(const struct iterator * startpos_iter)1622 static void *startpos_exclude_iter_get(const struct iterator *startpos_iter)
1623 {
1624 struct startpos_iter *iter = STARTPOS_ITER(startpos_iter);
1625 return iterator_get(&iter->nation_iter);
1626 }
1627
1628 /****************************************************************************
1629 Implementation of iterator 'valid' function.
1630 ****************************************************************************/
startpos_exclude_iter_valid(const struct iterator * startpos_iter)1631 static bool startpos_exclude_iter_valid(const struct iterator *startpos_iter)
1632 {
1633 struct startpos_iter *iter = STARTPOS_ITER(startpos_iter);
1634 return iterator_valid(&iter->nation_iter);
1635 }
1636
1637 /****************************************************************************
1638 Initialize and return an iterator for the nations at this start position.
1639 ****************************************************************************/
startpos_iter_init(struct startpos_iter * iter,const struct startpos * psp)1640 struct iterator *startpos_iter_init(struct startpos_iter *iter,
1641 const struct startpos *psp)
1642 {
1643 if (!psp) {
1644 return invalid_iter_init(ITERATOR(iter));
1645 }
1646
1647 if (startpos_allows_all(psp)) {
1648 return nation_iter_init((struct nation_iter *) iter);
1649 }
1650
1651 if (!psp->exclude) {
1652 return nation_hash_key_iter_init((struct nation_hash_iter *) iter,
1653 psp->nations);
1654 }
1655
1656 iter->vtable.next = startpos_exclude_iter_next;
1657 iter->vtable.get = startpos_exclude_iter_get;
1658 iter->vtable.valid = startpos_exclude_iter_valid;
1659 iter->psp = psp;
1660 (void) nation_iter_init((struct nation_iter *) &iter->nation_iter);
1661
1662 return ITERATOR(iter);
1663 }
1664
1665
1666 /****************************************************************************
1667 Is there start positions set for map
1668 ****************************************************************************/
map_startpos_count(void)1669 int map_startpos_count(void)
1670 {
1671 if (NULL != game.map.startpos_table) {
1672 return startpos_hash_size(game.map.startpos_table);
1673 } else {
1674 return 0;
1675 }
1676 }
1677
1678 /****************************************************************************
1679 Create a new start position at the given tile and return it. If a start
1680 position already exists there, it is first removed.
1681 ****************************************************************************/
map_startpos_new(struct tile * ptile)1682 struct startpos *map_startpos_new(struct tile *ptile)
1683 {
1684 struct startpos *psp;
1685
1686 fc_assert_ret_val(NULL != ptile, NULL);
1687 fc_assert_ret_val(NULL != game.map.startpos_table, NULL);
1688
1689 psp = startpos_new(ptile);
1690 startpos_hash_replace(game.map.startpos_table, tile_hash_key(ptile), psp);
1691
1692 return psp;
1693 }
1694
1695 /****************************************************************************
1696 Returns the start position at the given tile, or NULL if none exists
1697 there.
1698 ****************************************************************************/
map_startpos_get(const struct tile * ptile)1699 struct startpos *map_startpos_get(const struct tile *ptile)
1700 {
1701 struct startpos *psp;
1702
1703 fc_assert_ret_val(NULL != ptile, NULL);
1704 fc_assert_ret_val(NULL != game.map.startpos_table, NULL);
1705
1706 startpos_hash_lookup(game.map.startpos_table, tile_hash_key(ptile), &psp);
1707
1708 return psp;
1709 }
1710
1711 /****************************************************************************
1712 Remove the start position at the given tile. Returns TRUE if the start
1713 position was removed.
1714 ****************************************************************************/
map_startpos_remove(struct tile * ptile)1715 bool map_startpos_remove(struct tile *ptile)
1716 {
1717 fc_assert_ret_val(NULL != ptile, FALSE);
1718 fc_assert_ret_val(NULL != game.map.startpos_table, FALSE);
1719
1720 return startpos_hash_remove(game.map.startpos_table, tile_hash_key(ptile));
1721 }
1722
1723 /****************************************************************************
1724 Implementation of iterator sizeof function.
1725 NB: map_sp_iter just wraps startpos_hash_iter.
1726 ****************************************************************************/
map_startpos_iter_sizeof(void)1727 size_t map_startpos_iter_sizeof(void)
1728 {
1729 return startpos_hash_iter_sizeof();
1730 }
1731
1732 /****************************************************************************
1733 Implementation of iterator init function.
1734 NB: map_sp_iter just wraps startpos_hash_iter.
1735 ****************************************************************************/
map_startpos_iter_init(struct map_startpos_iter * iter)1736 struct iterator *map_startpos_iter_init(struct map_startpos_iter *iter)
1737 {
1738 return startpos_hash_value_iter_init((struct startpos_hash_iter *) iter,
1739 game.map.startpos_table);
1740 }
1741
1742 /****************************************************************************
1743 Return random direction that is valid in current map.
1744 ****************************************************************************/
rand_direction(void)1745 enum direction8 rand_direction(void)
1746 {
1747 return game.map.valid_dirs[fc_rand(game.map.num_valid_dirs)];
1748 }
1749
1750
1751 /****************************************************************************
1752 Return direction that is opposite to given one.
1753 ****************************************************************************/
opposite_direction(enum direction8 dir)1754 enum direction8 opposite_direction(enum direction8 dir)
1755 {
1756 return direction8_max() - dir;
1757 }
1758