Freeciv-3.3
Loading...
Searching...
No Matches
mapgen_utils.c
Go to the documentation of this file.
1/***********************************************************************
2 Freeciv - Copyright (C) 2004 - Marcelo J. Burda
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#ifdef HAVE_CONFIG_H
14#include <fc_config.h>
15#endif
16
17/* utility */
18#include "fcintl.h"
19#include "log.h"
20#include "rand.h"
21#include "support.h" /* bool type */
22
23/* common */
24#include "map.h"
25#include "packets.h"
26#include "terrain.h"
27#include "tile.h"
28
29#include "mapgen_utils.h"
30
31/**************************************************************************
32 Map that contains, according to circumstances, information on whether
33 we have already placed terrain (special, hut) here.
34**************************************************************************/
35static bool *placed_map;
36
37/**********************************************************************/
41{
42 return placed_map != NULL;
43}
44
45/**********************************************************************/
54
55/**********************************************************************/
64
65
66#define pmap(_tile) (placed_map[tile_index(_tile)])
67
68/**********************************************************************/
71bool not_placed(const struct tile *ptile)
72{
73 return !pmap(ptile);
74}
75
76/**********************************************************************/
79void map_set_placed(struct tile *ptile)
80{
81 pmap(ptile) = TRUE;
82}
83
84/**********************************************************************/
87void map_unset_placed(struct tile *ptile)
88{
89 pmap(ptile) = FALSE;
90}
91
92/**********************************************************************/
96{
97 whole_map_iterate(&(wld.map), ptile) {
98 if (is_ocean_tile(ptile)) {
99 map_set_placed(ptile);
100 }
102}
103
104/**********************************************************************/
107void set_placed_near_pos(struct tile *ptile, int dist)
108{
109 square_iterate(&(wld.map), ptile, dist, tile1) {
112}
113
114/**********************************************************************/
124 int int_map_max, void *data,
125 bool (*filter)(const struct tile *ptile,
126 const void *data))
127{
129 int minval = 0, maxval = 0, total = 0;
130 bool first = TRUE;
131
132 /* Determine minimum and maximum value. */
133 whole_map_iterate_filtered(ptile, data, filter) {
134 if (first) {
135 minval = int_map[tile_index(ptile)];
136 maxval = int_map[tile_index(ptile)];
137 } else {
138 maxval = MAX(maxval, int_map[tile_index(ptile)]);
139 minval = MIN(minval, int_map[tile_index(ptile)]);
140 }
141 first = FALSE;
142 total++;
144
145 if (total == 0) {
146 return;
147 }
148
149 {
150 int const size = 1 + maxval - minval;
151 int i, count = 0, frequencies[size];
152
154
155 /* Translate value so the minimum value is 0
156 and count the number of occurrences of all values to initialize the
157 frequencies[] */
158 whole_map_iterate_filtered(ptile, data, filter) {
159 int_map[tile_index(ptile)] -= minval;
160 frequencies[int_map[tile_index(ptile)]]++;
162
163 /* create the linearize function as "incremental" frequencies */
164 for (i = 0; i < size; i++) {
165 count += frequencies[i];
166 frequencies[i] = int_map_min + (count * int_map_delta) / total;
167 }
168
169 /* apply the linearize function */
170 whole_map_iterate_filtered(ptile, data, filter) {
173 }
174}
175
176/**********************************************************************/
179bool is_normal_nat_pos(int x, int y)
180{
181 NATIVE_TO_MAP_POS(&x, &y, x, y);
182 return is_normal_map_pos(x, y);
183}
184
185/**********************************************************************/
192{
193 static const float weight_standard[5] = { 0.13, 0.19, 0.37, 0.19, 0.13 };
194 static const float weight_isometric[5] = { 0.15, 0.21, 0.29, 0.21, 0.15 };
195 const float *weight;
196 bool axe = TRUE;
197 int *target_map, *source_map;
199
201
202 weight = weight_standard;
205
206 do {
207 whole_map_iterate(&(wld.map), ptile) {
208 float N = 0, D = 0;
209
210 axis_iterate(&(wld.map), ptile, pnear, i, 2, axe) {
211 D += weight[i + 2];
212 N += weight[i + 2] * source_map[tile_index(pnear)];
214 if (zeroes_at_edges) {
215 D = 1;
216 }
217 target_map[tile_index(ptile)] = (float)N / D;
219
220 if (MAP_IS_ISOMETRIC) {
221 weight = weight_isometric;
222 }
223
224 axe = !axe;
225
228
229 } while (!axe);
230
232}
233
234/**********************************************************************/
237static void recalculate_surrounders(void)
238{
239 size_t size;
240
244
245 size = (wld.map.num_oceans + 1) * sizeof(*wld.map.server.lake_surrounders);
248
249 whole_map_iterate(&(wld.map), ptile) {
250 const struct terrain *pterrain = tile_terrain(ptile);
251 Continent_id cont = tile_continent(ptile);
252
253 if (T_UNKNOWN == pterrain) {
254 continue;
255 }
256
257 if (is_ocean(pterrain)) {
258 fc_assert_action(cont < 0, continue);
259 adjc_iterate(&(wld.map), ptile, adj_tile) {
261
262 if (!is_ocean_tile(adj_tile)) {
263 fc_assert_action(adj_cont > 0, continue);
266 } else if (wld.map.server.island_surrounders[adj_cont] != -cont) {
268 }
269 }
271 } else {
272 fc_assert_action(cont > 0, continue);
273 adjc_iterate(&(wld.map), ptile, adj_tile) {
275
276 if (is_ocean_tile(adj_tile)) {
277 fc_assert_action(adj_cont < 0, continue);
280 } else if (wld.map.server.lake_surrounders[-adj_cont] != cont) {
282 }
283 }
285 }
287}
288
289/**********************************************************************/
297static void assign_continent_flood(struct tile *ptile, bool is_land, int nr)
298{
299 struct tile_list *tlist = NULL;
300 const struct terrain *pterrain;
301
302 fc_assert_ret(ptile != NULL);
303
304#ifndef FREECIV_NDEBUG
305 pterrain = tile_terrain(ptile);
306#endif
307 /* Check if the initial tile is a valid tile for continent / ocean. */
308 fc_assert_ret(tile_continent(ptile) == 0
309 && T_UNKNOWN != pterrain
311
312 /* Create tile list and insert the initial tile. */
314 tile_list_append(tlist, ptile);
315
316 while (tile_list_size(tlist) > 0) {
317 struct tile *ptile2 = tile_list_get(tlist, 0);
318
319 /* Iterate over the adjacent tiles. */
321 pterrain = tile_terrain(ptile3);
322
323 /* Check if it is a valid tile for continent / ocean. */
324 if (tile_continent(ptile3) != 0
325 || T_UNKNOWN == pterrain
326 || !XOR(is_land, terrain_type_terrain_class(pterrain) == TC_OCEAN)) {
327 continue;
328 }
329
330 /* Add the tile to the list of tiles to check. */
333 }
335
336 /* Set the continent data and remove the tile from the list. */
339
340 /* Count the tile */
341 if (nr < 0) {
342 wld.map.ocean_sizes[-nr]++;
343 } else {
345 }
346 }
347
349}
350
351/**********************************************************************/
357{
359
360 {
361 struct terrain *lakes[2][5];
362 int num_laketypes[2] = { 0, 0 };
363 int i;
364
369
372 } else {
373 log_verbose("Ruleset has more than %d %s lake types, ignoring %s",
374 (int) ARRAY_SIZE(lakes[frozen]),
375 frozen ? "frozen" : "unfrozen",
377 }
378 }
380
381 /* We don't want to generate any boundaries between fresh and
382 * non-fresh water.
383 * If there are no unfrozen lake types, just give up.
384 * Else if there are no frozen lake types, use unfrozen lake instead.
385 * If both are available, preserve frozenness of previous terrain. */
386 if (num_laketypes[0] == 0) {
387 return;
388 } else if (num_laketypes[1] == 0) {
389 for (i = 0; i < wld.map.num_oceans; i++) {
391 = lakes[0][fc_rand(num_laketypes[0])];
392 }
393 } else {
394 for (i = 0; i < wld.map.num_oceans; i++) {
395 int frozen;
396 for (frozen = 0; frozen < 2; frozen++) {
399 }
400 }
401 }
402 }
403
404 whole_map_iterate(&(wld.map), ptile) {
405 struct terrain *pterrain = tile_terrain(ptile);
407
408 if (T_UNKNOWN == pterrain) {
409 continue;
410 }
411 if (terrain_type_terrain_class(pterrain) != TC_OCEAN) {
412 continue;
413 }
414 if (0 < wld.map.server.lake_surrounders[-here]) {
415 if (terrain_control.lake_max_size >= wld.map.ocean_sizes[-here]) {
416 int frozen = terrain_has_flag(pterrain, TER_FROZEN);
418 }
419 }
421}
422
423/**********************************************************************/
432{
433 /* Initialize */
435 wld.map.num_oceans = 0;
436
437 whole_map_iterate(&(wld.map), ptile) {
438 tile_set_continent(ptile, 0);
440
441 /* Assign new numbers */
442 whole_map_iterate(&(wld.map), ptile) {
443 const struct terrain *pterrain = tile_terrain(ptile);
444
445 if (tile_continent(ptile) != 0) {
446 /* Already assigned. */
447 continue;
448 }
449
450 if (T_UNKNOWN == pterrain) {
451 continue; /* Can't assign this. */
452 }
453
454 if (terrain_type_terrain_class(pterrain) != TC_OCEAN) {
457 (wld.map.num_continents + 1) * sizeof(*wld.map.continent_sizes));
460 } else {
463 (wld.map.num_oceans + 1) * sizeof(*wld.map.ocean_sizes));
466 }
468
470
471 log_verbose("Map has %d continents and %d oceans",
473}
474
475/**********************************************************************/
480{
481 bool oceans = FALSE, frozenmatch = FALSE;
482 struct terrain *shallow = NULL;
483
488
489 if (!oceans && nonfresh) {
490 /* First ocean type seen, reset even if frozenness doesn't match */
491 oceans = TRUE;
492 shallow = pterr;
494 continue;
495 } else if (oceans && !nonfresh) {
496 /* Dismiss any step backward on freshness */
497 continue;
498 }
499 if (!frozenmatch && frozen_ok) {
500 /* Prefer terrain that matches frozenness (as long as we don't go
501 * backwards on freshness) */
503 shallow = pterr;
504 continue;
505 } else if (frozenmatch && !frozen_ok) {
506 /* Dismiss any step backward on frozenness */
507 continue;
508 }
509 if (!shallow
510 || pterr->property[MG_OCEAN_DEPTH] <
511 shallow->property[MG_OCEAN_DEPTH]) {
512 shallow = pterr;
513 }
514 }
516
517 return shallow;
518}
519
520/**********************************************************************/
525struct terrain *pick_ocean(int depth, bool frozen)
526{
527 struct terrain *best_terrain = NULL;
529
530 terrain_type_iterate(pterrain) {
531 if (terrain_type_terrain_class(pterrain) == TC_OCEAN
533 && !!frozen == terrain_has_flag(pterrain, TER_FROZEN)
534 && !terrain_has_flag(pterrain, TER_NOT_GENERATED)) {
535 int match = abs(depth - pterrain->property[MG_OCEAN_DEPTH]);
536
537 if (best_match > match) {
538 best_match = match;
539 best_terrain = pterrain;
540 }
541 }
543
544 return best_terrain;
545}
546
547/**********************************************************************/
550static int real_distance_to_land(const struct tile *ptile, int max)
551{
552 square_dxy_iterate(&(wld.map), ptile, max, atile, dx, dy) {
554 return map_vector_to_real_distance(dx, dy);
555 }
557
558 return max + 1;
559}
560
561/**********************************************************************/
565static struct terrain *most_adjacent_ocean_type(const struct tile *ptile)
566{
567 const int need = 2 * MAP_NUM_VALID_DIRS / 3;
568 int count;
569
570 terrain_type_iterate(pterrain) {
571 if (terrain_type_terrain_class(pterrain) != TC_OCEAN) {
572 continue;
573 }
574
575 count = 0;
576 adjc_iterate(&(wld.map), ptile, atile) {
577 if (pterrain == tile_terrain(atile) && need <= ++count) {
578 return pterrain;
579 }
582
583 return NULL;
584}
585
586/**********************************************************************/
592{
593 const int OCEAN_DEPTH_STEP = 25;
594 const int OCEAN_DEPTH_RAND = 15;
596 struct terrain *ocean;
597 int dist;
598
599 /* First, improve the coasts. */
600 whole_map_iterate(&(wld.map), ptile) {
602 continue;
603 }
604
606 if (dist <= OCEAN_DIST_MAX) {
607 /* Overwrite the terrain (but preserve frozenness). */
608 ocean = pick_ocean(dist * OCEAN_DEPTH_STEP
611 if (NULL != ocean && ocean != tile_terrain(ptile)) {
612 log_debug("Replacing %s by %s at (%d, %d) "
613 "to have shallow ocean on coast.",
615 terrain_rule_name(ocean), TILE_XY(ptile));
616 tile_set_terrain(ptile, ocean);
617 }
618 }
620
621 /* Now, try to have something more continuous. */
622 whole_map_iterate(&(wld.map), ptile) {
624 continue;
625 }
626
627 ocean = most_adjacent_ocean_type(ptile);
628 if (NULL != ocean && ocean != tile_terrain(ptile)) {
629 log_debug("Replacing %s by %s at (%d, %d) "
630 "to smooth the ocean types.",
632 terrain_rule_name(ocean), TILE_XY(ptile));
633 tile_set_terrain(ptile, ocean);
634 }
636}
637
638/**********************************************************************/
642{
643}
644
645/**********************************************************************/
650{
651 bool has_flag[terrain_count()];
652 int count = 0;
653
654 terrain_type_iterate(pterrain) {
655 if ((has_flag[terrain_index(pterrain)]
656 = (terrain_has_flag(pterrain, flag)
657 && !terrain_has_flag(pterrain, TER_NOT_GENERATED)))) {
658 count++;
659 }
661
662 count = fc_rand(count);
663 terrain_type_iterate(pterrain) {
664 if (has_flag[terrain_index(pterrain)]) {
665 if (count == 0) {
666 return pterrain;
667 }
668 count--;
669 }
671
672 return T_UNKNOWN;
673}
674
675
676/**********************************************************************/
693 enum mapgen_terrain_property prefer,
694 enum mapgen_terrain_property avoid)
695{
696 int sum = 0;
697
698 /* Find the total weight. */
699 terrain_type_iterate(pterrain) {
700 if (!terrain_has_flag(pterrain, TER_NOT_GENERATED)) {
701 if (avoid != MG_UNUSED && pterrain->property[avoid] > 0) {
702 continue;
703 }
704 if (prefer != MG_UNUSED && pterrain->property[prefer] == 0) {
705 continue;
706 }
707
708 if (target != MG_UNUSED) {
709 sum += pterrain->property[target];
710 } else {
711 sum++;
712 }
713 }
715
716 /* Now pick. */
717 sum = fc_rand(sum);
718
719 /* Finally figure out which one we picked. */
720 terrain_type_iterate(pterrain) {
721 if (!terrain_has_flag(pterrain, TER_NOT_GENERATED)) {
722 int property;
723
724 if (avoid != MG_UNUSED && pterrain->property[avoid] > 0) {
725 continue;
726 }
727 if (prefer != MG_UNUSED && pterrain->property[prefer] == 0) {
728 continue;
729 }
730
731 if (target != MG_UNUSED) {
732 property = pterrain->property[target];
733 } else {
734 property = 1;
735 }
736 if (sum < property) {
737 return pterrain;
738 }
739 sum -= property;
740 }
742
743 /* This can happen with sufficient quantities of preferred and avoided
744 * characteristics. Drop a requirement and try again. */
745 if (prefer != MG_UNUSED) {
746 log_debug("pick_terrain(target: %s, [dropping prefer: %s], avoid: %s)",
750 return pick_terrain(target, MG_UNUSED, avoid);
751 } else if (avoid != MG_UNUSED) {
752 log_debug("pick_terrain(target: %s, prefer: MG_UNUSED, [dropping avoid: %s])",
755 return pick_terrain(target, prefer, MG_UNUSED);
756 } else {
757 log_debug("pick_terrain([dropping target: %s], prefer: MG_UNUSED, avoid: MG_UNUSED)",
759 return pick_terrain(MG_UNUSED, prefer, avoid);
760 }
761}
762
763/**********************************************************************/
767struct extra_type *pick_resource(const struct terrain *pterrain)
768{
769 int freq_sum = 0;
770 struct extra_type *result = NULL;
771
772 fc_assert_ret_val(NULL != pterrain, NULL);
773
775 /* This is a standard way to get a weighted random element from
776 * pterrain->resources with weights from pterrain->resource_freq,
777 * without computing its length or total weight in advance.
778 * Note that if *(pterrain->resources) == NULL,
779 * then this loop is a no-op. */
780
781 if (res->generated && freq > 0) {
782 freq_sum += freq;
783 if (freq > fc_rand(freq_sum)) {
784 result = res;
785 }
786 }
788
789 return result;
790}
char * incite_cost
Definition comments.c:76
signed short Continent_id
Definition fc_types.h:231
#define MG_UNUSED
struct world wld
Definition game.c:62
#define fc_assert_ret(condition)
Definition log.h:192
#define log_verbose(message,...)
Definition log.h:110
#define fc_assert_ret_val(condition, val)
Definition log.h:195
#define fc_assert_action(condition, action)
Definition log.h:188
#define log_debug(message,...)
Definition log.h:116
bool is_normal_map_pos(int x, int y)
Definition map.c:1099
struct terrain_misc terrain_control
Definition map.c:68
int map_vector_to_real_distance(int dx, int dy)
Definition map.c:623
#define adjc_iterate_end
Definition map.h:430
#define square_iterate(nmap, center_tile, radius, tile_itr)
Definition map.h:388
#define adjc_iterate(nmap, center_tile, itr_tile)
Definition map.h:425
#define NATIVE_TO_MAP_POS(pmap_x, pmap_y, nat_x, nat_y)
Definition map.h:170
#define square_iterate_end
Definition map.h:391
#define whole_map_iterate(_map, _tile)
Definition map.h:573
#define square_dxy_iterate(nmap, center_tile, radius, tile_itr, dx_itr, dy_itr)
Definition map.h:378
#define whole_map_iterate_end
Definition map.h:582
#define square_dxy_iterate_end
Definition map.h:381
static void recalculate_surrounders(void)
struct extra_type * pick_resource(const struct terrain *pterrain)
static struct terrain * most_adjacent_ocean_type(const struct tile *ptile)
void smooth_int_map(int *int_map, bool zeroes_at_edges)
void set_all_ocean_tiles_placed(void)
void create_placed_map(void)
static int real_distance_to_land(const struct tile *ptile, int max)
#define pmap(_tile)
static bool * placed_map
void map_set_placed(struct tile *ptile)
void destroy_placed_map(void)
void adjust_int_map_filtered(int *int_map, int int_map_min, int int_map_max, void *data, bool(*filter)(const struct tile *ptile, const void *data))
bool not_placed(const struct tile *ptile)
struct terrain * pick_terrain_by_flag(enum terrain_flag_id flag)
void assign_continent_numbers(void)
void regenerate_lakes(void)
void set_placed_near_pos(struct tile *ptile, int dist)
void generator_free(void)
void smooth_water_depth(void)
bool placed_map_is_initialized(void)
bool is_normal_nat_pos(int x, int y)
struct terrain * pick_terrain(enum mapgen_terrain_property target, enum mapgen_terrain_property prefer, enum mapgen_terrain_property avoid)
struct terrain * most_shallow_ocean(bool frozen)
struct terrain * pick_ocean(int depth, bool frozen)
static void assign_continent_flood(struct tile *ptile, bool is_land, int nr)
void map_unset_placed(struct tile *ptile)
#define whole_map_iterate_filtered(_tile, pdata, pfilter)
#define axis_iterate(nmap, center_tile, _tile, _index, dist, is_X_axis)
#define whole_map_iterate_filtered_end
#define axis_iterate_end
#define fc_calloc(n, esz)
Definition mem.h:38
#define FC_FREE(ptr)
Definition mem.h:41
#define fc_realloc(ptr, sz)
Definition mem.h:36
#define fc_malloc(sz)
Definition mem.h:34
#define fc_rand(_size)
Definition rand.h:56
#define INITIALIZE_ARRAY(array, size, value)
Definition shared.h:101
#define ARRAY_SIZE(x)
Definition shared.h:85
#define MIN(x, y)
Definition shared.h:55
#define MAX(x, y)
Definition shared.h:54
#define XOR(p, q)
Definition shared.h:71
size_t size
Definition specvec.h:72
struct sprite int int y
Definition sprite_g.h:31
struct sprite int x
Definition sprite_g.h:31
Continent_id num_continents
Definition map_types.h:83
Continent_id * island_surrounders
Definition map_types.h:132
Continent_id * lake_surrounders
Definition map_types.h:133
struct civ_map::@44::@46 server
int * continent_sizes
Definition map_types.h:92
int * ocean_sizes
Definition map_types.h:93
Continent_id num_oceans
Definition map_types.h:84
int property[MG_COUNT]
Definition terrain.h:146
Definition tile.h:50
struct civ_map map
#define TRUE
Definition support.h:46
#define FALSE
Definition support.h:47
Terrain_type_id terrain_count(void)
Definition terrain.c:118
Terrain_type_id terrain_index(const struct terrain *pterrain)
Definition terrain.c:138
const char * terrain_rule_name(const struct terrain *pterrain)
Definition terrain.c:247
enum terrain_class terrain_type_terrain_class(const struct terrain *pterrain)
Definition terrain.c:582
#define terrain_type_iterate(_p)
Definition terrain.h:266
#define T_UNKNOWN
Definition terrain.h:62
#define is_ocean(pterrain)
Definition terrain.h:194
#define is_ocean_tile(ptile)
Definition terrain.h:196
#define terrain_type_iterate_end
Definition terrain.h:272
#define TERRAIN_OCEAN_DEPTH_MAXIMUM
Definition terrain.h:148
#define terrain_has_flag(terr, flag)
Definition terrain.h:176
#define terrain_resources_iterate_end
Definition terrain.h:294
#define terrain_resources_iterate(pterrain, _res, _freq)
Definition terrain.h:285
void tile_set_terrain(struct tile *ptile, struct terrain *pterrain)
Definition tile.c:124
void tile_change_terrain(struct tile *ptile, struct terrain *pterrain)
Definition tile.c:496
void tile_set_continent(struct tile *ptile, Continent_id val)
Definition tile.c:382
#define tile_index(_pt_)
Definition tile.h:89
#define tile_terrain(_tile)
Definition tile.h:111
#define TILE_XY(ptile)
Definition tile.h:43
#define tile_continent(_tile)
Definition tile.h:93
#define MAP_NUM_VALID_DIRS
#define MAP_INDEX_SIZE
#define MAP_IS_ISOMETRIC