[Freeciv-Dev] [PATCH] base_real_map_distance (PR#1049)

[jdorje@xxxxxxxxxxxxxxxxxxxxx]

This patch introduces a new topology function,
base_real_map_distance().  It performs a similar function to
real_map_distance, but also finds a distance vector from the source to
the destination coordinate pair.  It also replaces xdist and ydist.

A function like this is absolutely essential for iso-rectangular
topologies.  xdist() and ydist() will not work because you cannot find
the distance along one coordinate axis independently of the other.

jason

? rc
? old
? topology
? corecleanup_08.ReadMe
Index: common/map.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.c,v
retrieving revision 1.98
diff -u -r1.98 map.c
--- common/map.c        2001/10/30 10:59:19     1.98
+++ common/map.c        2001/11/01 14:09:30
@@ -288,28 +288,10 @@
 /***************************************************************
 ...
 ***************************************************************/
-int xdist(int x0, int x1)
-{
-  int dist = (x0 > x1) ? x0 - x1 : x1 - x0;
-  return MIN(dist, map.xsize-dist);
-}
-
-/***************************************************************
-...
-***************************************************************/
-int ydist(int y0, int y1)
-{
-  return (y0 > y1) ? y0 - y1 : y1 - y0;
-}
-
-/***************************************************************
-...
-***************************************************************/
 int real_map_distance(int x0, int y0, int x1, int y1)
 {
-  int xd = xdist(x0, x1);
-  int yd = ydist(y0, y1);
-  return MAX(xd, yd);
+  int xd, yd;
+  return base_real_map_distance(&xd, &yd, x0, y0, x1, y1);
 }
 
 /***************************************************************
@@ -317,8 +299,10 @@
 ***************************************************************/
 int sq_map_distance(int x0, int y0, int x1, int y1)
 {
-  int xd = xdist(x0, x1);
-  int yd = ydist(y0, y1);
+  /* We assume base_real_map_distance gives us the vector with
+     the minimum squared distance.  Right now this is true. */
+  int xd, yd;
+  base_real_map_distance(&xd, &yd, x0, y0, x1, y1);
   return (xd*xd + yd*yd);
 }
 
@@ -327,7 +311,11 @@
 ***************************************************************/
 int map_distance(int x0, int y0, int x1, int y1)
 {
-  return xdist(x0, x1) + ydist(y0, y1);
+  /* We assume base_real_map_distance gives us the vector with
+     the minimum map distance.  Right now this is true. */
+  int xd, yd;
+  base_real_map_distance(&xd, &yd, x0, y0, x1, y1);
+  return abs(xd) + abs(yd);
 }
 
 /***************************************************************
@@ -1340,6 +1328,32 @@
 }
 
 /**************************************************************************
+Topology function to find the minimum "real" distance between positions
+(x0, y0) and (x1, y1).  We find not only the distance but the vector
+(*dx, *dy) that has that "real" distance. If there is more than one vector
+with equal distance, no guarantee is made about which is found.
+
+Real distance is defined as the larger of the distances in the x and y
+direction; since units can travel diagonally this is the "real" distance
+a unit has to travel to get from point to point.
+
+(See also: real_map_distance, map_distance, and sq_map_distance.)
+**************************************************************************/
+int base_real_map_distance(int *dx, int *dy, int x0, int y0, int x1, int y1)
+{
+  if (x0 > x1)
+    *dx = x0 - x1;
+  else
+    *dx = x1 - x0;
+  if (*dx > map.xsize - *dx)
+    *dx = map.xsize - *dx;
+
+  *dy = y1 - y0;
+
+  return MAX(abs(*dx), abs(*dy));
+}
+
+/**************************************************************************
 Random neighbouring square.
 **************************************************************************/
 void rand_neighbour(int x0, int y0, int *x, int *y)
@@ -1436,11 +1450,13 @@
 **************************************************************************/
 int is_move_cardinal(int start_x, int start_y, int end_x, int end_y)
 {
+  int diff_x, diff_y;
   assert(is_real_tile(start_x, start_y) && is_real_tile(end_x, end_y));
   normalize_map_pos(&start_x, &start_y);
   normalize_map_pos(&end_x, &end_y);
   assert(is_tiles_adjacent(start_x, start_y, end_x, end_y));
 
-  /* FIXME: this check will not work with an orthogonal map */
-  return (start_x == end_x) || (start_y == end_y);
+  /* This check could be done better. */
+  base_real_map_distance(&diff_x, &diff_y, start_x, start_y, end_x, end_y);
+  return (diff_x == 0) || (diff_y == 0);
 }
Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.101
diff -u -r1.101 map.h
--- common/map.h        2001/10/30 10:59:20     1.101
+++ common/map.h        2001/11/01 14:09:30
@@ -183,8 +183,6 @@
 char *map_get_tile_fpt_text(int x, int y);
 struct tile *map_get_tile(int x, int y);
 
-int xdist(int x0, int x1);
-int ydist(int y0, int y1);
 int map_distance(int x0, int y0, int x1, int y1);
 int real_map_distance(int x0, int y0, int x1, int y1);
 int sq_map_distance(int x0, int y0, int x1, int y1);
@@ -284,6 +282,7 @@
 
 int normalize_map_pos(int *x, int *y);
 void nearest_real_pos(int *x, int *y);
+int base_real_map_distance(int *dx, int *dy, int x0, int y0, int x1, int y1);
 
 void rand_neighbour(int x0, int y0, int *x, int *y);
 void rand_map_pos(int *x, int *y);
Index: server/gotohand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/gotohand.c,v
retrieving revision 1.122
diff -u -r1.122 gotohand.c
--- server/gotohand.c   2001/10/08 12:11:17     1.122
+++ server/gotohand.c   2001/11/01 14:09:32
@@ -414,17 +414,7 @@
 {
   int diff_x, diff_y, dx, dy, scalar_product;
 
-  if (dest_x > src_x) {
-    diff_x = dest_x - src_x < map.xsize / 2 ? 1 : -1;
-  } else if (dest_x < src_x) {
-    diff_x = src_x - dest_x < map.xsize / 2 ? -1 : 1;
-  } else {                     /* dest_x == src_x */
-    diff_x = 0;
-  }
-  if (dest_y != src_y)
-    diff_y = dest_y > src_y ? 1 : -1;
-  else
-    diff_y = 0;
+  base_real_map_distance(&diff_x, &diff_y, src_x, src_y, dest_x, dest_y);
 
   DIRSTEP(dx, dy, dir);
   scalar_product = diff_x * dx + diff_y * dy;
@@ -443,23 +433,19 @@
 static int straightest_direction(int src_x, int src_y, int dest_x, int dest_y)
 {
   int best_dir;
-  int go_x, go_y;
+  int diff_x, diff_y;
 
-  /* Should we go up or down, east or west: go_x/y is the "step" in x/y.
-     Will allways be -1 or 1 even if src_x == dest_x or src_y == dest_y. */
-  go_x = dest_x > src_x ?
-    (dest_x-src_x < map.xsize/2 ? 1 : -1) :
-    (src_x-dest_x < map.xsize/2 ? -1 : 1);
-  go_y = dest_y > src_y ? 1 : -1;
-
-  if (src_x == dest_x)
-    best_dir = (go_y > 0) ? 6 : 1;
-  else if (src_y == dest_y)
-    best_dir = (go_x > 0) ? 4 : 3;
-  else if (go_x > 0)
-    best_dir = (go_y > 0) ? 7 : 2;
-  else /* go_x < 0 */
-    best_dir = (go_y > 0) ? 5 : 0;
+  /* Should we go up or down, east or west: diff_x/y is the "step" in x/y. */
+  base_real_map_distance(&diff_x, &diff_y, src_x, src_y, dest_x, dest_y);
+
+  if (!diff_x)
+    best_dir = (diff_y > 0) ? DIR8_SOUTH : DIR8_NORTH;
+  else if (!diff_y)
+    best_dir = (diff_x > 0) ? DIR8_EAST : DIR8_WEST;
+  else if (diff_x > 0)
+    best_dir = (diff_y > 0) ? DIR8_SOUTHEAST : DIR8_NORTHEAST;
+  else /* diff_x < 0 */
+    best_dir = (diff_y > 0) ? DIR8_SOUTHWEST : DIR8_NORTHWEST;
 
   return (best_dir);
 }
Index: server/settlers.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/settlers.c,v
retrieving revision 1.112
diff -u -r1.112 settlers.c
--- server/settlers.c   2001/10/14 21:02:17     1.112
+++ server/settlers.c   2001/11/01 14:09:33
@@ -769,8 +769,8 @@
   for (i = 0; i < game.nplayers; i++) {
     city_list_iterate(game.players[i].cities, pcity) {
       if (map_distance(x, y, pcity->x, pcity->y)<=8) {
-        dx = xdist(pcity->x, x);
-        dy = ydist(pcity->y, y);
+       base_real_map_distance(&dx, &dy, pcity->x, pcity->y, x, y);
+       dx = abs(dx), dy = abs(dy);
        /* these are heuristics... */
         if (dx<=5 && dy<5)
           return 0;