[Freeciv-Dev] (PR#7481) meta-ticket for hex maps
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
<URL: http://rt.freeciv.org/Ticket/Display.html?id=7481 >
Here is a complete and updated patch for hex maps.
I plan to break this up into some smaller patches. Including:
- Rewrite iterate_outward.
- New iterator iterate_outward_dxy used by square_dxy_iterate.
- Remove rectangle_iterate.
- Fix circle_iterate.
- ADD HEX STUFF
jason
Index: client/connectdlg_common.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/connectdlg_common.c,v
retrieving revision 1.14
diff -u -r1.14 connectdlg_common.c
--- client/connectdlg_common.c 30 Jun 2004 14:34:30 -0000 1.14
+++ client/connectdlg_common.c 13 Jul 2004 22:51:08 -0000
@@ -243,12 +243,18 @@
* get an iso-map and for a classic tileset you get a classic map. In
* both cases the map wraps in the X direction by default.
*
+ * This works with hex maps too now. A hex map always has is_isometric
+ * set. An iso-hex map has hex_height != 0, while a non-iso hex map
+ * has hex_width != 0.
+ *
* Setting the option here is a bit of a hack, but so long as the client
* has sufficient permissions to do so (it doesn't have HACK access yet) it
* is safe enough. Note that if you load a savegame the topology will be
* set but then overwritten during the load. */
my_snprintf(buf, sizeof(buf), "/set topology %d",
- TF_WRAPX | (is_isometric ? TF_ISO : 0));
+ (TF_WRAPX
+ | ((is_isometric && hex_height == 0) ? TF_ISO : 0)
+ | ((hex_width != 0 || hex_height != 0) ? TF_HEX : 0)));
send_chat(buf);
return TRUE;
Index: common/city.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/city.c,v
retrieving revision 1.229
diff -u -r1.229 city.c
--- common/city.c 13 Jul 2004 21:54:17 -0000 1.229
+++ common/city.c 13 Jul 2004 22:51:09 -0000
@@ -155,7 +155,7 @@
or the sort order will be left up to qsort and will be undefined. This
would mean that server execution would not be reproducable.
***************************************************************************/
-static int compare_index(const void *a, const void *b)
+int compare_iter_index(const void *a, const void *b)
{
const struct iter_index *index1 = a, *index2 = b;
int value;
@@ -204,7 +204,7 @@
}
assert(i == CITY_TILES);
- qsort(array, CITY_TILES, sizeof(*array), compare_index);
+ qsort(array, CITY_TILES, sizeof(*array), compare_iter_index);
#ifdef DEBUG
for (i = 0; i < CITY_TILES; i++) {
Index: common/city.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/city.h,v
retrieving revision 1.152
diff -u -r1.152 city.h
--- common/city.h 13 Jul 2004 21:54:17 -0000 1.152
+++ common/city.h 13 Jul 2004 22:51:09 -0000
@@ -399,6 +399,9 @@
int city_map_y);
bool city_map_to_map(int *map_x, int *map_y, const struct city *const pcity,
int city_map_x, int city_map_y);
+
+/* Initialization functions */
+int compare_iter_index(const void *a, const void *b);
void generate_city_map_indices(void);
/* shield on spot */
Index: common/map.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.c,v
retrieving revision 1.178
diff -u -r1.178 map.c
--- common/map.c 13 Jul 2004 22:43:41 -0000 1.178
+++ common/map.c 13 Jul 2004 22:51:09 -0000
@@ -215,6 +215,98 @@
map.have_huts = FALSE;
}
+/**************************************************************************
+ Fill the iterate_outwards_indices array. This may depend on the topology.
+***************************************************************************/
+static void generate_map_indices(void)
+{
+ int i = 0, nat_x, nat_y, tiles;
+ struct iter_index *array = map.iterate_outwards_indices;
+ int nat_center_x, nat_center_y, nat_min_x, nat_min_y, nat_max_x, nat_max_y;
+ int map_center_x, map_center_y;
+
+ /* These caluclations are done via tricky native math. We need to make
+ * sure that when "exploring" positions in the iterate_outward we hit each
+ * position within the distance exactly once.
+ *
+ * To do this we pick a center position (at the center of the map, for
+ * convenience). Then we iterate over all of the positions around it,
+ * accounting for wrapping, in native coordinates. Note that some of the
+ * positions iterated over before will not even be real; the point is to
+ * use the native math so as to get the right behavior under different
+ * wrapping conditions.
+ *
+ * Thus the "center" position below is just an arbitrary point. We choose
+ * the center of the map to make the min/max values (below) simpler. */
+ nat_center_x = map.xsize / 2;
+ nat_center_y = map.ysize / 2;
+ native_to_map_pos(&map_center_x, &map_center_y,
+ nat_center_x, nat_center_y);
+
+ /* If we wrap in a particular direction (X or Y) we only need to explore a
+ * half of a map-width in that direction before we hit the wrap point. If
+ * not we need to explore the full width since we have to account for the
+ * worst-case where we start at one edge of the map. Of course if we try
+ * to explore too far the extra steps will just be skipped by the
+ * normalize check later on. So the purpose at this point is just to
+ * get the right set of positions, relative to the start position, that
+ * may be needed for the iteration.
+ *
+ * If the map does wrap, we go map.Nsize / 2 in each direction. This
+ * gives a min value of 0 and a max value of Nsize-1, because of the
+ * center position chosen above. This also avoids any off-by-one errors.
+ *
+ * If the map doesn't wrap, we go map.Nsize-1 in each direction. In this
+ * case we're not concerned with going too far and wrapping around, so we
+ * just have to make sure we go far enough if we're at one edge of the
+ * map. */
+ nat_min_x = (topo_has_flag(TF_WRAPX) ? 0 : (nat_center_x - map.xsize + 1));
+ nat_min_y = (topo_has_flag(TF_WRAPY) ? 0 : (nat_center_y - map.ysize + 1));
+
+ nat_max_x = (topo_has_flag(TF_WRAPX)
+ ? (map.xsize - 1)
+ : (nat_center_x + map.xsize - 1));
+ nat_max_y = (topo_has_flag(TF_WRAPY)
+ ? (map.ysize - 1)
+ : (nat_center_y + map.ysize - 1));
+ tiles = (nat_max_x - nat_min_x + 1) * (nat_max_y - nat_min_y + 1);
+
+ array = fc_realloc(array, tiles * sizeof(*array));
+
+ for (nat_x = nat_min_x; nat_x <= nat_max_x; nat_x++) {
+ for (nat_y = nat_min_y; nat_y <= nat_max_y; nat_y++) {
+ int map_x, map_y, dx, dy;
+
+ /* Now for each position, we find the vector (in map coordinates) from
+ * the center position to that position. Then we calculate the
+ * distance between the two points. Wrapping is ignored at this
+ * point since the use of native positions means we should always have
+ * the shortest vector. */
+ native_to_map_pos(&map_x, &map_y, nat_x, nat_y);
+ dx = map_x - map_center_x;
+ dy = map_y - map_center_y;
+
+ array[i].dx = dx;
+ array[i].dy = dy;
+ array[i].dist = map_vector_to_real_distance(dx, dy);
+ i++;
+ }
+ }
+ assert(i == tiles);
+
+ qsort(array, tiles, sizeof(*array), compare_iter_index);
+
+#if 0
+ for (i = 0; i < tiles; i++) {
+ freelog(LOG_DEBUG, "%5d : (%3d,%3d) : %d",
+ i, array[i].dx, array[i].dy, array[i].dist);
+ }
+#endif
+
+ map.num_iterate_outwards_indices = tiles;
+ map.iterate_outwards_indices = array;
+}
+
/****************************************************************************
Set the map xsize and ysize based on a base size and ratio (in natural
coordinates).
@@ -226,7 +318,7 @@
/* In TF_ISO we need to double the map.ysize factor, since xsize is
* in native coordinates which are compressed 2x in the X direction. */
- const int iso = topo_has_flag(TF_ISO) ? 2 : 1;
+ const int iso = (topo_has_flag(TF_ISO) || topo_has_flag(TF_HEX)) ? 2 : 1;
/* We have:
*
@@ -383,6 +475,7 @@
} whole_map_iterate_end;
generate_city_map_indices();
+ generate_map_indices();
}
/***************************************************************
@@ -444,7 +537,13 @@
****************************************************************************/
static int map_vector_to_distance(int dx, int dy)
{
- return abs(dx) + abs(dy);
+ if (topo_has_flag(TF_HEX)) {
+ /* Hex: all directions are cardinal so the distance is equivalent to
+ * the real distance. */
+ return map_vector_to_real_distance(dx, dy);
+ } else {
+ return abs(dx) + abs(dy);
+ }
}
/****************************************************************************
@@ -452,7 +551,33 @@
****************************************************************************/
int map_vector_to_real_distance(int dx, int dy)
{
- return MAX(abs(dx), abs(dy));
+ if (topo_has_flag(TF_HEX)) {
+ if (topo_has_flag(TF_ISO)) {
+ /* Iso-hex: you can't move NE or SW. */
+ if ((dx < 0 && dy > 0)
+ || (dx > 0 && dy < 0)) {
+ /* Diagonal moves in this direction aren't allowed, so it will take
+ * the full number of moves. */
+ return abs(dx) + abs(dy);
+ } else {
+ /* Diagonal moves in this direction *are* allowed. */
+ return MAX(abs(dx), abs(dy));
+ }
+ } else {
+ /* Hex: you can't move SE or NW. */
+ if ((dx > 0 && dy > 0)
+ || (dx < 0 && dy < 0)) {
+ /* Diagonal moves in this direction aren't allowed, so it will take
+ * the full number of moves. */
+ return abs(dx) + abs(dy);
+ } else {
+ /* Diagonal moves in this direction *are* allowed. */
+ return MAX(abs(dx), abs(dy));
+ }
+ }
+ } else {
+ return MAX(abs(dx), abs(dy));
+ }
}
/****************************************************************************
@@ -460,7 +585,15 @@
****************************************************************************/
int map_vector_to_sq_distance(int dx, int dy)
{
- return dx * dx + dy * dy;
+ if (topo_has_flag(TF_HEX)) {
+ /* Hex: The square distance is just the square of the real distance; we
+ * don't worry about pythagorean calculations. */
+ int dist = map_vector_to_real_distance(dx, dy);
+
+ return dist * dist;
+ } else {
+ return dx * dx + dy * dy;
+ }
}
/***************************************************************
@@ -1628,14 +1761,16 @@
bool is_valid_dir(enum direction8 dir)
{
switch (dir) {
- case DIR8_NORTH:
+ case DIR8_SOUTHEAST:
+ case DIR8_NORTHWEST:
+ return !(topo_has_flag(TF_HEX) && !topo_has_flag(TF_ISO));
case DIR8_NORTHEAST:
+ case DIR8_SOUTHWEST:
+ return !(topo_has_flag(TF_HEX) && topo_has_flag(TF_ISO));
+ case DIR8_NORTH:
case DIR8_EAST:
- case DIR8_SOUTHEAST:
case DIR8_SOUTH:
- case DIR8_SOUTHWEST:
case DIR8_WEST:
- case DIR8_NORTHWEST:
return TRUE;
default:
return FALSE;
Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.193
diff -u -r1.193 map.h
--- common/map.h 13 Jul 2004 16:01:42 -0000 1.193
+++ common/map.h 13 Jul 2004 22:51:10 -0000
@@ -146,6 +146,8 @@
int topology_id;
enum direction8 valid_dirs[8], cardinal_dirs[8];
int num_valid_dirs, num_cardinal_dirs;
+ struct iter_index *iterate_outwards_indices;
+ int num_iterate_outwards_indices;
int size; /* used to calculate [xy]size */
int xsize, ysize; /* native dimensions */
int seed;
@@ -181,7 +183,8 @@
/* Changing these values will break map_init_topology. */
TF_WRAPX = 1,
TF_WRAPY = 2,
- TF_ISO = 4
+ TF_ISO = 4,
+ TF_HEX = 8
};
#define CURRENT_TOPOLOGY (map.topology_id)
@@ -234,13 +237,13 @@
/* Obscure math. See explanation in doc/HACKING. */
#define native_to_map_pos(pmap_x, pmap_y, nat_x, nat_y) \
- (topo_has_flag(TF_ISO) \
+ ((topo_has_flag(TF_ISO) || topo_has_flag(TF_HEX)) \
? (*(pmap_x) = ((nat_y) + ((nat_y) & 1)) / 2 + (nat_x), \
*(pmap_y) = (nat_y) - *(pmap_x) + map.xsize) \
: (*(pmap_x) = (nat_x), *(pmap_y) = (nat_y)))
#define map_to_native_pos(pnat_x, pnat_y, map_x, map_y) \
- (topo_has_flag(TF_ISO) \
+ ((topo_has_flag(TF_ISO) || topo_has_flag(TF_HEX)) \
? (*(pnat_y) = (map_x) + (map_y) - map.xsize, \
*(pnat_x) = (2 * (map_x) - *(pnat_y) - (*(pnat_y) & 1)) / 2) \
: (*(pnat_x) = (map_x), *(pnat_y) = (map_y)))
@@ -327,9 +330,10 @@
* we bend this rule here.
*/
#define MAPSTEP(dest_x, dest_y, src_x, src_y, dir) \
-( (dest_x) = (src_x) + DIR_DX[(dir)], \
- (dest_y) = (src_y) + DIR_DY[(dir)], \
- normalize_map_pos(&(dest_x), &(dest_y)))
+ (is_valid_dir(dir) \
+ && ((dest_x) = (src_x) + DIR_DX[(dir)], \
+ (dest_y) = (src_y) + DIR_DY[(dir)], \
+ normalize_map_pos(&(dest_x), &(dest_y))))
struct player *map_get_owner(int x, int y);
void map_set_owner(int x, int y, struct player *pplayer);
@@ -356,7 +360,6 @@
bool contains_special(enum tile_special_type all,
enum tile_special_type to_test_for);
-
bool is_singular_map_pos(int map_x, int map_y, int dist);
bool normalize_map_pos(int *x, int *y);
void nearest_real_pos(int *x, int *y);
@@ -410,86 +413,38 @@
extern struct terrain_misc terrain_control;
-/* This iterates outwards from the starting point (Duh?).
- Every tile within max_dist will show up exactly once. (even takes
- into account wrap). All positions given correspond to real tiles.
- The values given are adjusted.
- You should make sure that the arguments passed to the macro are adjusted,
- or you could have some very nasty intermediate errors.
-
- Internally it works by for a given distance
- 1) assume y positive and iterate over x
- 2) assume y negative and iterate over x
- 3) assume x positive and iterate over y
- 4) assume x negative and iterate over y
- Where in this we are is decided by the variables xcycle and positive.
- each of there distances give a box of tiles; to ensure each tile is only
- returned once we only return the corner when iterating over x.
- As a special case positive is initialized as 0 (ie we start in step 2) ),
- as the center tile would else be returned by both step 1) and 2).
-*/
-#define iterate_outward(ARG_start_x, ARG_start_y, ARG_max_dist, ARG_x_itr,
ARG_y_itr) \
-{ \
- int ARG_x_itr, ARG_y_itr; \
- int MACRO_max_dx = map.xsize/2; \
- int MACRO_min_dx = -MACRO_max_dx - 1 + (map.xsize % 2); \
- bool MACRO_xcycle = TRUE; \
- bool MACRO_positive = FALSE; \
- bool MACRO_is_border = IS_BORDER_MAP_POS(ARG_start_x, ARG_start_y, \
- ARG_max_dist); \
- int MACRO_dxy = 0, MACRO_do_xy; \
- CHECK_MAP_POS(ARG_start_x, ARG_start_y); \
- while(MACRO_dxy <= (ARG_max_dist)) { \
- for (MACRO_do_xy = -MACRO_dxy; MACRO_do_xy <= MACRO_dxy; MACRO_do_xy++) { \
- if (MACRO_xcycle) { \
- ARG_x_itr = (ARG_start_x) + MACRO_do_xy; \
- if (MACRO_positive) \
- ARG_y_itr = (ARG_start_y) + MACRO_dxy; \
- else \
- ARG_y_itr = (ARG_start_y) - MACRO_dxy; \
- } else { /* ! MACRO_xcycle */ \
- if (MACRO_dxy == MACRO_do_xy || MACRO_dxy == -MACRO_do_xy) \
- continue; \
- ARG_y_itr = (ARG_start_y) + MACRO_do_xy; \
- if (MACRO_positive) \
- ARG_x_itr = (ARG_start_x) + MACRO_dxy; \
- else \
- ARG_x_itr = (ARG_start_x) - MACRO_dxy; \
- } \
- { \
- int MACRO_dx = (ARG_start_x) - ARG_x_itr; \
- if (MACRO_dx > MACRO_max_dx || MACRO_dx < MACRO_min_dx) \
- continue; \
- } \
- if (MACRO_is_border && !normalize_map_pos(&ARG_x_itr, &ARG_y_itr)) { \
- continue; \
- }
+/* This iterates outwards from the starting point. Every tile within max_dist
+ * will show up at exactly once, in an outward (based on real map distance)
+ * order. The returned values are always real and are normalized. The
+ * starting position must be normal. */
+#define iterate_outward_dxy(start_x, start_y, max_dist, x_itr, y_itr, \
+ dx_itr, dy_itr) \
+{ \
+ int _start_x = (start_x), _start_y = (start_y), _max_dist = (max_dist); \
+ bool _is_border = IS_BORDER_MAP_POS(_start_x, _start_y, _max_dist); \
+ int x_itr, y_itr, dx_itr, dy_itr, _index; \
+ \
+ CHECK_MAP_POS(_start_x, _start_y); \
+ for (_index = 0; _index < map.num_iterate_outwards_indices; _index++) { \
+ if (map.iterate_outwards_indices[_index].dist > _max_dist) { \
+ break; \
+ } \
+ dx_itr = map.iterate_outwards_indices[_index].dx; \
+ dy_itr = map.iterate_outwards_indices[_index].dy; \
+ x_itr = dx_itr + _start_x; \
+ y_itr = dy_itr + _start_y; \
+ if (_is_border && !normalize_map_pos(&x_itr, &y_itr)) { \
+ continue;
\
+ }
-#define iterate_outward_end \
- } \
- if (!MACRO_positive) { \
- if (!MACRO_xcycle) \
- MACRO_dxy++; \
- MACRO_xcycle = !MACRO_xcycle; \
- } \
- MACRO_positive = !MACRO_positive; \
- } \
+#define iterate_outward_dxy_end
\
+ } \
}
-#define rectangle_iterate(map_x0, map_y0, map_width, map_height, \
- x_itr, y_itr) \
-{ \
- int RI_dx_itr, RI_dy_itr; \
- for (RI_dy_itr = 0; RI_dy_itr < (map_height); RI_dy_itr++) { \
- for (RI_dx_itr = 0; RI_dx_itr < (map_width); RI_dx_itr++) { \
- int x_itr = RI_dx_itr + (map_x0), y_itr = RI_dy_itr + (map_y0); \
- if (normalize_map_pos(&x_itr, &y_itr)) {
+#define iterate_outward(start_x, start_y, max_dist, x_itr, y_itr) \
+ iterate_outward_dxy(start_x, start_y, max_dist, x_itr, y_itr, _dx, _dy)
-#define rectangle_iterate_end \
- } \
- } \
- } \
-}
+#define iterate_outward_end iterate_outward_dxy_end
/*
* Iterate through all tiles in a square with given center and radius.
@@ -499,23 +454,12 @@
* position. Note that when the square is larger than the map the
* distance vector may not be the minimum distance vector.
*/
-#define square_dxy_iterate(center_x, center_y, radius, x_itr, y_itr, \
- dx_itr, dy_itr) \
-{ \
- int dx_itr, dy_itr; \
- bool _is_border = IS_BORDER_MAP_POS((center_x), (center_y), (radius)); \
- CHECK_MAP_POS((center_x), (center_y)); \
- for (dy_itr = -(radius); dy_itr <= (radius); dy_itr++) { \
- for (dx_itr = -(radius); dx_itr <= (radius); dx_itr++) { \
- int x_itr = dx_itr + (center_x), y_itr = dy_itr + (center_y); \
- if (_is_border && !normalize_map_pos(&x_itr, &y_itr)) { \
- continue; \
- }
+#define square_dxy_iterate(center_x, center_y, radius, x_itr, y_itr, \
+ dx_itr, dy_itr) \
+ iterate_outward_dxy(center_x, center_y, radius, x_itr, y_itr,
\
+ dx_itr, dy_itr)
-#define square_dxy_iterate_end \
- } \
- } \
-}
+#define square_dxy_iterate_end iterate_outward_dxy_end
/*
* Iterate through all tiles in a square with given center and radius.
@@ -540,7 +484,7 @@
int _cr_radius = (int)sqrt((double)(sq_radius)); \
square_dxy_iterate(center_x, center_y, _cr_radius, \
x_itr, y_itr, _dx, _dy) { \
- if (_dy * _dy + _dx * _dx <= (sq_radius)) {
+ if (map_vector_to_sq_distance(_dx, _dy) <= (sq_radius)) {
#define circle_iterate_end \
} \
@@ -632,9 +576,23 @@
/* is the direction "cardinal"? Cardinal directions
* (also called cartesian) are the four main ones */
-#define DIR_IS_CARDINAL(dir) \
- ((dir) == DIR8_NORTH || (dir) == DIR8_EAST || \
- (dir) == DIR8_WEST || (dir) == DIR8_SOUTH)
+static inline bool DIR_IS_CARDINAL(enum direction8 dir)
+{
+ switch (dir) {
+ case DIR8_NORTH:
+ case DIR8_SOUTH:
+ case DIR8_EAST:
+ case DIR8_WEST:
+ return TRUE;
+ case DIR8_SOUTHEAST:
+ case DIR8_NORTHWEST:
+ return !(topo_has_flag(TF_HEX) && !topo_has_flag(TF_ISO));
+ case DIR8_NORTHEAST:
+ case DIR8_SOUTHWEST:
+ return !(topo_has_flag(TF_HEX) && topo_has_flag(TF_ISO));
+ }
+ return FALSE;
+}
enum direction8 dir_cw(enum direction8 dir);
enum direction8 dir_ccw(enum direction8 dir);
@@ -667,7 +625,7 @@
#define MAP_ORIGINAL_TOPO TF_WRAPX
#define MAP_DEFAULT_TOPO TF_WRAPX
#define MAP_MIN_TOPO 0
-#define MAP_MAX_TOPO 7
+#define MAP_MAX_TOPO 15
#define MAP_DEFAULT_SEED 0
#define MAP_MIN_SEED 0
@@ -744,6 +702,11 @@
****************************************************************************/
static inline bool IS_BORDER_MAP_POS(int map_x, int map_y, int dist)
{
+ if (topo_has_flag(TF_HEX)) {
+ /* TODO */
+ return TRUE;
+ }
+
do_in_native_pos(nat_x, nat_y, map_x, map_y) {
/* HACK: An iso-map compresses the value in the X direction but not in
* the Y direction. Hence (x+1,y) is 1 tile away while (x,y+2) is also
Index: server/stdinhand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/stdinhand.c,v
retrieving revision 1.326
diff -u -r1.326 stdinhand.c
--- server/stdinhand.c 12 Jul 2004 15:51:11 -0000 1.326
+++ server/stdinhand.c 13 Jul 2004 22:51:16 -0000
@@ -274,7 +274,15 @@
" 4 Flat Earth (isometric)\n"
" 5 Earth (isometric)\n"
" 6 Uranus (isometric)\n"
- " 7 Donut World (isometric)"
+ " 7 Donut World (isometric)\n"
+ " 8 Flat Earth (hexagonal)\n"
+ " 9 Earth (hexagonal)\n"
+ " 10 Uranus (hexagonal)\n"
+ " 11 Donut World (hexagonal)\n"
+ " 12 Flat Earth (iso-hex)\n"
+ " 13 Earth (iso-hex)\n"
+ " 14 Uranus (iso-hex)\n"
+ " 15 Donut World (iso-hex)"
), NULL,
MAP_MIN_TOPO, MAP_MAX_TOPO, MAP_DEFAULT_TOPO)
|
|
