Freeciv-3.1: /fast/freeciv/nightly/S3_1/server/generator/mapgen_topology.c Source File

Freeciv-3.1

Loading...
Searching...
No Matches
mapgen_topology.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#include <math.h> /* sqrt */
18
19/* utility */
20#include "log.h"
21
22/* common */
23#include "game.h"
24#include "map.h"
25
26#include "mapgen_topology.h"
27
28 int ice_base_colatitude = 0 ;
29
30/************************************************************************/
38 int map_colatitude(const struct tile *ptile)
39{
40 double x, y;
41 int tile_x, tile_y;
42
43 fc_assert_ret_val(ptile != NULL, MAX_COLATITUDE / 2);
44
45 if (wld.map.server.alltemperate) {
46 /* An all-temperate map has "average" temperature everywhere.
47 *
48 * TODO: perhaps there should be a random temperature variation. */
49 return MAX_COLATITUDE / 2;
50 }
51
52
53 index_to_map_pos(&tile_x, &tile_y, tile_index(ptile));
54 do_in_natural_pos(ntl_x, ntl_y, tile_x, tile_y) {
55 if (wld.map.server.single_pole) {
56 if (!current_topo_has_flag(TF_WRAPY)) {
57 /* Partial planetary map. A polar zone is placed
58 * at the top and the equator is at the bottom. */
59 return MAX_COLATITUDE * ntl_y / (NATURAL_HEIGHT - 1);
60 }
61 if (!current_topo_has_flag(TF_WRAPX)) {
62 return MAX_COLATITUDE * ntl_x / (NATURAL_WIDTH -1);
63 }
64 }
65
66 /* Otherwise a wrapping map is assumed to be a global planetary map. */
67
68 /* we fold the map to get the base symmetries
69 *
70 * ......
71 * :c__c:
72 * :____:
73 * :____:
74 * :c__c:
75 * ......
76 *
77 * C are the corners. In all cases the 4 corners have equal temperature.
78 * So we fold the map over in both directions and determine
79 * x and y vars in the range [0.0, 1.0].
80 *
81 * ...>x
82 * :C_
83 * :__
84 * V
85 * y
86 *
87 * And now this is what we have - just one-quarter of the map.
88 */
89 x = ((ntl_x > (NATURAL_WIDTH / 2 - 1)
90 ? NATURAL_WIDTH - 1.0 - (double)ntl_x
91 : (double)ntl_x)
92 / (NATURAL_WIDTH / 2 - 1));
93 y = ((ntl_y > (NATURAL_HEIGHT / 2 - 1)
94 ? NATURAL_HEIGHT - 1.0 - (double)ntl_y
95 : (double)ntl_y)
96 / (NATURAL_HEIGHT / 2 - 1));
97 } do_in_natural_pos_end;
98
99 if (!current_topo_has_flag(TF_WRAPY)) {
100 /* In an Earth-like topology the polar zones are at north and south.
101 * This is equivalent to a Mercator projection. */
102 return MAX_COLATITUDE * y;
103 }
104
105 if (!current_topo_has_flag(TF_WRAPX) && current_topo_has_flag(TF_WRAPY)) {
106 /* In a Uranus-like topology the polar zones are at east and west.
107 * This isn't really the way Uranus is; it's the way Earth would look
108 * if you tilted your head sideways. It's still a Mercator
109 * projection. */
110 return MAX_COLATITUDE * x;
111 }
112
113 /* Otherwise we have a torus topology. We set it up as an approximation
114 * of a sphere with two circular polar zones and a square equatorial
115 * zone. In this case north and south are not constant directions on the
116 * map because we have to use a more complicated (custom) projection.
117 *
118 * Generators 2 and 5 work best if the center of the map is free. So
119 * we want to set up the map with the poles (N,S) along the sides and the
120 * equator (/,\‍) in between.
121 *
122 * ........
123 * :\ NN /:
124 * : \ / :
125 * :S \/ S:
126 * :S /\ S:
127 * : / \ :
128 * :/ NN \:
129 * ''''''''
130 */
131
132 /* Remember that we've already folded the map into fourths:
133 *
134 * ....
135 * :\ N
136 * : \
137 * :S \
138 *
139 * Now flip it along the X direction to get this:
140 *
141 * ....
142 * :N /
143 * : /
144 * :/ S
145 */
146 x = 1.0 - x;
147
148 /* Since the north and south poles are equivalent, we can fold along the
149 * diagonal. This leaves us with 1/8 of the map
150 *
151 * .....
152 * :P /
153 * : /
154 * :/
155 *
156 * where P is the polar regions and / is the equator. */
157 if (x + y > 1.0) {
158 x = 1.0 - x;
159 y = 1.0 - y;
160 }
161
162 /* This projection makes poles with a shape of a quarter-circle along
163 * "P" and the equator as a straight line along "/".
164 *
165 * The formula is
166 * lerp(1.5 (x^2 + y^2), (x+y)^2, x+y)
167 * where
168 * lerp(a,b,t) = a * (1-t) + b * t
169 * is the linear interpolation between a and b, with
170 * lerp(a,b,0) = a and lerp(a,b,1) = b
171 *
172 * I.e. the colatitude is computed as a linear interpolation between
173 * - a = 1.5 (x^2 + y^2), proportional to the squared pythagorean
174 * distance from the pole, which gives circular lines of latitude; and
175 * - b = (x+y)^2, the squared manhattan distance from the pole, which
176 * gives straight, diagonal lines of latitude parallel to the equator.
177 *
178 * These are interpolated with t = (x+y), the manhattan distance, which
179 * ranges from 0 at the pole to 1 at the equator. So near the pole, the
180 * (squared) pythagorean distance wins out, giving mostly circular lines,
181 * and near the equator, the (squared) manhattan distance wins out,
182 * giving mostly straight lines.
183 *
184 * Note that the colatitude growing with the square of the distance from
185 * the pole keeps areas relatively the same as on non-toroidal maps:
186 * On non-torus maps, the area closer to a pole than a given tile, and
187 * the colatitude at that tile, both grow linearly with distance from the
188 * pole. On torus maps, since the poles are singular points rather than
189 * entire map edges, the area closer to a pole than a given tile grows
190 * with the square of the distance to the pole - and so the colatitude
191 * at that tile must also grow with the square in order to keep the size
192 * of areas in a given range of colatitude relatively the same.
193 *
194 * See OSDN#43665, as well as the original discussion (via newsreader) at
195 * news://news.gmane.io/gmane.games.freeciv.devel/42648 */
196 return MAX_COLATITUDE * (1.5 * (x * x * y + x * y * y)
197 - 0.5 * (x * x * x + y * y * y)
198 + 1.5 * (x * x + y * y));
199}
200
201/************************************************************************/
205 bool near_singularity(const struct tile *ptile)
206{
207 return is_singular_tile(ptile, CITY_MAP_DEFAULT_RADIUS);
208}
209
210
211/************************************************************************/
215 static void set_sizes(double size, int Xratio, int Yratio)
216{
217 /* Some code in generator assumes even dimension, so this is set to 2.
218 * Future topologies may also require even dimensions. */
219 /* The generator works also for odd values; keep this here for autogenerated
220 * height and width. */
221 const int even = 2;
222
223 /* In iso-maps we need to double the map.ysize factor, since xsize is
224 * in native coordinates which are compressed 2x in the X direction. */
225 const int iso = MAP_IS_ISOMETRIC ? 2 : 1;
226
227 /* We have:
228 *
229 * 1000 * size = xsize * ysize
230 *
231 * And to satisfy the ratios and other constraints we set
232 *
233 * xsize = i_size * xratio * even
234 * ysize = i_size * yratio * even * iso
235 *
236 * For any value of "i_size". So with some substitution
237 *
238 * 1000 * size = i_size * i_size * xratio * yratio * even * even * iso
239 * i_size = sqrt(1000 * size / (xratio * yratio * even * even * iso))
240 *
241 * Make sure to round off i_size to preserve exact wanted ratios,
242 * that may be importante for some topologies.
243 */
244 const int i_size
245 = sqrt((float)(size)
246 / (float)(Xratio * Yratio * iso * even * even)) + 0.49;
247
248 /* Now build xsize and ysize value as described above. */
249 wld.map.xsize = Xratio * i_size * even;
250 wld.map.ysize = Yratio * i_size * even * iso;
251
252 /* Now make sure the size isn't too large for this ratio or the overall map
253 * size (MAP_INDEX_SIZE) is larger than the maximal allowed size
254 * (MAP_MAX_SIZE * 1000). If it is then decrease the size and try again. */
255 if (wld.map.xsize > MAP_MAX_LINEAR_SIZE
256 || wld.map.ysize > MAP_MAX_LINEAR_SIZE
257 || MAP_INDEX_SIZE > MAP_MAX_SIZE * 1000) {
258 fc_assert(size > 100.0);
259 set_sizes(size - 100.0, Xratio, Yratio);
260 return;
261 }
262
263 /* If the ratio is too big for some topology the simplest way to avoid
264 * this error is to set the maximum size smaller for all topologies! */
265 if (wld.map.server.size * 1000 > size + 900.0) {
266 /* Warning when size is set uselessly big */
267 log_error("Requested size of %d is too big for this topology.",
268 wld.map.server.size);
269 }
270
271 /* xsize and ysize must be between MAP_MIN_LINEAR_SIZE and
272 * MAP_MAX_LINEAR_SIZE. */
273 wld.map.xsize = CLIP(MAP_MIN_LINEAR_SIZE, wld.map.xsize, MAP_MAX_LINEAR_SIZE);
274 wld.map.ysize = CLIP(MAP_MIN_LINEAR_SIZE, wld.map.ysize, MAP_MAX_LINEAR_SIZE);
275
276 log_normal(_("Creating a map of size %d x %d = %d tiles (%d requested)."),
277 wld.map.xsize, wld.map.ysize, wld.map.xsize * wld.map.ysize,
278 (int) size);
279}
280
281/************************************************************************/
287 static void get_ratios(int *x_ratio, int *y_ratio)
288{
289 if (current_topo_has_flag(TF_WRAPX)) {
290 if (current_topo_has_flag(TF_WRAPY)) {
291 /* Ratios for torus map. */
292 *x_ratio = 1;
293 *y_ratio = 1;
294 } else {
295 /* Ratios for classic map. */
296 *x_ratio = 3;
297 *y_ratio = 2;
298 }
299 } else {
300 if (current_topo_has_flag(TF_WRAPY)) {
301 /* Ratios for uranus map. */
302 *x_ratio = 2;
303 *y_ratio = 3;
304 } else {
305 /* Ratios for flat map. */
306 *x_ratio = 1;
307 *y_ratio = 1;
308 }
309 }
310}
311
312/************************************************************************/
317 void generator_init_topology(bool autosize)
318{
319 int sqsize;
320 double map_size;
321
322 /* The server behavior to create the map is defined by 'map.server.mapsize'.
323 * Calculate the xsize/ysize if it is not directly defined. */
324 if (autosize) {
325 int x_ratio, y_ratio;
326
327 switch (wld.map.server.mapsize) {
328 case MAPSIZE_XYSIZE:
329 wld.map.server.size = (float)(wld.map.xsize * wld.map.ysize) / 1000.0 + 0.5;
330 wld.map.server.tilesperplayer = ((map_num_tiles() * wld.map.server.landpercent)
331 / (player_count() * 100));
332 log_normal(_("Creating a map of size %d x %d = %d tiles (map size: "
333 "%d)."), wld.map.xsize, wld.map.ysize, wld.map.xsize * wld.map.ysize,
334 wld.map.server.size);
335 break;
336
337 case MAPSIZE_PLAYER:
338 map_size = ((double) (player_count() * wld.map.server.tilesperplayer * 100)
339 / wld.map.server.landpercent);
340
341 if (map_size < MAP_MIN_SIZE * 1000) {
342 wld.map.server.size = MAP_MIN_SIZE;
343 map_size = MAP_MIN_SIZE * 1000;
344 log_normal(_("Map size calculated for %d (land) tiles per player "
345 "and %d player(s) too small. Setting map size to the "
346 "minimal size %d."), wld.map.server.tilesperplayer,
347 player_count(), wld.map.server.size);
348 } else if (map_size > MAP_MAX_SIZE * 1000) {
349 wld.map.server.size = MAP_MAX_SIZE;
350 map_size = MAP_MAX_SIZE * 1000;
351 log_normal(_("Map size calculated for %d (land) tiles per player "
352 "and %d player(s) too large. Setting map size to the "
353 "maximal size %d."), wld.map.server.tilesperplayer,
354 player_count(), wld.map.server.size);
355 } else {
356 wld.map.server.size = (double) map_size / 1000.0 + 0.5;
357 log_normal(_("Setting map size to %d (approx. %d (land) tiles for "
358 "each of the %d player(s))."), wld.map.server.size,
359 wld.map.server.tilesperplayer, player_count());
360 }
361 get_ratios(&x_ratio, &y_ratio);
362 set_sizes(map_size, x_ratio, y_ratio);
363 break;
364
365 case MAPSIZE_FULLSIZE:
366 /* Set map.xsize and map.ysize based on map.size. */
367 get_ratios(&x_ratio, &y_ratio);
368 set_sizes(wld.map.server.size * 1000, x_ratio, y_ratio);
369 wld.map.server.tilesperplayer = ((map_num_tiles() * wld.map.server.landpercent)
370 / (player_count() * 100));
371 break;
372 }
373 } else {
374 wld.map.server.size = (double) map_num_tiles() / 1000.0 + 0.5;
375 wld.map.server.tilesperplayer = ((map_num_tiles() * wld.map.server.landpercent)
376 / (player_count() * 100));
377 }
378
379 sqsize = get_sqsize();
380
381 /* initialize the ICE_BASE_LEVEL */
382
383 /* if maps has strip like poles we get smaller poles
384 * (less playables than island poles)
385 * 5% for little maps
386 * 2% for big ones, if map.server.temperature == 50
387 * except if separate poles is set */
388 if (wld.map.server.separatepoles) {
389 /* with separatepoles option strip poles are useless */
390 ice_base_colatitude =
391 (MAX(0, 100 * COLD_LEVEL / 3 - 1 * MAX_COLATITUDE)
392 + 1 * MAX_COLATITUDE * sqsize) / (100 * sqsize);
393 } else {
394 /* any way strip poles are not so playable as isle poles */
395 ice_base_colatitude =
396 (MAX(0, 100 * COLD_LEVEL / 3 - 2 * MAX_COLATITUDE)
397 + 2 * MAX_COLATITUDE * sqsize) / (100 * sqsize);
398 }
399
400 /* correction for single pole (Flat Earth) */
401 if (wld.map.server.single_pole) {
402 if (!current_topo_has_flag(TF_WRAPY) || !current_topo_has_flag(TF_WRAPX)) {
403 ice_base_colatitude /= 2;
404 }
405 }
406
407 if (wld.map.server.huts_absolute >= 0) {
408 wld.map.server.huts = wld.map.server.huts_absolute * 1000 / map_num_tiles();
409 wld.map.server.huts_absolute = -1;
410 }
411
412 map_init_topology();
413}
414
415/************************************************************************/
418 int get_sqsize(void)
419{
420 int sqsize = sqrt(MAP_INDEX_SIZE / 1000);
421
422 return MAX(1, sqsize);
423}
CITY_MAP_DEFAULT_RADIUS
#define CITY_MAP_DEFAULT_RADIUS
Definition city.h:70
_
#define _(String)
Definition fcintl.h:67
wld
struct world wld
Definition game.c:58
game.h
log.h
fc_assert
#define fc_assert(condition)
Definition log.h:176
fc_assert_ret_val
#define fc_assert_ret_val(condition, val)
Definition log.h:194
log_normal
#define log_normal(message,...)
Definition log.h:107
log_error
#define log_error(message,...)
Definition log.h:103
map_num_tiles
int map_num_tiles(void)
Definition map.c:1012
map_init_topology
void map_init_topology(void)
Definition map.c:301
is_singular_tile
bool is_singular_tile(const struct tile *ptile, int dist)
Definition map.c:1384
map.h
MAP_MAX_SIZE
#define MAP_MAX_SIZE
Definition map.h:590
current_topo_has_flag
#define current_topo_has_flag(flag)
Definition map.h:45
MAP_MAX_LINEAR_SIZE
#define MAP_MAX_LINEAR_SIZE
Definition map.h:606
do_in_natural_pos
#define do_in_natural_pos(ntl_x, ntl_y, map_x, map_y)
Definition map.h:204
MAP_INDEX_SIZE
#define MAP_INDEX_SIZE
Definition map.h:131
NATURAL_HEIGHT
#define NATURAL_HEIGHT
Definition map.h:221
MAP_IS_ISOMETRIC
#define MAP_IS_ISOMETRIC
Definition map.h:40
MAP_MIN_LINEAR_SIZE
#define MAP_MIN_LINEAR_SIZE
Definition map.h:607
MAP_MIN_SIZE
#define MAP_MIN_SIZE
Definition map.h:589
NATURAL_WIDTH
#define NATURAL_WIDTH
Definition map.h:220
do_in_natural_pos_end
#define do_in_natural_pos_end
Definition map.h:211
index_to_map_pos
#define index_to_map_pos(pmap_x, pmap_y, mindex)
Definition map.h:227
MAPSIZE_FULLSIZE
@ MAPSIZE_FULLSIZE
Definition map_types.h:39
MAPSIZE_PLAYER
@ MAPSIZE_PLAYER
Definition map_types.h:40
MAPSIZE_XYSIZE
@ MAPSIZE_XYSIZE
Definition map_types.h:43
get_ratios
static void get_ratios(int *x_ratio, int *y_ratio)
Definition mapgen_topology.c:287
generator_init_topology
void generator_init_topology(bool autosize)
Definition mapgen_topology.c:317
get_sqsize
int get_sqsize(void)
Definition mapgen_topology.c:418
ice_base_colatitude
int ice_base_colatitude
Definition mapgen_topology.c:28
set_sizes
static void set_sizes(double size, int Xratio, int Yratio)
Definition mapgen_topology.c:215
map_colatitude
int map_colatitude(const struct tile *ptile)
Definition mapgen_topology.c:38
near_singularity
bool near_singularity(const struct tile *ptile)
Definition mapgen_topology.c:205
mapgen_topology.h
COLD_LEVEL
#define COLD_LEVEL
Definition mapgen_topology.h:36
MAX_COLATITUDE
#define MAX_COLATITUDE
Definition mapgen_topology.h:22
player_count
int player_count(void)
Definition player.c:808
CLIP
#define CLIP(lower, current, upper)
Definition shared.h:57
MAX
#define MAX(x, y)
Definition shared.h:54
size
size_t size
Definition specvec.h:72
civ_map::xsize
int xsize
Definition map_types.h:77
civ_map::ysize
int ysize
Definition map_types.h:77
civ_map::alltemperate
bool alltemperate
Definition map_types.h:101
civ_map::mapsize
enum mapsize_type mapsize
Definition map_types.h:85
civ_map::size
int size
Definition map_types.h:86
civ_map::tilesperplayer
int tilesperplayer
Definition map_types.h:87
civ_map::landpercent
int landpercent
Definition map_types.h:94
civ_map::server
struct civ_map::@41::@43 server
civ_map::huts
int huts
Definition map_types.h:91
civ_map::single_pole
bool single_pole
Definition map_types.h:100
civ_map::separatepoles
bool separatepoles
Definition map_types.h:98
civ_map::huts_absolute
int huts_absolute
Definition map_types.h:92
tile
Definition tile.h:49
world::map
struct civ_map map
Definition world_object.h:38
tile_index
#define tile_index(_pt_)
Definition tile.h:87