? diff
Index: server/gotohand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/gotohand.c,v
retrieving revision 1.115
diff -u -r1.115 gotohand.c
--- server/gotohand.c	2001/09/15 15:31:26	1.115
+++ server/gotohand.c	2001/09/18 16:00:54
@@ -483,35 +483,62 @@
 }
 
 /**************************************************************************
-Return the direction that takes us most directly to dest_x,dest_y.
-The direction is a value for use in DIR_DX[] and DIR_DY[] arrays.
-
-FIXME: This is a bit crude; this only gives one correct path, but sometimes
-       there can be more than one straight path (fx going NW then W is the
-       same as going W then NW)
+Return the direction that takes us most directly to (dest_x, dest_y).
 **************************************************************************/
-static int straightest_direction(int src_x, int src_y, int dest_x, int dest_y)
+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 best_dir = -1, dir;
+  float best = -1;
+  int diff_x, diff_y;
+
+  /* This code is topology-dependent */
+  diff_x = dest_x - src_x;
+  if (diff_x < -map.xsize / 2)
+    diff_x += map.xsize;
+  if (diff_x > map.xsize / 2)
+    diff_x -= map.xsize;
+  diff_y = dest_y - src_y;
+
+  /*
+   * The straightest direction is the direction which has the most
+   * minimal |angle| of all directions. angle is the angle between the
+   * difference vector (diff) and one of the direction vectors (d_i).
+   *
+   * cos(angle) = (diff * d_i)/(||diff|| * ||d_i||)
+   *
+   * The direction which has the smallest |angle| is the direction
+   * which has the largest cos(angle). ||diff|| is constant and so
+   * doesn't affect the maximum searching of m.
+   *
+   * m = (diff * d_i)/||d_i||
+   *
+   * Any direction for which (diff * d_i) is negative isn't a solution
+   * (wrong semi-circle). If both dividend and divisor are >=0 the
+   * fraction can be squared without affecting the maximum search.
+   *
+   * m2=(diff * d_i)^2 / ||d_i||^2
+   *
+   * ||d_i||^2 can have the values 1 and 2. So the division will not
+   * loose any precision if the dividend is multiplied by 2 and the
+   * whole operation is carried out with integer numbers.
+   */
+  for (dir = 0; dir < 8; dir++) {
+    int di_x = DIR_DX[dir], di_y = DIR_DY[dir];
+    int m2 = diff_x * di_y + diff_y * di_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 (m2 < 0)
+      continue;
+    m2 = (2 * m2 * m2) / (di_x * di_x + di_y * di_y);
 
-  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;
+    if (best_dir == -1 || m2 > best) {
+      best = m2;
+      best_dir = dir;
+    }
+  }
 
-  return (best_dir);
+  assert(best >= 0 && best_dir >= 0);
+  return best_dir;
 }
 
 /**************************************************************************